USENIX Security '24 - Efficient Lattice-Based Key Exchange

SWOOSH: Efficient Lattice-Based Non-Interactive Key Exchange

Phillip Gajland, Max Planck Institute for Security and Privacy, Ruhr University Bochum; Bor de Kock, NTNU - Norwegian University of Science and Technology, Trondheim, Norway; Miguel Quaresma, Max Planck Institute for Security and Privacy; Giulio Malavolta, Bocconi University, Max Planck Institute for Security and Privacy; Peter Schwabe, Max Planck Institute for Security and Privacy, Radboud University

The advent of quantum computers has sparked significant interest in post-quantum cryptographic schemes, as a replacement for currently used cryptographic primitives. In this context, lattice-based cryptography has emerged as the leading paradigm to build post-quantum cryptography. However, all existing viable replacements of the classical Diffie-Hellman key exchange require additional rounds of interactions, thus failing to achieve all the benefits of this protocol. Although earlier work has shown that lattice-based Non-Interactive Key Exchange (NIKE) is theoretically possible, it has been considered too inefficient for real-life applications. In this work, we challenge this folklore belief and provide the first evidence against it. We construct an efficient lattice-based NIKE whose security is based on the standard module learning with errors (M-LWE) problem in the quantum random oracle model. Our scheme is obtained in two steps: (i) A passively-secure construction that achieves a strong notion of correctness, coupled with (ii) a generic compiler that turns any such scheme into an actively-secure one. To substantiate our efficiency claim, we provide an optimised implementation of our passively-secure construction in Rust and Jasmin. Our implementation demonstrates the scheme's applicability to real-world scenarios, yielding public keys of approximately 220 KBs. Moreover, the computation of shared keys takes fewer than 12 million cycles on an Intel Skylake CPU, offering a post-quantum security level exceeding 120 bits.

View the full USENIX Security '24 program at https://www.usenix.org/conference/usenixsecurity24/program