From Lattice Crypto to Lættis Krypto: Various Approaches to Post-Quantum Key Exchange

Abstract

Key exchange is a cryptographic mechanism: it enables two or more parties to agree upon a shared key that is known only to them, even in the presence of an adversary that has access to all communication between the parties. In postquantum key exchange we assume that this adversary additionally has access to a large-scale quantum computer that they can run computations on when trying to find the secret key. Several key exchange protocols that remedy this have been proposed in recent years, but a definitive solution is yet to be found. This dissertation consists of four contributions that approach the issue of postquantum key exchange from different angles. In the first contribution we create a new key exchange protocol using CSIDH, the Commutative variant of Supersingular Isogeny-based Diffie-Hellman. The protocol we introduce comes with an optimally tight security proof, due to CSIDHs similarity to classical (prequantum) Diffie-Hellman. The second contribution uses evolving symmetric keys to achieve the security properties typically found in public-key systems. In this work we provide five new protocols that all provide very small message sizes, and are proven to be secure in a new, strong, security model. For the third contribution we use KEM, a primitive closely related to key exchange, as a modular component. We show that we can systematically build authenticated key exchange protocols, using KEM, digital signatures and Message Authentication Codes as modular building blocks. For the final contribution we build a non-interactive key exchange protocol based on lattice- cryptography. This is a construction that has been folklore for at least a decade, but has always been thought too impractical for real-world usage. We implement a passively secure variant of the scheme and show that it is significantly more practical than it was believed to be.