K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures

K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures

Speakers: Daniel Collins, Loïs Huguenin-Dumittan, Ngoc Khanh Nguyen, Nicolas Rolin, Serge Vaudenay

Conference: USENIX Security '24

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

Overview

In an era increasingly cognizant of the threat posed by quantum computers to current cryptographic standards, the development of post-quantum cryptography (PQC) has become a paramount concern. This talk, "K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures," presented by Daniel Collins and his collaborators from EPFL (École Polytechnique Fédérale de Lausanne), addresses a critical challenge in secure messaging: how to achieve deniable post-quantum key exchange efficiently. The widely adopted Signal Protocol, which underpins applications like WhatsApp and Signal itself, relies on the Extended Triple Diffie-Hellman (X3DH) protocol for its initial key exchange. While X3DH offers robust classical security guarantees, including secrecy, authentication, and crucial deniability, it is vulnerable to quantum adversaries.

K-Waay proposes a novel approach to extend X3DH's properties into the post-quantum realm without the performance bottlenecks traditionally associated with such constructions. Specifically, previous attempts to achieve fully post-quantum secure and deniable X3DH often leveraged post-quantum ring signatures, a primitive known for its computational cost and complexity. K-Waay circumvents this by introducing a design primarily based on split Key Encapsulation Mechanisms (KEMs), a generalization of standard KEMs. This innovation promises to deliver the desired security posture against active quantum attackers while significantly improving efficiency, marking a crucial step forward for future secure messaging protocols.

The significance of K-Waay lies in its ability to reconcile the stringent requirements of asynchronous messaging protocols – namely, efficiency, deniability, and support for offline users – with the imperative of post-quantum security. By offering a faster and provably secure alternative to ring-signature-based designs, K-Waay presents a practical blueprint for integrating quantum-resistant key exchange into real-world secure communication platforms, safeguarding user privacy against the long-term threat of quantum computation.

Background

▶ Watch: X3DH properties: secrecy, authentication, deniability, offline users (1:00)

Secure messaging applications have become a cornerstone of modern digital communication, with the Signal Protocol emerging as the de facto standard for two-party messaging. This protocol's architecture comprises two main components: a key exchange mechanism and a messaging protocol, with the latter often employing a double ratchet for forward secrecy and deniability. The key exchange component, particularly for initial key establishment, has historically relied on the X3DH (Extended Triple Diffie-Hellman) protocol. X3DH provides essential security guarantees such as secrecy (the key is hidden from adversaries) and authentication (the communicating party is who they claim to be).

Beyond these fundamental properties, X3DH is tailored for messaging by offering two additional critical features: deniability and support for offline users. Deniability ensures that Alice and Bob can plausibly deny having communicated with each other, even if an adversary compromises their devices after the fact. This property is crucial for protecting users in environments where communication records could be used against them. Offline support allows users to exchange initial keying material via a central server (e.g., the Signal server), enabling one party to initiate a conversation even if the other is offline, facilitating asynchronous communication.

The advent of quantum computing, specifically Shor's algorithm, poses a significant threat to classical cryptographic primitives like Diffie-Hellman, which X3DH is built upon. This necessitated the development of post-quantum cryptography (PQC). The National Institute of Standards and Technology (NIST) has been actively standardizing PQC primitives, leading to the recent selection of several core algorithms. In response to this threat, Signal has already deployed a protocol known as pqXDH (or pqX), which incorporates NIST-standardized KEMs. However, as noted in the talk, pqXDH primarily offers security against "store now, decrypt later" quantum attacks. This means it protects against an adversary who passively collects encrypted communications today, hoping to decrypt them with a future quantum computer. Crucially, pqXDH does not provide full post-quantum security against an active quantum attacker during the key exchange process, as its authentication still relies on classical signatures.

Achieving full post-quantum security against active attackers while maintaining X3DH's deniability property has proven challenging. Prior research, such as work by Hash and Brändli, explored constructions based on post-quantum ring signatures. Ring signatures allow a member of a group to sign a message anonymously on behalf of the group, which can be adapted to provide deniable authentication. While these protocols offered a path to full post-quantum deniability, they faced significant performance issues. Ring signatures, especially their post-quantum instantiations, are computationally intensive and often lead to large key sizes or slow operations. The speakers highlighted that previous ring-signature-based benchmarks often fell short of achieving full security levels, particularly in terms of provable security, and lacked proofs in the Quantum Random Oracle Model (QROM).

This context sets the stage for K-Waay: a search for a more efficient and robust method to achieve post-quantum deniable X3DH without the prohibitive overhead of ring signatures. The talk identifies split KEMs as a promising primitive to emulate the Diffie-Hellman-like key exchange structure and provide the necessary properties for deniable post-quantum key exchange.

Key Findings

▶ Watch: Signal's PQXDH: security against passive quantum attackers (3:30)

The K-Waay protocol represents a significant advancement in the field of post-quantum secure messaging, offering a novel approach to achieving deniable X3DH without the performance drawbacks of ring signatures. The key findings and contributions of this work are multifaceted:

1. Novel Protocol Design for Deniable Post-Quantum X3DH: The core finding is the K-Waay protocol itself, which provides a fast and deniable post-quantum secure key exchange mechanism. Unlike previous proposals that relied on post-quantum ring signatures, K-Waay achieves its security and deniability primarily through the judicious use of split KEMs alongside regular KEMs and long-term signature keys. This design choice directly addresses the performance bottlenecks identified in earlier work.

1. Leveraging Split KEMs for Key Exchange: The research formally demonstrates that split KEMs, a generalization where encapsulation and decapsulation algorithms take both public and secret keys as input, can effectively imply key exchange. Previous work that introduced split KEMs did not formally prove this implication, making K-Waay's construction a foundational step in validating their utility for key exchange protocols. Split KEMs are shown to enable a symmetric key agreement primitive that allows for deniable authentication.

1. Enhanced Security Notions for Split KEMs: The authors revisited and refined the security notions for split KEMs. They found that original notions, primarily focused on IND-CCA-like security, were insufficient for the specific requirements of X3DH-like protocols, particularly regarding authentication guarantees. K-Waay introduces enhanced security notions that explicitly capture the necessary authentication properties tailored for post-quantum X3DH applications. This includes a notion of semi-honest deniability, following the work of Brändli et al.

1. Practical Instantiation based on Plain LWE: K-Waay provides a concrete, provably secure instantiation of its split KEMs based on the plain Learning With Errors (LWE) assumption. This conservative assumption underpins well-known PQC schemes like FrodoKEM, lending high confidence to K-Waay's security. The instantiation details demonstrate how the As+error structure of LWE can be adapted to the split KEM primitive.

1. Superior Performance and Security Guarantees: Benchmarking results demonstrate that K-Waay significantly outperforms existing post-quantum deniable X3DH protocols based on ring signatures. It achieves speeds comparable to non-deniable X3DH protocols, being at least three times faster than conservative comparisons with ring-signature-based schemes using primitives like Kyber 512 and Raptor ring signatures (instantiated with Falcon and Lithium). Furthermore, K-Waay offers stronger security guarantees, achieving 128 bits of classical security and 64 bits of quantum security even after applying the Quantum Random Oracle Model (QROM), which typically incurs security loss. Previous ring-signature protocols struggled to achieve this level of security and often lacked QROM proofs.

1. Trade-offs in Key Size: While offering significant speed and security advantages, K-Waay's plain LWE instantiation results in larger public key sizes, on the order of 20 kilobytes. This is an acknowledged trade-off, primarily due to not using structured lattices, which could potentially reduce key sizes but might introduce additional assumptions.

In summary, K-Waay successfully addresses a critical gap in post-quantum secure messaging by providing a high-performance, deniable, and provably secure X3DH protocol that avoids the pitfalls of ring signatures, establishing split KEMs as a viable and efficient primitive for this application.

Technical Deep Dive

▶ Watch: Limitations of post-quantum ring signatures for X3DH (4:20)

The K-Waay protocol is designed to emulate the asynchronous, deniable key exchange properties of X3DH in a post-quantum setting, primarily by replacing Diffie-Hellman operations with Key Encapsulation Mechanisms (KEMs) and, more specifically, split KEMs.

The foundational primitive in K-Waay is the split KEM. Unlike a standard KEM, where encapsulation only requires the recipient's public key and decapsulation requires the recipient's secret key and the ciphertext, a split KEM introduces a symmetric element. In a split KEM:

• Key Generation (KeyGen): Alice and Bob both run a KeyGen algorithm to generate a public/secret key pair (pk_A, sk_A) and (pk_B, sk_B).
• Encapsulation (Encaps): If Alice wants to encapsulate a key towards Bob, she takes Bob's public key (pk_B) and her own secret key (sk_A) as input, producing a shared secret K and a ciphertext C. (K, C) = Encaps(pk_B, sk_A).
• Decapsulation (Decaps): Bob, to decapsulate, takes his secret key (sk_B), the ciphertext C, and Alice's public key (pk_A) as input, recovering the shared secret K. K = Decaps(sk_B, pk_A, C).

This structure inherently provides a form of non-interactive key exchange, reminiscent of Diffie-Hellman, but with a ciphertext component that offers additional flexibility for security notions and authentication. The K-Waay paper revisits the security notions for split KEMs, tailoring them to provide explicit authentication guarantees, which were missing from prior definitions. This is crucial for deniability, as it ensures that parties cannot convincingly deny participation in a key exchange without being detected by the protocol itself. A key insight is the ability to support ephemeral key reuse without requiring full CCA (Chosen-Ciphertext Attack) security, utilizing a specific trick detailed in the paper, leveraging the passive security properties of the underlying KEM.

The K-Waay protocol flow for Alice initiating a message to Bob is as follows:

1. Pre-Key Upload (Offline Phase):

• Both Alice and Bob generate and upload signed pre-key bundles to a central server (e.g., Signal server). These bundles contain various public keys, including split KEM public keys.
• Bob, acting as the receiver, also uploads an ephemeral public key to the server, which is a split KEM public key intended for single or limited use.
• The use of different key types (ephemeral, long-term, signature) is critical for providing security guarantees under various key exposure scenarios. For instance, if an ephemeral key is compromised, the long-term keys should still provide security.

1. Key Establishment (Alice Initiates):

• Alice retrieves Bob's pre-key bundle from the server.
• Alice then performs several encapsulation operations to derive shared secrets:
• She encapsulates using a regular KEM under Bob's long-term public key.
• She encapsulates using a regular KEM under Bob's ephemeral public key.
• Crucially, she performs an encapsulation using her own ephemeral split KEM secret key and Bob's ephemeral split KEM public key. This is where the deniable authentication property is primarily derived, binding Alice's identity to the key exchange.
• These three derived keys are then input into a Key Derivation Function (KDF) to produce the final session key.
• Alice then encrypts her initial message with this session key and uploads the ciphertext to the server for Bob.

1. Key Decapsulation (Bob Receives):

• When Bob comes online, he retrieves Alice's message and the associated keying material.
• Bob performs the corresponding decapsulation operations:
• He decapsulates the regular KEM ciphertexts using his own long-term and ephemeral secret keys.
• He decapsulates the split KEM ciphertext using his own ephemeral split KEM secret key and Alice's ephemeral split KEM public key.
• Bob verifies the integrity of the keys and, if successful, inputs them into the same KDF to derive the identical session key.
• With the session key, Bob can then decrypt Alice's message and begin secure communication.

Instantiation with Plain LWE:

The practical instantiation of the split KEMs in K-Waay is based on the plain Learning With Errors (LWE) problem. This is a conservative choice, similar to the security basis of FrodoKEM. The general structure involves:

• Alice and Bob generate (A, s, e) where A is a public matrix, s is a secret vector, and e is an error vector (e.g., pk = As + e).
• Encapsulation involves operations akin to Diffie-Hellman, where Alice combines Bob's public key with her own secret key, adding her own error terms. For example, Alice might compute pk_B * s_A + e_A.
• Decapsulation involves Bob combining Alice's public key with his own secret key to recover a value that, after noise reduction, matches the shared secret.

The parameters chosen for K-Waay's instantiation aim for 192 or 128 bits of classical security and 128 bits of quantum security. Even after applying the Quantum Random Oracle Model (QROM), which often leads to a reduction in provable security, K-Waay maintains 64 bits of quantum security, assuming a certain number of KEM queries. This is a significant improvement over previous ring-signature-based schemes that struggled with QROM proofs and higher security levels.

The performance benchmarks comparing K-Waay to other schemes, including Kyber 512 and Raptor ring signatures (instantiated with Falcon and Lithium), showed K-Waay to be substantially faster—at least three times quicker than ring-signature-based protocols. This efficiency comes at the cost of larger public keys, approximately 20 kilobytes, due to the use of plain LWE rather than structured lattices (e.g., Ring-LWE or Module-LWE), which could offer smaller key sizes but rely on stronger algebraic assumptions. The authors acknowledge this trade-off but emphasize the conservative security and performance benefits as key advantages.

Demo / Proof of Concept

▶ Watch: How Split KEMs work: encapsulation and decapsulation syntax (5:40)

The presentation did not include a live demonstration or a detailed description of a specific proof-of-concept implementation beyond the performance benchmarks. The focus of the talk was on the theoretical construction, security analysis, and comparative performance evaluation of the K-Waay protocol against existing and proposed post-quantum X3DH solutions. The benchmarks, however, served as a strong indication of the protocol's practical viability and efficiency.

Defensive Implications

▶ Watch: K-Waay's contributions: formal model, construction, benchmarks (7:00)

The K-Waay protocol carries significant defensive implications for the future of secure communication, particularly for messaging applications. As quantum computers advance, the security of current cryptographic protocols, including the widely used X3DH, will inevitably be compromised. Defenders need robust, quantum-resistant alternatives that maintain critical properties like deniability.

1. Transition to Full Post-Quantum Security: K-Waay provides a blueprint for moving beyond "store now, decrypt later" security (like pqXDH) to a state of full post-quantum security against active adversaries. This is paramount for protecting communications from sophisticated state-sponsored attackers who might possess quantum capabilities and actively interfere with key exchange processes. Defenders should prioritize adopting protocols that can withstand such active quantum attacks.

1. Maintaining Deniability: Deniability is a non-negotiable feature for many secure messaging users, especially those operating in sensitive environments. K-Waay demonstrates that this property can be preserved in the post-quantum era without incurring prohibitive performance costs. Organizations and developers building secure messaging platforms should ensure that their post-quantum migration strategies include solutions that uphold deniability, preventing metadata or communication records from being retroactively linked to individuals.

1. Efficiency and Scalability: The significant speed improvements offered by K-Waay over ring-signature-based approaches (being at least three times faster) are critical for real-world deployment. Efficient key exchange is essential for maintaining a smooth user experience and ensuring the scalability of large messaging services. Defenders evaluating PQC solutions must consider performance metrics alongside security guarantees to ensure practical applicability.

1. Conservative Security Assumptions: The reliance on plain LWE, a conservative and well-studied assumption, enhances confidence in K-Waay's long-term security. This choice minimizes reliance on more complex algebraic structures that might introduce unforeseen vulnerabilities. Defenders should favor PQC schemes built on robust and well-understood mathematical problems.

1. Trade-offs Awareness: While K-Waay offers compelling advantages, defenders must be aware of the inherent trade-offs, particularly the larger key sizes (approximately 20 kilobytes) compared to schemes built on structured lattices. This might impact bandwidth usage or storage requirements, especially in resource-constrained environments. A comprehensive evaluation of PQC options should weigh key size against security, performance, and specific deployment constraints.

1. Guidance for Protocol Development: K-Waay's design, particularly its innovative use of split KEMs and refined security notions, provides valuable guidance for cryptographers and protocol designers. It highlights a viable pathway for constructing complex PQC protocols without resorting to primitives that are computationally expensive or difficult to instantiate securely. Defenders should encourage research and development in similar directions to foster a diverse ecosystem of efficient PQC solutions.

In essence, K-Waay empowers defenders with a robust, efficient, and deniable post-quantum key exchange mechanism, enabling them to future-proof secure messaging applications against the looming threat of quantum computing while preserving crucial privacy properties.

Key Takeaways

• K-Waay is a novel protocol for fast and deniable post-quantum X3DH key exchange, designed for secure messaging applications.
• It achieves full post-quantum security against active attackers, unlike pqXDH, which primarily protects against "store now, decrypt later" attacks.
• The protocol innovatively uses split KEMs (a generalization of KEMs) and regular KEMs, circumventing the performance bottlenecks of post-quantum ring signatures used in prior deniable PQC X3DH proposals.
• K-Waay's instantiation is based on the conservative plain LWE assumption, similar to FrodoKEM, providing strong security guarantees.
• Performance benchmarks show K-Waay to be at least three times faster than ring-signature-based protocols, while providing 128 bits of classical security and 64 bits of quantum security (after QROM).
• The trade-off for this enhanced security and speed is larger public key sizes, approximately 20 kilobytes, due to the use of plain LWE.

About the Speaker(s)

The talk "K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures" was presented by Daniel Collins, representing a joint work conducted with his collaborators Loïs Huguenin-Dumittan, Ngoc Khanh Nguyen, Nicolas Rolin, and Serge Vaudenay. At the time of this research and presentation, the team was affiliated with EPFL (École Polytechnique Fédérale de Lausanne), a leading research institution in Switzerland. Their work focuses on advancing cryptographic protocols, particularly in the domain of post-quantum security and secure messaging.