Cryptology ePrint Archive: Report 2014/797

Tightly-Secure Authenticated Key Exchange

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

Abstract: We construct the first Authenticated Key Exchange (AKE) protocol whose security does not degrade with an increasing number of users or sessions. We describe a three-message protocol and prove security in an enhanced version of the classical Bellare-Rogaway security model.

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.

Category / Keywords: cryptographic protocols / Authenticated key exchange, tight security proofs, digital signature schemes, Groth-Sahai proofs

Original Publication (with minor differences): IACR-TCC-2015

Date: received 5 Oct 2014, last revised 12 Jan 2015

Contact author: christoph bader at rub de

Available format(s): PDF | BibTeX Citation

Version: 20150112:140554 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]