Tightly Secure Authenticated Key Exchange

Christoph Bader, Dennis Hofheinz, Tibor Jager, Eike Kiltz, Yong Li

TCC 2015


We construct the first Authenticated Key Exchange (AKE) protocol whose security does not degrade with an increasing number of users or sessions. Our construction is modular, and can be instantiated efficiently from standard assumptions (such as the SXDH or DLIN assumptions in pairing-friendly groups). For instance, we provide an SXDH-based protocol whose communication complexity is only 14 group elements and 4 exponents (plus some bookkeeping information).

Along the way we develop new, stronger security definitions for digital signatures and key encapsulation mechanisms. For instance, we introduce a security model for digital signatures that provides existential unforgeability under chosen-message attacks in a multi-user setting with adaptive corruptions of secret keys. We show how to construct efficient schemes that satisfy the new definitions with tight security proofs under standard assumptions.


Tags: authenticated key exchange, digital signature schemes, Groth-Sahai Proofs, Tight Security Proofs