arXiv:2411.04030 · EPJ Quantum Technology

Quantum-safe hybrid key exchanges with KEM-based authentication

Christopher Battarbee, Christoph Striecks, Ludovic Perret, Sebastian Ramacher, Kevin Verhaeghe

Published Nov 10, 2025• 9 citations

Abstract

AKE (HAKE) protocol dubbed Muckle+, which is particularly useful in large quantum-safe networks consisting of a large number of nodes. The Muckle+ protocol is of a hybrid nature, in that it facilitates the incorporation of key material from conventional, post-quantum, and quantum cryptography primitives into a unified authenticated shared key. To achieve the desired authentication properties, Muckle+ utilizes post-quantum digital signatures. However, the efficiency of available instantiations of such signature schemes is not yet comparable to that of their post-quantum key-encapsulation mechanism (KEM) counterparts, particularly in large networks with potentially several connections in a short period of time. In order to address this discrepancy, the present work proposes Muckle#, a protocol that aims to expand the existing boundaries of efficiency within the HAKE framework. Muckle# utilizes post-quantum KEMs for implicit authentication, drawing inspiration from recent advancements in the domain of Transport Layer Security (TLS) protocols, particularly in KEMTLS (CCS'20). Our KEM-based approach results in a slightly different message flow compared to prior work and we developed novel proof techniques in the process. Moreover, we implemented a proof of concept, thereby demonstrating practicality of this alternative approach to authentication within HAKE.

DOI: 10.1140/epjqt/s40507-025-00425-3

Related papers

Versatile quantum-safe hybrid key exchange and its application to MACsec

Jaime S. Buruaga, Augustine Bugler, Juan P. Brito +2 more

Advancements in quantum computing pose a significant threat to most of the cryptography currently deployed in our communication networks. Fortunately, cryptographic building blocks to mitigate this threat are already available; mostly based on Post-Quantum Cryptography (PQC) and Quantum Key Distribution (QKD), but also on symmetric cryptography techniques. Notably, those building blocks must be deployed as soon as possible in communication networks due to the “harvest-now decrypt-later” attack scenario, which is already challenging our sensitive and encrypted data today. Following an agile and defense-in-depth approach, Hybrid Authenticated Key-Exchange (HAKE) protocols have recently been gaining significant attention. Such protocols have the benefit of modularly combining classical (symmetric) cryptography, PQC, and QKD to achieve strong confidentiality, authenticity, and integrity guarantees for network channels. Unfortunately, only a few protocols have yet been proposed (mainly Muckle and Muckle+) with different flexibility guarantees. Looking at available standards in the network domain – especially at the Media Access Control Security (MACsec) standard – we believe that HAKE protocols could already bring strong security benefits to MACsec today. MACsec is a standard designed to secure communication at the data link layer in Ethernet networks by providing confidentiality, authenticity, and integrity for all traffic between trusted nodes. In addition, it establishes secure channels within a Local Area Network (LAN), ensuring that data remain protected from eavesdropping, tampering, and unauthorized access, while operating transparently to higher layer protocols. Currently, MACsec does not offer enough protection against the aforementioned threats. In this work, we tackle the challenge and propose a new versatile HAKE protocol, dubbed VMuckle, which is sufficiently flexible for use in MACsec. The use of VMuckle in MACsec provides LAN participants with quantum-safe hybrid key material to ensure secure communication even in the event of cryptographically relevant quantum computers.

arXiv:2505.14162EPJ Quantum TechnologyJul 4, 202512 citations

Integrating code-based post-quantum cryptography into SSL TLS protocols through an interoperable hybrid framework

Aasim Zafar, Syed Shamikh Iqbal

The advancement of quantum computing creates a big threat to classical cryptographic protocols, including TLS, which is responsible for secure internet communications. While recent industry and academic efforts have focused on integrating lattice-based post-quantum key encapsulation mechanisms (KEMs) such as Kyber+X25519 into hybrid TLS handshakes, these approaches often prioritize performance at the cost of cryptanalytic diversity. Code-based KEMs, despite their proven security measure they remain underexplored in hybrid frameworks due to some limitations like large key sizes and integration complexity. This paper proposes a novel hybrid TLS framework that explicitly incorporates code-based post-quantum cryptography—specifically McEliece—alongside classical key exchange mechanisms. The framework introduces a dual-handshake mechanism, adaptive parameter selection, and seamless fallback negotiation, enabling flexible deployment across heterogeneous networks while ensuring backward compatibility. Integration with Quantum Random Number Generators (QRNGs) and multifactor authentication further increases entropy quality and session security. We implemented and evaluated the framework using an OpenSSL-OQS integration. We measure handshake latency, CPU utilization, memory usage, and throughput across emulated and real-world testbeds. Results show that the proposed hybrid approach achieves up to 30% lower latency and significantly reduced resource overhead compared to pure post-quantum TLS variants, while maintaining near-classical efficiency levels. Mathematical modeling formalizes these trade-offs which offers a foundation for optimizing deployment in both resource-constrained IoT devices and high-performance servers. By advancing cryptographic diversity and aligning with emerging NIST and IETF standardization efforts, the proposed framework provides a practical pathway toward quantum-resilient secure communication.It shows that code-based post-quantum cryptography can be added to current TLS systems without any problems, keeping security, performance, and compatibility in mind as we get ready for the quantum age.

Discover ComputingSep 21, 20256 citations

Practical and post-quantum authenticated key exchange from one-way secure key encapsulation mechanism

Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa +1 more

This paper discusses how to realize practical post-quantum authenticated key exchange (AKE) with strong security, i.e., CK+ security (Krawczyk, CRYPTO 2005). It is known that strongly secure post-quantum AKE protocols exist on a generic construction from IND-CCA secure key encapsulation mechanisms (KEMs) in the standard model.

ACM Asia Conference on Computer and Communications Security (ASIA CCS)May 8, 201353 citations

Extensible Post Quantum Cryptography-Based Authentication

Homer A. Riva-Cambrin, Rahul Singh, Sanju Lama +1 more

Cryptography underpins the security of modern digital infrastructure, from cloud services to health data. However, many widely deployed systems will become vulnerable after the advent of scalable quantum computing. Although quantum-safe cryptographic primitives have been developed, such as lattice-based digital signature algorithms (DSAs) and key encapsulation mechanisms (KEMs), their unique structural and performance characteristics make them unsuitable for existing protocols. In this work, we introduce a quantum-safe single-shot protocol for machine-to-machine authentication and authorization that is specifically designed to leverage the strengths of lattice-based DSAs and KEMs. Operating entirely over insecure channels, this protocol enables the forward-secure establishment of tokens in constrained environments. By demonstrating how new quantum-safe cryptographic primitives can be incorporated into secure systems, this study lays the groundwork for scalable, resilient, and future-proof identity infrastructures in a quantum-enabled world.

arXiv:2505.16112IEEE Transactions on Information Forensics and SecurityJan 1, 20260 citations

QKD Oracles for Authenticated Key Exchange

Kathrin Hövelmanns, Daan Planken, Christian Schaffner +1 more

Authenticated Key Exchange (AKE) establishes shared ('symmetric') cryptographic keys which are essential for secure online communication. AKE protocols can be constructed from public-key cryptography like Key Encapsulation Mechanisms (KEMs). Another approach is to use Quantum Key Distribution (QKD) to establish a symmetric key, which uses quantum communication. Combining post-quantum AKE and QKD appropriately may provide security against quantum attacks even if only one of the two approaches turns out to be secure. We provide an extensive review of existing security analyses for combined AKE and their formal security models, and identify some gaps in their treatment of QKD key IDs. In particular, improper handling of QKD key IDs leads to Dependent-Key attacks on AKE. As our main conceptual contribution, we model QKD as an oracle that closely resembles the standard ETSI 014 QKD interface. We demonstrate the usability of our QKD oracle for cryptographic security analyses by integrating it into a prominent security model for AKE, called CK+ model, thereby obtaining a security model for combined AKE that catches Dependent-Key attacks. In this model, we formally prove security of a new protocol that combines QKD with a triple-KEM handshake. This is the first provably secure hybrid protocol that maintains information-theoretic security of QKD.

arXiv:2509.12478Sep 15, 20250 citations

Hybrid Quantum-Safe Cryptographic Scheme With Secure Key Exchange and Signature Scheme

Perera K. Maduni, Ilmu Byun, Jeongil Seo +1 more

Hybrid cryptographic protocol was proposed by integrating quantum-safe algorithms (Kyber and Dilithium) together with a classical ECDSA-based signature scheme to verify secure proof on blockchain. Since quantum computers pose some loopholes in existing cryptography algorithms, the proposed mechanism addresses those vulnerabilities by maintaining compatibility with the existing infrastructure. The protocol integrates post-quantum key exchange to derive shared secrets securely. The shared secrets are used to enable hybrid encryption for efficient data protection. Additionally, the implementation uses a dual-signature approach, using quantum safe and classical signatures. These signatures are combined to ensure robust and tamper-resistant proof verification. The deployed solution validates its feasibility and efficiency for smart contract-based verification. The protocol maintains backward compatibility with existing systems while providing strong resistance to quantum attacks. Benchmark results demonstrate the system’s scalability and robustness under high transaction loads, with efficient gas usage for on-chain proof validation. This approach paves the way for post-quantum secure applications, including verifiable proofs, secure key exchanges, and decentralized systems resilient to quantum adversaries.

IEEE AccessJan 1, 20257 citations