Paper 2022/382

Witness-Authenticated Key Exchange Revisited: Improved Models, Simpler Constructions, Extensions to Groups

Matteo Campanelli, Protocol Labs
Rosario Gennaro, City University of New York, Protocol Labs
Kelsey Melissaris, Aarhus University
Luca Nizzardo, Protocol Labs

We study witness-authenticated key exchange (WAKE), in which parties authenticate through knowledge of a witness to any NP statement. WAKE achieves generic authenticated key exchange in the absence of trusted parties; WAKE is most suitable when a certificate authority is either unavailable or undesirable, as in highly decentralized networks. In practice WAKE approximates witness encryption, its elusive non-interactive analogue, at the cost of minimal interaction. This work is the first to propose, model and build witness-authenticated key exchange amongst groups of more than two parties, as well as the first to provide practical and provably secure constructions in the two-party case for general NP statements. Specifically our contributions are: (1) both game-based and universally composable (Canetti, FOCS '01) definitions for WAKE along with equivalence conditions between the two definitions, (2) a highly general compiler that introduces witness-authentication to any key exchange protocol along with, as a direct consequence, a three-round group WAKE protocol from DDH and signatures of knowledge (SOK), and (3) an optimized two-round group WAKE construction from DDH and SOK along with experimental benchmarks to demonstrate concrete practicality. Additionally, we study the specialized two-party case and provide a critique of prior work on this topic (Ngo et al., Financial Crypto '21) by pinpointing nontrivial weaknesses in the model, constructions and security proofs seen therein. We rectify those limitations with this work, significantly diverging in our techniques, design and approach.

Available format(s)
Cryptographic protocols
Publication info
key agreementsignatures of knowledgewitness encryption
Contact author(s)
matteo @ protocol ai
rosario gennaro @ protocol ai
kelseymelissaris @ gmail com
luca nizzardo @ protocol ai
2023-02-10: revised
2022-03-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Matteo Campanelli and Rosario Gennaro and Kelsey Melissaris and Luca Nizzardo},
      title = {Witness-Authenticated Key Exchange Revisited: Improved Models, Simpler Constructions, Extensions to Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2022/382},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.