On tiny-probability lattice enumeration

Area of Science:

• Computational mathematics
• Number theory
• Cryptography

Background:

• Lattice enumeration is crucial for computational lattice problems, using tree-based algorithms.
• Existing algorithms face super-exponential time complexity relative to lattice rank.
• The extreme pruning strategy offers exponential speedups but relies on accurate cost prediction.

Purpose of the Study:

• To investigate scenarios where pruned lattice enumeration's actual cost exceeds predicted cost.
• To identify the failure of the Gaussian heuristic as a cause for this discrepancy.
• To propose modifications for cost prediction and lower bound discussions in lattice enumeration.

Main Methods:

• Analysis of pruned lattice enumeration cost under specific conditions.
• Identification of the Gaussian heuristic's failure in predicting lattice point counts.
• Development of a modified cost prediction model and updated lower bound discussions.

Main Results:

• Demonstrated practical cases where pruned enumeration cost significantly surpasses predictions.
• Linked this discrepancy to the Gaussian heuristic's failure when pruning for very low success probabilities.
• Proposed revised lower bounds that are 20-30 times larger in cryptographically relevant settings.

Conclusions:

• The Gaussian heuristic can underestimate lattice point counts, leading to inaccurate cost predictions in pruned enumeration.
• The confinement of the search region to a subspace is identified as a likely cause.
• Updated cost prediction and lower bounds are necessary for more reliable analysis of pruned lattice enumeration.