Towards Generalized Diffie-Hellman-esque Key Agreement via Generic Split KEM Construction

The Diffie-Hellman (DH) problem is a cornerstone of countless key agreement schemes. One of these schemes is the popular instant messaging protocol, Signal. The Signal protocol relies on a subprotocol based on the DH-problem in order to create a secure session key. Unfortunately, as the threat of robust quantum computers continues to loom over traditionally hard problems such as the DH problem, quantum-resistant replacements for these schemes must be created. One candidate for a drop-in DH-style replacement is a special type of key encapsulation mechanism (KEM) called a split KEM, which maintains the same message flow of DH key agreement schemes. In this work, we present an efficient combiner to construct a split from a public key encryption scheme, a signature algorithm, and a special type of pseudorandom function (PRF), called a constrained PRF. Constrained PRFs can produce PRF keys with limited domains, and by selecting the domain to be a single point, the master secret key can be reused. We then use the remaining schemes to transport the constrained key and point and ensure the authenticity of the source of the ciphertext. We then prove that our construction reaches the split KEM formulation of traditional IND-CCA-security with a tight reduction.

Public-Key Cryptography, Provable Security, Key Agreement, Signal Protocol, Key Encapsulation

Conference (external link, opens in new window)