Provable Subexponential Algorithms for NIST Third-Round Lattice Families

Name: Provable Subexponential Algorithms for NIST Third-Round Lattice Families
Uploaded: 2026-10-11T14:49:10.180047+00:00
Duration: 628 s
Description: This research develops provably subexponential algorithms to recover secret keys from noisy or rounded linear equations across all seven NIST lattice families, including Kyber and FrodoKEM. The method uses Gaussian sampling to find short secrets in expected time complexity of $2(1/2+o(1))n/ ext{poly}( ext{log } n)$, providing concrete efficiency guarantees for practical cryptography.

This research develops provably subexponential algorithms to recover secret keys from noisy or rounded linear equations across all seven NIST lattice families, including Kyber and FrodoKEM. The method uses Gaussian sampling to find short secrets in expected time complexity of $2(1/2+o(1))n/ ext{poly}( ext{log } n)$, providing concrete efficiency guarantees for practical cryptography.

Open the full episode