Quantum-safe hybrid key exchanges with KEM-based authentication

Authenticated Key Exchange (AKE) is a foundational cryptographic building block that plays a critical role in safeguarding digital networks and infrastructures. In PQCrypto 2023, Bruckner, Ramacher, and Striecks proposed a novel hybrid 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.