Swoosh: Efficient Lattice-Based Non-Interactive Key Exchange

Phillip Gajland; Bor de Kock; Miguel Quaresma; Giulio Malavolta; Peter Schwabe

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

Abstract

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.

Metadata

Available format(s): PDF
Category: 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
History: 2023-10-23: last of 2 revisions; 2023-02-23: received; See all versions
Short URL: https://ia.cr/2023/271
License: CC0

BibTeX

@misc{cryptoeprint:2023/271,
      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{https://eprint.iacr.org/2023/271}},
      url = {https://eprint.iacr.org/2023/271}
}