Intrinsically, the main challenge in a 0-RTT key exchange is to achieve forward secrecy and security against replay attacks for the very first payload message sent in the protocol. According to cryptographic folklore, it is impossible to achieve forward secrecy for this message, because the session key used to protect it must depend on a non-ephemeral secret of the receiver. If this secret is later leaked to an attacker, it should intuitively be possible for the attacker to compute the session key by performing the same computations as the receiver in the actual session.
In this paper we show that this belief is actually false. We construct the first 0-RTT key exchange protocol which provides full forward secrecy for all transmitted payload messages and is automatically resilient to replay attacks. In our construction we leverage a puncturable key encapsulation scheme which permits each ciphertext to only be decrypted once. Fundamentally, this is achieved by evolving the secret key after each decryption operation, but without modifying the corresponding public key or relying on shared state.
Our construction can be seen as an application of the puncturable encryption idea of Green and Miers (S&P 2015). We provide a new generic and standard-model construction of this tool that can be instantiated with any selectively secure hierarchical identity-based key encapsulation scheme.
Category / Keywords: cryptographic protocols / 0-RTT key exchange , Hierarchical IBE, Puncturable Encryption Original Publication (with minor differences): EUROCRYPT'17 Date: received 3 Mar 2017, last revised 25 Sep 2017 Contact author: tibor jager at upb de Available format(s): PDF | BibTeX Citation Note: Publication copyright information, citation fixes Version: 20170925:114210 (All versions of this report) Short URL: ia.cr/2017/223 Discussion forum: Show discussion | Start new discussion