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, it 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 with only 14 group elements and 4 exponents communication complexity (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
adaptive corruptions of secret keys
. We show how to construct efficient schemes that satisfy the new definitions with
security proofs under standard assumptions.