Paper 2022/382

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

Abstract

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.