Quantum computers pose a long-term threat to many currently used cryptographic schemes as they are able to efficiently solve the computational problems those schemes are based on. This threat has lead to research into quantum-resistant cryptographic schemes to eventually replace those currently used, as well as research into how to ease the transition from classical schemes to quantum-resistant ones. One approach to address these issues is to use a combiner that creates hybrid schemes, that is schemes which are classically and quantum-resistant, to protect against quantum attacks and maintain current security guarantees. Such combiners are used as a way to provide trust from different schemes and their differing computational difficulty assumptions rather than a single scheme. which may later become vulnerable. An important type of scheme that must be secure against both classical and quantum attacks are key encapsulation mechanisms (KEMs), as they are commonly used for constructing public-key encryption and key exchange protocols. We first define new security notions for KEMs modeling attackers of various levels of quantum power ranging from fully classical to fully quantum. We then construct a combiner that creates hybrid schemes for key encapsulation mechanisms which is secure against adversaries with varying levels of quantum power over time and can be implemented efficiently. Our construction provides an efficient method to combine KEMs using an additional scheme. This construction is also general enough that it can be implemented in settings such as key exchange protocols, like those used in the Transport Layer Security (TLS) protocol for web browsers, without affecting existing structure meaningfully.

Quantum computers present a threat to current cryptography, as they would be able to break many widely used public-key encryption schemes. In order maintain the security of communication infrastructure it is important that quantum-resistant algorithms become more common in use. However, adoption of quantum-resistant algorithms has been relatively slow, in part due to not wanting to risk abandoning schemes that are secure currently. In this thesis we focus on a specific type of scheme called a key encapsulation mechanism (KEM), used to fix a session key for communicating. We construct a secure way to combine currently secure KEMs and quantum-resistant KEMs that are secure now and against quantum computer. Our construction is simple enough that it can be implemented efficiently to provide quantum-resistant security, thus encouraging adoption of quantum-resistant algorithms.

Master of Science (MSc)

Thesis