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.
Has parts
Paper A: de Kock, Bor; Gjøsteen, Kristian; Veroni, Mattia. Practical Isogeny-Based Key-Exchange with Optimal Tightness. Lecture Notes in Computer Science (LNCS) 2021 ;Volum 12804. s. 451-479. Copyright © 2021 Springer Nature Switzerland AG. Available at: http://dx.doi.org/10.1007/978-3-030-81652-0_18Paper B: Boyd, Colin Alexander; Davies, Gareth T.; de Kock, Bor; Gellert, Kai; Jager, Tibor; Millerjord, Lise. Symmetric Key Exchange with Full Forward Security and Robust Synchronization. Lecture Notes in Computer Science (LNCS) 2021 ;Volum 13093. s. 681-710. © 2021 International Association for Cryptologic Research. Available at: http://dx.doi.org/10.1007/978-3-030-92068-5_23
Paper C: Boyd, Colin; de Kock, Bor; Millerjord, Lise. Modular Design of KEM-Based Authenticated Key Exchange. Accepted for publication at ACISP 2023 (the 28th Australasian Conference on Information Security and Privacy). A manuscript is made public on the Cryptology ePrint Archive under number 2023/167 https://eprint.iacr.org/2023/167
Paper D: Gajland, Phillip; de Kock Bor; Quaresma, Miguel; Malavolta, Giulio; Schwabe, Peter. SWOOSH: Practical Lattice-Based Non-Interactive Key Exchange. Paper in submission. A manuscript is made public on the Cryptology ePrint Archive under number 2023/271 https://eprint.iacr.org/2023/271