MilestoneTheory & algorithmsConfirmed

Regev links quantum algorithms to hard lattice problems

Apr 1, 2003

Oded Regev shows that a quantum algorithm for a version of the hidden subgroup problem on the dihedral group, the group of symmetries of a polygon, would solve a hard lattice problem, the unique shortest vector problem.

Why it matters

Lattice problems underpin much of today's post-quantum cryptography. This link explains why a fast quantum algorithm for the dihedral case would matter; none is known.

Oded Regev

See it on the timeline

Related

• Kuperberg finds a faster quantum attack on the dihedral hidden subgroup problem (Feb 14, 2003)
• Chen proposes a quantum lattice algorithm, then identifies a fatal bug (Apr 10, 2024)
• NIST publishes the first post-quantum encryption standards (Aug 13, 2024)