Paper 2023/271

Swoosh: Efficient Lattice-Based Non-Interactive Key Exchange

Phillip Gajland, Max Planck Institute for Security and Privacy, Ruhr University Bochum
Bor de Kock, Norwegian University of Science and Technology
Miguel Quaresma, Max Planck Institute for Security and Privacy
Giulio Malavolta, Max Planck Institute for Security and Privacy
Peter Schwabe, Max Planck Institute for Security and Privacy, Radboud University Nijmegen

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.

Note: Full version.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. USENIX 2024
Contact author(s)
phillip gajland @ mpi-sp org
bor dekock @ ntnu no
miguel quaresma @ mpi-sp org
giulio malavolta @ mpi-sp org
peter @ cryptojedi org
2023-10-23: last of 2 revisions
2023-02-23: received
See all versions
Short URL
No rights reserved


      author = {Phillip Gajland and Bor de Kock and Miguel Quaresma and Giulio Malavolta and Peter Schwabe},
      title = {Swoosh: Efficient Lattice-Based Non-Interactive Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2023/271},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.