Gentry's breakthrough ideal-lattice-based homomorphic encryption system at STOC 2009 was shown several years later to be breakable by a fast quantum algorithm. The same attack recovers keys in the Smart–Vercauteren system, the Gentry–Halevi system, the Garg–Gentry–Halevi multilinear-map system, etc. The worst-case Ideal-SVP lattice problem was then shown to be efficiently breakable with vastly smaller approximation factors than previously thought, leaping halfway from essentially exponential towards polynomial.
However, all of these attacks assume that the underlying number field is chosen as a cyclotomic field (plus technical assumptions that are true for typical cyclotomic fields). Lattice-based cryptography can instead use other number fields. Two scalable families of Galois number fields are common topics in books on algebraic number theory: cyclotomic fields and multiquadratic fields. A standard argument for choosing cyclotomic fields is the performance benefit of FFTs; the same argument is applicable to multiquadratic fields, with FFTs replaced by twisted Hadamard transforms.
We have shown that switching the Gentry/Smart–Vercauteren/Gentry–Halevi system to use multiquadratics is not a good idea: the resulting cryptosystem is efficiently breakable without quantum computers for a wide range of multiquadratic fields. The new attack exploits the automorphisms and subfields available in multiquadratic fields.
Contributors (alphabetical order)
- Jens Bauch, Simon Fraser University, Canada
- Daniel J. Bernstein, University of Illinois at Chicago, USA, and Technische Universiteit Eindhoven, Netherlands
- Henry de Valence, Technische Universiteit Eindhoven, Netherlands
- Tanja Lange, Technische Universiteit Eindhoven, Netherlands
- Christine van Vredendaal, Technische Universiteit Eindhoven, Netherlands
Acknowledgments
This work was supported by the Netherlands Organisation for Scientific Research (NWO) under grants 613.001.011 and 639.073.005.
This work was supported by the Commission of the European Communities through the Horizon 2020 program under project number 645622 (PQCRYPTO), project number 643161 (ECRYPT-NET), and project number 645421 (ECRYPT-CSA).
This work was supported by the U.S. National Science Foundation under grant 1314919. "Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation."
Calculations were carried out on the Saber cluster of the Cryptographic Implementations group at Technische Universiteit Eindhoven, and the Saber2 cluster at the University of Illinois at Chicago.
Version: This is version 2017.05.01 of the Introduction web page.
