Security News > 2024 > May > Lattice-Based Cryptosystems and Quantum Cryptanalysis
On April 10, Yilei Chen from Tsinghua University in Beijing posted a paper describing a new quantum attack on that shortest-path lattice problem.
Adi Shamir, the "S" in RSA and a 2002 recipient of ACM's A.M. Turing award, described the result as psychologically significant because it shows that there is still a lot to be discovered about quantum cryptanalysis of lattice-based algorithms.
There have been decades of unsuccessful research into breaking lattice-based systems with classical computers; there has been much less research into quantum cryptanalysis.
While Chen's work doesn't provide a new security bound, it illustrates that there are significant, unexplored research areas in the construction of efficient quantum attacks on lattice-based cryptosystems.
Breaking lattice-based cryptography with a quantum computer seems to require orders of magnitude more qubits than breaking RSA, because the key size is much larger and processing it requires more quantum storage.
This essay originally appeared in Communications of the ACM. Tags: cryptography, essays, quantum computing, quantum cryptography.