Title: Are cryptosystems based on ideal lattices quantum-safe ?
| Speaker | Jean-Francois Biasse |
| Affiliation: | University of South Florida |
| Room: | QNC 1501 |
Abstract:
Shor's algorithm factors RSA integers and solves the Discrete Logarithm Problem (DLP) in quantum polynomial time. Therefore, alternatives to these cryptosystems must be developed to replace the current cryptographic schemes. One of the most interesting family of schemes that have been proposed for the replacement of RSA-based and DLP-based primitives relies on the hardness of finding short vectors in Euclidean lattices. This problem seems intractable, even for quantum computers, and it allows many interesting functionalities such as Fully Homomorphic Encryption. Certain cryptosystems rely on the hardness of finding short vectors in lattices that have the structure of an ideal in a number field (hence the name: "ideal lattice"). This allows a performance gain, but it also raises the question: does this computational problem remain as hard when we restrict ourselves to this specific class of lattices ? In this talk we report on recent results showing that finding short vectors can be significantly faster in certain ideal lattices when using a quantum computer. These results affected certain cryptosystems based on ideal lattices, while others remained quantum-safe. In any case, this showed that the restriction to ideal lattices did affect the hardness of the search for short vectors.