There was a recent flurry of concern over the strength of the Lattice based encryption algorithms approved by NIST due to a paper titled Quantum Algorithms for Lattice Problems published earlier this month by Yilei Chen, a professor at the Tsinghua University Institute for Interdisciplinary Information Science (IIIS). Two algorithms this would possibly have affected include ML-KEM (CRYSTALS-Kyber) and ML-DSA (CRYSTALS-Dilithium) which use an LWE (Learning with Errors) approach. These algorithms are based upon the computationally hard problems of determining the length of the shortest nonzero vector in a given n-dimensional lattice. His paper proposed a method to find a polynomial time algorithm for doing this with a quantum computer. The current best algorithms are only able to do this in exponential time.
Professor Chen did post a 65 page paper describing the algorithm that included nine steps. Immediately, many researchers started reviewing it to see if any errors in it could be found. It turns out there was. A problem was found in Step 9 and the author has admitted he doesn’t know how to fix it. The paper is still of interest to researchers, but at this point it no longer represents a threat to the Lattice based cryptographic codes.
However, there are lessons here for anyone responsible for implementing quantum safe cryptography within their organizations. The first is to ensure that your implementation provides a means to maintain crypto agility. Although this research effort no longer threatens the existing codes, we can’t say for sure that some brilliant PhD student somewhere will discovery an algorithm that works. There is no mathematical proof available that certifies that the PQC algorithms are bullet proof and there probably never will be. So if someday one of the existing PQC algorithms displays a weakness, an organization should be ready to swap in a alternate algorithm based upon a different approach that isn’t threatened. A second lesson is to implement hybrid solutions that use both the traditional as well as the PQC algorithms. That way if a weakness is found in the PQC algorithm, the adversary would still need to break through the classical algorithm in order to decrypt the message. Apple has taken this approach in the recent update to their iMessage app.
More information about this can be found in a copy of the paper here, a statement posted on the author’s website here and in additional comments posted on Scott’s Aaronson’s Shtetl Optimized blog here.
April 19, 2024
