Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time 2 0.292n

arXiv:2609.37482 · cs.CR, cs.DS, math.MG · Submitted 2026-09-26 · Read on arXiv

cs.CR, cs.DS, math.MG

Submitted: 2026-09-26

Updated: 2026-09-26

Terminology

• Sampling Biases — 2× in this paper · explained in 2 episodes
• Admissibility — 1× in this paper · explained in 2 episodes
• Fingerprinting — 1× in this paper · explained in 2 episodes
• Initial Data — 1× in this paper · explained in 2 episodes
• Phase Transitions — 1× in this paper · explained in 2 episodes

Sources

• On the Lattice Distortion Problem
• Wagner's Algorithm Provably Runs in Subexponential Time for SIS$^\infty$
• Solving the Shortest Vector Problem in 2 0.6039n Time via Mid-point Hessian
• One Discrete Gaussian Sample in $2^{n/2+o(n)}$ Time
• Sieving for closest lattice vectors (with preprocessing)
• Discrete Gaussian Sampling Reduces to CVP and SVP

Related papers

• SoK: AI-Augmented Binary Reversing
• Relaxed Sender Anonymity for CBDC Interbank Settlement: A Zero-Knowledge Approach on Permissioned EVM
• Calibration-Family Overfit: Why Trusted Sabotage Monitors Don't Transfer Across Lineages
• Efficient Fuzzy PSI under One-Sided Assumptions
• Sealing the Audit-Runtime Gap for LLM Skills
• Token Composition: A Graph Based on EVM Logs