PQ4DH - A Pathway for Quantum-Vulnerable Cryptography

In today's digital landscape, securing communication is paramount. Our proposal project focuses on a class of cryptographic primitives called key exchange, which underpins secure communication protocols used by billions globally. This includes Signal, the cryptographic protocol behind WhatsApp and Facebook Messenger, or Transport Layer Security (TLS), which safeguards communication between servers and users. These protocols rely on the Diffie-Hellman key exchange (DHKE). However, DHKE is vulnerable to attacks by quantum computers, and faces a growing quantum computing threat. One solution to this is post-quantum cryptography, a subset of cryptography that remain secure even against quantum computers. However, while post-quantum cryptography is finally maturing (as evidenced by NIST's post-quantum standardisation), their integration into real-world cryptography has not. This proposal addresses an important gap in the field: while numerous protocols have introduced post-quantum modifications individually, a systematised, universal approach to replacing quantum-vulnerable DHKE primitives with post-quantum cryptography has not been undertaken. Our proposal aims to create a universally-applicable framework that seamlessly transitions quantum-vulnerable DHKE into post-quantum cryptography based on NIST's proposed standards, specifically post-quantum key encapsulation mechanisms (KEMs). A key encapsulation mechanism is a cryptographic primitive in which one user (the sender) can transmit a secret to another user (the receiver) using their public key. The difficulty in this approach lies in the flexibility of DHKE, which post-quantum KEMs do not share. For instance, a DHKE public key can be combined with many different DHKE private keys to generate a shared secret key, allowing for many different variations of DHKE. However, a post-quantum KEM ciphertext can only be correctly decapsulated by a specific public key. This means that post-quantum cryptography used as a DHKE replacement cannot be combined similarly to DHKE, and thus a straightforward transform from DHKE to post-quantum cryptography does not exist. Our project aims to introduce a framework of generic transformations, to replace DHKE with post-quantum KEMs, while achieving (and formally proving) the same security properties. Thus, we aim to introduce a single, standardised approach to the post-quantum transition for secure communication. Our project will begin with surveying and categorising the security properties of all DHKEs, including forward secrecy, authentication, and key-indistinguishability. For each, we propose a generic replacement using KEMs, preserving their security properties, and each transformation will be formally analysed to prove that it maintains the security of the original. After, our project transitions to implementing and benchmarking these new replacements to understand their specific performance characteristics, demonstrating the exact costs and benefits associated with each transformation. We will propose a standard that allows stakeholders, such as designers of secure cryptographic protocols and the wider research community to utilise the proposed framework. Finally, our project applies our generic transformation to real-world cryptographic protocols, implementing and benchmarking these transformed protocols. The impact of the proposed research is significant - users of DHKE-based cryptographic protocols range from the general public, securing the communication of online transactions, to national interests, where DHKE establishes the security of messaging protocols used daily by politicians. Businesses and institutions can all benefit from our work when considering the scope of post-quantum transition. The Project Lead, Benjamin Dowling, is an expert in the formal analysis of cryptographic protocols, and has also been involved in post-quantum transitional efforts, such as the post-quantum Noise framework, a DHKE-based cryptographic protocol that is used by WhatsApp.