Witness-Authenticated Key Exchange Revisited

Improved Models, Simpler Constructions, Extensions to Groups

,2 Matteo Campanelli¹, Rosario Gennaro¹^, Kelsey Melissaris², and Luca Nizzardo¹

¹ Protocol Labs {matteo,rosario.gennaro,luca.nizzardo}@protocol.ai ² City University of New York kelseymelissaris@gmail.com

Abstract. We revisit the notion of Witness Authenticated Key Exchange (WAKE) where a party can be authenticated through a generic witness to an NP statement. We point out shortcomings of previous definitions, protocols and security proofs in Ngo et al. (Financial Cryptography 2021) for the (unilaretally-authenticated) two-party case. In order to overcome these limitations we introduce new models and protocols, including the first definition in literature of group witness-authenticated key exchange. We provide simple constructions based on (succinct) signatures of knowledge. Finally, we discuss their concrete performance for several practical applications in highly decentralized networks.

1 Introduction

Public-Key Cryptography as introduced in the seminal paper by Diffie and Hellman [DH76] allows two parties who have never met to exchange confidential information by either interactively establishing a secret key or by means of a single encrypted message from the sender to the receiver [RSA78]. The identity of the communicating parties is traditionally established through the use of certificates: digital signatures from trusted authorities binding the parties’ identities to their public keys used to encrypt the messages.

More flexible ways to determine the recipient of an encrypted message were devised with identity- based [Sha84] (where public keys can be arbitrary strings) and attribute-based [SW05] encryption (where messages are encrypted under security policies and only parties holding attributes satisfying the policy can 3 decrypt) removing the need to obtain certificates in advance of sending the message.

Witness encryption [GGSW13] is arguably the most general way to determine the intended recipient of an encrypted message. In WE a message is encrypted under a specific instance ϕ of an NP language L, and can be decrypted if and only if ϕ ∈ L, using an efficient decryption procedure that takes a witness w for ϕ as input⁴. Remarkably, no trusted party is required for WE: the secret decryption key is the witness itself.

$$ \phi\in L $$

In a theoretical sense all of these notions only make sense in the non-interactive setting of a sender encrypting a message for a receiver. Indeed, in the interactive key agreement setting, certificates can be sent as part of the communication flow in the case of IBE/ABE and generic secure two-party computation techniques can be used to establish a secure channel between a sender and a receiver who knows a specific witness. However interactive versions of these models have been introduced mostly for efficiency reasons + (e.g. [FG10, BBC 13, CCGS10, NMKW21]).

Another, perhaps more important, advantage of looking at interactive key agreement in these models is that they additionally allow for the establishment of group keys which enable confidential communication among arbitrary numbers of authorized participants.

In this paper we revisit the notion of witness authenticated key exchange (WAKE) introduced in [NMKW21], by (i) pointing out shortcomings in their definition and proofs, and (ii) proposing a new and much simpler protocol for the two-party case. We then (iii) extend our results to the group setting and construct the first witness-based group key agreement protocol.

³ In these models there is a trusted party which issues secret keys to the users matching respectively their identity and their attributes (and as a consequence can decrypt all messages).

⁴ The original notion requires that a witness is sufficient to decrypt but does not guarantee that knowledge of w is necessary for a successful decryption.

1.1 Motivation

As mentioned above, the main application of witness based key exchange is the establishment of secure communication channels based on arbitrary conditions that are satisfied by what the parties know or hold. The lack of a centralized trusted authority that issues secret keys or certificates makes this tool particularly interesting for decentralized applications, where parties can dynamically and flexibly confidentially connect with other parties based on common policies. Decoupling authentication and the notion of identity also allows for more flexible deniable and anonymous authentication. In this section we present some concrete examples, many of them exploiting our novel construction for groups.

Dark Pools Transactions. This was the original motivation in [NMKW21]. In this scenario Alice wants to confidentially negotiate with a party who has enough funds. Given a public commitment to his balance Bob can establish a secret key with Alice if his funds satisfy her condition. Here the witness w is the balance held by Bob and the NP relation that must be satisfied is that w is the correct committed value and satisfies Alice’s conditions.

Chat with the same wallet. Several services are offered that allow parties to create chatrooms and schedule meetings amongst parties that hold similar tokens in a blockchain (e.g. [cwe, mee]). A group witnessauthenticated key exchange can be used to establish secure communication channels for such tasks. Thanks to the inherent flexibility of a witness key agreement these schemes can also be extended to more general conditions (e.g. confidential chatrooms for owners of NFTs by a particular artist).

Retrieval Markets. In decentralized storage systems such as Filecoin [Proa] and IPFS [Prob] files are stored by providers and addressed by a content identifier (CID) which is basically a cryptographic hash of the file. While the CID does not say where the file is stored, it does provide a unique handle for the file to be retrieved later. The CID also serves as a commitment to the file and therefore providers can use the file itself as a witness to establish confidential negotiation channels with clients interested in its retrieval. Similarly, providers storing the same file (or files satisfying certain properties) can establish a confidential group channel to communicate via a group witness key agreement.

Decentralized Anonymous Routing. Several proposals have been put forward for decentralized naming and routing protocols over the internet (see e.g. [han] and [ens]). We believe that WAKE can play an important role in securing such protocols since it provides a method with which parties can ”authenticate” themselves without the need for centralized trusted authorities.

1.2 Our Contributions

–A critique of the previous model and construction in [NMKW21]: we observe that the definition of witness key agreement in [NMKW21] is not sufficient for the proposed applications. We also point out limitations of their construction.

–A new definition for WAKE**:** we rectify the above limitations and propose a new definition for (group) WAKE (Witness Authenticated Key Exchange).

–A construction of U**-**WAKE: we provide a definition for Unilaterally Witness Authenticated Key Exchange (two-party key exchange where only one party is authenticated) as a special case of WAKE, along with a simple construction for U-WAKE. This construction generalizes UAKE [DF17] in the standard setting.

–A construction of (group) WAKE: we show a compiler turning any key exchange with “passive security” into one with full security in the witness-based setting. This compiler revisits that in [KY03] for standard group key exchange. We also show a three-round WAKE protocol, obtained by applying our compiler to the passively secure key exchange from [BD95].

–Evaluation in practice and applications: we show the feasibility of our construction by experimentally evaluating its efficiency.

1.3 Technical Overview

Definition of WAKE**.** Our WAKE definition extends the definition of unilaterally-authenticated key agreement from [DF17] in the PKI model to work in the case of witness authentication. This is not a trivial task: one main difference is how to model the adversary’s knowledge with respect to the NP instance ϕ, acting as the “public key” for the authenticating party. In the PKI case the adversary does not know the secret key of the honest parties, but in the WAKE case it is conceivable that for a specific instance ϕ the adversary may know the corresponding witness w. Under these circumstances obviously we cannot prevent the adversary from successfully authenticating, but we can still require that the adversary is not able to decrypt conversations involving any honest parties that have authenticated with respect to the same instance ϕ. This is somewhat the equivalent of perfect forward secrecy in the PKI case, where compromise of the long-term secret key of a party does not compromise the secrecy of the session keys established by that party. Our definition requires the extraction of a witness from any adversary that successfully authenticates and completes a WAKE.

By leveraging interaction we obtain stronger security properties than (non-interactive) witness encryption, both in terms of confidentiality (parties can confidentially exchange a secret even if the adversary knows a witness) and authentication (we guarantee knowledge of a witness upon successful authentication). We finally remark that our confidentiality definition also guarantees perfect forward secrecy.

Simulatability. In general it is not necessary to enforce that no information about the witness is leaked during the protocol as long as we can prove that knowledge of the witness is required to successfully authenticate. This brings up an interesting question: assume we have a protocol where the adversary can learn a bit of the witness. After several executions, the adversary will learn the witness and be able to authenticate and perform the WAKE on its own. This would obviously be a problem in PKI-based KA protocols, as the adversary would be able to impersonate a different party. But in WAKE such a protocol does not violate the definition of security since once the adversary is able to complete the protocol it does know the witness. This leads us to introduce an additional simulatability condition enforcing that no information about the witness is leaked.

Our Protocol. Our two-party protocol uses Signatures of Knowledge [CL06] to perform witness authentication. The initiator (who does not have the witness) sends the “public key” for a Key Encapsulation Module (KEM) and the responder sends the KEM message “signed” with a Signature of Knowledge of the witness. The initiator accepts if the signature verifies and then decrypts the session key from the KEM message. We point out that [NMKW21] had ruled out the use of SOK, due to problems with their proposed solution but our solution is different from that proposed in [NMKW21].

Group WAKE Construction. The group protocol adapts the Katz-Yung [KY03] general compiler (which maps unauthenticated group key exchange protocols to authenticated ones) to be able to use Signatures of Knowledge. Then, following [KY03], we obtain a 3-round group WAKE by applying our transformation to the Burmester-Desmedt [BD95] group key exchange. We point out that in our group protocols, each party may refer to a different NP statement when authenticating, if required by the authentication policy in place.

1.4 Related Work

1.4.1 Comparison to and Limitations of [NMKW21] Model and Definitions: A basic requirement of key agreement schemes is that one should not to able to learn anything about the session-key. This is usually modeled by requiring that the adversary should not be able to distinguish the real session key from a random key (in a session not tampered by the adversary obviously). Indistinguishability is required to claim that exchanging messages in a session protected by the key is equivalent to sending those messages over a secure channel. We note that an adversary can either be passive (eavesdropping exchanges by honest players), or active (man in the middle).

The definition in [NMKW21] does not follow the typical modeling of authenticated key agreement protocols, and in doing so weakens the security of the session key. In fact, indistinguishability is only required for passive adversaries. A separate definition for active adversaries only requires unpredictability of the session key.

Constructions. Both our construction and that in [NMKW21] rely on non-interactive arguments of knowledge; [NMKW21] employs designated-verifier SNARKs while we use succint, publicly-verifiable signatures of knowledge.

A primary limitation of [NMKW21] is that it requires a trusted setup every time a new party wants to initiate a key exchange⁵ (see Fig. 4 and end of Section 4 in [NMKW21]). This is due to the designatedverifier argument systems. Although the verifier often has access to “all the secrets” used during parameter generation it is still necessary for a trusted party to ensure that the parameters are computed correctly. This is true of the specific instantiation considered, for example ([Gro16]). We provide general and modular constructions, along with concrete instantiations, without this limitation.

Finally, we find it unclear whether the security of the construction in [NMKW21] actually holds. Their + construction and proof use a variant of the techniques in [BCI 13] where secret points in the setup are encrypted with a limited-malleability encryption scheme. The construction in [NMKW21] diverges, however, in that they add additional encryptions of the randomness used to encrypt the other ciphertexts. This introduces additional leakage and plausibly requires a stronger encryption scheme: one with randomness-dependent message security [BCPT13]. Nonetheless, neither the theorem statement nor the proof in [NMKW21] explicitly acknowledges this fact.

$$ [\mathrm{B C B^{+}13}] $$

• 1.4.2 LAKE Language Authenticated Key Exchange LAKE [BBC 13] (and its predecessor CAKE [CCGS10]) enables two parties to establish a shared key over an insecure network. Authentication is done on the basis of words in languages; participants terminate with a common session key if and only if each participant has knowledge of a word that lies in the language defined by their partner. This implies that not only does the witness remain secret, but that the language and the statement are also secret. In contrast, our definition of WAKE does not guarantee secrecy of the statement. Additionally, LAKE is defined in the UC setting with a common reference string while our WAKE definitions are game-based.

$$ [\mathrm{B B C^{+}13}] $$

The construction provided handles algebraic languages (languages which admit a smooth projective hash function [CS98]) and therefore is not as general as WAKE. There is no mention of group key agreement in

• ⁺ [BBC 13, CCGS10], whereas WAKE is defined for groups. The construction provided in [BBC 13] gives a three round protocol with an additional preliminary round. Our two-party U-WAKE protocol, when run bilaterally, can achieve WAKE for two parties in two rounds.

$$ \mathrm{{[B B C^{+}13} $$

$$ [\mathrm{B B C^{+}13}] $$

1.4.3 Conditional Disclosure of Secrets Conditional disclosure of secrets (CDS) [GIKM98] is an interactive primitive that allows a Sender to disclose a secret message m to a Receiver holding some secret input w under some condition C on w. We now show a CDS protocol based on Fully Homomorphic Encryp- 6 tion (FHE) for any NP Language. On input a language L and an instance ϕ, let R be the corresponding relation for L (i.e. R(ϕ,w) = 1 if ϕ ∈ L and w is the witness). The Initiator (who owns the witness) sends an FHE public key E and the value c = E[w] to the Responder, who, using the FHE property, sends back ′ ^′ c = E[r(R(ϕ,w) − 1) + m] where r is a uniform random value. The Initiator can now decrypt c to m if (ϕ,w) ∈R or a random value otherwise.

$$ \mathrm{(F H E)^{6}} $$

$$ L $$

$$ \phi, $$

$$ L,(\mathrm{i.e.},\mathcal{R}(\phi,w)=1,\mathrm{i f},\phi\in L $$

$$ c=E[w] $$

$$ c^{\prime}=E[r(R(\phi,w)-1)+m] $$

$$ c^{\prime} $$

$$ (\phi,w)\in\mathcal{R} $$

It would be tempting to use the above protocol to establish a session key (by setting the session key K as m in the above protocol). However that would lead to an easy “malleability” attack, where instead of ′ ′ computing r(1*−R*(ϕ,w)) +K, the responder computes r(1*−R*(ϕ,w)) +K where K is a session key related to K. This will break the indistinguishability condition on K.

$$ r\bigl(1!-!\mathcal{R}\bigl(\phi,w\bigr)\bigr)!+!K $$

$$ r\bigl(1!-!\mathcal{R}\bigl(\phi,w\bigr)\bigr)!+!K^{\prime} $$

$$ K^{\prime} $$

The above attack can probably be thwarted by adding a zero knowledge proof that the Responder really computed r(1 −R(ϕ,w)) + K and knows r,K. But this brings us back to our solution requiring the computation of a ZK proof over the relation R, this time with the FHE overhead on top. On the other hand it has the advantage of putting the cost of the ZK proof on the party who does not know the witness which could be an advantage in some cases (e.g. when the party with the witness has to establish many sessions).

$$ r\big(1-\mathcal{R}\big(\phi,w\big)\big)+K $$

$$ r,K. $$

$$ {\mathfrak R}, $$

1.5 Outline

We define our mode for (group) WAKE in section 3.1. We then specialize it to the unilaterally-authenticated case in section 4; we provide a simple construction in that same section. We show a compiler from passively

$$ 4{;cdot} $$

⁵ Although, if the same party wants to run multiple key agreements on the same relation, it could potentially reuse the setup.

⁶ It is possible to build CDS also from additively homomorphic encryption [AIR01] where however communication grows linearly in the description of the condition C

$$ C $$ secure to actively secure (group) WAKE in section 5; we elaborate on how to instantiate it in section 6. Finally in Sections 7 and 8 we respectively show how to optimize our constructions with an offline preprocessing and discuss their concrete practical costs .

$$ ^{5} $$

2 Preliminaries

2.1 Notation

∗ The concatenation of two strings, a,b ∈ {0,1}, is denoted a||b, the concatenation of two vectors u = (u₁,...,u_n) and v = (v₁,...,v_m) is denoted u||v = (u₁,...,u_n,v₁,...,v_m). We write x ← X to denote sampling the element x uniformly at random from the set X, x ← D to denote sampling x according to distribution D, and x ← A(y) to denote running algorithm A on input y to get output x.

$$ a,b,\in,{0,1}^{*} $$

$$ a\vert b, $$

$$ (u_{1},\ldots,u_{n}) $$

$$ u= $$

$$ v,=,\left(v_{1},\ldots,v_{m}\right) $$

$$ \ {big vert}v=\left(u_{1},\ldots,u_{n},v_{1},\ldots,v_{m}\right) $$

$$ x\gets X $$

$$ X,,x\gets\mathcal{D} $$

$$ x\gets A(y) $$

The security parameter is denoted λ and is considered public. We say a function f is negligible if −ω(1) |f(λ)| = λ. PPT is used to denote probabilistic polynomial time. A participant U is initialized with inputs (input₁*,...,* inputⁿ) using square brackets: U[input₁*,...,* inputⁿ]. A protocol run between participants O U₁,...,U_ℓis written as ⟨U₁,...,U_ℓ⟩. For an oracle O we use A to say that algorithm A has access to oracle O. The keyspace in a key exchange is denoted K.

$$ |f(\lambda)|=\lambda^{-\omega(1)} $$

$$ \mathsf{u t}{1},\ldots,\mathsf{i n p u t}{n}) $$

$$ U[\ \mathsf{i n p u t}{1},\ldots,\mathsf{i n p u t}{n}] $$

$$ U_{1},\ldots,U_{\ell} $$

$$ \langle U_{1},\ldots,U_{\ell}\rangle $$

$$ A^{o} $$

2.2 Key Encapsulation Mechanism

Definition 1(Key Encapsulation Mechanism (KEM)). A key encapsulation mechanism is defined by a triple of algorithms (KG*,Encap,*Decap) with the following syntax:

^λ KG(1) → (ek*,*dk) : the key generation algorithms is randomized and outputs an encapsulation and a decap- sulation key.

$$ {\mathsf{K G}}(1^{\lambda})\to({\mathsf{e k}},{\mathsf{d k}}) $$

Encap(ek) → (C, k) : the encapsulation algorithm is randomized and outputs a ciphertext C and a session key K.

$$ {\mathfrak{a p}}(\mathsf{e k})\to(C,\mathsf{k}) $$

Decap(dk*,C*) → k : the decapsulation algorithm is deterministic and retrieves the session key from the ci- phertext and the decapsulation key.

For correctness we require that for all (ek*,*dk) output by the key generation algorithm, k_e= k_dfor Encap(ek) → (C,k_e) and Decap(dk,C) → k_d. For CPA security we require that an adversary cannot distinguish the real session key from a random one.

$$ \mathrm {k} _ {e} = \mathrm {k} _ {d} $$

$$ \mathsf{E n c a p}(\mathsf{e k})\to\big(C,\mathsf{k}_{e}\big) $$

$$ {\mathsf{D e c a p}}({mathsf\mathsf d{}}{\mathsf{k}},C)\to{\mathsf{k}}_{d} $$

Definition 2(KEM-CPA). We say that a KEM is CPA*-secure if for any PPT adversary A and for any* λ ∈ N the advantage of A, as defined, is negligible:

$$ \lambda\in\mathbb{N} $$

$$ \mathbf {A d v} _ {\mathrm {K E M - C P A}, \mathcal {A}} (\lambda) := 2 \cdot \Pr [ \mathbf {E x p} _ {\mathrm {K E M - C P A}, \mathcal {A}} (\lambda) = 1 ] - 1 \leq \operatorname {n e g l} (\lambda) $$

where ExpKEM*-*CPA_,Ais defined in fig. 1.

2.3 Signature of Knowledge

A signature of knowledge allows signers to produce signatures that verify under the condition that they were generated with knowledge of a witness to associated statement ϕ.

Definition 3(Signature of Knowledge (SOK)). A Signature of Knowledge is a tuple of four efficient algorithms (SSetup*,SSign,SVfy,SSimSetup,SSimSign), where R is a relation generator and {M*_λ}_λ∈Na se- quence of message spaces, with the following syntax:

$$ \phi, $$

$$ {\mathcal{M}{\lambda}}{\lambda\in\mathbb{N}} $$

λ SSetup(1*,R*) → pp : the setup algorithm is randomized and takes as input a relation R ∈ R_λ, and the security parameter λ, and returns public parameters pp.

$$ {\mathsf{S S e t u p}}(1^{\lambda},R)\to p p $$

$$ R\in\mathcal{R}_{\lambda} $$

SSign(pp,ϕ,w,m) → σ : the signing algorithm is randomized and takes as input the public parameters pp, an instance-witness pair in the relation (ϕ,w) ∈ R and a message m ∈M_λand returns a signature σ.

$$ {\mathfrak{S S i g n}}\ p(p p,\phi,w,m)\to\sigma\ : $$

$$ (\phi,w)\in R $$

$$ m\in\mathcal{M}_{\lambda} $$

$$ \sigma $$

$$ \mathrm{E x p}_{\mathsf{K E M},\mathcal{A}}^{\mathsf{C P A}}(\lambda) $$

$$ b\gets\S\left{0,1\right} $$

$$ (\mathsf{e k},\mathsf{d k})\leftarrow\mathsf{K E M}.\mathsf{K G}(1^{\lambda}) $$

$$ b^{\prime}\leftarrow\mathcal{A}(\mathsf{e k},C,\mathsf{k}_{b}) $$

$$ {\mathrm{i f}}b^{\prime}=b,:{\mathrm{o u t p u t}}1 $$

$$ \mathsf{k}_{0}\xleftarrow{\S}\mathcal{K} $$

$$ (C,\mathsf{k}_{1})\leftarrow\mathsf{K E M.E n c a p(e k)} $$

CPA Fig. 1: Exp_KEM,A: Experiment for KEM-CPA security.

$$ \ {\mathtt x x p}_{{{mathsf K K K}},{\mathcal{A}}}^{\ \ C{\mathsf A}} $$

$$ \mathbf{E x p}_{\mathsf{S O K},\mathcal{A}}^{\mathsf{s i m u l}}(\lambda) $$

$$ \mathcal{S}{p p{0},\tau}^{0}(\phi_{i},w_{i},m_{i}) $$

$$ R\leftarrow\mathcal{R}_{\lambda};:b\xleftarrow{\S}{0,1} $$

$$ \operatorname{a s s e r t}\left(\phi_{i},w_{i}\right)\in R\land m_{i}\in\mathcal{M}_{\lambda} $$

$$ p p_{0}\leftarrow\mathsf{S S e t u p}(R) $$

$$ \sigma_{i}\leftarrow{mathsf{S S i n}}(p p_{0},\phi,w,m) $$

$$ (p p_{1},\tau)\leftarrow\mathsf{S S i m S e t u p}(R) $$

$$ b^{\prime}\leftarrow\mathcal{A}^{\mathcal{S}{p p{b}}^{b},\tau}(p p_{b}) $$

$$ \mathcal{S}{p p{1},\tau}^{1}(\phi_{i},w_{i},m_{i}) $$

$$ \left(\phi_{i},w_{i}\right)\in R\wedge m_{i}\in\mathcal{M}_{\lambda} $$

$$ {\mathrm{i f}};b=b^{\prime};:;{\mathrm{r e t u r n}};1 $$

$$ \sigma_{i}\leftarrow\mathsf{S S i m S l g n}(p p_{1},\tau,\phi,m) $$

$$ :\mathrm{\ r e t u r n\ 0} $$

simul Fig. 2: Exp_SOK,A: Experiment for SOK perfect simulatability.

$$ \sigma_{i} $$

$$ \mathtt{E x p}_{\mathsf{S O K},\mathcal{A}}^{\mathsf{s i m u l}}: $$

SVfy(pp,ϕ,m,σ) →{0,1} : the verification algorithm is deterministic and takes as input the public param- eters pp, an instance ϕ, a message m ∈M_λand a signature σ, and outputs either 0 for reject or 1 for accept.

$$ {\mathsf{S V f y}}(p p,\phi,m,\sigma)\to\left{0,1\right} $$

$$ m\in\mathcal{M}_{\lambda} $$

$$ \sigma, $$

SSimSetup(R) → (pp,τ) : the simulated setup algorithm is randomized and takes as input a relation R ∈R_λ and returns the public parameters pp and a trapdoor τ.

$$ R\in\mathcal{R}_{\lambda} $$

$$ \ \mathsf{p}(R)\to(p p,\tau) $$

SSimSign(pp,τ,ϕ,m) → σ : the simulated signing algorithm is randomized and takes as input some public parameters pp, a simulation trapdoor τ and an instance ϕ and returns a signature σ.

$$ \mathsf{i i g n}(p p,\tau,\phi,m)\to\sigma $$

$$ p p, $$

$$ \phi $$

$$ \sigma. $$

Perfect correctness requires that the verifier will always be convinced by a signature of knowledge produced with an instance-witness pair in the relation.

Definition 4(Perfect Correctness). A signature of knowledge is perfectly correct if for all security pa- rameters λ ∈ N and for all relations R ∈ R_λ, for all valid instance-witness pairs satisfying the relation (ϕ,w) ∈ R and for all messages m ∈M_λ:

$$ R\in\mathcal{R}_{\lambda} $$

$$ \lambda\in\mathbb{N} $$

$$ (\phi,w)\in R $$

$$ m\in\mathcal{M}_{\lambda} $$

$$ \Pr [ \mathrm {S V f y} (p p, \phi , m, \sigma) = 1 | p p \leftarrow \mathrm {S S e t u p} (R); \sigma \leftarrow \mathrm {S S i g n} (p p, \phi , w, m) ] = 1 $$

Definition 5(Perfect Simulatability). We say that a signature of knowledge is perfectly simulatable if simul simul for any PPT adversary A, the advantage of the adversary A_SOK,A(λ) = 2*·Pr[Exp_SOK,A(λ) = 1] − 1 = 0,* simul where Exp_SOK,Ais defined in fig. 2.

$$ \cal{A}{\sf S O K,\cal A}^{\sf s i m u l}(\lambda)\ =\ 2{\cdot}\ \operatorname*{P r}[\ E x p{\sf S O K,\cal A}^{\sf s i m u l}(\lambda)\ =\ 1]\ -\ 1\ =\ 0 $$

$$ \mathtt{E x p}_{\mathsf{S O K},\mathcal{A}}^{\mathsf{s i m u l}} $$

For simulation extractability we require that an adversary cannot generate a new signature with respect to a statement ϕ without knowledge of a witness w for ϕ, and from any adversary that outputs a verifying signature we can extract a witness.

$$ \phi $$

$$ \phi, $$

$$ \mathbf{E x p}{\mathsf{S O K},\mathcal{A},\mathcal{E}{\mathcal{A}}}^{\mathsf{s i g-e x t}}(\lambda) $$

$$ \mathsf{S S i m S i g n}{p p,\tau}(\phi{i},m_{i}) $$

$$ \sigma_{i}\leftarrow\mathsf{S S i m S i g n}(p p,\tau,\phi_{i},m_{i}) $$

$$ (p p,\tau)\leftarrow{\sf S S S i m S e t u p}(R) $$

$$ \mathcal{Q}=\mathcal{Q}\cup\left{\left(\phi_{i},m_{i},\sigma_{i}\right)\right} $$

$$ \sigma_{i} $$

$$ (\phi,w)\notin R $$

$$ w\leftarrow\mathcal{E}{\mathcal{A}}(\operatorname{t r a n s}{\mathcal{A}}) $$

$$ (\phi,m,\sigma)\notin\mathcal{Q} $$

$$ \mathsf{S V f y}(p p,\phi,m,\sigma) $$

sig−ext Fig. 3: Exp : Experiment for SOK simulation extractability. SOK,A,EA

$$ \operatorname{E x p}{\mathsf{S O K},\mathcal{A},\mathcal{E}{\mathcal{A}}}^{\mathsf{s i g-e x t}} $$

Definition 6(Simulation Extractability). We say that a signature of knowledge is simulation-extractable sig−ext sig−ext if for any PPT adversary A, there exists a PPT extractor E_Asuch that: Adv (λ) = Pr[Exp (λ) = _SOK,A,EASOK,A,EA sig−ext 1] ≈ 0, where Exp is defined in fig. 3. SOK,A,EA

$$ \mathcal{E}_{\mathcal{A}} $$

$$ \bf{A{v v}}{S O K,A,E{A}}^{s i g\mathrm{}{-}e x t\ }(\lambda)=\operatorname*{P r}[E\bf{E x p}{S O K,A,E{A}}^{s i g\mathrm{}{-}e x t}(\lambda)]} $$

$$ \mathbf{1}]\approx\mathbf{0} $$

$$ \mathtt{E x p}{\mathtt{S O K},\mathcal{A},\mathcal{E}{\mathcal{A}}}^{\mathsf{s i g-e x t}} $$

2.4 Transcripts and Views

The transcript of a protocol execution is defined to be the concatenation of all messages sent by any participant in the execution.

Definition 7(Protocol Transcript). The transcript of a protocol session between k participants is the sequence of messages exchanged by the participants during a run of the protocol Π. If Π is n-round then a 1 n n i transcript T is of the form T = M₁₁||M₂₁||···||M_k||···||M₁ ||M₂ ||M_knwhere messages M₁,...,M_kiare the 1 n i k_imessages sent in round i.

$$ T\hat{=}M_{1mathbf}^{1|}M_{2}^{1\ }||\cdots|\bar{|{M{1}}^{1}}||\cdots||\bar{M_{1}^{n}}||M_{2}^{n}||\hat{M}{k{r}}^{n} $$

$$ M_{1}^{i},\ldots,M_{k_{i}}^{i} $$

$$ k_{i} $$

All messages are recorded by each party in the order in which they were received so a transcript is sorted by round, but different participants may have messages appear in different order in the transcript they recorded. As the transcript for a session will be the session identifier (see Section 3.1) there must be a notion of equivalence for transcripts containing the same messages but messages within each round appear in arbitrary order. Two transcripts match if they have the same set of messages in each round. This is formalized in Definition 8.

Definition 8(Matching Transcripts). Let T and Tˆ be two protocol transcripts and define R (resp ^i,T ˆ ˆ ˆ∗ R_ˆ) to be the set of messages appearing in round i of T (resp T). We say that T matches T (or T ≡ T) i,T if R_i,T= R_ˆfor all i. i,T

$$ \hat{T} $$

$$ R_{i,T} $$

$$ R_{i,\hat{T}}) $$

$$ (o r;T\equiv\hat{T}^{*}) $$

$$ :R_{i,T}=R_{i,\hat{T}} $$

Finally, we define the view of a participant to be the following:

Definition 9(Participant View). The view of participant P_i, written as view_Pi, is defined to be all inputs and outputs of that participant including the transcript, all oracle queries, oracle responses, and all random coins given to that participant.

$$ P_{i} $$

3 Defining WAKE

The goal of WAKE is that for any set of participants engaging in the key exchange protocol, authenticating with respect to (not necessarily distinct) statements, if each participant has knowledge of a witness to their associated statement then the participants terminate with a shared key, otherwise the participants terminate without a session key.

The model proposed is fundamentally similar to that of the group key exchange provided in [KY03] with minor modifications related to the unique setting of witness-authentication. The most impactful change is to the concept of identity. In authenticated group key exchange a participant’s identity is associated to their public key and is interpreted as participant i is the holder of the secret key corresponding to public key PK_i. Below the public key vector is replaced by a public statement vector Φ = ⟨ϕ₁,...,ϕ_ℓ⟩ and each participant V_iclaims to have knowledge of a witness w_ifor the statement of the same index. This, in conjunction with the simulatability (zero knowledge) requirement, implies that all participants authenticating with respect to the same statement are indistinguishable. Crucially, any meaningful notion of personal identity is absent; witness-authentication remains agnostic to the true identity of the sender and instead asks: were these messages generated with knowledge of a witness?

$$ \mathrm {P K} _ {i} $$

$$ \varPhi = \langle \phi_ {1}, \dots , \phi_ {\ell} \rangle $$

$$ V_{i} $$

$$ \mathbb{W}_{i} $$

3.1 Model

We fix a relation R and assume a polynomial-size set of potential participants P = {V₁,...,V_ℓ} for some polynomial ℓ = ℓ(λ). Each participant U is associated with some public statement ϕ_Uand has knowledge of a witness w_U. We assume that each witness w_iis sampled according to an arbitrary distribution D_ϕisuch that (ϕ_i, w_i) ∈R. The statement vector is Φ = ⟨ϕ₁,...,ϕ_ℓ⟩ and the distribution over witnesses D_Φis such that a sample w ←D_Φis a vector of witnesses w = ⟨w₁,...,w_ℓ⟩ corresponding to the statements in Φ. The subscript notation is overloaded for ease; it is convenient to associate participants V_i, statements ϕ_iand witnesses w_iwith the same index i when listing or assigning these values, but it is also convenient to index statements ϕ_Uand witnesses w_Uby their associated participant U when discussing a single instance.

$$ \mathcal{P}={V_{1},\ldots,V_{\ell}} $$

$$ \ell=\ell(\lambda) $$

$$ \mathrm{w}_{i} $$

$$ {\sf W{}}U $$

$$ \mathcal{D}{\phi{i}} $$

$$ \Phi = \left\langle \phi_ {1}, \dots , \phi_ {\ell} \right\rangle $$

$$ \left(\phi_{i},\mathsf{w}_{i}\right)\in\mathcal{R} $$

$$ \mathcal{D}_{\phi} $$

$$ W\gets\mathcal{D}_{\phi} $$

$$ \mathsf{w}=\left\langle w_{1},\ldots,w_{\ell}\right\rangle $$

$$ V_{i}, $$

$$ w_{i} $$

$$ \phi_{i} $$

$$ \ {it W W} $$

$$ \phi_{U} $$

Each participant U can participate in polynomially many protocol executions with an arbitrary subset of i potential participants. This is modelled with single use instances denoted Π^U, meanⁱng the ith instance of i participant U. Each instance Π_Uhas the following associated variables, in addition to their statement and witness ϕ_U, w_U:

$$ \ {boldsymbol\Pi}_{U}^{i} $$

$$ \ pi{}_{U}^{i} $$

$$ \phi_{U},\mathsf{W}_{U} $$

iU – state : the current internal state of the instance

$$

• \mathrm {s t a t e} _ {U} ^ {i} $$

^iU – acc : a boolean denoting if the instance has accepted

$$ \mathsf{a c c}_{U}^{i}. $$

^iU – term : a boolean denoting if the instance has terminated

^iU – sid : the concatenation of messages sent and received by the instance thus far

$$ \mathsf{s i d}_{U}^{i}{} $$

^iU – sk : the session key

$$ \ -,,mathsf s s k_{U}^{i} $$

The adversary has control over all communication between the participants in every execution via the following oracles:

i – Send(U,i,M) sends message M to instance Π_Uand returns their reply

$$ -{\mathrm{\sf~S~n n n}}(U,i,M) $$

$$ \ {boldsymbol\Pi}_{U}^{i} $$

j1 j2 jn – Execute(U_i1,j₁,U_i2,j₂*,...,U*_in,jn): outputs a transcript of an execution between instances Π_U,Π_U,...,Π_{U i}1 i_{2 in} iU i – Reveal(U,i): outputs the session key sk generated by Π_U

$$ -\mathrm{}{\sf~E x e c u t e}(U_{i_{1}},j_{1},U_{i_{2}},j_{2},\ldots,U_{i_{n}},j_{n}) $$

$$ \varPi_{U_{i_{1}}}^{j_{1}},\varPi_{U_{i_{2}}}^{j_{2}},\ldots,\varPi_{U_{i_{}}}^{j_{n}} $$

$$ -\ {\sf{R e v e a l}}(U,i) $$

$$ \mathsf{s k}_{U}^{i} $$

$$ \ pi{}_{U}^{i} $$

Prior to the first execution of the key exchange these public parameters are generated with a setup λ algorithm, pp ← SetUp(1*, R*). The SetUp algorithm takes as input the security parameter λ and the relation ⁷ R. WAKE is also equipped with an additional SimSetUp algorithm, towards simulatability, which is discussed further below. The common inputs to all participants is (pp,Φ): the set of public parameters for the key exchange including the relation R, and the public statement vector.

$$ {\mathfrak{p p}}\leftarrow{\mathsf{S e t U p}}(1^{\lambda},\mathcal{R}) $$

$$ \ {mathcal R^{7}} $$

$$ (p p, \Phi) $$

$$ \mathcal{R{} $$

The first message in an execution initiated by some participant U involving participants {U,U_i2,...,U_in} is realized by the adversary querying Send with input (U,i,U ||Uⁱ²||···||Uⁱⁿ). For brevity multiple sequential i i j messages M₁,...,M_ncan be sent to the instance Π_Uw_ith Send(U,i,M₁||···||M_n). Instances Π_Uand Π_V have a record of the same messages being sent throughout the interaction and thus can be said to have iU jV participated in the same interaction if sid ≡ sid according to Definition 8.

$$ {U,U_{i_{2}},\ldots,U_{i_{n}}} $$

$$ (U,i,U||U_{i_{2}}||\cdots||U_{i_{n}}) $$

$$ M_{1},\ldots,M_{n} $$

$$ \ Pi{}_{U}^{i} $$

$$ (U,i,M_{1}||\cdots||M_{n}) $$

$$ \ pi{}_{U}^{i} $$

$$ \ pi{}_{V}^{j} $$

$$ {\mathsf{s i d}}{U}^{i}\equiv{\mathsf{s i d}}{V}^{j} $$

Correctness requires that any instances participating in the same execution of Π with valid witnesses to their associated statements will terminate and accept with equal session keys.

Definition 10(Correctness). A WAKE protocol Π is correct if for all relations R, for all sets of po- tential participants P of size ℓ = ℓ(λ), for all participants U,V ∈ P, for all instances i,j ∈ N such that iU jV iU jV iU jV (ϕ_U, w_U), (ϕ_V, w_V) ∈R, sid ≡ sid and acc = acc = TRUE then sk = sk*.*

$$ \ell=\ell(\lambda) $$

$$ U,V,\in,\mathcal{P} $$

$$ i,j\in\mathbb{N} $$

$$ (\phi_{U},\mathsf{w}{U}),(\phi{V},\mathsf{w}{V})\in\mathcal{R},;\mathsf{s i d}{U}^{i}\equiv\mathsf{s i d}_{V}^{j} $$

$$ {\mathsf{a c c}}{U}^{i}={\mathsf{a c c}}{V}^{j}={\mathsf{T R U E}} $$

$$ {\mathsf{s k}}{U}^{\imath}={\mathsf{s k}}{V}^{\jmath} $$

⁷ + We notice this syntax can easily be extended to the case where the setup is universal [GKM 18].

$$ [\mathrm{G K M^{+}18}] $$

3.2 Security

This subsection discusses the security requirements for WAKE. First we discuss which adversaries should be considered admissible in the confidentiality and authenticity games (see Definition 13). Then we introduce the adaptations of the notions of authenticity and confidentiality to the witness-authenticated setting (see Definitions 14 and 19). Then we discuss the distinction between passively and actively secure protocols (see Remark 2). Finally we introduce the definition of Simulatability (see Definition 16).

Admissible Adversaries: The goal of an adversary in the authenticity experiment (Figure 5) is to force a iU challenge instance to accept without knowledge of a witness: acc = TRUE. But, any adversary can convince i any instance Π^Uto accept by playing as a wire between that instance and the authenticated participants, forwarding messages and responses according to Π without injecting any of her own messages. In summary, i a forwarding A does not adversarially convⁱnce Π^Uto accept. The instance would accept because he is interacting with authenticated participants. A forwarding adversary (Definition 11) forwards all messages between the challenge instance and instances of participants authenticating with respect to the expected 8 statements. This behavior, referred to as ping-pong by [DF17] in the two party case, is generalized to groups and modified to witness-authentication in Definition 11.

$$ {\mathsf{a c c}}_{U}^{i}={\mathsf{T R U E}} $$

$$ \ pi{}_{U}^{i} $$

$$ \ pi{}_{U}^{i} $$

Definition 11(Forwarding Adversary). Let P = {V₁,...,V_ℓ} be a set of potential parties, authenti- cating with respect to (not necessarily distinct) statements Φ = ⟨ϕ₁,...,ϕ^ℓ⟩ in WAKE protocol Π. Let the iU challenge instance be (U,i), with associated session identifier sid = M₁||···||M_ncontaining first message M₁ the set of participants for the session. Then, A is forwarding for (U,i) if either there exists a query to ′ ′ the Execute oracle with input including the instance (U,i) or if for all V ∈ M₁ with V ̸= U there exists an instance (V,j) ∈P× N such that all of the following conditions hold:

$$ \mathcal{P}=\left{V_{1},\ldots,V_{\ell}\right} $$

$$ \varPhi=\langle\phi_{1},\ldots,\phi_{\ell}\rangle $$

$$ {\mathsf{s i d}}{U}^{i}=M{1}|cdotscdots|M_{n} $$

$$ M_{1} $$

$$ (U,i) $$

$$ V^{\prime}\in M_{1} $$

$$ (V,j)\in\mathcal{P}\times\mathbb{N} $$

$$ V^{\prime}\neq U $$

1. ϕ_V= ϕ_V′, and

$$ \phi_{V}=\phi_{V^{\prime}} $$

2.for each query to the send oracle of the form Send(U,i,M) → R outputting response R ̸= NULL from i instance Π^Uthere exists a corresponding query to the send oracle Send(V,j,R) forwarding the response to j instance Π^V, unless the response was empty, and

$$ \ {mathfrak I(U,i,M)},\,\to,R $$

$$ R,\neq,\mathsf{N U L L} $$

$$ \ pi{}_{U}^{i} $$

$$ (V,j,R) $$

$$ \Pi_{V}^{\mathcal{J}} $$

′ ′ ′ 3.for each query to the send oracle of the form Send(V,j,M) → R outputting a response R ̸= NULL from j ′ instance Π^Vthere exists a corresponding query to the send oracle Send(U,i,R) forwarding the response i to instance Π_U, unless the response was empty.

$$ (V,j,M^{\prime})\to R^{\prime} $$

$$ \boldsymbol{\Pi}_{V}^{\mathcal{J}} $$

$$ R^{\prime}\neq\mathsf{N U L L} $$

$$ {\mathsf{S e n d}}(U,i,R^{\prime}) $$

$$ \ pi{}_{U}^{i} $$

′ The set of participants V ∈ M₁ such that the above outlined conditions do not hold are called the impersonated set, denoted IS(U,i).

$$ V^{\prime}\in M_{1} $$

$$ {\mathcal{I S}}(U,i) $$

As usual, the goal of an adversary in the confidentiality experiment (Definition 4) is to distinguish the challenge session key from a random key given access to (1) transcripts of valid executions via the Execute oracle, (2) the ability to reveal keys for eavesdropped transcripts via the Reveal oracle, and (3) access to long term secrets (witnesses) of the participants. Notably, any adversary with the long term secret of a participant can participate in the key exchange on behalf of that participant and then will then be able to trivially distinguish the computed session key. Additionally, an adversary that has revealed the session key for the challenge session⁹ can also trivially distinguish the session key from random. This motivates an additional requirement, namely that the challenge participant must be fresh according to Definition 12.

i The freshness requirement specifies that for challenge Π^Uthe adversary has neither revealed the session key for any instance participating in the execution with (U,i) nor has she injected any messages after learning a participant’s witness.

$$ \Pi_{U}^{i} $$

$$ (U,i) $$

i Definition 12(Freshness). An instance Π^Uis considered to be fresh if for all V ∈P, A has not queried j jV iU Reveal(V,j) for any Π_Vsuch that sid ≡ sid*.*

$$ \ {boldsymbol\Pi}_{U}^{i} $$

$$ V\in{\mathcal{P}} $$

$$ (V,j) $$

$$ {\mathfrak{s i d}}{V}^{j}\equiv{\mathfrak{s i d}}{U}^{i} $$

$$ \Pi_{V}^{\mathcal{I}} $$

An admissible adversary is one that does not trivially violate the properties of authenticity or confidentiality; the only adversaries considered are those that output a fresh challenge (U,i) with respect to which they are not forwarding.

$$ (U,i) $$

⁸ The expected statements are the statements associated to the parties appearing in message 1 of the session identifier. iU For sid = M₁||···||Mn with M₁ = Ui₁,...,Uik the challenge instance would expect to interact with participants authenticating with respect to {ϕi₁,...,ϕik}.

$$ {\mathsf{s i d}}{U}^{i}=M{1}||\cdots||M_{n} $$

$$ M_{1}=U_{i_{1}},\ldots,U_{i_{k}} $$

$$ {\phi_{i_{1}},\ldots,\phi_{i_{k}}} $$

⁹ The challenge session is the session executed by the challenge instance.

Definition 13(Admissible Adversary). Consider participants P = {V₁,..., V_ℓ} executing a WAKE protocol Π. An adversary A is considered admissible if A outputs a fresh challenge (U,i) on which A is not forwarding.

$$ {\mathcal{P}},=,{V_{1},\ldots,,V_{\ell}} $$

Confidentiality: Confidentiality is the requirement that an eavesdropping adversary cannot distinguish the real session key from a random one. In the confidentiality experiment, seen in Figure 4, the adversary is an eavesdropper that cannot inject any messages. The adversary must then output a challenge instance (U,i). If the challenge instance has accepted and generated a key then the adversary receives as input either the real session key or a random key, Confidentiality stipulates that no admissible adversary can determine which key she has received, even given the secret vector of witnesses.

Definition 14(WAKE Confidentiality). The advantage of an adversary A with respect to the WAKE pro- WAKE-confid tocol Π in the confidentiality game seen in Figure 4 is defined as the following quantity: Adv_Π,A(λ, R,Φ, DΦ) = WAKE-confid |2·Pr[ExpΠ,A(λ, R,Φ, D_Φ) = 1] − 1|. The WAKE protocol Π is confidential if, for all λ ∈ N, for all relations R, for all statement vectors Φ, for all distributions over witness sets D_Φand for all admissible non-uniform PPT A, the advantage of A is negligible.

$$ \pi_ {\varPi , \mathcal {A}} ^ {\mathrm {W A K E - c o n t i d}} \left(\lambda , \mathcal {R}, \varPhi , \mathcal {D} _ {\varPhi}\right) = $$

$$ | 2 \cdot \Pr [ \mathbf {E x p} _ {\Pi , \mathcal {A}} ^ {\mathrm {W A K E - c o n f i d}} (\lambda , \mathcal {R}, \Phi , \mathcal {D} _ {\Phi}) = 1 ] - 1 | $$

$$ \lambda\in\mathbb{N} $$

$$ \mathcal{D}_{\phi} $$

| Exp$^{\text{WAKE-confid}}{\Pi,A}(\lambda,\mathcal{R},\Phi,\mathcal{D}{\Phi})$ b $ \leftarrow $ {0,1} pp $ \leftarrow $ SetUp(1λ，R) w $ \leftarrow $ Dφ P $ \leftarrow $ {Vi[φi，wi]}{i=1}^{|w|} (U,i) $ \leftarrow $ AExecute()Reveal()($\Phi$,w) if acc$^{i}{U}$ = FALSE：output b k1 $ \leftarrow $ sk$^{i}_{U}$, k0 $ \leftarrow $ $ K$ b' $ \leftarrow $ AExecute()Reveal()(kb) if b=b'：output 1

$$ \mathbf{E x p}{\varPi,\mathcal{A}}^{\mathsf{W A K E-c o n f i d}}(\lambda,\mathcal{R},\varPhi,\mathcal{D}{\varPhi}) $$

$$ \ p{p}\leftarrow\mathsf{S e t U p}(1^{\lambda},\mathcal{R}) $$

$$ \boldsymbol{w{} $$

$$ \mathcal{P}\leftarrow\left{V_{i}[\phi_{i},\mathsf{w}{i}]\right}{i=1}^{|\mathsf{w}|} $$

$$ (U,i)\leftarrow\mathcal{A}^{\sf{E x e c u t e(),R,v e v e l l()}}(\varPhi,\mathsf{w}) $$

$$ \mathrm{i f};\mathsf{a c c}_{U}^{i}=\mathsf{F A L S E}:\mathrm{o u t p u t};b $$

$$ \mathsf{k}{1}\xleftarrow{}\mathsf{s k}{U}^{i},\mathsf{k}_{0}\xleftarrow{}\mathcal{K} $$

$$ b^{\prime}\leftarrow\mathcal{A}^{\sf E{E c c u t e(),R e v e a l()}}(\mathsf{k}_{b}) $$

WAKE-confid Fig. 4: Exp_Π,A: Experiment for WAKE confidentiality.

In the confidentiality experiment the adversary is granted access to Execute, but not Send. The adversary is also provided the complete vector of witnesses at the start of the experiment. This models the fact that an eavesdropping adversary with access to valid witnesses should not be able to distinguish the key from random. The Send oracle can be simulated by the adversary with knowledge of the witnesses.

Remark 1(Forward Secrecy). We observe that our model of confidentiality guarantees forward secrecy, i.e. that a session key remains indistinguishable from random even if the long term secrets of the participants are compromised. This is modelled by providing A with the entire vector of witnesses w at the beginning of the confidentiality experiment. We also observe that this is a somewhat stronger notion of forward secrecy than the one modelled through a corruption oracle in [KY03].

Authenticity: Authenticity is the requirement that an unauthenticated participant cannot convince another participant to accept and consequently generate a session key; if an instance accepts in the authenticity experiment then either the adversary was forwarding on that instance or the adversary knows some witness. Knowledge of a witness is modeled by the existence of an extractor that can output a witness from the view of the adversary. In the authenticity experiment, seen in Figure 5, each participant U receives a witness and the adversary facilitates communication between the authenticated participants via the Send and Reveal oracles. The adversary ultimately outputs a challenge: (U,i,V). For any admissible adversary outputting a challenge i consisting of an accepting instance Π^Uthere exists an extractor which can output a witness to the statement ϕ_V. It is important that V must appear in the impersonation set of the challenge instance, meaning that the i adversary was not merely forwarding messages between Π_Uand any participant authenticating with respect to ϕ_V. This is formalized in Definition 15.

$$ \ pi{}_{U}^{i} $$

$$ \ pi{}_{U}^{i} $$

**Definition 15(**WAKE Authenticity). The advantage of an adversary A with respect to WAKE protocol Π in the authentication game seen in Figure 5 is defined as

$$ \bf{A d v}{\varPi,\mathcal{A},\mathcal{E}{\varLambda}}^{\sf{N A M E\ a a r t}}(\lambda,\mathcal{R},\varPhi,\mathcal{D}{\varPhi})=\sf{P r}[\bf{E x p}{\varPi,\mathcal{A},\mathcal{E}{\varLambda}}^{\sf{N A M E\ a r t h}}(\lambda,\mathcal{R},\varPhi,\mathcal{D}{\varPhi})=1] $$

A WAKE protocol Π is witness-authenticated if for all admissible non-uniform PPT A there exists a PPT extractor E_A, for all λ ∈ N*, for all relations R, for all statement vectors Φ, and for all witness distributions* D_Φ, the advantage of A is negligible.

$$ \mathcal{E}_{\mathcal{A}}. $$

$$ \mathcal{D}_{\phi} $$

$$ \mathbf {E x p} _ {\Pi , \mathcal {A}} ^ {\mathrm {W A K E - a u t h}} (\lambda , \mathcal {R}, \varPhi , \mathcal {D} _ {\varPhi}) $$

$$ \ p{p}\leftarrow\mathsf{S e t U p}(1^{\lambda},\mathcal{R}) $$

$$ w\gets\mathcal{D}_{\emptyset} $$

$$ \mathcal{P}\leftarrow{V_{i}[\phi_{i},\mathsf{w}{i}]}{i=1}^{|\mathsf{w}|} $$

$$ (U,i,V)\leftarrow\mathcal{A}^{\sf e n d(),\sf R e v e a l()}(\varPhi) $$

$$ \operatorname{a s s e r t};\big(V\in\mathcal{I S}(U,i)\big) $$

$$ b_{\mathsf{a c c}}\leftarrow\mathsf{a c c}_{U}^{i} $$

$$ \mathsf{w}^{\prime}\leftarrow\mathcal{E_{A}}(\mathsf{v i e w_{A}}) $$

$$ b _ {\mathrm {e x t}} \leftarrow \left(\phi_ {V}, \mathrm {w} ^ {\prime}\right) \in \mathcal {R} $$

$$ \operatorname{o\ t u t p u t}\ (b_{\mathsf{a c c}}\wedge\bar{b}_{\mathsf{e x t}}) $$

WAKE-auth Fig. 5: Exp_Π,A,E: Experiment for WAKE authenticity. A

In the authentication experiment A is not equipped with an Execute oracle; the Execute oracle is redundant as it can be simulated with the Send oracle.

Active & Passive Security: The distinction between passively and actively secure group key agreement, as seen in [KY03], is centered around the Send oracle; a protocol is considered actively secure if it is secure against an adversary that has access to Send, otherwise the protocol is considered passively secure. This distinction is not applicable to WAKE.

Consider a variant of the WAKE confidentiality experiment in which the adversary is also granted access to the Send oracle. The inclusion of Send does not change the experiment; A has access to w, the vector of witnesses, and can therefore simulate Send even if she is not granted access to it explicitly. Additionally, any queries to the Send oracle will not affect the challenge session as the adversary is necessarily eavesdropping on the challenge. Alternatively, consider a variant of the WAKE authenticity experiment in which the adversary is not allowed any Send queries but instead can query Execute. The removal of Send renders every adversary inadmissible; an adversary exclusively using the Execute oracle has not injected any of her own messages and is forwarding. Therefore, in the absence of a distinction between passive and active variants of the confidentiality and authenticity experiments, we define passive and active security for WAKE as in Remark 2. Passively secure protocols are those that satisfy confidentiality while actively secure protocols additionally satisfy authenticity and simulatability.

Remark 2(Active and Passive Security for WAKE*).* We say a WAKE protocol achieves passive security if it satisfies confidentiality (Definition 14); it achieves active security if it satisfies confidentiality, authenticity (Definition 15).

Passive security for WAKE (as defined here) is equivalent to passive security for group key exchange (as defined in [KY03]). This can be seen by comparing the relevant experiments; a passively secure group key exchange generates session keys that are indistinguishable from random by an adversary that controls all communication in the network and has access to Execute*,Reveal,*Corrupt and outputs a fresh challenge. This is equivalent to the WAKE-confid experiment, except instead of providing a Corrupt oracle the adversary is given all of the secrets at the start of the experiment.

In fact, a passively secure WAKE does not have to require that the participants make use of their witnesses at all. Therefore, the following simulatability requirement is only meaningful for actively-secure WAKE.

Simulatability: Given a correct and confidential group key exchange protocol Π between participants P = {P₁,...,P_ℓ}, one can obtain witness-authentication for associated statements Φ and witnesses W = {w^V1,...,w^Vℓ} by following Π with the following modifications: (1) when participant U should send a message M according to Π he concatenates his witness to the message, instead sending M ||w_U, (2) when participant ′ ′ U receives a message M = M ||w_U′ from participant U he verifies that (ϕ_U′, w_U′) ∈R and aborts if this verification fails. Such a solution does not align with our intuition. This, along with the malleability attack seen in Section 1, motivates a third requirement: simulatability. Simulatability is the requirement that the adversary cannot learn anything about the witness from the messages sent by that participant. This is implied by the existence of a simulator which, without access to the witness, can generate messages indistinguishable from those of a real participant.

$$ \mathcal{P}={P_{1},\ldots,P_{\ell}} $$

$$ \mathcal{W}= $$

$$ \left{\mathsf{w}{V{1}},\ldots,\mathsf{w}{V{\ell}}\right} $$

$$ M\vert\vert\mathsf{w}_{U},\thinspace(2) $$

$$ \ =M^{\prime}||\mathsf{w}_{U^{\prime}} $$

$$ U^{\prime} $$

$$ \ \ (\phi_{U^{\prime}},\mathsf{w}_{U^{\prime}})\in\mathcal{R} $$

Simulatability requires the existence of a second setup algorithm, SimSetUp, which outputs public parameters indistinguishable from those output by the usual setup algorithm along with a trapdoor τ. With the trapdoor any participant can be simulated without access to their associated witness. In the simulatability experiment the adversary is given access to a SetKey oracle which takes as input (ϕ, w) and generates a new participant associated with the statement-witness pair. The adversary then interacts with either the ∗ real participants or the simulated versions using Send_b. The real participants behave honestly and interact using the witness provided to them by some query to SetKeys, whereas the simulated version only has access to the public statements and the trapdoor. Any oracle query must have a corresponding SetKeys query for ′ each participant appearing in the input. The adversary outputs her guess b, indicating if she believes she is interacting with real participants or simulators.

$$ (\phi,) $$

Definition 16(WAKE Simulatability). A WAKE protocol Π is simulatable if there exist efficient algo- rithms (SimSetUp,Sim) (the latter stateful) such that for all λ ∈ N, relations R and for all non-uniform PPT A, the advantage of A in the simulatability game seen in Figure 6 is negligible, where the latter is defined as WAKE-sim WAKE-_sim Adv_Π,A(λ, R) = 2·Pr[Exp_Π,A(λ, R) = 1] − 1.

$$ \lambda\in\mathbb{N} $$

$$ \bf{A d v}{H,A}^{\sf{V A N E-s i m}}(\lambda,R)^{\cdot}=2\cdot\mathrm{P{}}[\bf{E x p}{H,A}^{\sf{V A N E-s i m}}(\lambda,\hat{R})=1]-1 $$

4 Unilateral WAKE

Unilateral Witness-Authenticated Key Exchange (U-WAKE) is a specialization of the above group WAKE to the two party, unilaterally authenticated, case. U-WAKE can also be seen as an adaptation of Unilaterally Authenticated Key Exchange (UAKE) [DF17], in which an unauthenticated participant establishes a key with an authenticated participant, to the witness-authenticated case. In U-WAKE, authentication is done with respect to a witness for some statement associated to the authenticated participant, called the Responder (Res). All adaptations of the WAKE model (appearing in Section 3) to the unilaterally authenticated two participant setting are listed:

10 – The set of potential participants is denoted P = {Init,Res₁,..., Res_ℓ(λ)−1}

$$ \mathcal{P}={\mathsf{|n i t,R e s_{1},\ldots,R e s_{\ell(\lambda)-1}\ }^{10}} $$

– ϕ_Initis a dummy statement (one that is in the language and is easy to decide)

¹⁰ Notice this is just a change of notation to make explicit which parties are authenticated or not, namely the responders and the initiatior.

| Exp$^{\text{WAKE-sim}}{\Pi,\mathcal{A}}(\lambda,\mathcal{R})$ b $ \leftarrow $ {0,1}; $\mathcal{P} \leftarrow \emptyset $ pp1 $ \leftarrow $ SetUp(1$^\lambda$,R);(pp0，τ) $ \leftarrow $ SimSetUp(1$^\lambda$,R) b' $ \leftarrow $ A$ ^{Send}{b}^{+}$,Reveal,SetKeys if b=b'：return1

$$ \operatorname{E x p}_{\varPi,\mathcal{A}}^{\mathsf{W A K E-s i m}}(\lambda,\mathcal{R}) $$

$$ b \leftarrow \stackrel {$} {\leftarrow} {0, 1 }; \mathcal {P} \leftarrow \emptyset ; $$

$$ p p _ {1} \leftarrow \operatorname {S e t U p} \left(1 ^ {\lambda}, \mathcal {R}\right); \left(p p _ {0}, \tau\right) \leftarrow \operatorname {S i m S e t U p} \left(1 ^ {\lambda}, \mathcal {R}\right) $$

$$ b{'}\gets\mathcal{A}^{\mathsf{s e n d}_{b}^{*}} $$

$$ (U,\phi_{U},w_{U}) $$

$$ (\phi_{U},w_{U})\in\mathcal{R} $$

$$ b=b^{\prime} $$

$$ U\not\in{\mathcal{P}} $$

$$ {\sf{S e n d}}_{0}^{*}(U,i,\tilde{m}) $$

$$ { } _ { 1 } ^ { * } ( U , i , \tilde { m } ) $$

$$ \mathsf{S i m}(U,i,\tilde{m}) $$

WAKE-sim Fig. 6: Exp_Π,A: Experiment for WAKE simulatability. Simulator Sim is stateful, has access to statements ϕ_Uand other parameters (e.g., trapdoor τ), but not to the witnesses w_U.

$$ \mathbf {E x p} _ {\varPi , \mathcal {A}} ^ {\mathrm {W A K E - s i m}} $$

$$ w_{U} $$

– Challenge instances: the authenticity challenge must be of the form (Init*,i,* Res_j) and the confidentiality challenge must be of the form (Init*,i*)

$$ (\mathsf{I n i t},i,\mathsf{R e s}_{j}) $$

Importantly, as Init is unauthenticated the associated statement ϕ_Initis such that a witness W can be 11 computed in polynomial time. Additionally, in a two party interaction the challenge must be an instance of the Init. Therefore, any admissible adversary for U-WAKE is an admissible adversary for WAKE that outputs such a challenge. The curious reader is referred to Appendix A for explicit formulations of the U-WAKE Experiments.

$$ \phi_{\mathrm{l n i t}} $$

4.1 Construction from KEM and SOK

Given a signature of knowledge and a key encapsulation mechanism one can construct U-WAKE. As a concrete example to keep in mind throughout this section, we recommend considering Diffie-Hellman (DHKE): Init x first samples randomness x and sends as their first message the associated public key h_I= g and Res does y the same, computing h_R= g, along with a signature of knowledge σ on m = h_I||h_R. The response is then x h_R,σ. Contingent upon signature validation, the Initiator then computes sk = (h_R) and the Responder y computes sk = (h_I) as the session key.

$$ h_{I}=g^{x} $$

$$ h_{R}=g^{y} $$

$$ h_{R},\sigma $$

$$ m=h_{I}||h_{R} $$

$$ =(h_{R})^{x} $$

$$ \mathsf{k}=(h_{I})^{y} $$

For U-WAKE, the public parameters output by SetUp are ppU-WAKE= {λ, R, ppSOK*}*, the security parameter, the relation and the public parameters for the signature of knowledge. The public parameters output by SimSetUp also include the trapdoor for the signature τ_SOK. In Figure 7 we present the construction of U-WAKE from KEM and SOK.

$$ p p_{\mathsf{U-W A K E}}=\left{\lambda,\mathcal{R},p p_{\mathsf{S0K}}\right} $$

Theorem 1(Π is secure.). Let KEM be a correct and CPA-secure key encapsulation mechanism. Let SOK be a perfectly correct and simulatable, simulation-extractable signature of knowledge. Then, the protocol Π, as seen in Figure 7, is an actively secure and simulatable U-WAKE.

¹¹ This modification can allow the group-WAKE to generalize to a setting where an arbitrary subset of the potential parties are unauthenticated in such a way.

Fig. 7: U-WAKE from KEM and SOK

A full proof of this theorem appears in Appendix B.

5 A Compiler From Passive to Active Security

In this section we describe a compiler that transforms any passively secure key-exchange into a witnessauthenticated, actively secure protocol. Our compiler revisits the one presented in [KY03], adapting it to the witness-authenticated setting.

5.1 The Compiler Construction

The compiler takes as input a passively secure protocol Π and outputs an actively secure, simulatable, ∗ protocol Π. This transformation is at the expense of an additional round in which each participant samples and distributes a random nonce. Following this round, each participant proceeds as they would in Π with a few additional steps. To each message m they should send according to Π, they add a signature of knowledge on that message concatenated with the nonces from Round 0 and upon receipt of any message the participant must first verify the signature. The explicit construction is provided in fig. 8.

$$ \varPi^ {*} $$

5.2 Security

∗ Theorem 2. If Σ is a passively-secure protocol (remark 2) then Σ (fig. 8) is a fully secure and simulatable witness-authenticated key exchange protocol (section 3.2 and remark 2) .

$$ \Sigma^{*}(f!g8) $$

Lemma 1. The protocol in fig. 8 satisfies confidentiality (definition 14).

$$ \textstyle g. $$

$$ I/) $$

Proof. We reduce to the confidentiality of the underlying passive scheme as follows. For a confidentiality ∗ adversary A_actagainst compiled protocol Σ, we construct a confidentiality adversary A_pasagainst the original passively secure protocol. See fig. 9.

$$ \mathcal{A}_{\mathrm{a c t}} $$

$$ \Sigma^{*} $$

$$ \mathcal{A}_{\mathrm{p a s}} $$

We claim that the advantage of A_pasin the confidentiality game for protocol Σ is negligibly close to that ∗ of A_actin the confidentiality game for protocol Σ. We now define three hybrids:

$$ \ {mathcal A A}_{\mathrm{p a s}} $$

$$ \mathcal{A}_{\mathrm{a c t}} $$

$$ \Sigma^{*} $$

$$ -,\mathcal{H}_{\mathrm{a c t}}. $$

∗ – H_act: this is the advantage of A_actin the confidentiality game for protocol Σ

$$ \mathcal{A}_{\mathrm{a c t}} $$

$$ \Sigma^{*} $$

∗ – H_act-zk. this is the advantage of A_actin a modified confidentiality game for protocol Σ, where the challenger acts as in H_act, except that it uses a simulator for signatures of knowledge. We claim that H_act≈H_act-zk: this follows from simulatability of signatures of knowledge. If the two advantages were not negligibly close than we can easily build a distinguisher for real/simulated signatures of knowledge.

$$ -\mathrm{~\ }mathcal H{}_{\mathrm{a c t-z k}}} $$

$$ \mathcal{A}_{\mathrm{a c t}} $$

$$ \Sigma^{*} $$

$$ \mathcal{H}_{\mathrm{a c t}} $$

$$ \mathcal{H}{\mathrm{a c t}}\approx\mathcal{H}{\mathrm{a c t-z k}} $$

–Setup: We run the setup for Σ and the setup for the signature of knowledge scheme. λ –Round 0: each user Uⁱsamples a random nonce rⁱ←$ {0,1} and sends message (Uⁱ||0||rⁱ) to all j the other parties. After receiving the related message from all the other parties, each instance Π_Usets _jU jU and stores nonces := U₁||r₁||... ||U_m||r_mand S := {U₁,...,U_m} (the set of participants) as local information. –Following rounds: i • Whenever instance ΠUshould send (U||j||m) by Σ to all other parties: () ∗ jU 1.it produces m = U ||j||m||nonces ∗ 2.it signs it as σ ← SOK.SSign(pp,ϕ_U,w_U,m) ^∗ 3.it sends (m ||σ) to all other parties i • Whenever instance Π^Ureceives (V ||j||m||nonces||σ): iU 1.it checks V ∈ S {U}; it aborts otherwise 2.it checks signature σ on *V ||j||m||*nonces against the statement of party V and that nonces = iU ¹² nonces; it aborts otherwise 3.it checks the sequence number j is the expected one; it aborts otherwise 4.it continues as in protocol Σ Above U = {U₁,...,Um} denotes the set of parties willing to establish a common key.

$$ (U_{i}||0||r_{i}) $$

$$ r_{i}\gets $$

$$ U_{i} $$

$$ \mathbf{\nabla}{U}^{j}:=U{1}||r_{1}||\ldots||U_{m}||r_{m} $$

$$ \dot{\Pi{}}_{U}^{j} $$

$$ \mathsf{S}{U}^{j}:=\left{U{1},\ldots,U_{m}\right} $$

$$ \ pi{}_{U}^{i} $$

$$ (U||j||m) $$

$$ m^{*}=\left(U||j||m||\mathsf{n o n c e s}_{U}^{j}\right) $$

$$ \sigma\leftarrow\ S O K.S S i g n(\mathsf{p p},\phi_{U},w_{U},m^{*}) $$

$$ (m^{*}||\sigma) $$

$$ \ {boldsymbol\Pi}_{I J}^{i} $$

$$ \ V||j||m|| $$

$$ V\in\mathsf{S}_{U}^{i}\setminus\tilde{{U}}\cdot $$

$$ V||j||m| $$

$$ \mathcal{U}={U_{1},\dots,U_{m}} $$

∗ Fig. 8: Compiler from protocol Σ with passive security to one with active security (Σ).

$$ \left(\Sigma^{*}\right) $$

$$ \mathcal{A}{\mathrm{p a s}}(\mathsf{p p}{\mathrm{p a s}}) $$

Apas(pppas) λ (pp_sok,τ) ← SSimSetup(1*,R*) Run Aact(ppsok*||pppas) and emulate each oracle query as follows Execute(·) : − Invoke Execute for Σ obtaining transcript(s) T ∗ − Extend T emulating rest of the protocol Σ as in fig. 8 : ∗ sample nonces as appropriately ∗ Compute signatures invoking SoK simulator − Return T “compiled” with nonces and simulated signatures Reveal(·*) : − Respond using its own Reveal oracle Let (U,i) be the output of Aact at the end of interaction Send (U,i) to the challenger receiving back a challenge key k Run Aact(k)(emulating oracles as before) till it outputs bit b Output b

$$ \left(\mathrm {p p} _ {\mathrm {s o k}}, \tau\right) \leftarrow \mathrm {S S i m S e t u p} \left(1 ^ {\lambda}, R\right) $$

$$ \mathcal{A}{\operatorname{a c t}}(\mathsf{p p}{\operatorname{s o k}}||\mathsf{p p}_{\operatorname{p a s}}) $$

$$ \Sigma^{*} $$

$$ \tau^{circ} $$

$$ (U,i) $$

$$ \mathcal{A}_{\mathrm{a c t}} $$

$$ (U,i) $$

$$ \mathcal{A}_{\mathrm{a c t}}(\mathsf{k}) $$

Fig. 9: Reduction for confidentiality in compiled construction.

$$ \mathcal{H}_{\mathrm{p a s}} $$

– H_pas: this is the advantage of A_pasin the confidentiality game for protocol Σ. We claim that H_act-zk≡H_pas: in fact they are exactly the same distribution except with different syntaxes (the former produces simulated signatures in the challenge while the latter in the adversary A_pas).

$$ \mathcal{H}{\mathrm{a c t-z k}}\equiv\mathcal{H}{\mathrm{p a s}} $$

$$ \mathcal{A}_{\mathrm{p a s}} $$

$$ \mathcal{A}_{\mathrm{p a s}}) $$

This concludes the proof.

Lemma 2. The protocol in fig. 8 satisfies authentication (definition 15)

∗ ∗13 Proof. In order to argue authentication security, given an adversary A, we construct an extractor E such ^∗ that: either E can extract a witness with reasonable probability (this probability should in particular be a ∗ ∗ noticeable fraction of the advantage of A), or A ’s advantage was too low to be of interest to begin with. ∗ To build this extractor E we rely on the simulation-soundness property of signatures of knowledge. The latter states that, given an adversary forging a valid signature (with access to a simulator oracle), there is an extractor E_SoKfor it that is able to produce a valid witness. We then first define adversary A_SoKfor the ∗ simulation-security experiment: it internally runs A and responds to each of its Send queries by emulating the behavior of the honest parties. Adversary A_SoKmay not know the witnesses of the honest parties, but ∗ can still emulate each of their signatures by using its simulation oracle. At the end of this interaction A will declare an instance challenge (U,i) where it “impersonated” some of the honest parties and that resulted ∗ in an acceptance. Adversary A_SoKwill then retrieve a forged message (m ||σ) (any message with sequence i number greater or equal than 1 will have this structure) in the transcript in Π^U. It wⁱll then return the ∗ ∗ challenge triple (x_V,σ,m) where party V is the party having message m claims as a sender. We can claim that either the returned triple is a valid challenge for the simulation-extractability game (with non-negligible ∗ probability), or A is not admissible.

$$ \mathcal{E}^{*13} $$

$$ \mathcal{A}^{*} $$

$$ \mathcal{E}^{*} $$

$$ \ ^{A^{*}},) $$

$$ \ {\mathcal A}^{*,3} $$

$$ \mathcal{E}^{*} $$

$$ \mathcal{A}_{\mathrm{S o K}} $$

$$ \mathcal{A}^{*} $$

$$ \mathcal{E}_{\mathrm{S o K}} $$

$$ \mathcal{A}_{\mathrm{S o K}} $$

$$ \mathcal{A}^{*} $$

$$ (U,i) $$

$$ \mathcal{A}_{\mathrm{S o K}} $$

$$ (m^{*}||\sigma) $$

$$ (x_{V},\sigma,m^{*}) $$

$$ V $$

$$ m^{*} $$

∗ i Recall that, for A to be admissible, it must be “forging” one of the messages in the instance Π^U. If ⁱt forges a message¹⁴ at round 0, then it’s using a nonce that is not the output of any of the honest parties. Say it’s nonce r_j. The adversary would not be able to query that party U_jusing that nonce since with overwhelming probability it would be rejected if appended to any message (since U_jdid not produce it). ∗ Therefore, A would be forced to forge the following messages too to stay admissible and thus we can reduce to the following case directly.

$$ \mathcal{A}^{*} $$

$$ \mathcal{A}^{*} $$

$$ \ Pi{}_{U}^{i} $$

$$ 0{,} $$

$$ U_{j} $$

$$ r_{j} $$

$$ U_{j} $$

$$ \mathcal{A}^{*} $$

∗ If adversary A is forging a message at a round j ≥ 1 on behalf of some party V, then it must also ∗ ∗ be producing a signature for it (recall that all messages at this stage are of the form m ||σ where m = jU (*V ||j||m||*nonces)). By construction this will be a valid challenge for the simulation-extraction game of SoK ∗ (in the event that the interaction produced by A is admissible). Reducing to the security of signatures of knowledge concludes the proof.

$$ \mathcal{A}^{*} $$

$$ V, $$

$$ j\geq1 $$

$$ m^{*}||\sigma $$

$$ m^{*}= $$

$$ (V||j||m||\mathsf{n o n c e s}{U}^{j}){,} $$

$$ \mathcal{A}^{*} $$

∗ ∗ We describe the adversary A_SoKand extractor E in fig. 10. In the description of E, we denote by E_SoK the extractor for A_SoKfrom the simulation-extractability of signatures of knowledge.

$$ \mathcal{A}_{\mathrm{S o K}} $$

$$ \mathcal{E}^{*} $$

$$ \mathcal{E}_{\mathrm{S o K}} $$

$$ \mathcal{E}^{*} $$

$$ \ {\mathcal{A}}_{\mathrm{S o K}} $$

Lemma 3. The protocol in fig. 8 satisfies simulatability (definition 16)

$$ \ g. $$

Proof. We simulate relying on the simulation property of signatures of knowledge. We define algorithm SimSetUp as the algorithm that runs SSimSetUp and returns its output (see definition 5). We define the ∗ simulator in fig. 11. Given A for the simulatability game of the key agreement, we build an adversary A ∗ (fig. 12) for the zero-knowledge property of signatures of knowledge. This adversary internally uses A and has access to an oracle O that can be either a simulator or the honest signing algorithm. The advantage ∗ of A is the same as that of A. Observing that the former must be negligible by simulatability of the SoK concludes the proof.

$$ \mathcal{A}^{*} $$

$$ \mathcal{A}^{*} $$

$$ \mathcal{A}^{*} $$

6 Achieving Three-Round WAKE for Groups

Here we show how we can instantiate a passive secure scheme (see remark 2) in our compiler in section 5 to obtain a three-round WAKE for groups (we discuss instantiations for signatures of knowledge in section 8) Presented in Figure 13 is Π_GKE, a passively secure protocol for group key exchange. This protocol was constructed by Burmester and Desmedt [BD95], and then was adapted and proven secure under the Decisional Diffie-Hellman assumption by Katz and Yung [KY03]. Running the compiler seen in Figure 8 on Π_gkeyields a three round, actively secure and simulatable WAKE protocol. This is formally stated in Theorem 1.

$$ \mathit{\Pi}_{\mathsf G K E} $$

First we review the Decisional Diffie-Hellman Assumption. For G a cyclic group of order q ∈ P with generator g, the Decisional Diffie-Hellman (DDH) Problem is to distinguish between Diffie-Hellman tuples x y xy x y z ∗ ∗ (g,g,g) and random tuples of the form (g,g,g) for x,y ∈ Z_q, z ∈ Z_q{xy}. Consider an infinite

$$ \mathit{\Pi}_{\mathrm{g k e}} $$

$$ g, $$

$$ q,\in,\mathbb{P} $$

$$ \left(g ^ {x}, g ^ {y}, g ^ {z}\right) $$

$$ x,y\in\mathbb{Z}{q}^{*},,z\in\mathbb{Z}{q}^{*}\setminus{x y} $$

$$ (g^{x},g^{y},g^{x y}) $$

¹³ We can show that we can build such an extractor for each of the parties in the impersonation set.

¹⁴ In this discussion we consider only messages that look valid to the receiver, since otherwise the latter would abort.

$$ \mathcal{A}^{*} $$

S(·) ASoK(ppSoK) ^∗ Run A and emulate each oracle query as follows Send(·) : − honestly run Send for all steps in fig. 8 except signatures − Compute signatures invoking simulator oracle S(·) Reveal(·) : − Respond honestly using the internal state from the Send queries ∗ Let (U,i,V) be the output of A at the end of interaction i For transcript of instance Π_U: ∗ ∗ − Find message (m ||σ) where m is of the form (V ||...) in IS(U,i) ∗ (this corresponds to a message claimed by party V but forged by A) − If no such message exists, abort ∗ return (ϕV,m,σ) ^∗ ∗ E (view) ^∗ Compute viewSoKfrom view*.*This includes: − the randomness used by ASoK − the query responses from Sim w ←ESoK(viewSoK) return w

$$ \mathcal{A}^{*} $$

$$ \ {boldsymbol\Pi}_{U}^{i} $$

Fig. 10: Adversary for the simulation-extractability of signature of knowledge (fig. 3) and extractor for the authenticy game (definition 15). The impersonating set IS is defined in definition 11.

Sim(U,i, m˜) Respond like the honest Send (definition 15) would for construction in fig. 8 except that signatures are produced as follows: ∗ σ ← SSimSign(τSoK*,ϕU,m*) ^∗ where U is the party claiming to send message m (see also bullet 2, case send, in fig. 8)

$$ m^{*} $$

Fig. 11: Simulator for construction in fig. 8

sequence of groups G = {G_λ}_λ≥1indexed by the security parameter λ and define the advantage of an adversary A against DDH in G_λas follows:

$$ \mathcal{G},=,{\mathbb{G}{\lambda}}{\lambda\geq1} $$

$$ \mathbb{G}_{\lambda} $$

$$ \mathsf{A d v}{\mathbb{G}{3},\mathcal{A}}^{\mathsf{O O t}}(\lambda)\ :=\ \big|\mathsf{P r}[\mathcal{A}(g^{x},g^{y},g^{x})\ =\ 1|x,y\ \leftarrow\ \mathbb{Z}{q}^{*}]\ {-}\ \mathsf{P r}[\mathcal{A}(g^{x},g^{y},g^{z})\ =\ 1|x,y,z\ \leftarrow\ \mathbb{Z}{q}^{*}\ \backslash\ {x y}]\big| $$

DDH The DDH assumption states that for all PPT A, the advantage Adv^G_,A(λ) is negligible. The variant of λ DDH described above excludes the possibility that z = xy for simplicity.

$$ \bf{A d v}{G_{\lambda},A}^{D\bf{}}(\lambda) $$

n The participant set is denoted P = {Uⁱ}_i⁼¹with participants indexed mod n, such that Uⁿ= U₀ and U_n+1= U₁. The inputs G*,g* are generated beforehand but can also be generated by a single player at the expense of an additional round. The communication style is referred to as broadcasting but it is important to note that a broadcast channel is not assumed in the construction; participants send all messages via point-to-point links which is referred to as broadcasting.

$$ U_{n+1}=U_{1} $$

$$ \mathcal{P}={U_{i}}_{i=1}^{n} $$

$$ U_{n}=U_{0} $$

x1 x2 +x2 x3 +···+xn x1 The session key generated by the protocol in Fig. 13 is sk = g aⁿd is common to all participants. Π_GKEachieves passive security for group key exchanges; the protocol is secure against an eavesdropping adversary in a RoR experiment. Passive security, along with forward security, is proven in [KY03].

$$ \ {sf s s k},=,g^{x_{1}x_{2}+x_{2}x_{3}+\cdots+x_{n}x_{1}} $$

O(·) A (ppSoK) ^∗ Run A emulating its oracles (and keeping appropriate state): − all oracles but Send are run as for the honest case − a query to Send is run as the honest Send for construction in fig. 8 except that signatures are produced invoking oracle O ∗ Return the same bit as A at the end of interaction

$$ \mathcal{A}^{\ {(\cdot)}}({\mathfrak{p p}_{\mathrm{S o K}}}) $$

$$ \mathcal{A}^{*} $$

$$ \mathcal{A}^{*} $$

Fig. 12: Adversary for reduction to zero-knowledge of SoK

$$ \mathcal{P}=\left{U_{1},\ldots,U_{n}\right} $$

$$ U_{i} $$

$$ x_{i}\xleftarrow{\S}\mathbb{Z}_{q} $$

$$ z_{i}=g^{x_{i}} $$

$$ U_{i} $$

$$ X_{i}=\left(z_{i+1}\middle/z_{i-1}\right)^{x_{i}} $$

$$ U_{i} $$

$$ s k_{i}=(z_{i-1})^{n x_{i}}\cdot X_{i}^{n-1}\cdot X_{i+1}^{n-2}\cdots X_{i+n-2} $$

Fig. 13: A passively secure group key exchange protocol [KY03]

Theorem 3(Passive Security of Π_GKE). The group key exchange protocol Π_GKEseen in Figure 13 is passively secure, as defined in Remark 2, under the DDH assumption.

$$ \mathit{\Pi}_{\mathsf G K E}) $$

$$ \mathit{\Pi}_{\mathsf G K E} $$

For concreteness, let Σ_SOKbe the signature of knowledge detailed in [GM17]. We apply the compiler detailed in Section 5 to Π_GKE, using Σ_SOKas the signature of knowledge, to get a three-round actively secure WAKE protocol.

$$ \ \mathit Pi\ _{\mathsf{G K E}} $$

Corollary 1(Three Round WAKE). Π_WAKE, the protocol resulting from applying the compiler (Fig- ure 8) on Π_GKE(Figure 13) and Σ_SOK, yields a three round actively secure WAKE*.*

$$ \Sigma_{\mathsf{S O N}} $$

7 Offline/Online Computation

The most expensive part of our protocol is the computation of the Signature of Knowledge, which is implemented using a Non-Interactive Proof of Knowledge of the witness. If implemented with a SNARK, this proof can be constructed with small bandwidth and verification time. It is well known that the bottleneck cost is the time it takes for the Prover to compute such proof, something which is confirmed by our evaluation experiments described in Section 8. We note that we can modify the protocol so that the cost of computing the SNARK can be moved to an offline phase, before the participant is contacted for a WAKE.

The intuition is as follows: during the offline phase the witness holder (Responder) generates (sk*,vk) a key pair for a signature scheme where sk is the secret signing key and vk is the public verification key. Then the Prover uses an SOK SNARK to sign vk. Let σ₁ the resulting signature. The Prover stores (sk,vk),σ₁*. During the online phase when the Responder receives ek it will sign m = C||ek it using sk, let σ₂ the resulting signature. The Responder then sends back vk,σ₁,σ₂. The Initiator checks that σ₁ is a correct SOK for vk, and that σ₂ is a correct signature of ek under vk.

$$ \sigma_{1} $$

$$ (\mathsf{s k},\mathsf{v k}),\sigma_{1} $$

$$ m=C| $$

$$ \sigma_{2} $$

$$ \sigma_{1},\sigma_{2} $$

$$ \sigma_{1} $$

$$ \sigma_{2} $$

$$ \mathsf{v k} $$

The modified protocol can be seen in Figure 14, where DS is an EUF-CMA digital signature scheme defined λ by the three algorithms: key generation (vk*,sk) ← Gen(1), signature σ ← Sign(sk,m*) and verification {0,1}← Vfy(vk*,m,σ*).

$$ (\mathsf{v k},\mathsf{s k}),\leftarrow,\mathsf{G e n}(1^{\lambda}) $$

$$ \sigma\leftarrow\mathsf{S i g n}(\mathsf{s k},m) $$

$$ {0,1}\leftarrow\mathsf{V f y}(\mathsf{v k},m,\sigma) $$

Intuitively, the proof of security follows from the security of both the SOK and the regular signature scheme, which incidentally can be a one-time signature since each verification key is used to sign only one message. The main technical issue is in the proof of extractability for the witness, since the Prover is guaranteed to know the witness when it computed σ₁ and not when it successfully completes the protocol.

$$ \sigma_{1} $$

Fig. 14: Offline & Online phases for U-WAKE

In some applications this may be an issue (e.g. when the WAKE should guarantee that the Responder still owns a particular file). One way to address this issue in practice is to add some form of timestamp to the message signed in the offline case, which guarantees at least that the Responder knew the witness relatively recently. A full proof will appear in the final version.

While the above discussion, and Figure 14, refer only to the U-WAKE setting this modification can be generalized and applied to the group-WAKE setting by having all authenticated participants execute the offline phase.

8 Experimental Evaluation

In this section we discuss the concrete efficiency of our constructions in some of the practical settings mentioned in the Introduction. While we explicitly focus on the two-party case where only one of the two parties is authenticated, the concrete complexity roughly extends to the group-authenticated case. The dominating costs in our constructions is that of signatures of knowledge. As discussed in Section 7, this cost can be pushed to an offline stage performed by the authenticated parties. We consider the following settings (see table 1):

– Dark pools: we consider the case of a committed value (e.g., a coin) and authentication through a proof that the value is above a certain range. We use ranges of 32 bits in our benchmarks and SHA256 as a commitment method.

– Zero-Knowledge Contingent Payment (ZKCP): this corresponds to the scenario where a seller wants to start a channel from a party claiming to have a digital good satisfying a certain property. A witnessauthenticated private channel can be used for example to negotiate a price before engaging in a ZKCP protocol. We consider two settings for ZKCP: the “Sudoku benchmark” used in previous works on ZKCP and the bug bounty setting (we benchmark a sudoku of standard size N = 10, but in general the circuit

$$ \underline{{c}}=\mathsf{C o m m}(s,\rho)\wedge s\geq\underline{{B}} $$

$$ {sf s s o v S u d o k u}(s,\underline{{z l}}) $$

$$ \mathcal{C}{\mathrm{b u g g y}}(w)=1\wedge\mathcal{C}{\mathrm{e x p e c t}}(w)=0 $$

Table 1: Running times for different settings/relations for construction in fig. 7 using Diffie-Hellman Key Exchanges as underlying KEM. Underlined identifiers denote public inputs; boldface denotes a witness held by the authenticated party.

complexity of checking a Sudoku solution roughly grows with N³). In the latter, a software producer of program C_buggyis incentivizing users to find potential bugs in the program. Here we model this by introducing an additional input, a (small) program C_expectchecking some necessary expected condition that is violated by the bug. As an example consider a prime-testing program C_buggy. here the bug could consist of an even number greater than 2 that the program erroneously recognizes as a prime. In this case we could have for example C_expect(z) := “z is odd ∨ z = 2”. In our benchmarks we use |C_expect|≈ 500K wires and |C_buggy|≈ 10K wires .

$$ N^{3}) $$

$$ C_{\mathrm{b u g g y}} $$

$$ C_{\mathrm{e x p e c t}} $$

$$ C_{\mathrm{b u g g y}} $$

$$ C_{\mathrm{e x p e c t}}(z):={}^{\mathrm{w}} $$

$$ |C_{\mathrm{e x p e c t}}|\approx500K $$

$$ |C_{\mathrm{b u g g y}}|\approx10K $$

$$ V_{z}=2^{} $$

– Retrieval Market: we model a settings similar to that of IPFS [Prob], in which files are identified through a content ID (CID) which roughly corresponds to a hash of the file. The typical block size files are broken up into is 256KB, which is what we use in our benchmarks¹⁵.

Concrete costs All the costs discussed here refer to the instantiations and experimental setting described at the end of this section. The offline running time of the authenticated party is summarized in table 1.

Communication complexity is constant. We estimate it to be below 0.5 KB in total for the unilateral two-party case and of approximately N KB for the group authentication of N parties.

The online running time is also always constant and is of the order of tens of milliseconds. In the unauthenticated setting it is even lower for the unautheunticated party. Naturally, if we do not use an offline/online approach the total running time of each party is the sum of the offline and online running times.

Details on Instantiations and Experimental Setting For signatures of knowledge we consider the construction from [GM17] based on a simulation-extractable variant of [Gro16]. A signature of knowledge consists of three group elements (two elements in G₁ and one in G₂), plus a hash. Using BLS12-381 [bls] as a concrete curve a signature of knowledge consists of 224 bytes (192 bytes for the group elements, plus 32 bytes for SHA256). For the online stage (see section 7), using BLS signatures [BLS04] as DS in section 7 would give us public keys of 48 bytes and signatures of 96 bytes (again using curve BLS12-381).

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{2}) $$

We run all our experiments on Amazon EC2 c5ad.16xlarge with 128 GiB of RAM running 3.3GHz AMD EPYC 7002 series CPUs. We ran our experiments using a single thread. For our estimates, we rely on the implementation of [GM17] in libsnark¹⁶ using the curve implemented in the libsnark library, BN254, (this

¹⁵ Our benchmarks differ from the current implementation of IPFS in the hash function: we use Blake3 [AONZ] instead of SHA256. Producing a (very succinct) signature of knowledge for a SHA computation of that size is 19 significantly more expensive: while hashing with Blake3 requires approximately 2 constraints, SHA256 would 27 require approximately 2. It is plausible IPFS will support proof-friendly hash functions such as Blake3 in the future.

$$ 2^{19} $$

$$ 2^{27} $$

¹⁶ https://github.com/scipr-lab/libsnark has comparable running times¹⁷ to BLS12-381 which provides 128 bit of security, which provides 110 bits of security of BN254).

References

AIR01.William Aiello, Yuval Ishai, and Omer Reingold. Priced oblivious transfer: How to sell digital goods. In Birgit Pfitzmann, editor, EUROCRYPT 2001, volume 2045 of LNCS, pages 119–135. Springer, Heidelberg, May 2001. AONZ.Jean-Philippe Aumasson, Jack O’Connor, Samuel Neves, and Zooko. Blake3 hash. https://github.com/ BLAKE3-team/BLAKE3. APRH21.Diego F Aranha, Elena Pagnin, and Francisco Rodr´ıguez-Henr´ıquez. Love a pairing. In International Conference on Cryptology and Information Security in Latin America, pages 320–340. Springer, 2021. ⁺ BBC 13.Fabrice Ben Hamouda, Olivier Blazy, C´eline Chevalier, David Pointcheval, and Damien Vergnaud. Efficient UC-secure authenticated key-exchange for algebraic languages. In Kaoru Kurosawa and Goichiro Hanaoka, editors, PKC 2013, volume 7778 of LNCS, pages 272–291. Springer, Heidelberg, February / March 2013. ⁺ BCI 13.Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct noninteractive arguments via linear interactive proofs. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 315–333. Springer, Heidelberg, March 2013. BCPT13.Eleanor Birrell, Kai-Min Chung, Rafael Pass, and Sidharth Telang. Randomness-dependent message security. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 700–720. Springer, Heidelberg, March 2013. BD95.Mike Burmester and Yvo Desmedt. A secure and efficient conference key distribution system (extended abstract). In Alfredo De Santis, editor, EUROCRYPT’94, volume 950 of LNCS, pages 275–286. Springer, Heidelberg, May 1995. bls.Bls12-381 curve. https://electriccoin.co/blog/new-snark-curve/. BLS04.Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. Journal of Cryp- tology, 17(4):297–319, September 2004. CCGS10.Jan Camenisch, Nathalie Casati, Thomas Groß, and Victor Shoup. Credential authenticated identification and key exchange. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 255–276. Springer, Heidelberg, August 2010. CGGN17.Matteo Campanelli, Rosario Gennaro, Steven Goldfeder, and Luca Nizzardo. Zero-knowledge contingent payments revisited: Attacks and payments for services. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 229–243. ACM Press, October / November 2017. CL06.Melissa Chase and Anna Lysyanskaya. On signatures of knowledge. In Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS, pages 78–96. Springer, Heidelberg, August 2006. CS98.Ronald Cramer and Victor Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In Hugo Krawczyk, editor, CRYPTO’98, volume 1462 of LNCS, pages 13–25. Springer, Heidelberg, August 1998. cwe.Cweb3. https://www.npmjs.com/package/cweb3. DF17.Yevgeniy Dodis and Dario Fiore. Unilaterally-authenticated key exchange. In Aggelos Kiayias, editor, FC 2017, volume 10322 of LNCS, pages 542–560. Springer, Heidelberg, April 2017. DH76.Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Infor- mation Theory, 22(6):644–654, 1976. ens.Ethereum Name Service. https://ens.domains/. FG10.Dario Fiore and Rosario Gennaro. Identity-based key exchange protocols without pairings. In Transac- tions on computational science X, pages 42–77. Springer, 2010. GGSW13.Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. Witness encryption and its applications. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, pages 467–476. ACM Press, June 2013. GIKM98.Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. In 30th ACM STOC, pages 151–160. ACM Press, May 1998. ⁺ GKM 18.Jens Groth, Markulf Kohlweiss, Mary Maller, Sarah Meiklejohn, and Ian Miers. Updatable and universal common reference strings with applications to zk-SNARKs. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 698–728. Springer, Heidelberg, August 2018. ¹⁷ Specifically, the work in [APRH21] reports a slowdown factor of roughly 2*×* for G₁ operations and 3*×* for G₂ operations in BLS12-381 compared to BN254.

$$ \mathbb{G}_{2} $$

GM17.Jens Groth and Mary Maller. Snarky signatures: Minimal signatures of knowledge from simulationextractable SNARKs. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part II, volume 10402 of LNCS, pages 581–612. Springer, Heidelberg, August 2017. Gro16.Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-S´ebastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 305–326. Springer, Heidelberg, May 2016. han.Handshake: Decentralized naming and certificate authority. https://handshake.org. KY03.Jonathan Katz and Moti Yung. Scalable protocols for authenticated group key exchange. In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, pages 110–125. Springer, Heidelberg, August 2003. Max.Greg maxwell’s zero knowledge contingent payment (bitcoin wiki). https://en.bitcoin.it/wiki/Zero_ Knowledge_Contingent_Payment. mee.MeetWallet: The Meet JS SDK Library for MEET.ONE Client. https://meet-common.gitlab.io/fe/ meet-js-sdk/classes/meetwallet.html. NMKW21.Chan Nam Ngo, Fabio Massacci, Florian Kerschbaum, and Julian Williams. Practical witness-keyagreement for blockchain-based dark pools financial trading. In International Conference on Financial Cryptography and Data Security, pages 579–598. Springer, 2021. Proa.Protocol Labs. Filecoin. https://filecoin.io/. Prob.Protocol Labs. IPFS: Interplanetary file system. https://ipfs.io. RSA78.Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the Association for Computing Machinery, 21(2):120–126, 1978. Sha84.Adi Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley and David Chaum, editors, CRYPTO’84, volume 196 of LNCS, pages 47–53. Springer, Heidelberg, August 1984. SW05.Amit Sahai and Brent R. Waters. Fuzzy identity-based encryption. In Ronald Cramer, editor, EURO- CRYPT 2005, volume 3494 of LNCS, pages 457–473. Springer, Heidelberg, May 2005.

A Unilaterally Witness-Authenticated Key Exchange Model

Unilateral authentication is defined in the two participant setting. One participant, the initiator (Init) is unauthenticated. The authenticated party is called the Responder (Res). The notation for the set of potential participants is changed to be P = {Init,Res₁,..., Res_ℓ−1}, authenticating with respect to the vector Φ = ⟨ϕ^R1,...,ϕ^Rℓ−1,ϕ^Init⟩ where ϕ^Initis a “dummy statement” for which a witness can be computed in polynomial time. All participant-associated variables and oracles remain the same as in the group setting of WAKE.

$$ \phi,= $$

$$ \mathcal{P}=\left{\mathsf{i n i t,R e s_{1},\ldots,R e s_{\ell-1}}\right} $$

$$ \langle\phi_{R_{1}},\ldots,\phi_{R_{\ell-1}},\phi_{\mathsf{I n i t}}\rangle $$

Correctness for U-WAKE then requires that Init, when executing the protocol with any Res_j(authenticated with respect to the instance ϕ_Rj), will accept and the two participants will terminate with a common session key. Correctness is adapted to explicitly apply to the unilateral authentication case but it should be noted that Definition 10 still applies under the condition that the statement ϕ_Initis easy.

$$ \phi_{R_{j}}) $$

$$ \phi_{\mathsf{I n i t}} $$

Definition 17(U-*WAKE Correctness). A U-WAKE protocol Π is correct if for all relations R, for all sets of potential participants P = {Init,Res₁,..., Res^ℓ−1} of size ℓ* = ℓ(λ), for all i,j,k ∈* N such that i j i j i j ϕ_Resk, w_Resk*∈R, sid_Init≡ sid and acc_Init= acc = TRUE then sk_Init= sk*.* _ReskReskResk

$$ \mathcal{P}=\left{\mathsf{n i i}R e s_{1},\ldots,R e s_{\ell-1}\right} $$

$$ \ell,=,\ell(\lambda) $$

$$ i,j,k;\in;\mathbb{N} $$

$$ \phi_{\mathsf{R e s}{k}},\mathsf{w}{\mathsf{R e s}{k}}\in\mathcal{R},,\mathsf{s i l}{\mathsf{I i i t}}^{i}\equiv\mathsf{s i l}{\mathsf{R e s}{k}}^{j} $$

$$ {\mathsf{a c c}}{\mathsf{I n i t}}^{i}={\mathsf{a c c}}{\mathsf{R e s}_{k}}^{\jmath}={\mathsf{T R U E}} $$

$$ \mathrm {s k} _ {\mathrm {I n i t}} ^ {i} = \mathrm {s k} _ {\mathrm {R e s} _ {k}} ^ {j} $$

Confidentiality: The goal of the adversary in the confidentiality game is to be able to distinguish a random key from the real session key generated by an eavesdropped protocol execution. The main modification to this experiment is that the challenge should be an instance of Init.

**Definition 18(U-*WAKE Confidentiality). The advantage of an adversary A with respect to the U-*WAKE protocol Π in the confidentiality game seen in Figure 15 is defined as

$$ \mathbf {A d v} _ {\varPi , \mathcal {A}} ^ {\mathrm {U - W A K E - c o n f i d}} (\lambda , \mathcal {R}, \Phi , \mathcal {D} _ {\Phi}) = | 2 \cdot \Pr [ \mathbf {E x p} _ {\varPi , \mathcal {A}} ^ {\mathrm {U - W A K E - c o n f i d}} (\lambda , \mathcal {R}, \Phi , \mathcal {D} _ {\Phi}) = 1 ] - 1 | $$

The U*-WAKE protocol Π is confidential if, for all λ ∈ N, for all relations R, for all statement vectors Φ,* for all distributions over witness sets D_Φand for all non-uniform admissible PPT A, the advantage of A is negligible.

$$ \lambda\in\mathbb{N}. $$

$$ \Phi , $$

$$ \mathcal{D}_{\phi} $$

$$ \ p{p}\leftarrow\mathsf{S e t U p}(1^{\lambda},\mathcal{R}) $$

$$ \ \boldsymbol{w}\gets\mathcal{D}_{\boldsymbol{\phi}} $$

$$ \mathcal{P}\leftarrow{{\mathsf{R e s}}{i}[\phi{i},{\mathsf{w}}{i}]}{i=1}^{|{\mathsf{w}}|}\cup{{\mathsf{I n i t}}[\phi_{{\mathsf{I n i t}}},{\mathsf{w}}_{{\mathsf{I n i t}}}]} $$

$$ i\leftarrow\mathcal{A}^{\mathsf{E x e c u t e()},\mathsf{R e v e a l()}}(\varPhi,\mathsf{w}) $$

$$ \mathrm {e l s e}: \mathrm {k} _ {1} \leftarrow \mathrm {s k} _ {\mathrm {I n i t}} ^ {i}, \mathrm {k} _ {0} \xleftarrow {$} \mathcal {K} $$

$$ b^{\prime}\leftarrow\mathcal{A}^{\sf E{E c c u t e()},\sf{R e v e a l()}}(\mathsf{k}_{b}) $$

U-WAKE-confid Fig. 15: Exp_Π,A: Experiment for U-WAKE confidentiality.

Authenticity: The goal of the adversary in the authenticity experiment should be to convince the Initiator to accept and consequently generate a session key. Therefore, the first and most obvious change to Figure 5 should be that the challenge instance output by A should always be an instance of Init. Then, A must i convince Π^Initto accept without knowledge of a witness. The adversary A must accomplish this goal without merely playing as a wire between Init and some Res and without otherwise cheating. Note that the extractor outputs a witness for the participant output along with the challenge instance of Init, which is a witness k corresponding to ϕ_jfor Π_R. _j

$$ \mathit{\Pi}_{\mathsf{l n t t}^{i}} $$

$$ \phi_{j} $$

$$ \mathit{\Pi}{R{j}}^{k} $$

**Definition 19(U-*WAKE Authenticity). The advantage of an adversary A with respect to the U-*WAKE protocol Π in the authentication game seen in Figure 16 is defined as

$$ \mathbf {A d v} _ {\Pi , \mathcal {A}} ^ {\mathrm {U - W A K E - a u t h}} (\lambda , \mathcal {R}, \varPhi , \mathcal {D}) = \Pr [ \mathbf {E x p} _ {\Pi , \mathcal {A}} ^ {\mathrm {U - W A K E - a u t h}} (\lambda , \mathcal {R}, \varPhi , \mathcal {D}) = 1 ] $$

A U*-WAKE protocol Π is witness-authenticated if for all admissible non-uniform PPT A there exists a PPT extractor E_Awhich for all λ ∈ N, for all relations R, for all statement vectors Φ, for all witness distributions* D_Φ, the advantage of A is negligible.

$$ \mathcal{E}_{\mathcal{A}} $$

$$ \lambda\in\mathbb{N} $$

$$ {\cal R}, $$

$$ {varPhi} $$

$$ \mathcal{D}_{\phi} $$

Simulatability: The simulatability experiment remains unchanged.

B Proof of Theorem 1

Restatement of Theorem 1: Let KEM be a correct and CPA-secure key encapsulation mechanism. Let SOK be a perfectly correct and simulatable, simulation-extractable signature of knowledge. Then, the protocol Π, as seen in Figure 7, is an actively secure and simulatable U-WAKE.

Proof. Correctness: Correctness follows directly from the correctness of the KEM and SOK. As these are both perfectly correct the U-WAKE is also perfectly correct.

Confidentiality: An adversary A_Cwith nonnegligible advantage in the confidentiality experiment implies the existence of an adversary A_Kwith nonnegligible advantage in the KEM-CPA experiment. Assume that R, Φ, D^Φare such that A^Chas a nonneligible advantage in the confidentiality experiment.

$$ A_{C} $$

$$ \mathcal{A}_{K} $$

$$ \mathcal{R},\varPhi,\mathcal{D}_{\emptyset} $$

$$ A_{C} $$

∗ ∗ The adversary A^Kis given challenge tuple (ek*,* C*,* k^b∗) and must guess the KEM-CPA real or random bit b_KEM-_CPA. A_Ksets up the U-WAKE as follows: generates the public parameters for the signature of knowledge pp_SOK← SOK*.SSetup(R), and sets the public parameters as pp_WAKE= {λ, R,pp_SOK}. Then, A_Kruns A_C with input pp_WAKE,Φ,* w.

$$ \ {mathcal A A}_{K} $$

$$ (\mathsf{e k\ }^{},\mathsf{C}^{},\mathsf{k}_{b}^{*}) $$

$$ \mathcal{A}_{K} $$

$$ \leftarrow\mathsf{S O K.S S e t u p}(\mathcal{R}) $$

$$ p p_{\mathsf{W A K E}}=\left{\lambda,\mathcal{R},p p_{\mathsf{S0K}}\right} $$

$$ \mathcal{A}_{K} $$

$$ \mathcal{A}_{C} $$

$$ \ {\varnothing{,}w} $$

$$ \mathbf {E x p} _ {\varPi , \mathcal {A}} ^ {\mathrm {U - W A K E - a u t h}} (\lambda , \mathcal {R}, \varPhi , \mathcal {D} _ {\varPhi}) $$

$$ p p\leftarrow\mathsf{S e t U p}(1^{\lambda},\mathcal{R}) $$

$$ \ \boldsymbol{w}\gets\mathcal{D}_{\boldsymbol{\Phi}} $$

$$ \mathcal {P} \leftarrow \left{\operatorname {R e s} _ {i} \left[ \phi_ {i}, w _ {i} \right]\right] _ {i = 1} ^ {\left| w _ {i} \right|} \cup \left{\operatorname {I n i t} \left[ \phi_ {\mathrm {I n i t}}, w _ {\mathrm {I n i t}} \right]\right) $$

$$ (i, j) \leftarrow \mathcal {A} ^ {\mathrm {S e n d ()}, \mathrm {E x e c u t e ()}} (\varPhi) $$

$$ \mathsf{w}^{\prime}\leftarrow\mathcal{E_{A}}(\mathsf{v i e w_{A}}) $$

$$ b_{\mathsf{a c c}}\leftarrow\mathsf{a c c}_{\mathsf{I n i t}}^{i} $$

$$ b_{\mathsf{e x t}}\leftarrow\left(\phi_{R_{j}},\mathsf{w}^{\prime}\right)\in\mathcal{R} $$

$$ \operatorname{a s s e r t};(\mathsf{R e s}_{j}\in\mathcal{I S}(\mathsf{I n i t},i)) $$

$$ \operatorname{\mathrm{t u t p u t}}\ (b_{\mathsf{a c c}}\wedge\bar{b}_{\mathsf{e x t}}) $$

U-WAKE-auth Fig. 16: Exp_Π,A: Experiment for U-WAKE authenticity.

$$ \operatorname {E x p} _ {\varpi , \mathcal {A}} ^ {\mathrm {U - W A K E - a u t h}} $$

In response to queries to Execute of the form q_k= (Init*,k,* Res_j,i), A_Kgenerates an honest transcript bek i tween Π_Initand Π_Resof the form T_k= ⟨ekk, (Ck,σ_k)⟩ with signature generated as σ_k← SOK*.SSign(pp_SOK,ϕ*_j, w_j,ek_k||C_k). j k i k i k i A^Kstores the generated session key as s^kInitand sk^Res, sets sid^Init= sⁱd^Res= T^kand sets acc^Init= acc^Res= j j j 1 TRUE. Let Q_Ebe the total number of queries made to Execute by A_C. With probability, A_Cresponds QE ∗ ∗ ∗ ∗ ∗ ∗ ∗ to the query with T = ⟨e_k, (C,σ)⟩ for σ ← SOK*.SSign(pp_SOK,ϕ*_j, w_j*,*ek ||C). In response to queries to iU Reveal of the form (U,i), A_Krepl_ies with sk.

$$ q_{k}=(\mathsf{I n i},k,\mathsf{R e s}{j},i),\mathcal{A}{K} $$

$$ \bar{\Pi_{\mathrm{l n i t}}^{k}} $$

$$ \Pi_ {\mathrm {R e s} _ {i}} ^ {i} $$

$$ T_{k}=\left\langle\mathsf{e k}{k},\left(\mathcal{C}{k},\sigma_{k}\right)\right\rangle $$

$$ \sigma_{k}\leftarrow\mathsf{S O K.S S i g n}(p p_{\mathsf{S O K}},\phi_{j},\mathsf{w}{j},\mathsf{e k}{k}||C_{k}) $$

$$ \ {mathcal A A}_{K} $$

$$ \mathsf{s k}_{\mathsf{l n i t}}^{k} $$

$$ \mathsf{s k}{\mathsf{R e s}{j}}^{i} $$

$$ {\mathsf{s i d}}{\mathsf{l n i t}}^{k}={\mathsf{s i d}}{\mathsf{R e s}{i}}^{i}=T{k} $$

$$ Q_{E} $$

$$ \mathrm {a c c} _ {\mathrm {I n i t}} ^ {k} = \mathrm {a c c} _ {\mathrm {R e s} _ {i}} ^ {i} $$

$$ A_{C} $$

$$ T^{}=\langle\mathsf{e k}^{},(left\mathcal{C}^{},\sigma^{})\rangle $$

$$ \frac{1}{Q_{E}},:\mathcal{A}_{C} $$

$$ \sigma^{}\leftarrow\mathsf{S O K.S S i g n}(p p_{\mathsf{S O K}},\phi_{j},\mathsf{w}_{j},\mathsf{e k}^{}||C^{*}) $$

$$ (U,i),\mathcal{A}_{K} $$

$$ \mathsf{s k}_{U}^{\iota} $$

i ∗ If A^Coutputs challenge i such that sid^Init≡ T then A^Kprovides k^b∗as the challenge session key. In this ′ case, when A_Coutputs her guess bit b_confid, A_Kforwards this bit as her guess for b_KEM-_CPA. If A_Coutputs some other challenge instance A_Kflips a bit and provides either the real key or a random key. Given that ∗ ^∗ 1 T appears only once in the list of Q^Equeries, the probability that A^Cselects T as her challenge is. Q^E

$$ \mathcal{A}_{C} $$

$$ \ \mathsf{s i d}_{\mathsf{I n i t}}^{i}\equiv T^{*} $$

$$ \ {mathcal A A}_{K} $$

$$ \mathsf{k}_{b}^{*} $$

$$ A_{C} $$

$$ b_{\mathsf{c o n f i d}}^{\prime},,\mathcal{A}_{K} $$

$$ A_{C} $$

$$ \mathcal{A}_{K} $$

$$ T^{*} $$

$$ Q_{E} $$

$$ \frac{1}{Q_{E}} $$

$$ \mathcal{A}_{K} $$

$$ \ _{C} $$

$$ 2Q_{E} $$

∗ A_Kruns 2Q_Eindependent copies of A_C. Call E the event that T appears only once in the set of responses to all queries. Consequently:

$$ T^{*} $$

$$ \ {cal A A}_{C} $$

$$ T^{*} $$

$$ \begin{array}{l} \Pr [ \operatorname {E x p} _ {\mathcal {A} _ {K}} ^ {\mathrm {K E M - C P A}} (\lambda) ] \geq 2 Q _ {E} \cdot \Pr [ \operatorname {E x p} _ {\Pi , \mathcal {A} _ {C}} ^ {\mathrm {W A K E - c o n f i d}} (\lambda , \mathcal {R}, \Phi , \mathcal {D} _ {\Phi}) ] \cdot \Pr [ T ^ {} \leftarrow \mathcal {A} _ {C} (\Phi , w) ] + \mathrm {n e g l} (\lambda) \ = 2 Q _ {E} \cdot \Pr [ \operatorname {E x p} _ {\Pi , \mathcal {A} _ {C}} ^ {\mathrm {W A K E - c o n f i d}} (\lambda , \mathcal {R}, \Phi , \mathcal {D} _ {\Phi}) ] \cdot \Pr [ T ^ {} \leftarrow \mathcal {A} _ {C} (\Phi , w) | E ] \cdot \Pr [ E ] + \mathrm {n e g l} (\lambda) \ = 2 \cdot \Pr [ \operatorname {E x p} _ {\Pi , \mathcal {A} _ {C}} ^ {\mathrm {W A K E - c o n f i d}} (\lambda , \mathcal {R}, \Phi , \mathcal {D} _ {\Phi}) ] \cdot \Pr [ E ] + \mathrm {n e g l} (\lambda) \ \geq 2 \cdot \left(1 - \frac {1}{e}\right) \cdot \Pr [ \operatorname {E x p} _ {\Pi , \mathcal {A} _ {C}} ^ {\mathrm {W A K E - c o n f i d}} (\lambda , \mathcal {R}, \Phi , \mathcal {D} _ {\Phi}) ] + \mathrm {n e g l} (\lambda) \ \geq \Pr [ \operatorname {E x p} _ {\Pi , \mathcal {A} _ {C}} ^ {\mathrm {W A K E - c o n f i d}} (\lambda , \mathcal {R}, \Phi , \mathcal {D} _ {\Phi}) ] + \mathrm {n e g l} (\lambda) \ \end{array} $$

Authenticity: An adversary A_Awith nonnegligible advantage against the authenticity game implies an adversary A_Sagainst the sig-ext of the SOK. Assume that R, Φ, D_Φare such that A_Ahas a nonneligible advantage in the authenticity experiment.

$$ \mathcal {A} _ {A} $$

$$ \mathcal{A}_{S} $$

$$ \mathcal{R},:\varPhi,:\mathcal{D}_{\varPhi} $$

$$ \ {cal A}_{A} $$

A_Sassigns as the public parameters pp_WAKE←{pp_SOK, R,λ} and runs A_Awith input Φ. Queries to Send and Reveal are answered honestly by A_S, all signatures are generated with queries to the SSimSign oracle.

$$ \leftarrow{p p_{\mathsf{S0\mathsf{K}}},\mathcal{R},\lambda} $$

$$ \mathcal{A}_{S} $$

$$ \mathcal{A}_{A} $$

$$ {\Phi{}} $$

A_Aoutputs her challenge (Init*,i,* Res_j) with Res_j∈IS(Init*,i*). A_Ais admissible, thus A_Awas not forwardi ing for Π and Res_j. By Definition 11 this implies that for all Res_j′ ∈P such that ϕ_Res= ϕ_Resjwe have for Init j′ ′ ′ k i all k : sid_Res̸≡ sid_Init. We assume that the only participant authenticating with respect to ϕ_jis Res_j, as there j′ k is only a single message sent from the Res to the Init. A^Aeither (1) sent to the instance Π^Res, for some k, a j ′ new encapsulation key not generated by the initiator ek ̸= ek ← Send(Init*,i,* Res_j), or (2) sent to the initiator ′ ′ ˆ), or (3) a signed ciphertext not output by a corresponding send query (C,σ) ̸= (C,σ) ← Send(Res_j,k, ek both. Consider case (1) where A^Adid not forward the first message, but forwarded the second. The signature ′ σ must be a signature of the message m = *C||*ek, so if A_Aonly supplied an ek ̸= ek, σ will not verify and Init

$$ \mathcal{A}S $$

$$ \mathcal{A}_{A} $$

$$ \mathsf{R e s}_{j}\in\mathcal{I S}(\mathsf{I n i t},i) $$

$$ \mathit{\Pi}_{\mathsf{l n t t}^{i}} $$

$$ (\mathsf{I n i t},i,\mathsf{R e s}_{j}) $$

$$ \mathcal{A}_{A} $$

$$ \ {cal A A} $$

$$ {mathsf{R e s}}_{j^{\prime}}\in\mathcal{P} $$

$$ \phi_{\mathsf{R e s}{j^{\prime}}}=\phi{\mathsf{R e s}_{!}} $$

$$ k^{\prime}\colon{\mathsf{s i d}}{{\mathsf{R e s}}{i}{}^{\prime}}^{k^{\prime}}\not\equiv{\mathsf{s i d}}_{{\mathsf{l n i t}}}^{i} $$

$$ \mathsf{R e s}_{j} $$

$$ \mathcal{A}_{A} $$

$$ \phi_{j} $$

$$ \mathit{\Pi}{\mathsf{R e s}{j}}^{k} $$

$$ k, $$

$$ \neq $$

$$ \leftarrow\mathsf{S e n d}(\mathsf{I n i t},i,\mathsf{R e s}_{j}) $$

$$ (2) $$

$$ \left(C ^ {\prime}, \sigma^ {\prime}\right) \neq (C, \sigma) \leftarrow \operatorname {S e n d} \left(\operatorname {R e s} _ {j}, k, \mathrm {e k}\right) $$

$$ \ {\mathcal A}_{A} $$

$$ m=\mathcal{C}\ |\mathsf{e k} $$

$$ e k^{\prime}\neq e k,\sigma $$

$$ \ {cal A}_{A} $$ will not accept. A_Amust not have replaced only the first message, she must have replaced either the second ′ ′ or both messages. In the remaining cases (2) and (3), (C,σ) was not generated as a response to a query ˆ) for any ˆ. Therefore ^′ Send(Res_j,k, ek k, ek σ was not an output of some query to the SSimSign oracle made i ′ ′ ′ by A^C, but Π^Initaccepted and therefore we know that σ verifies: SVfy(pp^SOK,ϕ^Resj,m = (C ||ek),σ) = 1 for i ′ ′ ek output by Π_Init. So, A_Soutputs (ϕ_j,m = (C ||ek),σ) as her forgery.

$$ \mathcal{A}_{A} $$

$$ (C^{\prime},\sigma^{\prime}) $$

$$ ({\mathsf{R e s}}_{j},k) $$

$$ k,{\hat{\mathsf{e k}}} $$

$$ \sigma^{\prime} $$

$$ \mathcal{A}_{C} $$

$$ \mathit{\Pi}_{\mathsf{l n t t}^{i}} $$

$$ \sigma^{\prime} $$

$$ \mathsf{S V f y}(p p_{\mathsf{S O K}},\phi_{\mathsf{R e s}_{j}},m=(C^{\prime}||\mathsf{e k}),\sigma^{\prime})=1 $$

$$ \mathit{\Pi}{\mathsf{I n i t}}^{i}.\ {mathit S o},\mathcal{A}{S} $$

$$ \left(\phi_{j},m=\big(C^{\prime}\ \ |mathsf e e k\big),\sigma^{\prime}\right) $$

If there exists an extractor for A_Sthen there necessarily exists an extractor for A_A. The view of A_S contains no information that cannot be calculated in polynomial time from view^AA. Let this transformation be view_AS= T(view_AA). Construct E_AA, running on view_AA, assuming the existence of E_ASas follows: E_AA ′ runs T on the view of the A_Ato get the view_ASthen runs E_ASto get a witness w and outputs this witness. Therefore, because there is no extractor for A_Athere is no extractor for A_S.

$$ \mathcal{A}_{S} $$

$$ \mathcal{A}_{A} $$

$$ \mathcal{A}_{S} $$

$$ A_{A} $$

$$ {bf_{\mathcal A}}{S}=T(\mathsf{v i e w}{\mathcal A_{A}}, $$

$$ \mathcal{E}{\mathcal{A}{A}} $$

$$ \mathcal{E}{\mathcal{A}{S}} $$

$$ \mathcal{A}_{A} $$

$$ \mathcal{E}{A{A}} $$

$$ T $$

$$ \ {\cal A}_{A} $$

$$ \mathcal{A}_{S} $$

$$ \mathcal{E}{\mathcal{A}{S}} $$

$$ w^{\prime} $$

$$ \mathcal{A}_{S} $$

$$ \mathcal{A}_{S} $$

The advantage A_Sis then non-negligible, as it is greater that that of A_A.

$$ \ {\mathcal A}_{A} $$

$$ \mathcal{A}_{A} $$

Simulatability: A_Wwith nonnegligible advantage against U-WAKE simulatability implies the existance of an adversary A_Sagainst SOK simulation. Assume that R is such that A_Whas a nonnegligle advantage in the simulation experiment.

$$ {\mathcal{A}}_{W} $$

$$ \mathcal{A}_{S} $$

b On input pp^b, A^Sconstructs the public parameters for the U-WAKE as pp^b= {pp^SOK, R,λ} and forwards this to A_W.

$$ {\mathcal{A}}_{W} $$

$$ p p_{b},\mathcal{A}_{S} $$

$$ \ {mathcal A A}_{W} $$

$$ p p_{b}={p p_{\mathsf{S0}\mathsf{K}}^{b},\mathcal{R},\lambda} $$

b For the ith call to SetKeys ^by A_W, A_Ssaves the statement witness pair as (ϕ_i, w_i) to use when responding to queries for Responder Res_i. A_Shonestly responds to all queries to Send and Reveal, except instead of using b the signing algorithm she queries her oracle S^pp,τto generate any signatures. Upon receipt of the guess bit b _′ b from A_W, A_Suses this as her own guess for the real or random bit.

$$ \mathsf{S e t k e y s}^{b} $$

$$ \mathcal{A}{W},\mathcal{A}{S} $$

$$ (\phi_{i},\mathsf{w}_{i}) $$

$$ \mathcal{A}_{S} $$

$$ \mathcal{S}{p p{b},\tau}^{b} $$

$$ \mathcal{A}{W},,\mathcal{A}{S} $$

$$ \mathcal{A}_{S} $$

The advantage of A_Sis then non-negligible, as it is greater than that of A_W.

$$ \ {\mathcal A{}}_{W} $$