SWOOSH: Efficient Lattice-Based Non-Interactive Key Exchange

SWOOSH: Efficient Lattice-Based Non-Interactive Key Exchange

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

Conference: USENIX Security '24

YouTube: https://www.youtube.com/watch?v=IpavvH9hJm0

Overview

In the realm of post-quantum cryptography, much attention has been directed towards Key Encapsulation Mechanisms (KEMs), largely driven by the NIST Post-Quantum Cryptography (PQC) standardization process. However, a critical need remains for Non-Interactive Key Exchange (NIKE) schemes, which allow two parties to establish a shared secret key by simply exchanging public keys, without any further real-time interaction. This talk, presented by Phillip Gajland and Miguel Quaresma, on joint work with Bor de Kock, Giulio Malavolta, and Peter Schwabe, introduces SWOOSH – an efficient lattice-based NIKE that challenges the long-held notion that such schemes are impractical.

SWOOSH provides a compelling post-quantum alternative to traditional Diffie-Hellman key exchange, specifically addressing use cases where the interactive nature of KEMs is undesirable or introduces significant overhead. These scenarios include implicit authentication, asynchronous messaging protocols, and resource-constrained environments like IoT devices. By focusing on concrete parameter choices rather than purely asymptotic analysis, the researchers demonstrate that efficient lattice-based NIKE is not only feasible but can offer performance advantages over other post-quantum NIKE candidates, albeit with certain trade-offs.

The significance of SWOOSH lies in its direct contribution to a more comprehensive post-quantum cryptographic landscape. While KEMs are suitable for many applications, the unique properties of NIKE—particularly its ability to enable "fire-and-forget" key agreement—are indispensable for certain protocol designs. SWOOSH's development provides cryptographers and system architects with a viable, performant option for integrating post-quantum security into these critical non-interactive contexts, expanding the practical applicability of lattice-based cryptography beyond its current KEM-centric focus.

Background

▶ Watch: Introduction: Lattice NIKES are not that bad! (0:28)

The ubiquitous Diffie-Hellman (DH) key exchange, while foundational to secure communication, lacks resilience against attacks by quantum computers. This looming threat has spurred intensive research into post-quantum cryptography (PQC), with the US National Institute of Standards and Technology (NIST) leading a multi-round competition to standardize quantum-resistant cryptographic algorithms. The majority of proposals and subsequent selections in this competition, such as Kyber and Classic McEliece, have focused on Key Encapsulation Mechanisms (KEMs).

KEMs operate as a two-stage, inherently interactive process. Alice first generates a key pair and sends her public key to Bob. Bob then uses Alice's public key to probabilistically encapsulate a symmetric key, producing a ciphertext and the shared key. He sends the ciphertext back to Alice, who then uses her secret key to decapsulate the ciphertext and derive the same shared key. While effective, this interaction model is not universally applicable.

In contrast, a Non-Interactive Key Exchange (NIKE) allows Alice and Bob to independently generate key pairs, broadcast their respective public keys, and then derive a shared secret key using only their private key and the other party's public key, without any further interaction. This "one-shot" key agreement is crucial for specific applications. For instance, in implicit authentication using static Diffie-Hellman keys (e.g., in TLS 1.3), NIKE can remove the need for handshake signatures and additional rounds of interaction, streamlining protocol execution. Similarly, asynchronous key agreement protocols, like X3DH used in Signal and WhatsApp, heavily rely on the non-interactive nature of key exchange for secure messaging when parties might not be simultaneously online. Furthermore, Radio Networks for IoT devices (e.g., eHoc, OSCORE) benefit from NIKE to minimize communication overhead and latency in resource-constrained environments.

Historically, lattice-based NIKE has been considered impractical, a "folk law" reinforced by certain impossibility results derived from asymptotic analyses. The core challenge in constructing efficient lattice-based NIKE schemes stems from a fundamental tension: to ensure the Learning With Errors (LWE) problem—the underlying hardness assumption—remains intractable against quantum adversaries, cryptographic parameters (such as the norm bound beta for secret and error vectors, and the polynomial degree D or matrix dimension n) must be sufficiently large. However, to guarantee correctness (i.e., that Alice and Bob derive the exact same shared key with very high probability) in a lattice-based construction, an even larger modulus q is often required. This disparity in parameter scaling leads to significant computational and communication overhead, making practical implementations seem elusive. SWOOSH directly confronts this challenge by meticulously optimizing parameters and implementation details for concrete, rather than asymptotic, performance.

Key Findings

▶ Watch: NIKEs vs. Key Encapsulation Mechanisms (KEMs) (2:07)

The SWOOSH project fundamentally challenges the long-standing belief regarding the impracticality of lattice-based Non-Interactive Key Exchange (NIKE). Its key findings and contributions are multifaceted:

1. Practicality of Lattice-Based NIKE: The most significant finding is the demonstration that efficient lattice-based NIKE is indeed practical when considering concrete parameter choices, directly refuting previous "folk law" and asymptotic impossibility results. This opens up new avenues for post-quantum secure protocol design.
2. Introduction of SWOOSH Scheme: The work presents a novel, module LWE-based NIKE scheme named SWOOSH. This scheme is designed with strong correctness guarantees, including a robust notion of semi-malicious correctness, and its security is proven in the Quantum Random Oracle Model (QROM).
3. Generic Transformation for Active Security: SWOOSH provides a generic transformation method to elevate the passively secure variant to an actively secure scheme. This is achieved by incorporating Non-Interactive Zero-Knowledge Proofs of Knowledge (NIZKPoK), allowing parties to prove they know the secret key corresponding to their public key without revealing the secret itself. This transformation, while incurring a performance penalty, ensures a higher level of security suitable for adversarial environments.
4. Optimized Implementation: The researchers developed an optimized implementation of the passive SWOOSH variant. This implementation, crafted using Rust and Jasmine, targets high efficiency. It specifically focuses on optimizing core cryptographic operations critical to lattice-based schemes.
5. Achieving Quantum Security and Efficiency: The chosen parameters for SWOOSH achieve 120 bits of security against quantum adversaries, aligning with common security targets. Despite the inherent challenges of lattice-based NIKE, the implementation demonstrates competitive performance.
6. Comparative Advantages: SWOOSH exhibits notable advantages over existing post-quantum schemes:

• Smaller Public Keys: It achieves smaller public key sizes compared to Classic McEliece, a prominent KEM candidate from the NIST PQC competition.
• Faster Operations: It significantly outperforms another post-quantum NIKE, CTIDH, in terms of both key generation and shared key derivation speed. This positions SWOOSH as a strong contender for applications requiring non-interactive key exchange.

Technical Deep Dive

▶ Watch: High-level Overview of the SWOOSH Protocol (4:10)

The SWOOSH protocol is built upon the Learning With Errors (LWE) problem over modular lattices, specifically leveraging polynomial rings for efficiency. The core mechanism closely mirrors a Diffie-Hellman-like exchange in the lattice setting:

Key Generation:

• Alice samples a secret key s as a row vector with short entries (norm at most beta). Her public key PK_A is an LWE sample: s^T * A + e^T, where A is a publicly known square matrix of dimension n, and e is a short error vector.
• Bob similarly samples a secret key s' as a column vector with short entries (norm at most beta). His public key PK_B is also an LWE sample: A * s' + e', where e' is another short error vector.
• Both s, s', e, and e' have entries that are polynomials of degree D. All operations are performed over a modulus q.

Shared Key Derivation:

• Alice computes K_A = s^T PK_B = s^T (A s' + e') = s^T A s' + s^T e'.
• Bob computes K_B = PK_A s' = (s^T A + e^T) s' = s^T A s' + e^T s'.

The challenge arises because the error terms s^T e' and e^T s' are generally different. To reconcile these, a deterministic reconciliation procedure is applied to K_A and K_B to derive the final shared key. This reconciliation relies on the fact that s^T A s' is common to both, and the error terms are "small" enough to be rounded to the same value. The probability of a correctness error (where Alice and Bob derive different keys) must be extremely low.

The "crux" of achieving practical lattice-based NIKE lies in balancing the parameters:

• To ensure the hardness of LWE, beta, D, and n must be sufficiently large.
• However, to guarantee a negligible correctness error, the modulus q must be even larger, often disproportionately so. This trade-off significantly impacts the efficiency of arithmetic operations.

Security Notions:

• Passive Security: This is the baseline, requiring that the derived key is indistinguishable from a random key to an eavesdropping adversary. The reconciliation procedure is designed to work under this model.
• Active Security: A stronger notion, requiring resistance against an adversary who can actively manipulate or substitute public keys. This demands semi-malicious correctness, meaning Bob cannot intentionally craft a public key (after seeing Alice's) to cause a correctness error. SWOOSH achieves this by incorporating a random scalar r into the reconciliation procedure, derived from a hash of both public keys: r = H(PK_A, PK_B).
• For full active security (e.g., against chosen-public-key attacks), SWOOSH proposes a generic transformation: appending a Non-Interactive Zero-Knowledge Proof of Knowledge (NIZKPoK) to each public key. This proof attests that the sender genuinely knows the secret key corresponding to their public key, preventing malicious key generation. This comes with a performance penalty.

Implementation Details and Optimizations:

The SWOOSH implementation focuses on modular lattices and polynomial arithmetic in Rust and Jasmine.

• Prime Modulus: A 214-bit prime modulus is used. While this provides a large enough range for correctness, it necessitates multi-precision arithmetic, which is inherently less efficient than single-register operations.
• Polynomial Degree: Polynomials of degree 256 are used.
• Number Theoretic Transform (NTT): This is a cornerstone optimization for polynomial multiplication in lattice-based cryptography. Instead of the naive schoolbook multiplication (quadratic complexity O(D^2)), NTT achieves quasi-linear complexity O(D log D), dramatically speeding up operations.
• NTT Optimizations:
• In-place NTT: Reduces memory usage, which is particularly important given SWOOSH's large parameters.
• NTT Domain Storage: The public matrix A and public keys are stored in the NTT domain. This halves the number of NTT and inverse NTT transformations required during key generation and shared key derivation, as many operations can be performed directly in the transformed domain.
• Noise Sampling: The coefficients for the secret and error vectors are sampled from the output of a Pseudo-Random Function (PRF), specifically AES256 in counter mode.
• Random Offset Computation: The random scalar r for semi-malicious correctness is computed using rejection sampling on the output of an Extendable Output Function (XOF), specifically cSHAKE256.
• Performance Bottlenecks:
• Key generation: Polynomial multiplication (NTT accounts for ~10% of execution time) and big integer arithmetic. Noise sampling is also a factor.
• Shared key derivation: The random offset computation (hashing two public keys and generating a polynomial from the hash output) is identified as a main performance culprit.

Demo / Proof of Concept

▶ Watch: The Crux: Parameter Challenges for Lattice NIKES (5:45)

While the talk does not detail a live demonstration or a specific proof-of-concept application, the researchers confirm the development of an optimized implementation of the passive SWOOSH scheme. This implementation is written in Rust and Jasmine, demonstrating the practical feasibility and performance characteristics of their proposed NIKE. The focus was on benchmarking and comparing the cryptographic primitives against other post-quantum candidates, rather than showcasing an end-user application. The code for this passive SWOOSH implementation is publicly available on GitHub, allowing other researchers and developers to inspect, verify, and build upon their work.

Defensive Implications

▶ Watch: Using NIZKPs for Active Security in SWOOSH (7:10)

The advent of SWOOSH has several critical implications for cybersecurity defenders and architects planning their transition to post-quantum cryptography.

First and foremost, SWOOSH provides a viable and efficient post-quantum replacement for static Diffie-Hellman key exchange. This is crucial for protocols that rely on implicit authentication or require key agreement without additional rounds of interaction. Defenders should identify existing systems or protocols using static DH that are vulnerable to quantum attacks and evaluate SWOOSH as a drop-in replacement. Examples include certain modes in TLS 1.3 for 0-RTT handshakes or scenarios involving pre-shared keys, where SWOOSH could provide quantum resistance without altering the fundamental interaction model.

For asynchronous messaging protocols like Signal or WhatsApp, which utilize the X3DH protocol, SWOOSH offers a direct path to post-quantum security. These applications are designed around the ability to establish session keys even when parties are not simultaneously online. Replacing the classical elliptic curve Diffie-Hellman (ECDH) components with SWOOSH would enable quantum-resistant key establishment without requiring a redesign of the asynchronous messaging architecture, thereby preserving user experience and protocol efficiency.

In resource-constrained environments, such as IoT devices participating in Radio Networks (e.g., eHoc, OSCORE), the optimized performance of SWOOSH's key generation and shared key derivation functions is a significant advantage. While SWOOSH public keys are larger than those of KEMs like Kyber, its speed in core operations might make it more suitable than other NIKE candidates like CTIDH for devices with limited computational power. Defenders deploying IoT solutions should consider the overall system constraints, including bandwidth for larger public keys versus the computational cost of key agreement, when selecting a post-quantum primitive.

Defenders must also be aware of the security model trade-offs. The passively secure version of SWOOSH is efficient but only protects against eavesdropping. For environments where active adversaries might attempt to forge or manipulate public keys, the generic transformation to active security using Non-Interactive Zero-Knowledge Proofs of Knowledge (NIZKPoK) is necessary. However, this transformation introduces a performance penalty. Organizations must assess their threat model to determine if the overhead of NIZKPoK is justified for the enhanced security guarantees. Implementing and verifying NIZKPoK correctly requires specialized cryptographic expertise.

Finally, while the paper details an optimized implementation in Rust and Jasmine, general best practices for cryptographic deployments remain paramount. This includes rigorous testing, adherence to secure coding standards, and vigilance against side-channel attacks, which, though not explicitly discussed in the talk, are a common concern for lattice-based implementations. Defenders should review the open-source implementation for any potential vulnerabilities and consider independent audits before widespread deployment. The availability of the code on GitHub facilitates community review and adoption.

Key Takeaways

• Lattice-based Non-Interactive Key Exchange (NIKE), exemplified by SWOOSH, is practically achievable with concrete parameter choices, challenging previous notions of impracticality.
• SWOOSH provides an efficient post-quantum NIKE solution, particularly well-suited for applications requiring implicit authentication, asynchronous key agreement (e.g., Signal, WhatsApp), and key exchange in resource-constrained IoT environments.
• The scheme achieves a robust 120 bits of security against quantum adversaries with strong correctness guarantees, including semi-malicious correctness, and is proven secure in the Quantum Random Oracle Model (QROM).
• Performance is optimized through techniques like Number Theoretic Transform (NTT), in-place operations, and storing public parameters in the NTT domain, significantly accelerating polynomial multiplication and reducing memory usage.
• SWOOSH demonstrates competitive performance, offering faster key generation and shared key derivation than other post-quantum NIKE schemes like CTIDH, while having smaller public keys than Classic McEliece, a prominent KEM.
• Achieving full active security against malicious adversaries requires the integration of Non-Interactive Zero-Knowledge Proofs of Knowledge (NIZKPoK), which introduces an additional performance overhead that must be considered based on the specific threat model.

About the Speaker(s)

The talk was presented by Phillip Gajland and Miguel Quaresma, who are part of a research team that also includes Bor de Kock, Giulio Malavolta, and Peter Schwabe. Based on the technical depth and academic nature of their work, they are likely researchers affiliated with universities or specialized cryptographic research institutions, contributing to the advancement of post-quantum cryptography. Their work on SWOOSH demonstrates expertise in lattice-based cryptography, cryptographic protocol design, and high-performance cryptographic implementation.