Tightly-secure Key Encapsulation Mechanism and its Application

Abstract

This thesis improves the security tightness of several cryptographic schemes and protocols in the post-quantum world, including key encapsulation mechanism, public-key encryption, and (password-based) authenticated key exchange. Tight security provides a provable and measurable security guarantee for a cryptosystem, and allows the cryptosystem to have more efficient instantiations. Our constructions use post-quantum assumptions and have tight security in the quantum idealized model, thereby providing better efficiency and stronger security guarantees against post-quantum adversaries. Post-Quantum Key Encapsulation Mechanism. Our main tool is tightly post-quantum secure key encapsulation mechanism, which serves as the enabler for improving the tightness of further cryptosystem. Existing constructions for post-quantum key encapsulation mechanism are highly non-tight. In this thesis, we design key encapsulation mechanism schemes that have tight(er) security against quantum adversaries, and use them as a primitive to construct other post-quantum cryptosystems. Public-key Encryption and Selective-Opening Security. Selective-opening secure publickey encryption lacks efficient constructions and tight security when facing quantum adversaries. We construct a tightly selective-opening secure public-key encryption scheme from key encapsulation mechanism. Our scheme is the first scheme having tight security against post-quantum adversaries in the selective-opening setting. (Password-based) Authenticated Key Exchange with Tight Security. Known security analyses of post-quantum authenticated key exchange and password-based key exchange are highly non-tight, which reduces confidence in their concrete security levels. Based on our tightly secure key encapsulation mechanism, we improve the security analysis of postquantum (password-based) authenticated key exchange, providing these protocols with more efficient constructions and more reliable security against post-quantum adversaries.