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: both game-based and universally composable (Canetti, FOCS ’01) definitions for WAKE along with equivalence conditions between the two definitions, 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 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.

Homomorphic authenticators (HAs) enable a client to authenticate a large collection of data elements and outsource them, along with the corresponding authenticators, to an untrusted server. At any later point, the server can generate a short authenticator vouching for the correctness of the output y of a function f computed on the outsourced data, i.e. . The notion of HAs studied so far, however, only supports executions of computations over data authenticated by a single user. Motivated by realistic scenarios in which large datasets include data provided by multiple users, we study the concept of multi‐key homomorphic authenticators. In a nutshell, multi‐key HAs are like HAs with the extra feature of allowing the holder of public evaluation keys to compute on data authenticated under different secret keys. In this paper, we introduce and formally define multi‐key HAs. Secondly, we propose a construction of a multi‐key homomorphic signature based on standard lattices and supporting the evaluation of circuits of bounded polynomial depth. Thirdly, we provide a construction of multi‐key homomorphic MACs based only on pseudorandom functions and supporting the evaluation of low‐degree arithmetic circuits.

Zero Knowledge Contingent Payment (ZKCP) protocols allow fair exchange of sold goods and payments over the Bitcoin network. In this paper we point out two main shortcomings of current proposals for ZKCP, and propose ways to address them.