Paper 2023/271

Swoosh: Practical Lattice-Based Non-Interactive Key Exchange

Abstract

The advent of quantum computers has generated a wave of interest for 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 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 provide the first evidence against this folklore belief. We construct a practical 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 present an optimised implementation of our construction in Rust and Jasmin, demonstrating its applicability to real-world scenarios. For this we obtain public keys of approximately 220 KBs and the computation of shared keys takes than 12 million cycles on an Intel Skylake CPU at a post-quantum security level of more than 120 bits.