Exact ℓ_p-CVP reduced to Euclidean SVP in polynomial space
The reduction enables polynomial-space algorithms for exact ℓ_p-CVP using existing SVP solvers, with time bounds N^{N/(2e)+o(N)} for p=2.
Stories per day · 30 days
2 RSS
Relatedpost-quantum2svp2cvp1dihedral-coset-problem1discrete-gaussian1lattice-reduction1lwe1ml-dsa1ml-kem1reduction1
9 stories, newest first · one card per story
Stories tagged #lattice-cryptography
Gaussian difference dynamics breaks 2^{n/2} barrier for shortest vector problem
New algorithm solves discrete Gaussian sampling and shortest vector problem in (3/2)^{n/2+o(n)} time and (4/3)^{n/2+o(n)} space.
Survey maps lattice assumptions if the Dihedral Coset Problem falls
A refuted 2026 quantum-algorithm claim frames which assumptions would move and which deployed parameters would not.
New infinity-norm method speeds rank-2 lattice reduction
The algorithm matches Lagrange-Gauss complexity at O(nT^2) and saves at least 2n multiplications per iteration.
Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples
A Kirchner–Fouque BKW variant solves bounded-error LWE subexponentially with near-linear samples.
Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale
Researchers certify a dependency-preserving upper bound of 2^-164.81 on honest decapsulation failure for ML-KEM-768 within an explicit ROM/CBD abstraction.
When Topology Betrays Privacy: Lattice-Based Reconstruction Attacks on Secure Aggregation in Decentralized Federated Learning
Researchers show colluding nodes in decentralized federated learning can reconstruct private updates despite secure aggregation, using lattice-based attacks tied to the Hidden Subset Sum Problem.
A Note on Sphere Packing Bounds for Tuple Lattice Sieving
Proves upper bounds on k-irreducible unit vector set rates, yielding nearly tight asymptotics relevant to tuple lattice sieving in cryptanalysis.
Has MIMO decoding been proved hard from lattice problems?
Researchers show the published lattice-hardness proof for MIMO decoding fails, as Regev's LWE reduction structure does not carry over to non-modular MIMO.