Subversion-Resilient Enhanced Privacy ID

Antonio Faonio¹, Dario Fiore², Luca Nizzardo⁴, and Claudio Soriente³

¹ EURECOM, Sophia Antipolis, France.

faonio@eurecom.fr

² IMDEA Software Institute, Madrid, Spain.

fantonio.faonio, dario.fioreg@imdea.org

³ NEC Labs Europe, Madrid, Spain.

claudio.soriente@neclab.eu

⁴ Protocol Labs luca@proto.ai

Abstract.

Anonymous attestation for secure hardware platforms leverages tailored group signature schemes and assumes the hardware to be trusted. Yet, there is an ever increasing concern on the trustworthiness of hardware components and embedded systems. A subverted hardware may, for example, use its signatures to exltrate identifying information or even the signing key.

In this paper we focus on Enhanced Privacy ID (EPID)|a popular anonymous attestation scheme used in commodity secure hardware platforms like Intel SGX. We dene and instantiate a subversion resilient EPID scheme (or SR-EPID). In a nutshell, SR-EPID provides the same functionality and security guarantees of the original EPID, despite potentially subverted hardware. In our design, a \sanitizer" ensures no covert channel between the hardware and the outside world both during enrollment and during attestation (i.e., when signatures are produced). We design a practical SR-EPID scheme secure against adaptive corruptions and based on a novel combination of malleable NIZKs and hash functions modeled as random oracles.

Our approach has a number of advantages over alternative designs. Namely, the sanitizer bears no secret information|hence, a memory leak does not erode security. Further, the role of sanitizer may be distributed in a cascade fashion among several parties so that sanitization becomes eective as long as one of the parties has access to a good source of randomness. Also, we keep the signing protocol non-interactive, thereby minimizing latency during signature generation.

Table of Contents

Subversion-Resilient Enhanced Privacy ID 1 Antonio Faonio, Dario Fiore, Luca Nizzardo, and Claudio Soriente 1 Introduction 2 1.1 Our Contribution 3 1.2 Related work 5 2 Subversion-Resilient Enhanced Privacy ID 6 2.1 Subversion-Resilient EPID 7 2.2 Syntax of Subversion-Resilient EPID (SR-EPID) 7 2.3 Subversion-resilient Security 9 3 Building Blocks 18 3.1 Bilinear groups 18 3.2 Structure-Preserving Signatures 18 3.3 Non-Interactive Zero-Knowledge Proof of Knowledge 20 4 Our SR-EPID Construction 22 4.1 Efficiency 24 4.2 Proof of Security 24

1 Introduction

Anonymous attestation is a key feature of secure hardware platforms, such as Intel SGX⁵ or the Trusted Computing Group’s Trusted Platform Module⁶. It allows a verier to authenticate a party as member of a trusted set, while keeping the party itself anonymous (within that set). This functionality is realized by using a privacy-enhanced avor of group signatures in which signatures cannot be traced, not even by the group manager.

Given such realization paradigm, the security of anonymous attestation schemes is grounded on the trustworthiness of the signer. In particular, anonymity and unforgeability denitions assume that the signer is trusted and does not exltrate any information via its signatures. Yet, in most applications, the signer is a small piece of hardware with closed-source rmware (e.g., a smart card) to which a user has only black-box access. In such a scenario, trusting the hardware to behave honestly may be too strong of an assumption for mainly two reasons. First, having only black-box access to a piece of hardware makes it virtually impossible to verify whether the hardware provides the claimed guarantees of security and privacy. Second, recent news on state-level adversaries corrupting security services⁷ have shown that subverted hardware is a realistic threat. In the context of anonymous attestation, if the hardware gets subverted (e.g., via rmware bugs or backdoors), it may output valid, innocent-looking signatures that, in reality, covertly encode identifying information (e.g., using special nonces). Such signatures may allow a remote adversary to trace the signer, thereby breaking anonymity. Using a similar channel, a subverted signer could also exltrate its

⁵ https://www.intel.com/content/www/us/en/architecture-and-technology/ software-guard-extensions.html

⁶ https://trustedcomputinggroup.org/resource/tpm-library-specification/

7 https://snowdenarchive.cjfe.org/ https://snowdenarchive.cjfe.org/

⁷ https://snowdenarchive.cjfe.org/ secret key, and this would enable an external adversary to frame an honest signer, for example by signing bogus messages on its behalf.

Previous work has studied subversion resilience in the context of Direct Anonymous Attestion (DAA)|the anonymous attestation scheme used in TPMs. The subversion-resilient DAA proposed by Camenisch et al. [9] leverages a \split" signature scheme where the secret key is split between the TPM and the host. Intuitively, this approach guarantees security in presence of a subverted TPM as long as the host behaves honestly and does not leak its share of the secret key.

1.1 Our Contribution

We continue the study of subversion-resilient anonymous attestation and we focus on Enhanced Privacy ID (EPID) [8,7], a popular anonymous attestation scheme that is currently deployed on commodity trusted execution environments like Intel SGX. Our contribution is mainly twofold: we rst formalize the notion of Subversion-Resilient EPID (SR-EPID), and then we propose an ecient realization of this cryptographic primitive in bilinear groups.

The Model of Subversion-Resilient EPID. Enhanced Privacy ID is essentially a privacyenhanced group signature where the group manager cannot trace a signature but signers can be revoked. In the context of remote attestation, a group member is instantiated by its signing component (the \signer"), which is typically a piece of hardware.

In order to counter subverted signers, our main idea is to enhance the EPID model by adding a \sanitizer" party whose goal is to ensure that no covert channel is established between a potentially 8 subverted signer and external adversaries. In practical application scenarios, the sanitizer could run on the same host of the signer (e.g., on a phone to sanitize signatures issued by the SIM card), or on a separate one (e.g., on a corporate rewall to sanitize signatures issued by local machines).

Compared to a subversion-resilient anonymous attestation scheme that uses split-signatures [9], our approach comes with multiple benets. First, signature generation is non-interactive and the communication ow is unidirectional from the signer to the sanitizer, on to the verier. Thus, our design decreases signing latency and provides more exibility as the sanitization of a signature does not need to be done online. Another benet of our design is the fact that the sanitizer holds no secret. This means that if a memory leak occurs on the sanitizer, one has nothing to recover but public information. Dierently, in a split signature approach, security properties no longer hold if the TPM is subverted and the key share of its host is leaked. Further, as sanitization is non-interactive and requires no secret, it may even be carried out by multiple parties in a cascade fashion so that covert channels are eradicated as long as one of the sanitizers has access to a good source of randomness|and such randomness is not available to the adversary. It is not clear how to achieve such \fault tolerance" with split signatures. One may split the signing key across several parties and design a multiparty signing protocol, but very likely this would lead to high latency for signature generation.

The idea of adding a sanitizer to mitigate subversion attacks in anonymous attestation is inspired by that of using a cryptographic reverse rewall of Mironov and Stephens-Davidowitz [22]. Besides subversion-resilient unforgeability (as in Ateniese et al. [2]), in an EPID scheme we have to guarantee additional properties such as anonymity and non-frameability, as well as to deal with the complications of supporting revocation. Formalizing all these properties in rigorous denitions turned out to be non trivial and is a signicant contribution of this paper.

⁸ Note that adding a party to mediate the communication between the potentially subverted signer and the outside world is necessary, as the signer could exltrate arbitrary information otherwise [9].

As a byproduct of our new denitions of SR-EPID, we also obtain a careful formalization of the notion of unforgeability for (non-subversion-resilient) EPID schemes, or more broadly, for group signature schemes with both key-revocation mechanisms and a blind join protocol. For completeness, we describe this simpler and non-subversion-resilient version of our notion in Appendix ??. Compared to the previous denition of [7], ours formalizes several technical aspects that in [7] were essentially expressed only in words and left to the reader’s interpretation. Given that EPID schemes are already deployed in real-world systems, we believe this is a result that can be of independent interest for the community.

Our SR-EPID in Bilinear Groups. Our next contribution is an ecient construction of a SR- EPID based on bilinear pairings. Our starting point is the classical blueprint of group signature schemes where: (I) the group manager holds the secret key of a signature scheme; (II) during the join protocol the group manager creates a blind signature_yon a value y private to the prospective group member, and both and y are the group member’s secret key; (III) a signature_Mon message M is a signature of knowledge for M of a_ythat veries for y and the group public key. (IV) Finally, to support revocation and linkability, a signature_Mis bound to an arbitrary basename B and contains a pseudorandom token R_B= f_y(B). Without knowing y the token looks random (and thus hides the signer’s identity) but, at the same time, can be eciently checked against a revoked key y. That is, the verier checks if R_B= f_y(B) for all the y in the revocation list. Similarly, a signer that allows for linkability of its signatures may accept to produce multiple signatures on the same basename; such signatures could be easily linked as they carry the same token. The approach described so far follows closely the one of EPID [8,7].

$$ \sigma_{y} $$

$$ \sigma $$

$$ y $$

$$ \sigma_{M} $$

$$ \sigma_{y} $$

$$ \sigma_{M} $$

$$ B $$

$$ R_{B}=f_{y}(B) $$

$$ R_{B}=f_{y^{*}}(B) $$

$$ y^{*} $$

$$ y^{*} $$

Our rst idea to contrast subversion attacks is to let the sanitizer re-randomize every signature Mproduced by the signer, eliminating in this way that the randomness chosen by the signer encodes a covert channel. Technically, we achieve this by employing re-randomizable NIZKs in step (III).

$$ \sigma_{M} $$

This is not, however, the only possible attack vector between a subverted signer and an external adversary. For example, the signer may come with an hardcoded value y known to the external adversary so that all the (valid) signatures produced by the signer can be easily traced. To counter this class of attacks we let the sanitizer contribute with its randomness to the choice of y during the join protocol. Even further, we require the sanitizer to re-randomize any message and NIZK sent to the group manager during the join protocol. Finally, another potential attack is that at any moment after the join protocol, the signer may switch to creating signatures by using a hardcoded secret y⁰;_y0. As above, an external party equipped with y⁰ could track those signatures. To contrast this class of attacks, we require the signer to produce, along with every signature_M, a proof that is veried by the sanitizer using a dedicated verication token and that ensures that the signer is using the same secret y used in the join protocol; if the check passes, the sanitizer strips o and returns a re-randomization of_M. Our model diverges from the cryptographic reverse rewall framework of [22] because of the verication token mechanism. Looking ahead, this is not simply a limitation of our scheme but more generally we can show that EPID schemes that admit secret-key based revocation cannot have a cryptographic reverse rewall, we give more details in Section 2.2.

$$ y $$

$$ y^{\prime},\sigma_{y^{\prime}} $$

$$ y^{\prime} $$

$$ \sigma_{M} $$

$$ \pi_{\sigma} $$

$$ y $$

$$ \sigma_{M} $$

$$ \pi_{\sigma} $$

The description above gives a high-level overview of the main ideas that we introduced in the protocol to counter subversion attacks. However, a signicant technical contribution in the design of our construction is a set of techniques that we introduced in order to reconcile our extensive use of malleable NIZKs (and in particular, Groth-Sahai proofs [18]) with the goal of obtaining an ecient SR-EPID scheme. The main problem to prove security of our scheme is that we need the NIZK to be

9 not only malleable but also to have a form of simulation-extractable soundness. In the EPID of [7], simulation-extractable soundness is also needed, but it is obtained for free by using Fiat-Shamir transformed Sigma protocols (Faust et al. [16]). In our case, this approach is not viable because the 10 Fiat-Shamir compiler breaks any chance for re-randomizability. One could use a re-randomizable and (controlled) simulation-extractable NIZK (Chase et al. [13]), but in practice these tools are very expensive|they would require hundreds of pairings for verication and hundreds of group elements for the proofs.

To overcome this problem, we propose a combination of (plain) GS proofs with the random oracle model. Briey speaking, we use the random oracle to generate the common reference string that will be used by the GS proof system and use the property that, in perfectly-hiding mode, this CRS can be created from a uniform random string. (In particular, we need cryptographic hash functions that allow to hash directly on G₁ and on G₂, see Galbraith et al. [17].) In this way we can program the random oracle to produce extractable common reference strings for the forged signature made by the adversary and for the messages in the join protocol with corrupted members, and program the random oracle to have perfectly-hiding common reference strings for all the material that the reduction needs to simulate. Our technique is a reminiscence of techniques based on programmable hash functions [19,12] and linearly homomorphic signatures [20]. However, our ROM-based technique enables for more ecient schemes with unbounded simulation soundness.

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

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

The resulting scheme provides the same functionality of EPID, tolerates subverted signers, and features signatures that are shorter than the ones in [7] for reasonable sizes of the revocation list: ours have 28 + 2n group elements whereas EPID signatures have 8 + 5n, where n is the size of the revocation list (i.e., ours are shorter already for n 7).

$$ 8+5n $$

$$ n\geq7] $$

1.2 Related work

Subversion-resilient signatures and Cryptographic Reverse Firewalls. Ateniese et al., [2] study subversion-resilient signature schemes and shows that unique signatures as well as the use of a cryptographic reverse rewall (RF) of [22] ensure unforgeability despite a subverted signing algorithm. Our scheme could be roughly interpreted as a new EPID scheme equipped with a cryptographic reverse rewall for the join protocol that allows a new party to join the group, and a cryptograhic reverse rewall that protects the signatures sent by the signer. However, as already mentioned, there are some technical details that dierentiate our model to the cryptographic reverse rewall framework.

Subversion-resilient anonymous attestation. Camenisch et al. [10] modify the UC corruption model and provide a UC denition for DAA that guarantees privacy despite a subverted TPM. The DAA scheme presented in [10] leverages dual-mode signatures of Camenisch and Lehmann [11] and builds upon the ideas of Bellare and Sandhu [5] to provide a signature scheme where the signing key is split between the host and the TPM. Later on, Camenisch et al. [9] build on the same idea of [10] and show a UC-secure DAA scheme that requires only minor changes to the TPM 2.0 interface and tolerates a subverted TPM by splitting the signing key between the host and the TPM.

⁹ In fact, on one hand we have to extract the witness from the adversary’s forgery, while on the other hand we rely on zero-knowledge in order to disable any covert channel from subverted signers.

¹⁰ Very informally speaking, any re-randomization algorithm should be able to change the hash value to a fresh one without the knowledge of the witness, which is in contrast with the special soundness of the sigma-protocols.

We argue that splitting the signing key between the potentially subverted hardware (e.g., the TPM) and the host to achieve resilience to subversions is viable in scenarios where (i) the channel between the two parties has low latency|because of the interactive nature of the signing protocol| and (ii) the user can trust the host. Both conditions holds for TPM scenarios. In particular, a TPM is soldered to the motherboard of the host and has a high-speed bus to the main processor. Also, the TPM manufacturer is usually dierent from the one of the main processor|hence, the user may trust the latter but not the former.

In case of TEEs such as Intel SGX, we note that there is no real separation between the TEE and the main processor. Thus, it would be hard to justify an untrusted TEE and a trusted processor since, in reality, they lie on the same die and are shipped by the same manufacturer. As such, the entity in charge of preventing the TEE from exltrating information (i.e., the one holding a share of the signing key) must be placed elsewhere along the channel between the TEE and the verier, thereby paying a latency penalty to generate signatures.

We argue that our solution is more suitable for TEE platforms like Intel SGX. In particular, the non-interactive nature of the signing protocol allows us to place the sanitizer \away" from the signer, without impact on performance. Thus, the sanitizer may be instantiated by a co-processor next to the TEE, or it may run on a company gateway that sanitizes attestations produced by hosts within the company network before they are sent out. As the sanitizer and the potentially subverted hardware may run on dierent platforms, they may come from dierent manufacturers. For example, one could pick an AMD or Risc-V processor to sanitize an Intel-based TEE such as SGX. A sanitizer may even be built by combining dierent COTS hardware as [21].

Finally, we note that our denition of SR-EPID is not UC but caters for adaptive corruptions whereas the UC denition of DAA in [10,9] only considers static corruptions.

2 Subversion-Resilient Enhanced Privacy ID

In this section we introduce our notion of Subversion-Resilient Enhanced Privacy ID (SR-EPID). Before we do so, we discuss EPID and its shortcomings in case of subverted hardware.

Background on EPID. Enhanced Privacy ID is essentially a privacy-enhanced group signature scheme with a group manager and a number of group members.

Compared to classic group signatures (see Bellare et al. [4]), EPID drops the ability of the group manager to trace signatures, and adds novel revocation mechanisms. In particular, EPID allows to revoke a group member by adding its private key to a revocation list named PrivRL; while verifying a signature, the verication algorithm checks that none of the private keys in PrivRL may have produced. In case the secret key of a misbehaving group member did not leak, EPID can still revoke that member by using one of its signatures. That is, EPID accounts for an additional revocation list, named SigRL, containing signatures of revoked members. Thus, a valid signature must carry a zero-knowledge proof that the private key used to compute is dierent from any of the keys used to produce any of the signatures in SigRL.

Security notions for EPID include anonymity and unforgeability. Informally, anonymity ensures that signatures are not traceable by any party, including the group manager. Unforgeability ensures that only non-revoked group members can generate valid signatures.

We note that EPID does not account for pseudonymous signatures. The latter allow for a sort of controlled linkability as each signature is bound to a \basename", and one can easily tell|via a Link algorithm| whether two signatures on the same basename where produced by the same group member. This signature mode is actually available in DAA and in the version of EPID used by Intel SGX. Further, DAA denes a security property tailored to pseudonymous signatures called non- frameability. Informally, non-frameability ensures that no adversary|not even a corrupted group manager|can create a signature on a message m and basename B, that links to a signature of an honest group member (when this honest group member never signed m;B). Given the usefulness of pseudonymous signatures in real-world deployments, we decide to include them|along with a denition of non-frameability|in our denition of subversion-resilient EPID.

2.1 Subversion-Resilient EPID

Overview and rationale of the denition. We introduce a \sanitizer" that proxies the communication between the signer and the outside world. For simplicity, we assume each signer to be 11 paired with a sanitizer and we denote a pair of signer-sanitizer as a \platform". In the security experiments we denote with I the issuer, with S the sanitizer, with M the signer, and with P the platform. Very often we refer to the signer as the \hardware" or the \machine" (thus the letter M for our notation). We assume group members to be platforms and gear security denition towards 12 them.

The goal of the sanitizer is to remove any possible covert channel from the signer to an external adversary. For example, a subverted signer could establish a covert channel through the randomness used at signature generation. Alternatively, a subverted signer may maliciously inuence the join protocol to obtain as output a xed secret key that it is a prior known to the adversary; later on, the adversary may simply use this known private key to break anonymity (since, by denition, private key based revocation allows a verier to tell if a signature has been produced with a given private key). Yet another option is for the signer to behave honestly during the join protocol, but 13 later use a preloaded secret key to produce signatures. Once again, the adversary may use that known key and a signature to break platform anonymity.

To deal with these issues, our notion of SR-EPID is designed so that (i) the sanitizer participates to the join protocol contributing to the private key of the signer, (ii) each signature output by the signer carries a proof (for the sanitizer to verify) that the private key used for signing is the very same one obtained during the join protocol, and (iii) the sanitizer sanitizes signatures to avoid covert channel based on maliciously-sampled randomness.

The resulting syntax is a generalization of EPID that adds a Sanitize algorithm and modies the original Join and Sig algorithms.

2.2 Syntax of Subversion-Resilient EPID (SR-EPID)

We denote by hd;e;fi P_A;B;Cha;b;ci an interactive protocol P between parties A, B and C where a;b;c (resp. d;e;f) are the local inputs (resp. outputs) of A, B and C, respectively.

$$ \langle d,e,f\rangle\leftarrow P_{\mathcal{A},\mathcal{B},\mathcal{C}}\langle a,b,c\rangle $$

$$ d,e,f) $$

¹¹ In practical deployments a sanitizer may sanitize signatures of multiple signers and a single signer may have multiple sanitizers.

¹² For example, the anonymity denition focuses on an adversary that must tell which, out of two platforms, output the challenge signature.

¹³ Since anonymity must hold also against a malicious group authority, it is possible for the signer to hold one or more certied private keys.

An SR-EPID consists of an interactive protocol Join and algorithms: Init, Setup, Sig, Ver, Sanitize. All the algorithms (and the protocol) but Init take as input public parameters (generated by Init); for readability reasons, we keep this input implicit.

Init(1)! pub. This algorithm takes as input the security parameter and outputs public parameters pub.

$$ \mathsf{I n i t}(1^{\lambda})\to $$

Setup(pub)! (gpk*;*isk). This algorithm takes the public parameters pub and outputs a group public key gpk and an issuing secret key isk for the issuer I.

Join_I;Si;Mih(gpk*;isk);gpk;gpk)i ! hb;(b; svt_i);skii. This is a three-party protocol between the issuer I, a sanitizer S_iand a signer M_i. The issuer inputs (gpk;*isk), while the other parties only input gpk. At the end of the protocol, I obtains a bit b indicating if the protocol terminated successfully, M_iobtains private key sk_i, and S_iobtains a sanitizer verication token svt_iand the same bit b of I.

$$ {mathsf{J o i n}}{{\mathcal{I},,\mathcal{S}{i},\mathcal{M}{i}}}\langle(\mathsf{g p k},\mathsf{i s k}),\mathsf{g p k},\mathsf{g p k}\ \rangle;\to;\langle b,(b,\mathsf{s v t}{i}),\mathsf{s k}_{i}\rangle $$

$$ S_{i} $$

$$ \ \mathcal{M}_{i}. $$

$$ \mathsf{S k}_{i}. $$

$$ \ {mathcal M M}_{i} $$

$$ S_{i} $$

$$ \mathsf{S V t}_{i} $$

Sig(gpk*;sk_i;bsn;M;* SigRL)! ?=(;). The signing algorithm takes as input the group public key gpk, a private key sk_i, a basename bsn, a message M, and a signature based revocation list SigRL. It outputs a signature and a proof, or an error*?* (if SigRL contains a signature produced with skⁱ).

$$ (mathfrak\ell,\mathfrak{s k}{i},\mathfrak{b s n},M,\mathfrak{S i g R L})\to\bot/\big(\sigma,\pi{\sigma}\big) $$

$$ \mathsf{s k}_{i}. $$

$$ \pi_{\sigma} $$

Ver(gpk*;bsn;M;;* SigRL*;PrivRL)!* 0*=*1. The verication algorithm takes as input the group public key gpk, a basename bsn, a message M, a signature, a signature based revocation list SigRL, and a private key based revocation list PrivRL. It outputs 0 or 1 if is respectively an invalid or a valid signature on M.

$$ M,\sigma,\mathsf{S i g R L},\mathsf{P i i N R L})\to0/1 $$

0 Sanitize(gpk*;bsn;M;(;);SigRL;svt_i)! ?=. The sanitization algorithm takes as input the group public key gpk, a basename bsn, a message M, a signature with corresponding proof , a signature based revocation list SigRL, and a sanitizer verication token svt_i. It outputs 0 either?* or a sanitized signature.

$$ M,(\sigma,\pi_{\sigma}),\mathsf{S i g R L},\mathsf{S t t}_{i})\to\bot/\sigma^{\ } $$

$$ \pi_{\sigma:} $$

$$ \mathsf{s v t}_{i} $$

$$ \sigma^{\prime} $$

Link(gpk*;bsn;M₁;₁;M₂;₂)!* 0*=*1. The linking algorithm takes as input the group public key gpk, a basename bsn, and two message-signature-SigRL triples M₁;₁and M₂;₂. It outputs 1 if both signatures are valid and were created, on the same basename, by the same signer; it outputs 0 otherwise.

$$ M_{1},\sigma_{1},M_{2},\sigma_{2})\rightarrow0/1 $$

$$ M_{1},\sigma_{1} $$

$$ M_{2},\sigma_{2} $$

In our syntax, we assume PrivRL to be a set of private keys fsk_ig_i, and SigRL to be a set of triples f(bsn_i;M_i;_i)g_i, each consisting of a basename, a message and a signature. We dene two forms of correctness with and without revocation lists.

$$ {\mathsf{s k}{i}}{i} $$

$$ {(\mathsf{b s b}{i},M{i},\sigma_{i})}_{i} $$

Correctness (without revocation lists): To keep the syntax more light we let Sig(gpk*;sk;bsn;M*) be equal to Sig(gpk*;sk;bsn;M;;), and Ver(gpk;bsn;M;) be equal to Ver(gpk;bsn;M;;;;;). We say that an SR-EPID scheme satises (standard) correctness if for all pub Init(1), all (gpk;gsk) Setup(pub), all hb;(b; svt);ski* Joinh(gpk*;gsk);gpk;gpk)i such that b = 1, and for any basename bsn, message M, and any signature Sanitize(gpk;bsn;M;* Sig(gpk*;sk;bsn;M*);svt) we have that Ver(gpk;bsn;M;) = 1.

$$ M,\sigma,\emptyset,\emptyset) $$

$$ \leftarrow\operatorname{l i i t}(1^{\lambda}) $$

$$ (\mathsf{g p k},\mathsf{g s k})\leftarrow $$

Correctness (with revocation lists): We say that an SR-EPID scheme satises correctness if any signature produced by a non-revoked group member passes the verication procedure. More formally, for all pub Init(1), all (gpk*;gsk) Setup(pub), all hb;(b; svt);ski* Joinh(gpk*;gsk);gpk;gpk)i such that b = 1, and for any basename bsn, message M, private-key revocation list PrivRL and signature revocation list SigRL, and any signature Sanitize(gpk;bsn;M;* Sig(gpk*;sk;bsn;M;* SigRL)*;SigRL;*svt) we have:

$$ \leftarrow\ \ {sf l n i t1}^{\lambda}) $$

$$ (\sf{s k}\not\in r i v R L)\land\ (\Sigma\cap\sf{S i g R L}=\emptyset)\Rightarrow\sf{V e r}(\sf{g p k},\sf{b s n},M,\sigma,\sf{S i g R L},\sf{P r i v R L})=1 $$

where is the set of signatures produced with sk.

2.3 Subversion-resilient Security

The security of an SR-EPID scheme is dened by three main properties, namely anonymity, unforgeability, and non-frameability that are dened below.

We consider subverted signers that can arbitrarily behave during the join protocol and, in particular, abort the execution of the protocol. However, once the join protocol is completed we assume that signers, although subverted, maintain a correct \input-output behavior". That is, a subverted signer produces a valid signature to a message and basename, namely a signature that veries if the signer were not revoked, but that could be arbitrarily (and maliciously) distributed over the set of all valid signatures. We formalize this idea in the following assumption.

Assumption 1. Let be a SR-EPID. We assume that for any public parameter pub, any adversary A, any gpk and auxiliary information aux, and any (possibly adaptively chosen) sequence of tuples (bsn₁*;M₁*);:::; (bsn_q;M_q), let hb;(b⁰;svt);state₁i be a possible output of the join protocol Join_A;S;Mh(gpk*;aux*);gpk;(gpk*;aux*)i conditioned on b⁰ = 1 or a possible output of the join protocol Join_I;A;Mh(gpk*;aux*);gpk;(gpk*;aux*)i conditioned on b = 1 and let_i;state_i M_i(state_{i 1};M_i;bsn_i) for i = 1;:::;q then

$$ (\mathsf{b s n}{1},M{1}),\ldots,(\mathsf{b s n}{q},M{q}) $$

$$ \langle b,(b^{\prime},{\sf s v t}),{\sf s t a t e}_{1}\rangle $$

$$ \mathsf{J o i n}_{\mathcal{A},\mathcal{S},\mathcal{M}}\langle(\mathsf{g p k},a u x),\mathsf{g p k},(\mathsf{g p k},a u x)\rangle $$

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

$$ \mathcal {I}, \mathcal {A}, \mathcal {M} \langle (\mathrm {g p k}, a u x), \mathrm {g p k}, (\mathrm {g p k}, a u x) \rangle $$

$$ b,=,1 $$

$$ \sigma_{i},{\mathsf t a a t e}_{i}\ \leftarrow $$

$$ \mathcal{M}{i}(\mathsf{s t a t e}{i-1},M_{i},\mathsf{b s n}_{i}) $$

$$ i=1,\ldots,q $$

$$ \forall i=1,\ldots,q:\mathsf{V f}(\mathsf{g p k},M_{1},\mathsf{b s n}{1},\sigma{i})=1 $$

Assumption 1 models the fact that, if signers can be subverted, a signer should be considered safe as long as it does not return errors when it comes to generating signatures. The occurrence of such an error should alert a sanitizer anyway. First, such an error can occur if one of the signatures produced by the signer was included in the signature based revocation list: if the list was honestly created, it means that the signer has been revoked; if the list was maliciously crafted, then the signature request may constitute an attempt to deanonymize the signer. Second, if the errors are arbitrary then they inevitably enable to signal any kind of information from the signer.

Macros for the Join Protocol and Signature generation. As mentioned, the join protocol is a three-party protocol with the sanitizer being in the middle. To simplify the already heavy notation, we dene the macro Join(M; state_S;state_M;_I) which identies one full round of the join protocol from the issuer point of view with an honest sanitizer and a machine M. In more detail, the macro takes as input the description of the (possibly subverted) machine M, the state of the sanitizer state_S, the state of the machine state_Mand the message sent by the issuer_I, and it identies the following set of actions:

$$ \left(\mathcal{M},\mathsf{s t a t e}{\mathcal{S}},\mathsf{s t a t e}{\mathcal{M}},\gamma_{\mathcal{I}}\right) $$

$$ \mathrm {s t a t e} _ {\mathcal {S}}, $$

$$ \mathsf{s t a t e}_{\mathcal{M}} $$

$$ \gamma_{}} $$

Join(M; state_S;state_M;_I): 0 ⁰S 1.(^S;state) S : Join(gpk;state^S;^I); 0M 0 2.(_M;state) M : Join(gpk;state_M;^S); ⁰M 3.(^S;state⁰⁰_S) S : Join(gpk;state;_M); _0M 4.Output (state⁰⁰_S;state;_S).

$$ \underline{{(\mathcal{M},\mathsf{s t a t e}{\mathcal{S}},\mathsf{s t a t e}{\mathcal{M}},\gamma_{\mathcal{I}})}}: $$

$$ (\gamma_{\mathcal{S}}^{\prime},\mathsf{s t a t e}{\mathcal{S}}^{\prime})\leftarrow\mathcal{S}.\mathsf{J o i n}(\mathsf{g p k},\mathsf{s t a t e}{\mathcal{S}},\gamma_{\mathcal{I}}) $$

$$ \left(\gamma_ {\mathcal {M}}, \mathrm {s t a t e} _ {\mathcal {M}} ^ {\prime}\right) \leftarrow \mathcal {M}. \operatorname {J o i n} (\mathrm {g p k}, \mathrm {s t a t e} _ {\mathcal {M}}, \gamma_ {\mathcal {S}} ^ {\prime}); $$

$$ (\gamma_{\mathcal{S}},\sf{s t a t e}{\mathcal{S}}^{\prime\prime})\leftarrow\mathcal{S}.\sf{J o i n}(\sf{g p k},\sf{s t a t e}{\mathcal{M}}^{\prime},\gamma_{\mathcal{M}}); $$

$$ \text {O u t p u t} \left(\text {s t a t e} _ {\mathcal {S}} ^ {\prime \prime}, \text {s t a t e} _ {\mathcal {M}} ^ {\prime}, \gamma_ {\mathcal {S}}\right). $$

Notice the procedures additionally take as input the group public key gpk, which we keep implicit. Similarly, the signature procedure is a two-phase protocol between the signer and the sanitizer for which we dene the macro:

Sig(M; state^M;svt;bsn;M; SigRL): 0 0 ₀M 1.(*;;*state) M : Sig(state

$$ \mathbf{\overline{{\ \ (\ sigma{{'}},\ \pi_{\sigma}^{\prime},{\sf t a t e}{\mathcal{M}}^{\prime})\leftarrow\mathcal{M}.{\sf S i g}({\sf s t a t e}{\mathcal{M}},{\sf b s n},M,{\sf S i g R L})}}}. $$

$$ M^{*},(\sigma^{\prime},\pi_{\sigma}^{\prime}) $$

M 0 0 2. if svt 6=? then Sanitize(gpk*;bsn;M;* (;)*;SigRL;*svt);

$$ \sigma\leftarrow\sigma^{\prime}. $$

⁰ 3. else;

0M 4.Output (state*;*).

$$ ({\ \ {\ {{\mathsf{s t a t e}}}}_{\mathcal{M}}^{\prime}},\sigma) $$

The macro additionally checks in step 2 that svt is a valid string. We use this check to discriminate the case when the sanitizer is corrupted.

Subversion-Resilient Anonymity. This notion formalizes the idea that an adversarial issuer cannot identify a group member through the signatures it produces. Recall that we assume a signer M_ito be paired with a sanitizer S_i; we denote the platform constituted by M_iand S_iwith P_i. We assume M_ito be subverted, i.e., it runs an adversarially specied program, while S_iis honest. The case when both M_iand S_iare corrupted is meaningless for anonymity since the adversary controls all the relevant parties. The remaining case in which M_iis honest but S_iis corrupted is also hopeless for anonymity since a corrupted sanitizer could always maul the outputs of the signer in order to reveal its identity.

$$ \mathcal{M}_{i} $$

$$ \mathcal{M}_{i} $$

$$ \mathcal{S}_{i}; $$

$$ \ _i, $$

$$ p_{i} $$

$$ \mathcal{M}_{i} $$

$$ \ _{i} $$

$$ \mathcal{M}_{i} $$

$$ S_{i} $$

$$ \mathcal{M}_{i} $$

$$ S_{i} $$

We formalize subversion-resilient anonymity for SR-EPID in a security experiment that appears in Fig. 1, and we formally dene anonymity as follows.

Denition 1. Consider the experiment described in Fig. 1. We say that an SR-EPID is anony- mous if and only if for any PPT adversary A:

$$ i f $$

$$ \mathbf {A d v} _ {\mathcal {A}, \Pi} ^ {\mathrm {a n o n}} (\lambda) := | \Pr \left[ \mathbf {E x p} _ {\mathcal {A}, \Pi} ^ {\mathrm {a n o n}} (\lambda , 0) = 1 \right] - \Pr \left[ \mathbf {E x p} _ {\mathcal {A}, \Pi} ^ {\mathrm {a n o n}} (\lambda , 1) = 1 \right] | \in \operatorname {n e g l} (\lambda). $$

In the experiment we let M_ibe an adversarially specied program, yet, as argued above, we assume that it preserves the expected input-output functionality. Namely, there is a command M_i: Sig that is supposed to follow the input-output behavior of the Sig algorithm.

$$ \mathcal{M}_{i} $$

Here we provide an intuitive explanation of the anonymity experiment. The idea is that the adversary plays the role of the issuer, i.e., it selects the group public key, and it can do the following: (1) ask platforms with subverted signers to join the system; (2) ask platforms with subverted signers to sign messages; (3) corrupt platforms. For (1), it means that the adversary species the code of a signer M_ithat, together with an honest sanitizer S_i, run the Join protocol with the adversary playing the role of the issuer. For (2), a subverted signer M_iproduced a signature that is sanitized by S_iand then delivered to the adversary. Finally, (3) simply models a full corruption of the platform in which the adversary learns the secret key sk_iobtained by M_iat the end of its Join protocol.

$$ \mathcal{M}_{i} $$

$$ \mathcal {S} _ {i}, $$

$$ \mathcal{S}_{i} $$

$$ \ {mathcal M M}_{i} $$

$$ \mathcal{M}_{i} $$

$$ {\sf k}_{i} $$

The adversary can choose two platforms (P_i0; P_i1), a basename bsn , and a message M and it receives a sanitized signature on *M;*bsn produced by one of the two platforms. The goal of the adversary is to gure out which platform produced the signature. In order to avoid trivial attacks the two \challenge" platforms must be non-corrupted and none of their signatures can be included in the SigRL used to produce the challenge signature. Further, if the adversary has previously requested a signature with bsn form either platform, the challenger aborts. Similarly, after seeing

$$ \left(\mathcal{P}{i{0}},\mathcal{P}{i{1}}\right) $$

$$ M^{*} $$

$$ \mathsf{b s n^{*}} $$

$$ M^{},\flat\flat^{} $$ anon Experiment Exp_A;(;b) 1 : Ljoin;Lusr;Lcorr ;; post 0; Bad true 2 : pub Init(1); gpk A (pub); C(gpk;) 3 : (bsn*;M;i₀;i₁;SigRL ) A ^(gpk); post 1; 4 : if (i₀;;;;) 2= Lusr _ (i₁;;;) 2= Lusr then Bad true; 5 : if VerSigRL(gpk;SigRL ) = 0 then Bad true 6 : for j = 0;1 do : 7 : Retrieve (ij; Mij;state_ij;svtij;Bij) from Lusr; 8 : if bsn 2 Bij then Bad true 0ij 9 : (state;j*) Sig(Mij;state_ij;svtij;bsn;M; SigRL); 0ij 10 : Update (ij; Mij;state;svtij;Bij [fbsn g) in Lusr; 11 : if*?2f* 0*;1g* then Bad true elseb; C(gpk;) 12 : b⁰ A (^); 13 : if Bad = false return b⁰; else return ~b $ f0*;* 1g: Oracle C(gsk*;) 1 : Upon query (join;i;I*) : 2 : Retrieve (i; Mi;state_S;state_M) from Ljoin;; 3 : If not nd parse I = Mi and add (i; Mi; ?; ?) in Ljoin and return ; 0M 4 : (state⁰⁰S;state;S) Join(Mi;state_S;state_M;I); 0M 5 : Store (i; M_i;state⁰⁰_S;state) in L_join; 6 : if S = concluded then 0M 7 : svti state⁰⁰_S; store (i; Mi;state;svti;;) in Lusr; return ( S;svti); 8 : else return S : 9 : Upon query (sign*;i;* bsn*;M;* SigRL) : 10 : if (i;;;;) 2= Lusr then Bad true; ¹¹ : else retrieve (i; Mⁱ;stateⁱ;svtⁱ;Bⁱ) 2 L^usr; 0i ¹² : (state*;) Sig(M_i;state_i;svt_i;bsn;M;* SigRL); 0i 13 : Update (i; M_i;state;svt_i;B_i [fbsng); 14 : if post = 0 or i 62fi₀;i₁g return else let i = i and 2f0*;* 1g; 15 : if bsn = bsn then Bad true; 16 : Let i = i₁; and retrieve tuple (i; Mi;state_i;svti;Bi) 2 Lusr; 0i 17 : (state*;* ~) Sig(Mi;state_i;svti;bsn;M; SigRL); 0i 18 : Update (i; Mi;state;svti;Bi [fbsng) in Lusr; 19 : if*?2f;* ~g then Bad true; endif return; 20 : Upon query (corrupt*;i*) : 21 : if post = 1 ^ i 2fi₀;i₁g then Bad true; 22 : else retrieve (i; Mi;state_i;svti) from Lusr; 23 : move the tuple from Lusr to Lcor; 24 : return (state_i;svti):

$$ L_{j o i n},L_{u s r},L_{c o r r}\leftarrow\emptyset;\ p o s t\leftarrow0;\ \mathsf{B a d}\leftarrow\mathsf{t r u e} $$

$$ {\mathfrak{p u b}}\leftarrow{\sf I n I t}(1^{\lambda});,{\mathfrak{p p k}}\leftarrow{\cal A}({\sf{p u b}}); $$

$$ (\mathsf{b s n}^{},M^{},i_{0},i_{1},\mathsf{S i g R L}^{*})\leftarrow\mathcal{A}(\mathsf{g p k})^{\mathcal{C}(\mathsf{g p k},\cdot)}; $$

$$ \leftarrow1; $$

$$ (i_{0},,,,)\notin\mathit{L}{s s r r}\vee(i{1},,,*)\notin\mathit{L}_{s s r} $$

$$ \mathsf{V e r S i g R L}(\mathsf{g P k},\mathsf{S i g R L}^{*})=0 $$

$$ j=0,1 $$

$$ (i_{j},\mathcal{M}{i{j}},\mathsf{s t a t e}{i{j}},\mathsf{s v t}{i{j}},B_{i_{j}}) $$

$$ L_{u s r}; $$

$$ \mathsf{b s n}^{*}\in B_{i_{i}} $$

$$ \left(\mathrm {s t a t e} _ {i j} ^ {\prime}, \sigma_ {j}\right) \leftarrow \operatorname {S i g} \left(\mathcal {M} _ {i j}, \mathrm {s t a t e} _ {i j}, \mathrm {s v t} _ {i j}, \mathrm {b s n}, M, \mathrm {S i g R L}\right); $$

$$ L_{u s r}; $$

$$ (i_{j},\mathcal{M}{i{j}},{\sf{s t a t e}}{i{j}}^{\prime},{\sf{s v t}}{i{j}},B_{i_{j}}\cup{{\sf{b s n}}^{*}}. $$

$$ \bot\in{\sigma_{0},\sigma_{1}} $$

$$ \sigma^{*}\leftarrow\sigma_{b}; $$

$$ b^{\prime}\leftarrow\mathcal{A}(\sigma^{*})^{\mathcal{C}(\mathsf{g p k},\cdot)}; $$

$$ \tilde{b}\gets!{!,\mathfrak{s},{0,1} $$

$$ b^{\prime}; $$

$$ \mathcal{C}(\mathsf{g s k},\cdot) $$

$$ (\mathtt{j o i n},i,\gamma_{\mathcal{I}}) $$

$$ \left(,mathcal M{}i,\mathsf{s t a t e}{\mathcal{S}},\mathsf{s t a t e}{\mathcal M}\right) $$

$$ L_{j o i n},\vdots $$

$$ \boldsymbol{\gamma}{\mathcal{I}}=\mathcal{M}{i} $$

$$ (i,\mathcal{M}_{i},\bot,\bot) $$

$$ L_{j o i n} $$

$$ (\sf{s t a t e}{\mathcal{S}}^{\prime\prime},\sf{s t a t e}{\mathcal{M}}^{\prime},\gamma_{\mathcal{S}})\leftarrow\sf{J o i n}(\mathcal{M}{i},\sf{s t a t e}{\mathcal{S}},\sf{s t a t e}{\mathcal{M}},\gamma{\mathcal{I}}); $$

$$ \ i,\mathcal{M}{i},\mathsf{s t a t e}{\mathcal{S}}^{\prime\prime},\mathsf{s t a t e}_{\mathcal{M}}^{\prime}\big) $$

$$ L_{\mathrm{}{j o i n}}; $$

$$ \mathsf{s v t}{i}\leftarrow\mathsf{s t a t e}{\mathcal{S}}^{\prime\prime}. $$

$$ L_{u s r}; $$

$$ (i,\mathcal{M}{i},\mathsf{s t a t e}{\mathcal{M}}^{\prime},\mathsf{s v t}_{i},\emptyset) $$

$$ (\gamma_{\mathcal{S}},\mathsf{s v t}_{i}); $$

$$ \ i,,,*,\ast\notin L_{u smathrm r{}} $$

$$ (i,\mathcal{M}{i},\mathsf{s t a t e}{i},\mathsf{s v t}{i},B{i})\in L_{u s r}; $$

$$ (\mathsf{s t a t e}{i}^{\prime},\sigma)\leftarrow\mathsf{S i g}(\mathcal{M}{i},\mathsf{s t a t e}_{i}, $$

$$ M,\mathsf{S i g R L}) $$

$$ {\tt{J p d a t e}}\left(i,{mathcal{M}}{i},{\mathsf{s t a t e}}{i}^{\prime},{\mathsf{s w t}}{i},B{i}\cup\ {{\tt{h s n}}}\right); $$

$$ i=i_{\beta} $$

$$ i\not\in{i_{0},i_{1}} $$

$$ \beta\in{0,1} $$

$$ {sf b n n}={\sf b s n}^{*} $$

$$ i=i_{1-\beta} $$

$$ (i_{\beta},\mathcal{M}{i{\beta}},{mathsf{s t a t e}}{i{\beta}},{\mathsf{s u t}}{i{\beta}},B_{i_{\beta}})\in L_{u s r}; $$

$$ (\mathtt{s t a t e}{i{\beta}}^{\prime},\tilde{\sigma})\xleftarrow{}\mathsf{S i g}(\mathcal{M}{i{\beta}},\mathtt{s t a t e}{i{\beta}},\mathtt{s v t}{i{\beta}},\mathtt{b s n},M,\mathtt{S i g R L}) $$

$$ \ {bf p d d t e e}\ (i_{\beta},{\mathcal M}{i{\beta}},{\sf s t a t e}{i{\beta}}^{\prime},{\sf s v t}{i{\beta}},{B{i_{\beta}}}\cup{{\sf b s n}})\mathrm{}{i n}L_{u s r}; $$

$$ \bot\in\left{\sigma,\tilde{\sigma}\right} $$

$$ \sigma, $$

$$ p o s t=1\land i\in{i_{0},i_{1}} $$

$$ (i,\mathcal{M}{i},\mathsf{s t a t e}{i},\mathsf{s v t}_{i}) $$

$$ \ _{u s r}; $$

$$ L_{u s r} $$

$$ L_{\mathrm{}{c o r}}; $$

$$ (\mathsf{s t a t e}{i},\mathsf{s v t}{i}) $$

Fig. 1: Subversion-resilient anonymity experiment.

the challenge signature, the adversary may not ask for a signature by any of the challenge platforms on basename bsn .

Technical details. The structure is the one depicted earlier: the adversary chooses the group public key on input the public parameters and then starts interacting with the oracle C. The experiment maintains lists L_join;L_usr;L_corrto bookkeep information on the state of the Join protocol sessions, and the list of non-corrupted and corrupted platforms, respectively. Also, it maintains a ag Bad, initialized to false, which is turned to true whenever the adversary violates the rules of the experiments (see below).

$$ L_{j o i n},L_{u s r},L_{c o r r} $$

At some point the adversary outputs a message M, a basename bsn , and two indices i₀;i₁, along with a signature revocation list SigRL ; it receives a sanitized signature generated using the anon subverted signer M^ib. In line 8 of Exp^A;(;b) we ensure that the adversary did not previously query for a signature with basename bsn by one of the challenge platforms; if that is the case, the anon adversary could trivially win by using the Link algorithm. In line 11 of Exp_A;(;b) we ensure that both challenge platforms generate valid signatures, after sanitization. Indeed if a dierence would occur (e.g., one of them is*?*), the adversary could trivially win the game. For example, this would be the case if the SigRL chosen by A would contain a signature from, e.g., M_i0. Similar checks are done in lines 15{19 of the C oracle upon a signing query that involves one of the challenge platforms, say i₁. The code of those lines essentially ensure that the queried basename is not the challenge one, and that the other challenge platform i would generate a signature on the same message M that is valid i so is the one generated by i₁. Again if such a dierence would occur the adversary could trivially distinguish and win the experiment. Similarly to the other case, this could occur if the queried SigRL contains a signature of (only) one of the challenge platforms.

$$ M^{*} $$

$$ \mathsf{b s n^{*}} $$

$$ i_{0},i_{1} $$

$$ \mathsf{S i g R L}^{*} $$

$$ \mathcal{M}{i{b}} $$

$$ \operatorname {E x p} _ {\mathcal {A}, \Pi} ^ {\mathrm {a n o n}} (\lambda , b) $$

$$ \mathsf{b s n^{*}} $$

$$ \operatorname {E x p} _ {\mathcal {A}, \Pi} ^ {\mathrm {a n o n}} (\lambda , b) $$

$$ \mathrm{e.g.},\mathcal{M}{i{0}} $$

$$ i_{1-\beta} $$

$$ i_{\beta} $$

$$ i_{1-\beta} $$

We stress that the mechanism that uses the verication tokens is necessary. Indeed, consider the denition above where the svt and the proof are missing. An attacker can rst performs two join protocols with two subverted machines M~ and M~ with hardcoded secret keys sk~ (resp. sk) 1 ₂ 1 2 that during joining time act honestly, thus obtaining new fresh secret keys, but that compute valid signature using the hardcoded secret keys. Suppose the scheme has a secret-key based revocation mechanism, then the adversary that knows sk and sk~ can easily distinguish which machine pro- 1 2 duced the signature. In particular, it could verify the challenge signature using the revocation list fsk~ g. Because the signatures are anonymous, the sanitizer, which only posses public information, 1 has no way to identify that a dierent secret key has been used and avoid this attack.

$$ \pi_{\sigma} $$

$$ \dot{\mathcal{M}}_{1} $$

$$ \mathbf{\dot{M}}_{2} $$

$$ \mathrm {s k} _ {1} (\text {r e s p .} \mathrm {s k} _ {2}) $$

$$ \mathrm {s k} _ {1} $$

$$ \tilde{k}_{2} $$

$$ {\tilde{\mathsf{s k}}_{1}} $$

Finally we notice that the model without verication token mechanism, after some necessary cosmetic changes, ts with the cryptographic reverse rewall framework. In the lingo of [22], the sanitizer of a scheme satisfying the anonymity property which works without the verication token mechanism, is a cryptographic reverse rewall that weakly preserve the anonymity property for the signer S.

Another aspect of the anonymity experiment that we would like to point out is that the adversary receives the verication token immediately after the Join protocol is over. This models the fact the adversary could have access to the internal state of an honest sanitizer (except for its random tape), and this does not break anonymity.

Subversion-Resilient Unforgeability. This notion formalizes the idea that an adversary who does not control the issuer cannot generate signatures on new messages on behalf of non-corrupted platforms. To model subversion attacks, we let the platform signer M_ibe an adversarially specied program. The sanitizer S_iis instead honest (unless the platform is fully corrupted).

$$ \mathcal{M}_{i} $$

$$ S_{i} $$

Here we provide an intuition of the notion. The idea is that the adversary receives the group public key, and it can do the following: (1) ask platforms with subverted signers to join the system; (2) ask corrupted platforms to join the system; (3) ask platforms with subverted signer to sign messages; (4) corrupt platforms. For (1), it means that the adversary species the code of a signer M_iand that signer together with sanitizer S_i, run the Join protocol where both the issuer and S_i are controlled by the challenger. For (2), the adversary runs the Join protocol with the challenger playing the role of the issuer, whereas both the signer M_iand the sanitizer S_iare fully controlled by the adversary. For (3), the adversary asks a platform that joined the system to create a signature using the subverted signing algorithm (specied in M_iat Join time), this signature is sanitized by S_iand given to the adversary. Finally, (4) simply models a full corruption of the platform in which the adversary learns the secret key sk_iobtained by M_iat the end of its Join protocol¹⁴

$$ \ {mathcal M M}_{i} $$

$$ {\mathcal{S}}_{i}. $$

$$ S_{i} $$

$$ \ _{i} $$

$$ \mathcal{M}_{i} $$

$$ \mathcal{M}_{i} $$

$$ \ _{i} $$

$$ {\sf{S k}}_{i} $$

$$ \mathcal{M}_{i} $$

The adversary’s goal is to produce a valid signature on a basename-message tuple bsn*;M*. On the one hand, we cannot require the tuple bsn*;M* to be fresh, since it is reasonable to assume that multiple platforms may sign the same bsn*;M*. On the other hand, strong unforgeability is impossible, as we require that the signatures must be valid before and after sanitization. To satisfy these two apparently contrasting requirements simultaneously, we instead require that the adversary’s forgery does not link to any of the other queried signatures on the same basenamemessage tuple. This essentially guarantees that the forgery is not a trivial rerandomization of signature obtained through a signing query.

$$ M^{*} $$

$$ \mathsf{b s n}^{},M^{} $$

$$ M^{*} $$

Since an SR-EPID is a (kind of) group signature and in the above game the adversary may have learnt the secret keys of some group members, we add some additional checks to formalize what is a forgery, namely to avoid trivial attacks that are unavoidable in this model. Intuitively, we want that the signature must verify with respect to a private-key revocation list PrivRL (resp. signature-based revocation list SigRL ) that includes the secret keys of (resp. a signature from) all corrupted group members. These corrupted group members include both the ones that honestly joined the system and were later corrupted, and those that were already corrupted (i.e., adversarially controlled) at join time. Modeling which keys should be revoked is not straightforward though. The rst issue is that in case of a corrupted platform joining the group, the challenger does not know what is the key obtained by the adversary. Essentially, unless we revoke exactly that key or a signature produced with that key, the adversary is able to create valid signatures on any message of its choice. The second issue is similar and involves cases when a platform with a subverted signer joins the group: the challenger obtains a secret key skⁱfrom the signer Mⁱat the end of the Join protocol, but Mⁱ 15 is subverted and thus we have no guarantee that sk_iis the \real" secret key. To dene forgeries, we solve these issues by assuming the existence of an extractor that, by knowing a trapdoor and seeing the transcript of the Join protocol between the issuer and the sanitizer, can extract a token uniquely linkable (via an ecient procedure) to the secret key that is supposed to correspond to such transcript. This denition is close to the notion of uniquely identiable transcripts used by [6] for DAA schemes. We stress that the extractor does not exist in the real world and is only an artifact 16 of the security denition. A practical interpretation of our denition is that unforgeability is guaranteed under the assumption that the revocation system is \perfect", namely that one revokes

$$ \ r i v R L^{*} $$

$$ \mathsf{S i g R L}^{*}) $$

$$ \ \mathsf{S k}_{{i}} $$

$$ \mathcal{M}_{i} $$

$$ \mathcal{M}_{i} $$

$$ {\sf k}_{i} $$

¹⁴ Here the corruption is adaptive in the sense that the platform rst joined honestly and later can be corrupted by the adversary but we assume secure erasure of the previous states of the sanitizer.

¹⁵ For instance, Mi may store locally only an obfuscated or encrypted version of the secret key.

$$ \mathcal{M}_{i} $$

¹⁶ More precisely, an extractor does not exist if in the real world the Init algorithm is realized in a trusted manner, akin to CRS generation in NIZK proof systems.

all the secret keys, or signatures produced by those secret keys, that an adversary obtained by interacting with the issuer in the Join protocol.

We formalize subversion-resilient unforgeability for SR-EPID via the experiment of Fig. 2, and we formally dene unforgeability as follows.

Denition 2. Consider the experiment described in Fig. 2. We say that an SR-EPID is un- forgeable if there exist PPT algorithms CheckTK*,* CheckSig*, and a PPT extractor E* = (E₀; E₁) such that the following properties hold:

$$ \mathcal{E}=(\mathcal{E}{0},\mathcal{E}{1}) $$

1.For any pair of keys (gpk*;isk) in the support of Setup(pub) and for any (even adversarial) tk;sk₁;sk₂ it holds (CheckTK(gpk;sk₁;tk) = 1 ^ CheckTK(gpk;sk₂;tk) = 2))* sk₁ = sk₂*.* (Namely, any tk is uniquely associated to one and only one sk*.)*

$$ \mathsf{c k T K}(\mathsf{g p k},\mathsf{s k}{1},\mathsf{t k})\ =\ 1\ \wedge\ \mathsf{C h e c k T K}(\mathsf{g p k},\mathsf{s k}{2},\mathsf{t k})\ =\ 2)\ \Rightarrow\ \mathsf{s k}{1}\ =\ \mathsf{s k}{2} $$

$$ \mathsf{s k}{1},\mathsf{s k}{2} $$

2.For any pair of keys (gpk*;isk) in the support of Setup(pub) and for any (even adversarial) tk;sk;M;* bsn*;;* SigRL*;PrivRL such that Vf(gpk;bsn;M;;* SigRL*;PrivRL) = 1 and Vf(gpk;bsn;M;* ;SigRL;PrivRL[fskg) = 0*, it is always the case that* CheckTK(gpk*;sk;tk) = 0_CheckSig(gpk;tk;) = 1. (Namely, the token* tk and the algorithm CheckSig allow to verify if a signature comes from a specic secret key.)

$$ \sigma , \operatorname {S i g R L}, \operatorname {P r i v R L} \cup {\mathrm {s k} }) = 0 $$

unf unf 3.For any PPT adversary A, Adv_A;E;() := Pr Exp_A;E;() = 1 2 negl().

$$ \downarrow,\ {bf\ A d v}{{mathcal\mathcal A{A},\mathcal{E},\mathcal{I I}}}^{\mathrm{{{t n f}}}}(\lambda):=\operatorname*{P r}\left[{{\bf E x p}{\mathcal{\mathcal{A},\mathcal{E},\mathcal{I I}}}^{\mathrm{}{{t n f}}}}(\lambda)=1\right]{\bf{\in\ n}e g g((lambdalambda)} $$

$ $ 4.The distribution fpub Init(1)g_2Nand fpubjpub*;*tp E₀(1)g_2Nare computationally in- distinguishable.

$$ \leftarrow^ {$} \operatorname {I n i t} \left(1 ^ {\lambda}\right) } _ {\lambda \in \mathbb {N}} $$

$$ \mathsf{t p}\overset{\S}{\leftarrow}\mathcal{E}{0}(1^{\lambda})}{\lambda\in\mathbb{N}} $$

Technical details. Besides the use of the extractor, the security experiment is rather technical in some of its parts. Here we explain the main technicalities. As mentioned earlier, the structure of the experiment is that the adversary receives the group public key and then starts interacting with the oracle. The experiment maintains lists L_join;L_usr;L_corr;L_msgto bookkeep information on the state of the Join protocol sessions, the list of uncorrupted and corrupted platforms respectively, and the list of the messages on which the adversary obtained signatures.

$$ L_{j o i n},L_{u s r},L_{c o r r},L_{m s g} $$

After interacting with the oracle, the adversary outputs a message M, a basename bsn , a signature and revocation lists PrivRL*;*SigRL . The adversary wins if either event (4), or the conjunction of events (1), (2) and (3) occur. Intuitively, event (4) means that the adversary has \fooled" the extractor. Namely, the adversary produced a secret key sk (provided in the privatekey revocation list PrivRL ) that the algorithm CheckTK recognizes as associated to a token tk extracted by E₁, but sk is not a valid signing key. In other words, our denition requires that any secret key¹⁷ extracted by E₁ should be valid. For the other winning case, events (2) and (3) are a generalization of the classical winning condition of digital signatures, i.e. where the adversary returns a valid signature on a new message. The conjunction of event (2) and (3) are more general than the classical unforgeability notion because instead of considering as new just the message, we also include the basename, and, more importantly, the fact that the forged signature apparently comes from a machine that either has never been set up or that has never signed the basenamemessage tuple.

$$ \sigma^{*} $$

$$ \mathsf{P r i v R L}^{},\mathsf{S i g R L}^{} $$

$$ M^{*}, $$

$$ \mathsf{b s n^{*}}. $$

$$ \mathcal{E}_{1} $$

$$ \mathcal{E}_{1} $$

Event (1) instead is there to avoid trivial attacks due to the possibility of corrupting group members. Basically, (1) ensures that for any corrupted platform we have either its secret key in PrivRL or a signature produced by that platform in SigRL . For the latter statement to be eciently checkable in the experiment we require the existence of an algorithm CheckSig for this purpose and that works with the token tk extracted by E₁.

$$ \mathsf{S i g R L}^{*} $$

$$ \mathsf{P r i v R L}^{*} $$

$$ \mathcal{E}_{1} $$

¹⁷ Precisely, E extracts a token tk linked to sk.

$$ \mathcal{E} $$ unf Experiment Exp_A;E;(): $ 1 : Ljoin*;Lusr;Lcorr;Lmsg ;; (pub;tp) E 0(1);* (gpk;gsk) Setup(pub); C(sk;) 2 : (bsn*;M;;PrivRL;SigRL ) A (gpk^); 3 : R f tki* : (i;;;;tki) 2 Lcorrg; 4 : return 1 if and only if ((1) ^ (2) ^ (3)) _ (4) : 5 : (1) 8tk2 R : (9sk2PrivRL : CheckTK(gpk*;sk;tk) = 1) OR (9 2 SigRL : CheckSig(gpk;tk;) = 1) 6 : (2) Ver(gpk;bsn;M;;SigRL;PrivRL ) = 1 7 : (3) 8(;bsn;M;) 2 Lmsg : Link(gpk;bsn;M;;M;) = 0 8 : (4) 9sk 2 PrivRL and tk 2 R such that CheckTK(gpk;sk;tk) = 1 but CheckSK(gpk;sk) = 0:* Oracle C(gsk*;) 1 : Upon query (honest join;i; Mi) : 2 : if 9(i;;;;) 2 Lusr [ Lcorr then return?; 3 : hb;(b; svti*);stateii JoinC;C;Mih(gpk*;isk);gpk;gpki*; 4 : let be the issuer-sanitizer transcript 5 : if b = 1 then tki E₁(tp*;); Lusr Lusr [ (i; Mi;state_i;svti;tki); 6 : return svti* 7 : Upon query (dishonestP join*;i;) : 8 : if (i;;;) 62 Ljoin; then Ljoin Ljoin [ (i; (gpk;gsk);;); 9 : Retrieve (i; state^I;;) from L^join; 0I 0I 10 : ( I;state) I : Join(stateI;); stateIstate; k(;I*); 11 : Update (i; state_I;;) in Ljoin; 12 : if I = concluded*;* then tki E 1(tp*;); store (i; ?; ?; ?; tki*) in Lcorr: 13 : Upon query (dishonestS join*;i; U;) : = U2fI; Mg 14 : if (i;;;) 62 Ljoin then Ljoin Ljoin [ (i; (gpk;gsk);;); 15 : Retrieve (i; state^I;state^M;) from L^join; 0U 0U 16 : ( U;state) U : Join(stateU;); stateUstate; if U = I then k(;I*); 17 : Update (i; stateI*;state_M;) in Ljoin; 18 : if U = I^ I = concluded;* then : 19 : tki E 1(tp*;); skistateM; store (i;:M; sk_i; ?;* tki) in Lusr: 20 : Upon query (sign*;i;* bsn*;M;* SigRL) : ²¹ : Retrieve the tuple (i; Mⁱ;stateⁱ;svtⁱ;tkⁱ) from L^usr; if not found return?; 0i ²² : (state*;) Sig(M_i;state_i;svtⁱ;bsn;M;* SigRL); 0i 23 : Lmsg L_msg [ (i; bsn*;M;); update(i; M_i;state;svt_i;tk_i); return : 24 : Upon query (corrupt;i*) : 25 : Retrieve (i; Mi;state_i;svti;tki) from Lusr; move the tuple from Lusr to Lcor; 26 : return state_i: Fig. 2: Subversion-resilient unforgeability experiment. The algorithm CheckSK(gpk*;*sk) is a short-

$$ \mathbf{E x p}_{\mathcal{A},\mathcal{E},\varPi}^{\mathsf{u n f}}(\lambda)\colon $$

$$ L_{j o i n},L_{w s r},L_{c o r r},L_{m s g}\xleftarrow{}\emptyset;(\mathbf{p u b},\mathbf{t p})\xleftarrow{}\mathcal{E}_{0}(1^{\lambda});(\mathbf{g p k},\mathbf{g s k})\xleftarrow{}\ {}\mathtt{S e t u p}(\mathbf{p u b}); $$

$$ (\mathsf{b s n}^{},M^{},\sigma^{},\mathsf{P r i v R L}^{},\mathsf{S i g R L}^{*})\leftarrow\mathcal{A}(\mathsf{g p k})^{\mathcal{C}(\mathsf{s k},\cdot)}; $$

$$ R \leftarrow \left{\mathrm {t k} _ {i}: (i, *, *, *, \mathrm {t k} _ {i}) \in L _ {\text {c o r r}} \right}; $$

$$ \mathfrak{f}\left((1)\wedge(2)\wedge(3)\right)\vee\big(4) $$

$$ \forall\mathsf{t k\ {in\mathrm R:\ }}(exists mathsf s k\ {\in}\mathsf{P r i v R L}{^\ *}:\mathsf{C h e c k T K}(\mathsf{g p k},\mathsf{s k},\mathsf{t k})=1) $$

$$ \mathsf{V e r}(\mathsf{g p k},\mathsf{b s n}^{},M^{},\sigma^{},\mathsf{S i g R L}^{},\mathsf{P r i v R L}^{*})=1 $$

$$ \forall(,\mathsf{b s n}^{},M^{},\sigma)\in L_{m s g}:\mathsf{L i n k}(\mathsf{g p k},\mathsf{b s n}^{},M^{},\sigma^{},M^{*},\sigma)=0 $$

$$ \in\ {mathsf P P i v R L}^{*} $$

$$ \mathsf{C h e c k S K}(\mathsf{g p k},\mathsf{s k})=0. $$

$$ \mathsf k\in R $$

$$ \mathbf{j j i n},i,\mathcal{M}_{i}) $$

$$ \exists(i,,,,)\in L_{u s r}\cup L_{c o r r} $$

$$ \langle b, \left(b, \mathrm {s v t} _ {i}\right), \mathrm {s t a t e} _ {i} \rangle \leftarrow \operatorname {J o i n} _ {\mathcal {C}, \mathcal {C}, \mathcal {M} _ {i}} \langle (\mathrm {g p k}, \mathrm {i s k}), \mathrm {g p k}, \mathrm {g p k} \rangle $$

$$ b=1\ {\bf t h e n}\ \ {\sf t k}{i}{\leftarrow}{mathcal}E{1}({\sf t p},\tau);\ L_{u s r}{\leftarrow}L_{u s r}\cup(i,{\mathcal{M}}{i},{\sf s t a t e}{i},{\sf s v t}{i},{\sf t k}{i}); $$

$$ (i,,,*)\not\in L_{\ i o i n},\ {mathbf{t h e n}}\ \ L_{j o i n}\leftarrow L_{j o i n}\cup(i,(\mathsf{g p k},\mathsf{g s k}),\xi,\xi); $$

$$ L_{\mathrm{}{j o i n}}; $$

$$ (i,{\sf s t a t e}_{\mathcal{I}},\xi,\tau) $$

$$ \mathrm {c a t e} _ {\mathcal {I}} \leftarrow \mathrm {s t a t e} _ {\mathcal {I}} ^ {\prime}; \tau \leftarrow \tau | (\gamma , \gamma_ {\mathcal {I}}); $$

$$ (\gamma_{\mathcal{I}},\sf{s t a t e}{\mathcal{I}}^{\prime})\leftarrow\mathcal{I}.\sf{J o i n}(\sf{s t a t e}{\mathcal{I}},\gamma) $$

$$ \mathrm {p d a t e} (i, \mathbf {s t a t e} _ {\mathcal {I}}, \xi , \tau) $$

$$ L_{j o i n}; $$

$$ \gamma_{\mathcal{I}}={\sf c o n c l u d e d} $$

$$ \mathsf{t k}{i}\leftarrow\mathcal{E}{1}(\mathsf{t p},\tau) $$

$$ (i,\bot,\bot,\bot,\mathsf{t k}_{i}) $$

$$ L_{c o r r.} $$

$$ i,\mathcal{U},\gamma):/^{*},\mathcal{U}\in{\mathcal{I},\mathcal{M}} $$

$$ L_{j o i n}\gets L_{j o i n}\cup(i,(\mathsf{g p k},\mathsf{g s k}),\xi,\xi); $$

$$ \big(i,,,*\big)\not\in L_{j o i n} $$

$$ L_{\mathrm{}{j o i n}}; $$

$$ (\gamma_{\mathcal{U}},\mathsf{s t a r e}{\ell}^{\prime})\leftarrow\mathcal{U}\ell\dot{\mathbb{J}}\mathsf{o l i n}(\mathsf{s t a r e}{\ell}{}{\ell},\gamma);\ \mathsf{s t a r e}{\ell}\leftarrow\mathsf{s t a r e}{\ell}{}{\ell}^{\prime};\ \mathbf{i f}\ \mathcal{U}=\mathcal{I}\ \mathbf{t h e n}\ \ \tau\leftarrow\tau|(\gamma,\gamma_{\mathcal{X}}); $$

$$ (i,{\sf s t a t e}{\mathcal{I}},{\sf s t a t e}{\mathcal{M}},\tau) $$

$$ L_{\mathrm{}{j o i n}}; $$

$$ \mathcal{U}=\mathcal{I}\wedge\gamma_{\mathcal{I}}=\mathsf{c o r} $$

$$ \leftarrow{\mathcal{E}}{1}({\mathsf{t p}},\tau);{\mathsf{s k}}{i}\leftarrow{\mathsf{s t a t e}}_{\mathcal{M}}; $$

$$ (i,\varPi.\mathcal{M},\mathsf{s k}{i},\bot,\mathsf{t k}{i}) $$

$$ L_{u s r} $$

$$ (\mathtt{s i g n},i,\mathtt{b s n},M,\mathsf{S i g R L}) $$

$$ (i,\mathcal{M}{i},\mathsf{s t a t e}{i},\mathsf{s v t}{i},\mathsf{t k}{i}) $$

$$ \ _{\mathrm{}{u s r}}, $$

$$ \bot; $$

$$ (\mathsf{s t a t e}{i}^{\prime},\sigma)\leftarrow\mathsf{S i g}(\mathcal{M}{i},\mathsf{s t a t e}{i},\mathsf{s v t}{i},\mathsf{b s n},M,\mathsf{S i g R L}); $$

$$ L_{m s g}\leftarrow L_{m s g}\cup(i,\mathsf{b s n},M,\sigma);\ \operatorname{u p d a t e}(i,\mathcal{M}{i},\mathsf{s t a t e}{i}^{\prime},\mathsf{s v t}{i},\mathsf{t k}{i}); $$

$$ {\boldsymbol{\sigma}}. $$

$$ (i,\mathcal{M}{i},\mathsf{s t a t e}{i},\mathsf{s v t}{i},\mathsf{t k}{i}) $$

$$ L_{u s r}; $$

$$ L_{u s r} $$

$$ L_{\mathrm{}{c o r}}, $$

$$ 1\mathrm{e}_{i}. $$

hand for the following process: sample a random message, generate a signature on it using sk and output 1 i the signature veries. The symbol denotes the empty string.

With honest join queries the adversary species the code of a signer M_i, which then runs the Join protocol with an honest issuer and an honest sanitizer controlled by the challenger. At the end, if the issuer accepts, we extract a secret-key token tk_ifrom the transcript of the Join protocol, and we store information about M_i, its state, the verication token and the extracted secret-key token. The verication token svt_iis also returned to the adversary.

$$ {\mathcal{M}}_{i}. $$

$$ \ {\sf t k}_{i} $$

$$ \tau $$

$$ \ \mathcal{M}_{i}. $$

$$ \mathsf{s v t}_{i} $$

With dishonestP join queries the adversary can let a fully corrupted platform (i.e., both M_i and S_iare under its control) join the group. In this case, the adversary runs the join protocol with the honest issuer controlled by the challenger: the oracle allows the adversary to start a Join session and then sends one message,, at a time; lines 9{11 formalize this step-by-step execution of the honest issuer on each message sent by the adversary on behalf of S_i. At the end, if the issuer accepts, we extract a secret-key token tk_ifrom the transcript of the Join protocol, and we store this token in the list L_corrof corrupted users.

$$ \ S{{}i} $$

$$ \mathcal{M}_{i} $$

$$ \gamma, $$

$$ S_{i} $$

$$ \mathsf{t k}_{i} $$

$$ L_{c o r r} $$

$$ \tau $$

With dishonestS join queries we consider the case in which the adversary fully controls the sanitizer but the signer is not subverted. In this case, the oracle allows the adversary to run in the Join protocol with the honest issuer and honest signer. This is done by letting the adversary send messages to either M or I; lines 15{17 formalize this step-by-step execution of the honest issuer and honest signer on each message sent by the corrupted sanitizer. At the end, if the issuer accepts, we extract a secret-key token tk_ifrom the transcript of the Join protocol, and we store all the relevant information in the list L_usrof honest platforms. Note that in this case we do not necessarily know the verication token since this is received by the sanitizer, which is the adversary.

$$ \mathcal {I}; $$

$$ \gamma $$

$$ \tau $$

$$ \mathrm {t k} _ {i} $$

$$ L{{}}_u s r r $$

For sign queries, the oracle rst checks that the platform has joined the system and if so it lets 0 0 the (possibly subverted) signer M_igenerate a signature and corresponding proof. Next, if svt_i6=? the signature is sanitized and given to the adversary, otherwise a non-sanitized signature is returned. Notice that the case svt_i=? (when i is in L_usr) can occur only if the platform joined the system using a dishonestS join query, in which case the sanitizer is controlled by the adversary but { we recall { the signer is not subverted.

$$ \pi_{\sigma}^{\prime} $$

$$ \ {mathcal M M}_{i} $$

$$ \sigma^{\prime} $$

$$ \mathsf{s v t}_{i}\neq\bot $$

$$ \mathsf{s v t}_{i}=\bot $$

$$ L_{u s r}) $$

Finally corrupt queries allow the adversary to corrupt an existing platform, which may have joined through either a honest join or dishonestS join query. As a result, the adversary learns the internal state of the signer, which is supposed to contain the secret key (note that the state of the sanitizer, that is the verication token, was already returned after the Join).

Subversion-Resilient Unforgeability in the Random Oracle Model. In order to capture also constructions in the random oracle model (ROM)|as ours|we provide a suitable adaptation of the unforgeability denition. A dedicated ROM-based denition is needed in order to consider extractors that may simulate, and program, the random oracle. The ROM denition is essentially the same as Def 2, except that condition (3) is modied to account for the programmability powers granted to the extractor. More in details, all the random oracle queries (both made by the adversary and by the corrupted signer M_i) are passed to the extractor, which is now a stateful machine; the extractor must provide a view to the adversary that is indistinguishable from the real world view, where the ROM outputs uniformly random strings. To formalize this, we consider a dummy extractor E~ that (i) initializes the public parameters as done by the SR-EPID scheme, and (ii) it does not program the ROM answers, but simply outputs uniformly random values. We additionally require that the view of the adversary in an execution of the experiment with the extractor and the view of the adversary in an execution of the experiment with the dummy extractor are indistinguishable.

$$ \mathcal{M}_{i}) $$

$$ \tilde{\varepsilon} $$

Denition 3(Unforgeability in the ROM.). Consider a game similar to Fig 2 where addi- tionally the extractor can program the random oracle. Namely, all the queries to the random oracle

made by A are re-directed and answered by the extractor E. We say that an SR-EPID scheme is unforgeable in the ROM if conditions (1), (2), (3) and (4) of Def. 2 hold, and additionally, the unf view of the adversary at the end of the experiment Exp_A;E;(1) and the view of the adversary at unf the end of the experiment Exp_~(1) are computationally indistinguishable. A;E;

$$ (4) $$

$$ \operatorname {E x p} _ {\mathcal {A}, \mathcal {E}, \Pi} ^ {\mathrm {u n f}} \left(1 ^ {\lambda}\right) $$

$$ \mathbf {E x p} _ {\mathcal {A}, \tilde {\mathcal {E}}, \varPi} ^ {\mathrm {u n f}} \left(1 ^ {\lambda}\right) $$

Comparison with Unforgeability of EPID. The notion of unforgeability dened above closely follows the one dened for EPID in [8], with the following main dierences. First, in [8] there is no sanitizer. Second, in [8] the adversary cannot specify a subverted signer, namely honest join and sign queries are executed according to the protocol description. Third, valid forgeries in [8] include fresh signatures on messages already signed by the oracle. Such a forgery is not valid in our case since signatures are sanitizable (essentially re-randomizable).

Notice that the unforgeability denition of [8] requires the adversary to return the secret key obtained via dishonest join queries (called Join of type (i) in [8]). Nevertheless, the denition does not enforce at any point that the adversary is returning the correct key. It is possible that the authors are implicitly making the assumption that the adversary is honest at this stage, and this what seems to be used in the security proof (where the reduction does not even look at the key returned by the adversary but uses the key extracted from the PoK made by A during the Join protocol). This is a quite strong assumption. If this assumption is not made we can show an attack. A rst performs a dishonest join query by playing honestly (the same works if this query is honest join followed by corrupt), it obtains a key sk₁. Next A performs another dishonest join query where it plays honestly in the Join protocol, it obtains another key sk₂ but returns to the challenger sk₁. When it comes to the forgery step, from the point of view of the challenger the key that must be in PrivRL is sk₁ (maybe twice). This means that technically sk₂ is not revoked and thus the adversary can use it to create a signature that would pass the forgery checks and win the game. Note that this attack works even if the forgery checks ensure that all sk in PrivRL must be \valid" (this check was proposed as part of the Revoke algorithm of the EPID construction).

$$ \mathcal{A} $$

$$ \mathrm {s k} _ {1} $$

$$ {\sf{S k}}_{2} $$

$$ {\sf{s k}}_{1} $$

$$ \mathsf{P r i v R L}^{*} $$

$$ \ {sf s s k}_{1} $$

$$ s{\mathsf{k}}_{2} $$

$$ \mathsf{P r i v R L}^{*} $$

In our denition of unforgeability we avoid the above attack by requiring a security property of the Join protocol. Specically, the join protocol is such that, if the execution of the protocol ends successfully, then the platform must have learnt one (and only one) secret key. We formalize this by requiring the existence on an extractor that can nd this key by only looking at the transcript. In this way, we avoid the unrealistic requirement that the adversary surrenders all the corrupted secret keys. Notice that the existence of the extractor is only for denitional purpose, namely, only to asses the security statement that \unforgeability holds if all the corrupted secret keys are revoked".

Subversion-Resilient Non-frameability. This notion formalizes the idea that an adversarial issuer should not be able to produce a signature that links to the identity of an honest platform. Since \linking" is only possible across signatures, we treat non-frameability as the property that guarantees that no adversary can output a signature that links to another signature output by an honest platform.

We formalize subversion-resilient non-frameability for SR-EPID in a security experiment in Fig. 3, and we formally dene non-frameability as follows.

Denition 4. Consider the experiment described in Fig. 3. We say that an SR-EPID is non- framable if for any PPT adversary A: h i

$$ \mathbf {A d v} _ {\mathcal {A}, \Pi} ^ {\mathrm {n o n - f r a m}} (\lambda) := \Pr \left[ \mathbf {E x p} _ {\mathcal {A}, \Pi} ^ {\mathrm {n o n - f r a m}} (\lambda) = 1 \right] \in \operatorname {n e g l} (\lambda). $$

Here we provide an intuition on the notion. Similar to the anonymity experiment, in the nonframeability one, the adversary plays the role of the issuer and can do the following: (1) ask platforms with subverted signers to join the system; (2) ask platforms with subverted signers to sign messages; (3) corrupt platforms. For (1), it means that the adversary species the code of a signer M_iand that signer together with sanitizer S_i, run the Join protocol where both the issuer and S_iare controlled by the challenger. For (2), a platform that joined the system creates a signature using the subverted signing algorithm (specied in M_i); this signature is sanitized by the honest sanitizer S_iand given to the adversary. Finally, (3) simply models a full corruption of the platform in which the adversary learns the secret key sk_iobtained by M_iat the end of its Join protocol.

$$ \mathcal{M}_{i} $$

$$ \mathcal {S} _ {i}; $$

$$ \ S{}i $$

$$ \ {cal S_{i}} $$

$$ \ {\mathcal{M}}_{i}) $$

$$ {\sf{s k}}_{i} $$

$$ \ {mathcal M M}_{i} $$

The adversary must output (i ; bsn*;M;) providing the victim platform index i and a basename-message-signature triple bsn;M;. The adversary wins the experiment if (1) is a valid signature for bsn;M*, (2) the signature \links" to one of the signatures produced by the oracle when queried on platform i, and (3) if the oracle has output a signature on bsn*;M* on behalf of platform i and if bsn = bsn , then M 6= M. In the experiment, the challenger keeps a list L_i of signatures and their respective basename-message pairs, for each of the non-corrupted platforms that have joined the group.

$$ (i^{},{\mathsf{b s n}}^{},M^{},\sigma^{}) $$

$$ i^{*} $$

$$ {\mathsf{b s n}}^{},M^{},\sigma^{*} $$

$$ (1)~\sigma^{*} $$

$$ M^{*} $$

$$ i^{*} $$

$$ =\mathsf{b s n}^{*} $$

$$ M\neq M^{*} $$

$$ L_{i} $$

3 Building Blocks

3.1 Bilinear groups

An asymmetric bilinear group generator is an algorithm G that upon input a security parameter 1 produces a tuple bgp = (p; G₁*;G₂;* G_T;e; P₁; P₂), where G₁*;G₂ and G_Tare groups of prime order p 2, the elements P₁; P₂ are generators of G₁;G₂ respectively, e : G₁ G₂!* G_Tis an eciently computable, non-degenerate bilinear map. In our construction we use Type-3 groups in which it is assumed that there is no eciently computable isomorphism between G₁ and G₂. We use the bracket notation introduced in [15]. Elements in G_i, are denoted in implicit notation as [a]_i:= aP_i, where i 2 f1*;* 2*;T g* and P_T:= e(P₁; P₂). Every element in G_ican be written as [a]_ifor some a 2 Z_q, but note that given [a]_i, it is in general hard to compute a 2 Z_q(discrete logarithm problem). Given a;b 2 Z_qwe distinguish between [ab]_i, namely the group element whose discrete logarithm base P_iis ab, and [a]_ib, namely the execution of the multiplication of [a]_i and b, and [a]₁[b]₂= [a b]_T, namely the execution of a pairing between [a]₁and [b]₂. Vectors and matrices are denoted in boldface. We extend the pairing operation to vectors and matrices as

e([A]₁;[B]₂) = [A B]_T. All the algorithms we describe next take implicitly as input the public parameters bgp.

$$ \mathcal{G} $$

$$ 1^{\lambda} $$

$$ \mathbb{G}_{T} $$

$$ \mathbb{G}{1},\mathbb{G}{2} $$

$$ {\mathfrak{b g p}}=(p,{\mathfrak{G}}{1},{\mathfrak{G}}{2},{\mathfrak{G}}{T},e,{\mathcal{P}}{1},{\mathcal{P}}_{2}) $$

$$ p\geq2^{\lambda} $$

$$ \mathcal{P}{1},\mathcal{P}{2} $$

$$ \mathbb{G}{1},\mathbb{G}{2} $$

$$ e:\mathbb{G}{1}\times\mathbb{G}{2},\rightarrow,\mathbb{G}_{T} $$

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

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

$$ [a]{i}:=a\mathcal{P}{i} $$

$$ \mathbb{G}_{i}. $$

$$ i,\in,{1,2,T} $$

$$ \mathcal{P}{T}:=e(\mathcal{P}{1},\mathcal{P}_{2}) $$

$$ \mathbb{G}_{i} $$

$$ [a]_{i} $$

$$ a\in\mathbb{Z}_{q}. $$

$$ [a]i_{} $$

$$ a\in\mathbb{Z}_{q} $$

$$ a,b\in\mathbb{Z}_{q} $$

$$ [a b]_{i} $$

$$ [a]i_{} $$

$$ p_{i} $$

$$ [a]{1}\cdot[b]{2}=[a\cdot b]_{T} $$

$$ [a]_{i}\cdot b, $$

$$ ^{b,} $$

$$ [b]_{2} $$

$$ [a]_{1} $$

$$ e([\mathbf{A}]{1},[\mathbf{B}]{2})=[\mathbf{A}^{\top}\cdot\mathbf{B}]_{T} $$

3.2 Structure-Preserving Signatures

A signature scheme over groups generated by G is a triple of ecient algorithms (KGen*;Sig;Ver). Algorithm KGen outputs a public verication key vk and a secret signing key sk. Algorithm Sig takes as input a signing key and a message m in the message space, and outputs a signature. Algorithm Ver takes as input a verication key vk, a message m and a signature, and returns either 1 or 0 (i.e., \accept" or \reject", respectively). The scheme (KGen;Sig;*Ver) is correct if for every correctly generated key-pair vk;sk, and for every message m in the message space, we have Ver(vk;m; Sig(sk;m)) = 1.

$$ \sigma, $$

$$ \sigma. $$

$$ \ \mathsf{V e r}(v k,m,\mathsf{S i g}(s k,m))=1 $$

$$ \mathbf{E x p}_{\mathcal{A},\varPi}^{\mathsf{n o n-mathrm r a{}m m}}(\lambda) $$

non-fram Experiment Exp_A;() 1 : pub Init(1); gpk A (pub); Ljoin;Lusr;Lcorr ;; C(gpk;) 2 : (i ; bsn*;M;) A ^(gpk); 3 : Retrieve the tuple (i ; Mi;state_i;svti;Li) from Lusr; 4 : Output 1 if and only if all of the following conditions hold: 5 : (1) (i ;;;;) 2 Lusr; 6 : (2) Ver(gpk;bsn;M;;;) = 1;* 7 : (3) 9hM; bsn*;i2 Li* such that Link(gpk*;M;;M;) = 1;* 8 : (4) 8hM; bsn*;i2 Li* : if bsn = bsn then M 6= M : Oracle C(gsk*;) 1 : Upon query (join;i;I*) : 2 : Retrieve (i; Mi;state_S;state_M) from Ljoin;; 3 : If not nd parse I = Mi and add (i; Mi; ?; ?) in Ljoin and return ; 0M 4 : (state⁰⁰S;state;S) Join(Mi;state_S;state_M;I); 0M 5 : Store (i; M_i;state⁰⁰_S;state) in L_join; 6 : if S = concluded then 0M 7 : svti state⁰⁰_S; store (i; Mi;state;svti;;) in Lusr; return ( S;svti); 8 : else return S : 9 : Upon query (sign*;i;* bsn*;M;* SigRL) : ¹⁰ : Retrieve (i; Mⁱ;stateⁱ;svtⁱ;Bⁱ) 2 L^usr; 0i ¹¹ : (state*;) Sig(M_i;state_i;svt_i;bsn;M;* SigRL); 0i 12 : Update (i; M_i;state;svt_i;L_i [fhbsn*;M;ig*); 13 : return; 14 : Upon query (corrupt*;i*) : 15 : Retrieve (i; Mi;state_i;svti) from Lusr; move the tuple from Lusr to Lcor; 16 : return (state_i;svti):

$$ \leftarrow\mathsf{l n i t}(1^{\lambda}) $$

$$ (\mathfrak{}^{},\mathfrak{b s n}^{},M^{},\sigma^{})\leftarrow\mathcal{A}(\mathfrak{g p k})^{\mathcal{C}(\mathfrak{g p k},\cdot)}. $$

$$ \mathrm{}{L}_{u s r}, $$

$$ \left(i ^ {}, \mathcal {M} _ {i ^ {}}, \mathrm {s t a t e} _ {i ^ {}}, \mathrm {s v t} _ {i ^ {}}, L _ {i ^ {*}}\right) $$

$$ \big(i^{},,,,*\big)\in L_{u s r}. $$

$$ \mathsf{V e r}(\mathsf{g P k},\mathsf{b s n}^{},M^{},\sigma^{*},\emptyset)=1, $$

$$ \exists\ \langle M,\mathsf{b s n},\sigma\rangle\in L_{i^{*}} $$

$$ M,\sigma,M^{},\sigma^{})=1. $$

$$ \forall\ \langle M,\mathsf{b s n},\sigma\rangle\in L_{i^{*}} $$

$$ =\mathsf{b s n}^{*} $$

$$ l\neq M^{*} $$

$$ \mathcal{C}(\mathsf{g s k},\cdot) $$

$$ (\mathtt{j o i n},i,\gamma_{\mathcal{I}}) $$

$$ L_{\mathrm{}{j o i n}};; $$

$$ \left(i,\mathcal{M}{i},\mathsf{s t a t e}{\mathcal{S}},\mathsf{s t a t e}_{\mathcal{M}}\right) $$

$$ \gamma_{\mathcal{I}}=\mathcal{M}_{i} $$

$$ L_{j o i n} $$

$$ (i,\mathcal{M}_{i},\bot,\bot) $$

$$ \mathcal{M},\gamma_{\mathcal{I}} $$

$$ L _ {j o i n}; $$

$$ \mathsf{s v t}{i}\leftarrow\mathsf{s t a t e}{\mathcal{S}}^{\prime\prime}. $$

$$ (i,\mathcal{M}{i},\mathsf{s t a t e}{\mathcal{M}}^{\prime},\mathsf{s v t}_{i},\emptyset) $$

$$ L_{u s r}; $$

$$ \left(\gamma_{\mathcal{S}},\mathsf{s v t}_{i}\right) $$

$$ \gamma s $$

$$ (\mathtt{s i g n},i,\mathtt{b s n},M,\mathtt{S i g R L}) $$

$$ (i,\mathcal{M}{i},\mathsf{s t a t e}{i},\mathsf{s v t}{i},B{i})\in L_{u s r}; $$

$$ (\mathsf{s t a t e}{i}^{\prime},\sigma)\leftarrow\mathsf{S i g}(\mathcal{M}{i},\mathsf{s t a t e}{i},\mathsf{s v t}{i},\mathsf{b s n},M,\mathsf{S i g R L}) $$

$$ (i,\mathcal{M}{i},\mathsf{s t a t e}{i}^{\prime},\mathsf{s w t}{i},L{i}\cup{\langle\mathsf{b s n},M,\sigma\rangle}) $$

$$ \sigma; $$

$$ (i,\mathcal{M}{i},\mathsf{s t a t e}{i},\mathsf{s v t}_{i}) $$

$$ L _ {u s r}; $$

$$ L_{u s r} $$

$$ L_{\mathrm{}{c o r}}; $$

$$ (\mathsf{s t a t e}{i},\mathsf{s v t}{i}) $$

Fig. 3: Subversion-resilient non-frameability experiment.

We say that a signature scheme (KGen*;Sig;*Ver) is existentially unforgeable under adaptive chosen message attack (EUF-CMA) if for any PTT adversary A we have that:

$$ \Pr \left[ \operatorname {V e r} (v k, m, \sigma) = 1 \wedge m \notin Q: \begin{array}{c} (v k, s k) \xleftarrow {\mathrm {s}} \mathrm {K G e n} (\mathcal {G} \left(1 ^ {\lambda}\right)), \ (m, \sigma) \leftarrow \mathcal {A} ^ {\mathrm {S i g} (s k, \cdot)} (v k) \end{array} \right] \in \operatorname {n e g l} (\lambda), $$

where Q is the set of messages queried by A to the signing oracle. A stronger notion of unforgeability, named \strong" EUF-CMA or sEUF-CMA, further prevents the adversary to forge a new signature on a message that has already been signed. This notion is captured by modifying the above denition so that (m;) 2= Q whereas Q is dened as the set of message-signature pairs stemming from the adversary’s queries to the signing oracle. Finally, a signature scheme over groups generated by G is structure-preserving [1] if (1) the verication key, the messages, and signatures consist of solely elements of G₁*;*G₂, and (2) the verication algorithm evaluates the signature by deciding group membership of elements in the signature and by evaluating pairing product equations.

$$ (m,\sigma)\not\in Q $$

$$ \mathbb{G}{1},\mathbb{G}{2}. $$

3.3 Non-Interactive Zero-Knowledge Proof of Knowledge

A non-interactive zero-knowledge (NIZK) proof system for a relation R is a tuple NIZK = (Init*;* P*;V) of PPT algorithms such that: Init on input the security parameter outputs a (uniformly random) common reference string crs 2f0;* 1g; P(crs*;x;w*), given (x;w) 2R, outputs a proof; V(crs*;x;*), given instance x and proof outputs 0 (reject) or 1 (accept).

$$ \mathcal{N I Z K}= $$

$$ {mathsf\mathsf c{s s}}\in{0,1}^{\lambda};,{mathsf{P}}(\mathsf{c r s},x,w) $$

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

$$ \mathsf{V}(\mathsf{c r s},x,\pi) $$

$$ \pi ; $$

In this paper we consider the notion of NIZK with labels, that are NIZKs where P and V additionally take as input a label L 2L (e.g., a binary string). A NIZK (with labels) is correct if for $ every crs Init(1), any label L 2L, and any (x;w) 2R, we have V(crs*;L;x;* P(crs*;L;x;w*)) = 1. Denition 5(Adaptive composable perfect zero-knowledge). A NIZK NIZK for relation R satises adaptive composable perfect zero-knowledge if the following properties hold:

$$ L\in{\mathcal{L}};({\mathrm{e.g.}}) $$

$$ \leftarrow\vert\sf{n i t t}^{\lambda}\rangle $$

$$ L\in{\mathcal{L}} $$

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

$$ \mathsf{V}(\mathsf{c r s},L,x,\mathsf{P}(\mathsf{c r s},L,x,w)\big)=1 $$

(i)There exists an algorithm Init_zkthat outputs crs*, and a simulation trapdoor* tp_ssuch that for any sequence fbgp G (1)g₀and for any PPT distinguisher D

$$ \overline{{\ \ \mathrm{l n i t}}}_{z k} $$

$$ \mathsf{t p}_{\mathrm{s}} $$

$$ {\mathsf{b g p}{\lambda}\leftarrow\mathcal{G}(1^{\lambda})}{\lambda\geq0} $$

$$ \begin{array}{l} | \Pr [ D (\mathrm {c r s}) = 1: (\mathrm {c r s}, \mathrm {t p} _ {\mathrm {s}}) \xleftarrow {\mathrm {s}} \overline {{\mathrm {I n i t}}} _ {z k} (\mathrm {b g p} _ {\lambda}) ] \ - \Pr [ D (c r s) = 1: c r s \xleftarrow {\mathrm {s}} \operatorname {I n i t} \left(b g p _ {\lambda}\right) ] | \in \operatorname {n e g l} (\lambda) \ \end{array} $$

$ (ii)There exists a PPT simulator S such that for any (x;w) 2 R, L 2 L and all (crs*;tp_s) ^$ $ Init_zk(bgp), the proofs generated via S* (tp_s;L;x) and P(crs*;L;x;w*) are identically distributed.

$$ \ x,w,\ \in,\mathcal{R},,L,\in,\mathcal{L} $$

$$ \left(\mathrm {c r s}, \mathrm {t p} _ {\mathrm {s}}\right) \leftarrow^ {$} $$

$$ \overline{{\ \ {mathsf l n n i t}}}_{z k}({\mathsf{b g p}}) $$

$$ \pi\stackrel{\S}{\leftarrow}\mathcal{S}(\mathsf{t p_{s}},L,x) $$

$$ \pi \leftarrow^ {$} \mathrm {P} (\mathrm {c r s}, L, x, w) $$

Denition 6(Adaptive extractable soundness). A NIZK NIZK for relation R is adaptive extractable sound (Ext) if the following properties hold:

(i)There exists an algorithm Init_sndthat outputs crs and an extraction trapdoor tp_esuch that for any sequence fbgp G (1)g₀and for any PPT distinguisher D

$$ \overline{{\mathsf{I n i t}}}_{s n d} $$

$$ \mathsf{t p}_{\mathrm{e}} $$

$$ {\mathsf{b g p}{\lambda}\leftarrow\mathcal{G}(1^{\lambda})}{\lambda\geq0} $$

$$ \begin{array}{l} | \Pr [ D (\mathrm {c r s}) = 1: (\mathrm {c r s}, \mathrm {t p} _ {\mathrm {s}}) \leftarrow^ {$} \overline {{\mathrm {I n i t}}} _ {s n d} (\mathrm {b g p} _ {\lambda}) ] \ - \Pr [ D (\mathrm {c r s}) = 1: \mathrm {c r s} \leftarrow^ {$} \mathrm {I n i t} (\mathrm {b g p} _ {\lambda}) ] | \in \mathrm {n e g l} (\lambda) \ \end{array} $$

(ii)There exists a PPT algorithm E(tp_e;x;) such that every PPT adversary A: --

$$ \mathcal{E}(\mathsf{t p}_{\mathsf{e}},x,\pi) $$

$$ \tt{A d v}{A\ N I Z K,E}^{e x t-s o u n}(\lambda):=\operatorname*{P r}\left[\tt{E x p}{N Z Z K,A,E}^{e x t-s o u n d}(\lambda)=1\right]\in\ g e g(\lambda) $$

where the experiment is dened in Fig. 4.

$$ \underline {{\mathbf {E x p}}} _ {A, N I Z K} ^ {\mathrm {d e r - p r i v}} (\lambda) \text {:} $$

$$ \mathsf{b g p}\stackrel{\S}{\leftarrow}\mathcal{G}(1^{\lambda});,b\stackrel{\S}{\leftarrow}{0,1}; $$

$$ \stackrel{\S}{\longleftarrow}\mathcal{G}(1^{\lambda}); $$

$$ \left(\mathrm {c r s}, \mathrm {t p} _ {\mathrm {s}}\right) \leftarrow^ {$} \overline {{\mathrm {I n i t}}} _ {z k} (\mathrm {b g p}); $$

$$ (\mathrm {c r s}, \mathrm {t p} _ {\mathrm {e}}) \xleftarrow {$} \overline {{\mathrm {I n i t}}} _ {s n d} (\mathrm {b g p}) $$

$$ (L, x, \pi , T) \leftarrow \mathcal {A} \left(\mathrm {c r s}, \mathrm {t p} _ {\mathrm {s}}\right); $$

$$ \operatorname{A s s e r t};\mathcal{V}(\mathsf{c r s},L,x,\pi)=1; $$

$$ (x,L,\pi)\leftarrow\mathcal{A}(\mathfrak{c r}\mathfrak{s});w\leftarrow\xi\big(\mathfrak{t p}_{\mathfrak{c}},L,\mathfrak{r},\pi\big); $$

$$ \text {I f} b = 0 \text {t h e n} \pi^ {\prime} \xleftarrow {$} \mathcal {S} \left(\mathrm {t p} _ {\mathrm {s}}, L, T _ {x} (x)\right); $$

$$ \pi^{\prime}\leftarrow\mathsf{Z}E E v a l(\mathsf{c r s},L,\pi,T); $$

$$ \ {mathsf V({\mathsf{c r s}},L,x,\pi)=}1\Lambda(x,w)\not\in{\mathcal{R}}. $$

$$ b^{\prime}\leftarrow\mathcal{A}(\pi^{\prime}); $$

Fig. 4: The security experiments for the strong derivation privacy and adaptive extractable soundness.

Malleable Proofs. We use the denitional framework of Chase et al [13] for malleable proof systems.

For simplicity of the exposition we consider only unary transformations (see the aforementioned paper for more details). Let T = (T_x;T_r) be a pair of eciently computable functions, that we refer as a transformation.

$$ T=(T_{x},T_{r}) $$

Denition 7(Admissible transformations [13]). An ecient relation R is closed under a transformation T = (T_x;T_w) if for any (x;w) 2 R the pair (T_x(x);T_w(w)) 2 R. If R is closed under T then we say that T is admissible for R. Let T be a set of transformations. If for every T 2T , T is admissible for R, then T is an allowable set of transformations.

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

$$ (T_{x}(x),T_{w}(w))\in\mathcal{R} $$

$$ f o r,\mathcal{R} $$

$$ T\in{\mathcal{T}} $$

Denition 8(Malleable NIZK [13]). Let NIZK = (Init*;* P*;V) be a NIZK for a relation R. Let T be an allowable set of transformations for R. The proof system NIZK is malleable with respect to T if there exists an PPT algorithm ZKEval that on input (crs;L;(x;);T*), where T 2T , L is a 0 label and V(crs*;L;x;) = 1, outputs a valid proof for the statement x⁰* = T_x(x).

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}=(\mathsf{I n i t},\mathsf{P},\mathsf{V}) $$

$$ (\mathsf{c r s},L,(x,\pi),T) $$

$$ T\in{\mathcal{T}} $$

$$ \mathcal{V}(\mathsf{c r s},L,x,\pi)=1 $$

$$ x^{\prime}=T_{x}(x) $$

For malleable NIZKs one can dene the property that one should not distinguish between \freshly" generated proofs and derived ones. This property is formalized with the notion of derivation privacy.

Denition 9. Let NIZK = (Init*;* P*;* V*;*ZKEval) be a malleable NIZK argument for a relation R and an allowable set of transformations T . We say that NIZK is strong derivation private if for any PPT adversary A we have that h i

$$ \mathcal{N I Z Z}=(\mathsf{I n i t,P},\mathsf{V}Z,Zmathsf{E v v a l}) $$

$$ \mathbf{A d v}{\mathcal{A},\mathcal{N I Z E}}^{\mathtt{d e r-p r i v}}(\lambda):=\left|\operatorname*{P r}\left[\textstyle\ \ {mathbf E x x}{\mathcal{A},\mathcal{N I Z K}}^{\mathtt{d e r-p r i v}}(1^{\lambda})=1\right]-\textstyle{\frac{1}{2}}\right|\in\mathsf{n e g l}(\lambda) $$

der-priv where Exp is the game described in Fig. 4. Moreover, we say that NIZK is perfectly strong derivation private (resp. statistically strong derivation private*) when for any (possibly unbounded)* adversary the advantage above is 0 (resp. negligible).

$$ \mathbf{E x p}^{\tt{d e r-p r i v}} $$

Re-randomizable NIZKs. First we notice that the derivation privacy property implicitly says that proofs are re-randomized (since outputs of ZKEval are indistinguishable from freshly generated proofs). In the special case of a malleable NIZK where the allowable transformation is the identity function we simply say that it is a re-randomizable NIZK and we omit the transformation from the inputs of ZKEval.

4 Our SR-EPID Construction

In this section we describe our construction of a subversion-resilient EPID. We start by providing a high-level explanation of our technique, next we describe the scheme, discuss how to instantiate it eciently, and prove its security.

An Overview of Our Scheme. We elaborate further on the overview from Sec. 1.1. Recall that our construction follows the classical template similar to many group signature schemes to prove in zero-knowledge the knowledge of a signature originated by the issuer. In particular: (I) The issuer I keeps a secret key isk of a (structure-preserving) signature scheme. (II) The secret key of a platform is a signature_spon a Pedersen commitment [t]₁whose opening y is known to the signer only. Following the description given in Sec. 1.1, the conjunction of_spand [t]₁forms a blind signature on y. (III) The signer generates a signature on a message M and basename bsn by creating a NIZK with label (bsn*;M*) of the knowledge of a valid signature_spmade by I on message a commitment [t]₁and the knowledge of the opening of such commitment to a value y. To realize the NIZK, our idea is to use a random oracle H to hash the string bsn*;M* and use the output string as the commonreference string of a (malleable) NIZK for the knowledge of the_sp, the commitment [t]₁and the opening y = (y₀;y₁). Furthermore, to be able to re-randomize the signature, we make use the re-randomizable NIZK. (IV) To support revocation and linkability the nal signature additionally contains the pseudorandom value [c₁]₁:= K(bsn) y₀, where K is a random oracle. More in details, linkability is trivially obtained, as two signatures by the same signer and for the same basename share the same value for [c₁]₁, while for (signature-based) revocation we additionally let the signer 0 0 prove that all the revoked signatures contain a [c₁]₁of the form K(bsn) y₀ where y₀ 6= y₀.

$$ \sigma_{s p} $$

$$ \sigma_{s p} $$

$$ [t]_{1} $$

$$ \sigma_{s p} $$

$$ [t]_{1} $$

$$ \sigma_{s p} $$

$$ [t]_{1} $$

$$ \mathbf{y},=,(big(y_{0},y_{1}\big) $$

$$ [c_{1}]{1}:={\mathsf{K}}({\mathsf{b s n}})\cdot y{0} $$

$$ [c_{1}]_{1} $$

$$ X(b\log)y_{0}^{\prime} $$

$$ ,[c_{1}]] $$

$$ y_{0}^{\prime}\neq y_{0} $$

Specic Building Blocks. Our scheme works over bilinear groups generated by a generator G, and it makes use of the following building blocks:

$$ \mathcal{G}_{\epsilon} $$

{ A structure-preserving signature scheme SS = (KGen_sp*;Sig_sp;*Ver_sp) where messages are elements ‘1 ‘2 of G₁ and signatures are in G¹G₂.

$$ {\mathcal{S S}}=({\mathsf{K G e n}}{s p},{\mathsf{S i g}}{s p},{\mathsf{V e r}}_{s p}) $$

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

$$ \mathbb{G}{1}^{\ell{1}}\times\mathbb{G}{2}^{\ell{2}} $$

{ An re-randomizable NIZK NIZK_signfor the relationship R_signdened as: 8 9

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ \mathcal{R}_{\mathsf{s i g n}} $$

$$ \left{\begin{matrix}{(\mathsf{g p k},[\mathbf{b}]{1},\mathsf{S i g R L}),\ \ \ [[t]{1},\sigma_{s p},[\mathbf{y}]{2})}\colon{array}&&[{\mathbf{b}]{1}\in\ a p a n([1,y_{0}]{1}^{\mathsf{T}})}\ {\mathsf[]{\mathbf{t}}=[\mathbf{h}^{\mathsf{T}}\cdot\mathbf{y}]{\mathbf{t}}}\ {\mathsf{V e r}{s p}(\mathbf{p k}{s p},[t]{1},\sigma_{s p})=1}\ {\forall i:[\mathbf{b}{i}]{1}\not\in s p a n([1,y_{0}]_{1}^{\mathsf{T}})}\ \end{matrix}\right} $$

r T where SigRL = f[bⁱ]¹gⁱ⁼¹, gpk = ([h]¹*;pk^sp), and y = (y₀;y₁). ^To simplify the exposition, in the description of the protocol below we omit gpk (the public key of the scheme) from the instance and we consider ([b]₁;*SigRL) as an instance for the relation.

$$ \ mathsf\ S S i R L={[\mathbf{b}{i}]{1}}{i=1}^{r},:mathsf g g p=([\mathbf{h}]{1},\mathsf{p k}_{s p}) $$

$$ \mathbf{y}=(y_{0},y_{1})^{\mathsf{T}} $$

$$ ([\mathbf{b}]_{1},\mathsf{S i g R L}) $$

{ A malleable and re-randomizable NIZK NIZK_comfor the following relationship R_comand set of transformations T_comdened below:

$$ \mathcal {N I Z K} _ {\mathrm {c o m}} $$

$$ \mathcal{R}_{\mathsf{c o m}} $$

$$ \tau_{\mathrm{c o m}} $$

$$ \begin{aligned}{\mathcal{R}{\mathsf{c o m}}:=\left{([\mathbf{h}]{1},[t]{1}),\ [\mathbf{y}]{2}:[t]{\mathtt{t}}=e([\mathbf{h}]{1},[\mathbf{y}]{2})\right}}\ {\mathcal{T}{\mathsf{c o m}}:=\left{T=(T_{x},T_{w}):\begin{array}{c}{T_{x}([\mathbf{h}]{1},[t]{1})=[\mathbf{h}]{1},[t+h{2},\cdot]{}}\ T{{w}([\mathbf{y}]{2})=[y_{0},y_{1}+y_{2}]^{\ }}\ \end{array}\right}}\ \end{aligned} $$

Namely, the relation proves the knowledge of the opening of a Pedersen’s commitment (in G₁) whose commitment key is [h]₁. The transformation allows to re-randomize the commitment by adding fresh randomness.

$$ (left(\operatorname{{i n}}\ \mathbb{G}_{1}) $$

$$ \mathcal{R}{\mathsf{s v t}}={[x,x y,z,z y]{1},y:x,y,z\in\mathbb{Z}_{p}} $$

$$ -\textsf{A}\mathcal{N I}\mathcal{Z}\mathcal{K}_{\mathsf{s v t}} $$

{ A NIZK_svtfor the relation R_svt= f[x;xy;z;zy]₁;y : x;y;z 2 Z_pg.

$$ {0,1}^{*}\rightarrow $$

{ Three cryptographic hash functions H*;J and K modeled as random oracles, where H : f0;* 1g! f0*;* 1g,J: f0*;* 1g!f0*;* 1g and K : f0*;* 1g! G₁.

$$ H, J $$

$$ {0,1}^{\lambda},\stackrel{\circ}{\mathsf{J}}\ {\stackrel{\circ}{0,1}}^{*}\to{0,1}^{\lambda} $$

$$ \mathsf{K}:{0,1}^{\lambda}\to\mathbb{G}_{1} $$

Our SR-EPID Scheme. Now we are ready to describe our scheme.

$$ \leftarrow^ {$} \mathcal {G} \left(1 ^ {\lambda}\right) $$

$ Init(1)! pub: Generate description of a type-3 bilinear group bgp G (1), the common $ $2 reference string crs^svt NIZK_svt: Init(bgp), and sample h Z_p. Output 18 pub = (bgp*;crs_svt;[h]₁) $ Setup(pub)!* (gpk*;isk): sample (sk^sp;pk^sp) KGen^sp(bgp), and set isk := sk^sp, gpk := pk^sp. Join_I;H;Mh(gpk;isk);gpk;gpki!hb;(b; svt);(sk;*svt)i: the platform P = (M; H) and issuer I start an interactive protocol that proceeds as described below: $

1. I samples id f 0*;* 1g and send id to H and M. All the parties compute crs_comJ(id). $
2. H samples y₀;c Z_p, sets svt := [c;cy₀]₁and sends (*y₀;*svt) to M.
3. M does as described below: $ { Sample y_MZ_pand compute [t_M]₁:= (y₀;y_M) [h]₁; {_M NIZK_com: P(crs_com;([h]₁; [t_M]₁); [y₀;y_M]₂); { Send ([t_M]₁;_M) to H.
4. H checks NIZK_com: V(crs_com;([h]₁; [t_M]₁);_M) = 1; if the check passes: $ { Sample y_HZ_pand set [t]₁:= [t_M+ h₂ y_H]₁; { Compute_H NIZK_com: ZKEval(crs_com;_M; [y_H]₁); { Send y_Hto M and ([t]₁;_H) to I.
5. I checks NIZK_com: V(crs_com;([h]₁; [t]₁);_H) = 1, and if the check passes then I computes ^spSig^sp(sk^sp; [t]¹) and sends_spto M (through H).
6. M does as described below: T { Compute y₁ = y_M+ y_H, and set y := (y₀;y₁); ^T { Verify (1) [h]₁y = [t]₁and (2) Ver_sp(pk_sp; [t]₁;_sp) = 1 { If so, send the special message completed to I (through H) and output sk := ([t]₁;_sp*;*y) and svt.
7. H outputs svt. 8.If I receives the special message completed then outputs it. Sig(gpk*;sk;svt;bsn;M;* SigRL)! (;): On input gpk*;sk = ([t]₁;_sp;y), the base name m bsn 2f0;* 1g, the message M 2f0*;* 1g, and a signature revocation list SigRL = f(bsn_i;M_i;_i)g_i2[n], generate a signature and a proof as follows: 1.Set [c]₁K(bsn) and set [c]₁:= [c;c y₀]₁; 2.Compute_sign: P(H(bsn*;M*);([c]₁;SigRL);([t]₁; [_sp]₁;[y]₂)); 3.Compute_svt: P(crs_svt;(svt*;[c]₁);y₀*); 4.Output := ([c]₁;) and. Sanitize(gpk*;bsn;M;(;);SigRL;svt): Parse = ([c]₁;) and proceed as follows: 1.If_sign:* V(crs_sign;H(bsn;M);([c]₁;SigRL);) = 0 or_svt: V(crs_svt;(svt*;[c]₁);) = 0 then output?. 0 2.Re-randomize by computing_sign:* ZKEval(H(bsn*;M*);([c]₁;SigRL);) 18

$$ \tt{p u b}=(g g,c r s_{s v t},[h]_{1})^{18} $$

$$ \sf{c r s}{s t t}\overset{\ }{\leftarrow}\cal I Z\cal K{s v t}.\sf{n i t}(b g p) $$

$$ \stackrel{\mathbb{S}}{\longleftarrow}\mathbb{Z}_{p}^{2} $$

$$ {\sf S e t u p}({\sf p u b})\to({\sf g p k},{\sf i S k}) $$

$$ \left(\mathrm {s k} _ {s p}, \mathrm {p k} _ {s p}\right) \xleftarrow {$} \mathrm {K G e n} _ {s p} (\mathrm {b g p}) $$

$$ {\mathsf{i S k}}:={\mathsf{s k}}{s p},,{\mathsf{g p k}}:={\mathsf{p k}}{s p}. $$

$$ \mathsf{J o i n}_{\mathcal{I},\mathcal{H},\mathcal{M}}\langle(\mathsf{g p k},\mathsf{i s k}),\mathsf{g p k},\mathsf{g p k}\rangle\to\langle b,(b,\mathsf{s v t}),(\mathsf{s k},\mathsf{s v t})\rangle $$

$$ \boldsymbol{x} $$

$$ \mathcal{P}=(\mathcal{M},\mathcal{H}) $$

$$ \leftarrow{0,1}^{\lambda} $$

$$ y_{0},c\xleftarrow{\S}\mathcal{D}_{p}, $$

$$ :=[c,c y_{0}]. $$

$$ \mathsf{c r s_{c o m}}\leftarrow\mathsf{J}(i\mathrm{{}d d}) $$

$$ \mathcal{M}. $$

$$ (y_{0},\mathsf{s v t}) $$

$$ y_{\mathcal{M}}\xleftarrow{\S}\mathbb{Z}_{p} $$

$$ [t_{\mathcal{M}}]{1}{:=}(y{0},y_{\mathcal{M}})\cdot[\mathbf{h}]{} $$

$$ \pi_{\mathcal{M}}\leftarrow\mathcal{N I Z K}{\mathsf{c o m}}.\mathsf{P}(\mathsf{c r s}{\mathsf{c o m}},([\mathbf{h}]{1},[t{\mathcal{M}}]{1}),[y{0},y_{\mathcal{M}}]_{2}); $$

$$ ([t_{\mathcal{M}}]{1},\pi{\mathcal{M}}) $$

$$ \mathcal{N I Z K}{\mathsf{o m m}}.\mathsf{V}(\mathsf{c r s}{\mathsf{o m m}},([\mathbf{h}]{1},[t{\mathcal{M}}]{1}),\pi{\mathcal{M}})=1; $$

$$ y_{\mathcal{H}}\xleftarrow{\S}\ {mathbb Z_{p}} $$

$$ [t]{1}:=[t{\mathcal{M}}+h_{2}\cdot y_{\mathcal{H}}]_{1}; $$

$$ \pi_{\mathcal{H}}\dot{\leftarrow\mathcal{N I}\mathcal{Z}\mathcal{K}_{o m}.2mathfrak} $$

$$ (\mathsf{c r s}{\mathsf{c o m}},\pi{\mathcal{M}},[y_{\mathcal{H}}]_{1}); $$

$$ ([t]{1},\pi{\mathcal{H}}) $$

$$ \mathcal{N I Z K}{\mathsf{c o m}}.\mathsf{V}(\mathsf{c r s}{\mathsf{c o m}},([\mathbf{h}]{1},[t]{1}),\pi_{\mathcal{H}})=1 $$

$$ \sigma_{s p}\leftarrow\mathsf{S i g}{s p}(\mathsf{s k}{s p},[t]_{1}) $$

$$ \sigma_{s p} $$

$$ y_{1}=y_{\mathcal{M}}+y_{\mathcal{H}} $$

$$ \mathbf{y}:=(y_{0},y_{1})^{\mathsf{T}}: $$

$$ (1);[\mathbf{h}]{1}^{\mathsf{T}}\cdot\mathbf{y}=[t]{1} $$

$$ \mathsf{V e r}{s p}(\mathsf{p k}{s p},[t]{1},\sigma{s p})=1 $$

$$ {=}([t]{1},\sigma{s p},\mathbf{y}) $$

$$ M,{\mathsf{S i g R L}})\to\left(\sigma,\pi_{\sigma}\right) $$

$$ \mathsf{k}=([t]{1},\sigma{s p},\mathbf{y}) $$

$$ \in{0,1}^{\lambda} $$

$$ M\in{0,1}^{m} $$

$$ \ {mathfrak j i g}{\mathsf R}={({\mathfrak{b s n}}{i},M{i},\sigma_{i})}_{i\in[n]} $$

$$ \pi_{\sigma} $$

$$ [c]_{1}\leftarrow\mathsf{K}(\mathsf{b s n}) $$

$$ \ \ {.\ \operatorname{C o m p u t e}\ }\pi\leftarrow\ \varPi_{\mathsf{a i g n}}.\mathsf{P}(\mathsf{H}(\mathsf{b s n},M),([\mathbf{c}]{1},\mathsf{S i g R L}),([t]{1},[\sigma_{s p}]{1},[\mathbf{y}]{2})); $$

$$ \pi_ {\sigma} \leftarrow \Pi_ {\mathrm {s v t}}. \mathrm {P} \left(\mathrm {c r s} _ {\mathrm {s v t}}, (\mathrm {s v t}, [ \mathbf {c} ] _ {1}), y _ {0}\right); $$

$$ \sigma:=([\mathbf{c}]_{1},\pi) $$

$$ \pi_{\sigma} $$

$$ \boldsymbol{\sigma}=([\mathbf{c}]_{1},\pi) $$

$$ M,(\sigma,\pi_{\sigma}) $$

$$ \it{I}{\sf{s i g n}}.\mathsf{V}(\sf{c r r}{\sf{s i g n}},\mathsf{H}(\sf{b s n},M),([\bf{c}]{1},\sf{S i g R L}),\pi)=0\mathrm{}{o r}\it{I}{\sf{s s t}}.\mathsf{V}(\sf{c r s}{\sf{s e r}},(\sf{s v r},[\bf{c}]{1}),\pi_{\sigma})=0 $$

$$ \pi^{\prime}\leftarrow\varPi_{\mathsf{s i g n}}.\mathsf{Z K E v a l}(\mathsf{H}(\mathsf{b s n},M),([\mathbf{c}]_{1},\mathsf{S i g R L}),\pi) $$

Notice that we could consider a stronger model of subversion where the adversary could additionally subvert the public parameters. Our scheme, indeed, could be proved secure under this stronger model if we generate [h]1 using the ROM and use NIZKsvt with subversion-resistant soundness [3].

$$ [\mathbf{h}]_{1} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s v t}} $$

$$ \sigma^{\prime}:=(|\mathbf{c}|,\pi^{\prime}) $$

3.Output := ([c];). Ver(gpk*;bsn;M;;* PrivRL*;SigRL): Parse = ([c]₁;*) and PrivRL := ff₁;:::;f_n1g. Return 1 if and only if:

$$ M,\sigma,\mathsf{P r i W R L},\mathsf{S i g R L}) $$

$$ \boldsymbol{\sigma}=([\mathbf{c}]_{1},\pi) $$

$$ {\dot{\mathsf{P r i v R L}}}:={f_{1},\ldots,f_{n_{1}}} $$

1. K(bsn) = [c]₁,

$$ {\mathsf{K}}({\mathsf{b s n}})=[c]_{1} $$

2._sign: V(H(bsn*;M*);([c]₁;SigRL);) and

$$ \Pi_{\mathsf{s i g n}}.V(\mathsf{H}(\mathsf{b s n},M),([mathsf c_{{1}},\mathsf{S i n L}),\pi) $$

3.for 8sk 2 PrivRL : let sk = ([t]₁;_sp; (y₀;y₁)) check ( y₀;1) [c]₁6= [0]₁. Link(gpk;bsn;M₁;₁;M₂;₂)! 0*=1. Parse_i= ([c_i]₁;_i) for i = 1;2. Return 1 if and only if [c₁]₁= [c₂]₁and both signatures are valid, i.e., Ver(gpk;bsn;M₁;₁) = 1 and Ver(gpk;bsn;M₂;*₂) = 1.

$$ {\mathfrak{z}}{\mathsf{k}}=\big[[]{1},\sigma{s p},(y_{0},y_{1})\big) $$

$$ (-y_{0},1)\cdot[\ \mathbf{c}]{1}\neq[0]{1} $$

$$ M_{1},\sigma_{1},M_{2},\sigma_{2})\rightarrow0/1 $$

$$ \sigma_{i}=([\mathbf{c}{i}]{1},\pi_{i}) $$

$$ i=1,2 $$

$$ [{\bf c}{1}]{1}=[{\bf c}_{2}]. $$

$$ \mathrm{i.e.,V e r}(\mathtt{g P k},\mathtt{b s n},M_{1},\sigma_{1})=1 $$

$$ \mathsf{V e r}(\mathsf{g p k},\mathsf{b s n},M_{2},\sigma_{2})=1. $$

Remark 1(On correctness without verication list). Additionally, we assume that for any crs*;(gpk;[b]₁;* SigRL) and if NIZK_sign:V(crs*;(gpk;[b]₁;SigRL);) = 1 then NIZK_sign:V*(crs*;(gpk;[b]₁;;);*) =

1. We notice that, by only minor modications of the verication algorithm, this property holds for GS-NIZK proof system for the relation R_sign. The reason is that GS-NIZK is a commit-and-prove NIZK system where each group element of the witness is committed separately, and where there are dierent pieces of proof for each of the equation in the conjunction dened by the relation.

$$ \pi \text {i f} \mathcal {N I Z K} _ {\mathrm {s i g n}}. \mathcal {V} (\mathrm {c r s}, (\mathrm {g p k}, [ \mathbf {b} ] _ {1}, \mathrm {S i g R L}), \pi) = 1 \text {t h e n} \mathcal {N I Z K} _ {\mathrm {s i g n}}. \mathcal {V} (\mathrm {c r s}, (\mathrm {g p k}, [ \mathbf {b} ] _ {1}, \emptyset), \pi) = $$

$$ \mathcal{R}_{\mathsf{s i g n}} $$

4.1 Eciency

A suitable SPS for our construction of SR-EPID is the one in [14] (see Section 5.3 of the reference). It features signatures in G²₁G₂ and verication requires 2 PPEs and 6 pairings. To evaluate r eciency of our construction we look at R_signwhere we have SigRL = f[b_i]₁g_i=1, gpk = ([h]₁;pk_sp), T and y = (y₀;y₁) and we rely on [15] (Table 1, where we consider ‘ = 2 and k = 1). We are committing to [t]₁;_sp;[y]₂: since_sphas size 3 and [y]₂has size 2, we have a total of 6 variables, thus the commitment is composed by 12 elements (since we are using ‘ = 2). Looking at the T proof, we have the following relations: [b]¹2 span([1*;y₀*]¹) is a linear equation, so the proof has T size k + 1 = 2; [t]_t= [h y]_tis a PPE and hence requires ‘ (k + 1) = 4 group elements. Moreover, Ver_sp(pk_sp; [t]₁;_sp) = 1 is the verication of a signature which requires 2 PPEs to be veried, for T a total of 8 elements. Finally, 8i : [b_i]₁62 span([1*;y₀*]₁) consists in n linear equations, for a total of 2n elements (2 elements for each signature in SigRL). It follows that the resulting SR-EPID has signatures of size 28+2n group elements, where n is the number of signatures in SigRL. The original EPID scheme [8] has signatures of size 8 + 5n. We note that signatures produced by our scheme, as well as the ones in related works [8,9], have sizes that are linear in the size of the revocation list SigRL. This is because each signature carries a proof that the private key used to produce is dierent from any of the keys used to produce any of the signatures in SigRL. We leave nding a scheme with signatures sublinear in jSigRLj (e.g., constant or logarithmic) as an interesting open problem. Nevertheless, note that in practical scenarios, if SigRL becomes too large it may be cheaper to have non-revoked members re-join the group.

$$ \mathbb{G}{1}^{2}\times\mathbb{G}{2} $$

$$ \mathcal{R}_{\mathsf{s i g n}} $$

$$ \ mathsf\ S S i R R L={[\mathbf b_{i}]{1}}{i=1}^{r},:\mathsf{g p k}=([\mathbf h]{1},\mathsf{p k}{s p}) $$

$$ \ {bf y==\ }(y_{0},y_{1})^{\mathsf{T}} $$

$$ [t]{1},\sigma{s p},[\mathbf{y}]_{2} $$

$$ \sigma_{s p} $$

$$ [\mathbf{y}]_{2} $$

$$ [\mathbf{b}]{1}\in p a a\big([1,y{0}]_{1}^{\mathsf{T}}\big) $$

$$ k+1=2;,[t]{\mathrm{t}}=[\mathbf{h}^{\mathsf{T}}\cdot\mathbf{y}]{\mathrm{t}} $$

$$ \ell\cdot(k+1)=4 $$

$$ \mathsf{V e r}{s p}(\mathsf{p k}{s p},[t]{1},\sigma{s p})=1 $$

$$ \forall i\ :[\mathbf{b}{i}]{1}\not\in\mathrm{}{s p a n}\big([1,y_{0}]_{1}^{\mathsf{T}}\big) $$

$$ \sigma $$

$$ \sigma $$

4.2 Proof of Security

We use of the following standard number-theoretic assumption:

$ Assumption 2(XDH Assumption). Given a bilinear group description bgp G (1), we say that the External Die-Hellman (XDH) assumption holds in G where 2f1*;* 2g if the distribution $3 [x;y;xy] and the distribution [x;y;z] where (x;y;z) Z_pare computationally indistinguishable.

$$ \stackrel {$} {\leftarrow} \mathcal {G} \left(1 ^ {\lambda}\right) $$

$$ \mathbb{G}_{\beta} $$

$$ \beta\in{1,2} $$

$$ [x,y,x y]_{\beta} $$

$$ [x,y,z]_{\beta} $$

$$ (x, y, z) \leftarrow^ {$} \mathbb {Z} _ {p} ^ {3} $$

Theorem 1. If SS is EUF-CM secure, both NIZK_signand NIZK_comare adaptive extractable sound, perfect composable zero-knowledge and strong derivation private, NIZK_svtis adaptive ex- tractable sound, composable zero-knowledge, and both the XDH assumption holds in G₁ and the Assumption 1 holds, the SP-EPID presented above is unforgeable in the ROM.

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ \mathcal{N I Z}{\mathsf{o K}{\mathsf{o o m}}} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s v t}} $$

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

We rst give a proof sketch. To prove unforgeability we need to dene an extractor: its main idea is to program the random oracle J to output strings (used as common reference strings in the protocol) that come with extraction trapdoors. Recall that by the properties of the NIZK, such strings are indistinguishable from random strings. Then, whenever required, the extractor can run the NIZK extractor over the NIZK proof provided by the platform during the join protocol to obtain a value [y]₂. Finally, looking at the transcript of the join protocol, the extractor can produce the token tk = ([t]₁;_sp;[y]₂). Notice that the created token looks almost like the secret key with the 19 only dierence that, in the secret key, the value y is given in Z²_q. It is clear that the token is uniquely linked to the secret key.

$$ [\mathbf{y}]_{2} $$

$$ \mathsf{t k}=\big([t]{1},\sigma{s p},[\mathbf{y}]_{2}\big) $$

$$ \mathbb{Z}_{q^{\cdot}}^{2\ 19} $$

With this extractor, we proceed with a sequence of hybrid experiments to prove unforgeability. In the rst part of the hybrid argument (from H₀ to H₆ in the formal proof ) we exploit the programmability of the random oracle to puncture the tuple (bsn*;M*) selected by the adversary for its forgery. In particular, we reach a stage where we can always extract the witnesses from valid signatures for (bsn*;M*), while for all the other basename-message tuples the challenger can always send to the adversary simulated signatures. To reach this point, we make use of the strong derivation privacy property of the NIZK proof system (which states that re-randomization of valid proofs are indistinguishable from brand-new simulated proofs for the same statement). Specically, we can switch from signatures produced by the subverted hardware and re-randomized by the challenger of the experiment to signatures directly simulated by the challenger. The latter cuto any possible channels that the subverted machines can setup with the adversary using biased randomness.

$$ \mathbf{H}_{0} $$

$$ \mathbf{H}_{6} $$

$$ (\mathsf{b s n}^{},M^{}) $$

$$ (\mathsf{b s n}^{},M^{}) $$

At this point we can dene the set Q_spof all the messages [t]₁signed by the challenger (impersonating the issuer) using the structure-preserving signature scheme. Notice that our denition allows the adversary to query the challenger for a signature on the message (bsn*;M*) itself. As the signatures for such basename-message tuple are always extractable, the challenger has no chances to simulate such signatures. However, by the security denition, the adversary is bound to output a forgery that does not link to any of the signatures for (bsn*;M*) output by the challenger. We exploit this property together with the fact that two not-linkable signatures must have dierent value for y₀, to show that the forged signature must be produced with a witness that contains a fresh value [t]₁that is not in Q_sp. Slightly more technically, we can reduce this to the binding property²⁰ of the Pedersen’s commitment scheme that we use.

$$ \mathcal{Q}_{s p} $$

$$ [t]_{\ 1} $$

$$ (\mathsf{b s n}^{},M^{}) $$

$$ (\mathsf{b s n}^{},M^{}) $$

$$ y_{0}; $$

$$ [t^{*}]_{1} $$

$$ \mathcal{Q}_{s p} $$

$$ \ {mathrm t t y}^{20} $$

Now, we can divide the set of the adversaries in two classes: the ones which produce a forged signature where [t]₁is in Q_spand the ones where [t]₁is not in Q_sp. For the latter, we can easily reduce to the unforgeability of the structure preserving signature scheme. For the former, instead, we need to proceed with more caution.

$$ [t^{*}]_{1} $$

$$ [t^{*}]_{1} $$

$$ \mathcal{Q}_{s p} $$

$$ \mathcal{Q}_{s p} $$

First of all, we are assured by the previous step that adversaries from the rst class of adversaries would never query the signature oracle on (bsn*;M*). Secondly, we use the puncturing technique again, however, this time we select the platform (let it be the platform number j) that is linked to the forged signature. By the denition of the class of adversaries this platform always exists. For

$$ (\mathsf{b s n}^{},M^{}) $$

$$ j^{*}) $$

¹⁹ In our concrete instantiation we use GS-NIZK proof system, for which extraction in the source groups is more natural and ecient.

²⁰ To be more precise, in the formal proof, we rely directly on the XDH assumption (see hybrid H₇).

$$ \mathrm {H} _ {7} $$ this platform we switch the common-reference string used in the join protocol to be zero-knowledge. Once we are in zero-knowledge mode, we can use strong derivation privacy to make sure that the join protocol does not leak any information about the secret key that the platform computes (even if the machine is corrupted). At this point the secret key of the j-th platform is apparently completely hidden from the view of the adversary, in fact: (1) all the signatures are simulated and (2) the join protocol of the j-th platform is simulated. However, the j-th platform is still using a subverted machine, which, although cannot communicate anymore using biased randomness with the outside adversary, still receives the secret key. We show that we can substitute this subverted machine with a well-behaving machine that might abort during the join protocol but that, if it does not so then it always sign every basename-message tuple received (here we rely on Assumption 1).

$$ j^{*}\mathrm{-t h} $$

$$ j^{*}\mathrm{-t h} $$

The last step is to show that such forgery would break the hiding property of the Pedersen’s commitment scheme that we make use of.

Proof. Given an adversary A for the unforgeability game, we assume, w.l.g. that if the adversary sends the query (sign*;;bsn;M;) for some bsn;M* then the adversary has already queried the random oracle H on the tuple (bsn*;M*). Notice that this assumption is without loss of generality²¹.

Given a PPT adversary A we dene the extractor E. Let E_combe the extractor for the NIZK_com. The extractor E is dened below:

$$ \mathrm{V}^{21} $$

$$ \mathcal{E}. $$

$$ \mathcal{E}_{\mathsf{c o m}} $$

$$ \mathcal{N I Z K}{}_{\mathsf{c o m}} $$

$$ \mathcal{E} $$

Extractor E( ):

$$ \mathcal{E}(\cdot); $$

{ At the rst call initialize the database D_ROas empty and generates the group parameter ^$ bgp G (1).

$$ D_{\mathrm{R0}} $$

$$ \leftarrow^ {\mathrm {s}} \mathcal {G} \left(1 ^ {\lambda}\right) $$

{ Upon input (RO*;* H*;x*) check if (H*;x;y; ?) exists in D_ROand if so return y, else sample ^$ y f 0;* 1g, add the tuple (H*;x;y; ?*) into the database and return y.

$$ (\mathtt{R0},\mathtt{H},x) $$

$$ (\mathsf{H},x,y,\bot) $$

$$ D_{\mathrm{R0}} $$

$$ y_{\cdot} $$

$$ y \leftarrow^ {$} {0, 1 } ^ {\lambda} $$

$$ (\mathsf{H},x,y,\bot) $$

$$ y $$

{ Upon input (RO*;* J*;x*) check if (J*;x;* crs*;tp_e) exists in D_ROand if so return crs₁, else $ sample crs;tp_e NIZK_com:* Init_snd(bgp), add the tuple (J*;x;* crs*;*tp_e) into the database and return crs₁.

$$ (\mathsf{J},x,\mathsf{c r s},\mathsf{t p}_{\mathsf{e}}) $$

$$ D_{\mathrm{R0}} $$

$$ \mathsf{c r s}_{1} $$

$$ \mathsf{c r s},\mathsf{t p}{\mathsf{e}}\xleftarrow{\mathsf{s}}\mathcal{N I Z\mathcal{K}{c o m}}\overline{{\mathsf{h i t}}}_{s n d}(\mathsf{b g p}) $$

$$ (\mathsf{J},x,\mathsf{c r s},\mathsf{t p}_{\mathsf{e}}) $$

{ Upon input (extract*;) parse the transcript as described by the messages sent in the join protocol and nd the value id, lookup for the tuple (J;id;* crs*;tp_e) into the database D_RO, and if it does not exist then it output?. Else, nd the message ([t]₁;_S) from S, run the extractor [y]₂ E_com(tp_e;_S), nd the message_spsent from the issuer I, and output tk = ([t]₁;_sp;*[y]₂).

$$ i d. $$

$$ (\mathsf{J},\mathrm{}{i d},\mathsf{c r s},\mathsf{t p}_{\mathsf{e}}) $$

$$ D_{\mathrm{R0}} $$

$$ \mathcal{S}, $$

$$ ([t]{1},\pi{\mathcal{S}}) $$

$$ [\bf{y}]{2}\leftarrow\cal{E}{c o m}(t p_{e},\pi_{\mathcal{S}}) $$

$$ \sigma_{s p} $$

$$ \mathcal{T}, $$

$$ \mathsf{t k}=([t]{1},\sigma{s p},[\mathbf{y}]_{2}) $$

We dene the CheckTK algorithm. The algorithm given in input gpk, sk and tk parses sk as ([t]₁; [_sp]₁;y) and check if tk = ([t]₁; [_sp]₁;[y]₂). We dene the CheckSig algorithm. The algorithm given in input gpk, tk and a signature, parses tk = ([t]₁; [_sp]₁; [y₀;y₁]₂) and = ([c₀;c₁]₁;) and return 1 if and only if e([c₀]₁; [y₀]₂) = e([c₁]₁;[1]₂). The property 1 is obviously true, in fact, the function that map x 2 Z_pto [x]22 G is injective, moreover, the property 2 is true too, in fact, the step (3) of the verication algorithm checks that [c₀]₁y₀ = [c₁]₁, which is the same of verifying e([c₀]₁; [y₀]₂) = e([c₁]₁;[1]₂).

$$ \left([ t ] _ {1}, \left[ \sigma_ {s p} \right] _ {1}, \mathbf {y}\right) $$

$$ \mathsf{k}=\big([t]{1},[\sigma{s p}]{1},[\mathbf{y}]{2}\big) $$

$$ \sigma $$

$$ \sigma=\big([c_{0},c_{1}]_{1},\pi\big) $$

$$ e\big([c_{0}]{1},[y{0}]{2}\big)=e\big([c{1}]{1},[1]{2}\big) $$

$$ x\in\mathbb{Z}_{p} $$

$$ [x]_{2}\in\mathbb{G} $$

$$ [c_{0}]{1}y{0}=[c_{1}]_{1} $$

$$ e\big([c_{0}]{1},[y{0}]{2}\big)=e\big([c{1}]{1},[1]{2}\big) $$

In the following we dene two sequences of hybrid experiments. In the rst sequence of hybrids experiment we consider the random variable view_A;ithat is the view of the adversary A in the 0i hybrid experiment H. Recall that Def. 3 also requires to compare the view of the adversary in the

$$ ^prime!{,i} $$

$$ \mathbf{\tilde{H}}_{i}^{\prime} $$

²¹ Given an adversary A⁰ that does not respect this rule, we can always dene a new adversary A that runs internally A⁰ and whenever it receives a message (sign*;;bsn;M;*) rst query the RO H and then forward the signing query.

$$ \mathcal{A}^{\prime} $$

$$ (\mathtt{s i g n},,\mathtt{b s n},M,) $$ unforgeability experiment with the dummy extractor and the same view with the extractor dened above.

unf Let H⁰₀() := Exp^~(), namely the experiment run with the dummy extractor that answers A;E; the random-oracle queries as a random oracle would do.

$$ \mathbf {H} _ {0} ^ {\prime} (\lambda) := \operatorname {E x p} _ {\mathcal {A}, \tilde {\mathcal {E}}, \Pi} ^ {\mathrm {u n f}} (\lambda) $$

unf Hybrid H⁰1(). Let H⁰1() := ExpA;E0;(), where E⁰ is the same as E, as dened above, but where when it is called upon input (extract*;) simply it returns?*.

$$ \mathbf{H}_{1}^{\prime}(\lambda) $$

$$ \mathrm{H}{1}^{\prime}(\lambda):=\mathrm{E x p}{\mathcal{A},\mathcal{E}^{\prime},\varPi}^{\mathtt{u n f}}(\lambda) $$

$$ {\mathcal{E}}^{\prime} $$

$$ \mathcal{E} $$

Lemma 1. For any PPT D we have j Pr [D(view_A;1) = 1] Pr [D(view_A;0) = 1] j2 negl().

$$ |\operatorname*{P r}\left[\mathsf{D}(i v e w_{\mathcal{A},1})=1\right]-\operatorname*{P r}\left[\mathsf{D}(i e w_{\mathcal{A},0})=1\right]|\in\mathsf{n e g l}(\lambda). $$

Proof. The proof of the lemma follows by the composable zero-knowledge property. Details omitted.

unf Hybrid H⁰₂(). Let H⁰₂() := Exp_A;E;().

$$ \mathbf {H} _ {2} ^ {\prime} (\lambda) := \operatorname {E x p} _ {\mathcal {A}, \mathcal {E}, \Pi} ^ {\mathrm {u n f}} (\lambda) $$

$$ \mathbf{H}_{2}^{\prime}(\lambda) $$

Lemma 2. For any PPT D we have Pr [D(view_A;2) = 1] = Pr [D(view_A;1) = 1].

$$ \operatorname*{P r}\ [\mathsf{D}(\mathrm{}{v i e w}{\mathcal{A},2})=1]=\operatorname*{P r}\left[\mathsf{D}(\mathrm{}{v i e w}{\mathcal{A},1})=1\right]. $$

Proof. Notice that the dierence between the two hybrids is that in the second the extractor additionally computes the tokens tk. However, the tokens are never add in the view of the adversary.

By the two lemmas above and the triangular inequality we already have the extra condition of the unforgeability in the ROM (Def 3).

In the next sequence of hybrids we will gradually modify the winning condition of the adversary. Recall that in the unforgeability experiment of Fig 2, we dened the winning condition of the adversary to be W := ((1) ^ (2) ^ (3)) _ (4). For notation, we call W_ithe winning condition in the hybrid experiment Hⁱ, we set W₀ := W and, whenever we don’t mention it explicitly, we set unf W_i+1:= W_i. Let H₀() := Exp_A;E;().

$$ W:=((1)\land(2)\land(3))\lor(4) $$

$$ W_{i} $$

$$ \mathbf{H}_{i} $$

$$ W_{0}:=W $$

$$ \mathcal{W}{i+1}:=W{i} $$

$$ \mathbf {H} _ {0} (\lambda) := \operatorname {E x p} _ {\mathcal {A}, \mathcal {E}, \Pi} ^ {\mathrm {u n f}} (\lambda) $$

Hybrid H₁(). Let H₁ be the same as H₀ but where the winning condition is changed. In particular, the condition (4) is omitted²², thus the winning condition is W₁ := (1) ^ (2) ^ (3).

$$ \mathbf{H}_{0} $$

$$ \mathbf{H}_{1} $$

$$ \mathbf{H}_{1}(\lambda) $$

$$ W_{1}:=(1)\wedge(2)\wedge(3) $$

Lemma 3. jPr [H₁() = 1] Pr [H₀() = 1] j2 negl():

$$ |\operatorname*{P r}\left[{\ H}{1}(\lambda)=1\right]-\operatorname*{P r}\left[{\bf H H}{0}(\lambda){{\ ==\ }}1\right]|{{\ \ \in\ }}{\ \ {\ n n l}}(\lambda). $$

Proof. We reduce to the adaptive knowledge soundness of the NIZK_com. Moreover we rely on the perfect correctness of NIZK_signand the perfect correctness of the signature scheme SS. The extractor E computes [y]₂using the knowledge extractor of NIZK_comand output tk = ([t]₁;_sp;[y]₂), since [t]₁;_spare generated by the issuer I they form a valid message-signature pair. Suppose that exists sk 2 PrivRL linked to tk, therefore sk = ([t]₁;_sp*;y) and that CheckSK(gpk;*sk) = 0, there-

fore, either [h y]_T6= [t]_T, but this would violate the adaptive knowledge soundness of NIZK_com, or the latter holds but, the signature ([c]₁;) for a random message M does not verify, but this would violate either the correctness of NIZK_signor the correctness of SS.

$$ \mathcal{N I Z}_{\mathsf{c o m}} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ [\mathbf{y}]_{2} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{c o m}} $$

$$ \mathsf{k}\mathsf{k}=([t]{1},\sigma{s p},[\mathbf{y}]_{2}) $$

$$ [t]{1},\sigma{s p} $$

$$ \in\mathsf{P r i v R L}^{*} $$

$$ \mathfrak{c}=([t]{1},\sigma{\mathrm{}{s p}},\mathbf{y}) $$

$$ [\mathbf{h}^{\top}\cdot\mathbf{y}]{T}\neq[t]{T} $$

$$ \mathcal {N I Z K} _ {\mathrm {c o m}} $$

$$ (\mathbf{[c]}_{1},\pi) $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

Hybrid H₂(). Let H₂ be the same as H₁ but where the winning condition is changed. In particular, let q_Hbe an upper bound on the number of oracle queries made by A to H, w.l.g. we assume the $ adversary does not query twice the RO with the same input. The hybrid samples an index i [q_H] ^$ and a common-reference string crs*;tp_e NIZK_sign:* Init_snd(bgp). At the i-th call to the random oracle H it set the output of the random oracle to be crs . Moreover, consider the condition (5) dened as:

$$ \mathbf{H}_{2}(\lambda) $$

$$ \mathbf{H}_{2} $$

$$ \mathbf{H}_{1} $$

$$ q_{\mathrm{H}} $$

$$ i^{*}\xleftarrow{\S}[q_{\mathsf{H}}] $$

$$ \mathrm {c r s} ^ {}, \mathrm {t p} _ {\mathrm {e}} ^ {} \leftarrow^ {$} \mathcal {N I Z K} _ {\mathrm {s i g n}}. \overline {{\mathrm {I n i t}}} _ {s n d} (\mathrm {b g p}) $$

$$ \mathsf{c r s^{*}} $$

$$ i^{*}{mathrm{-h h}} $$

²² Recall that condition (4) states that 9sk 2 PrivRL and tk 2 R, where R is the set of secret-key tokens of the corrupted users, such that CheckTK(gpk*;sk;tk) = 1 but CheckSK(gpk;*sk) = 0.

$$ \mathsf{varsigma in P P i v R L}^{*} $$

$$ \mathsf{k}\in R. $$

$$ \mathsf{K}(\mathsf{g k},\mathsf{s k})=0 $$

(bsn*;M*) (the basename-message tuple of the forgery) is queried to the random oracle H at the i-th query.

$$ (\mathsf{b s n}^{},M^{}) $$

$$ i^{*}\mathrm{-t h} $$

The new winning condition is W₂ := W₁ ^ (5).

$$ W_{2}:=W_{1}\wedge(5) $$

Lemma 4. Pr [H₂() = 1] Pr [H₁() = 1] =q_Hnegl().

$$ \Pr \left[ \mathbf {H} _ {2} (\lambda) = 1 \right] \geq \Pr \left[ \mathbf {H} _ {1} (\lambda) = 1 \right] / q _ {\mathrm {H}} - \operatorname {n e g l} (\lambda). $$

Proof. First consider the intermediate hybrid H₂_;1equal to H₂ (we sample crs and assign it to the i-th query to the random oracle), but where we do not change the winning condition. By property (i) of Def. 6 (extractable sound CRSs are indistinguishable from random strings) we know that jPr [H₂_;1() = 1] Pr [H₁() = 1] j2 negl().

$$ \mathbf{H}_{2,1} $$

$$ \mathsf{c r s}^{*} $$

$$ \mathbf{H}_{2} $$

$$ |\operatorname*{P r}\left[\mathbf{H}{2,1}(\lambda)=1\right]-\operatorname*{P r}\left[\mathbf{H}{1}(\lambda)=1\right]|\in\mathsf{n e g l}(\lambda) $$

Notice that Pr [H₂() = 1] = Pr [H₂_;1() = 1 ^ (5)] = Pr [H₂_;1()] Pr [(5)], in fact, the view of the adversary is independent of the random variable i. Moreover, the probability of (5) is 1*=q*_H.

$$ \operatorname*{P r}\left[{\bf H}{2}(\lambda)=1\right]{\ =\ \operatorname*{P r}\left[{\bf H}{2,1}(\lambda)=1\wedge(5)\right]{\ =\ }}operatorname*{P r}\left[{\bf H}_{2,1}(\lambda)\right]\operatorname*{P r}\left[{5}\right] $$

$$ 1/q\mathsf{H} $$

$$ i^{*} $$

$$ {\bf H}_{3}(\lambda) $$

Hybrid H₃(). Let H₃ be the same as H₂ but where the winning condition of the adversary is changed. In particular, after the adversary outputs its forgery the hybrid additionally computes ([t]₁; [_sp]₁;[y ]₂) E_sign(tp_e;), where (;[c ]₁) is the forged signature. The winning condition is changed to W₃ := W₂ ^ (6) where (6) is dened as:

$$ \mathbf{H}_{3} $$

$$ \mathbf{H}_{2} $$

$$ \left([ t ^ {} ] _ {1}, \left[ \sigma_ {s p} ^ {} \right] _ {1}, \left[ \mathbf {y} ^ {} \right] _ {2}\right) \leftarrow \mathcal {E} _ {\mathrm {s i g n}} \left(\mathrm {t p} _ {\mathrm {e}} ^ {}, \pi^ {*}\right) $$

$$ (\pi^{},[\mathtt{c}^{}]_{1}) $$

$$ W_{3}:=W_{2}\wedge(6) $$

T 0 Check that Ver_sp(pk_sp; [t]₁; [_sp]₁) = 1 and [t]_t= [h y ]_tand for any ([c⁰₀;c⁰₁]₁;) 2 SigRL we have [c⁰₁]_t6= [c⁰₀y₀]_t.

$$ \mathsf{r}{s p}\big(\mathsf{p k}{s p},[t^{}]{1},[\sigma{s p}^{}]_{1}\big)=1 $$

$$ [t^{}]_{\mathsf{t}},=,[\mathbf{h}^{\mathsf{T}}\cdot\mathbf{y}^{}], $$

$$ ([c_{0}^{\prime},c_{1}^{\prime}]_{1},\pi^{\prime})\in, $$

$$ [c_{1}^{\prime}]{\mathsf{t}}\neq[c{0}^{\prime}y_{0}^{*}]_{\mathsf{t}} $$

Lemma 5. Pr [H₃() = 1] = Pr [H₂() = 1].

$$ \Pr \left[ \mathbf {H} _ {3} (\lambda) = 1 \right] = \Pr \left[ \mathbf {H} _ {2} (\lambda) = 1 \right]. $$

Proof. We reduce to adaptive extractable soundness of NIZK_sign. Notice that by the Shoup’s dierence lemma we need to bound the probability of the event W₂^:(6), namely that the hybrid H₂ outputs 1 but H₃ does not. The event W₂^:(6) implies that the proof for the statement [c ]₁;SigRL and with label y does verify but (by the condition :(6) ) either the Ver_sp(gpk; [t]₁;_sp) = 0 or T 0 [t]_t= [h y]_texists ([c⁰₀;c⁰₁]₁;) 2 SigRL where [c⁰₁]_t= [c⁰₀y₀]_t, which violates the soundness of the proof system.

$$ \mathcal{N I Z5_{s i g n}} $$

$$ \mathbf{H}_{2} $$

$$ W_{2}\land\lnot(6) $$

$$ \mathbf{H}_{3} $$

$$ W_{2}\land\lnot(6) $$

$$ \pi^{*} $$

$$ [\mathbf{c}^{}]_{1},\mathsf{S i g R L}^{} $$

$$ y^{*} $$

$$ \neg(6)~! $$

$$ [t]{\mathrm{t}}=[\mathbf{h}^{\mathsf{T}}\cdot\mathbf{y}]{\mathrm{t}} $$

$$ \mathsf{V e r}{s p}(\mathsf{g p k},[t^{*}]{1},\sigma_{s p})=0 $$

$$ ([c_{0}^{\prime},c_{1}^{\prime}]_{1},\pi^{\prime})\in\mathsf{S i g R L}^{*} $$

$$ [c_{1}^{\prime}]{\mathrm{t}}=[c{0}^{\prime}y_{0}^{*}]_{\mathrm{t}} $$

Hybrid H₄(). Let H₄ be the same as H₃ but where we program dierently the random oracle H. $ In particular, upon the i-th query (RO*;* H*;x*) where i 6= i sample crs*;tp_s NIZK_sign:* Init_zk(bgp) and set the tuple (H*;x;* crs*;*tp_s) into the database D_RO.

$$ \mathbf {H} _ {4} (\lambda) $$

$$ \mathbf{H}_{4} $$

$$ \mathbf{H}_{3} $$

$$ i\neq i^{*} $$

$$ (\mathtt{R0},\mathtt{H},x) $$

$$ (\mathsf{H},x,\mathsf{c r s},\mathsf{t p_{s}}) $$

$$ D_{\mathrm{R0}} $$

Lemma 6. jPr [H₄() = 1] Pr [H₃() = 1] j2 negl().

$$ |\operatorname*{P r}\left[{\bf H}{4}(\lambda)=1\right]-\operatorname*{P r}\left[{\bf H}{3}(\lambda)=1\right]|\in\ \mathsf{n e g l}(\lambda). $$

Proof. The proof of the lemma follows by property (i) of Def. 5 (adaptive composable perfect zero-knowledge) of NIZK_sign.

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

Hybrid H₅(). Let H₅ be the same as H₄ but where the queries (sign*;;;) are answered in a different way. Let S_signbe the zero-knowledge simulator of NIZK_sign. Upon query (sign;i;* bsn*;M;* SigRL) where (i; M_i;state_i;svt_i;tk_i) 2 L_ursand svt_i6=? (namely, the sanitizer S is honest) and (bsn*;M*) 6= (bsn*;M*) (where (bsn*;M*) is the i-th query to the random oracle H), the hybrid computes 0i = ([c]₁;);state M_i(state_i;bsn;M; SigRL), retrieve the tuple (H*;(bsn;M;* crs*;tp_s) from D_RO (or create it if it does not exist), computes ~ S (tp_s;([c]₁;SigRL)) and outputs ([c]₁;* ~).

$$ {\bf H}_{5}(\lambda) $$

$$ \mathbf{H}_{5} $$

$$ \mathbf{H}_{4} $$

$$ (\mathtt{s i g n},,) $$

$$ S_{\mathrm{s i g n}} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ (i,\mathcal{M}{i},\mathsf{s t a t e}{i},\mathsf{s v t}{i},\mathsf{t k}{i})\in L_{u r s} $$

$$ \mathsf{s v t}_{i}\neq\bot $$

$$ \mathcal{S} $$

$$ (\mathsf{b s n}^{},M^{}) $$

$$ (\mathsf{b s n},M)\neq $$

$$ (\mathsf{b s n}^{},\dot{M}^{}) $$

$$ \sigma,=,([\mathbf{c}]_{1},\pi) $$

$$ \leftarrow\mathcal{M}{i}(\mathsf{s t a t e}{i} $$

$$ \tilde{\pi}\gets\mathcal{S}(\mathsf{t p}{\mathsf{s}},([\mathsf{c}]{1},\mathsf{S i g R L})) $$

$$ D_{\mathrm{R0}} $$

$$ ([\mathbf{c}]_{1},\tilde{\pi}) $$

Lemma 7. jPr [H₅() = 1] Pr [H₄() = 1] j2 negl().

$$ |\operatorname*{P r}\left[{\bf H}{5}(\lambda)=1\right]-\operatorname*{P r}\left[{\bf H}{4}(\lambda)=1\right]|\in\mathsf{n e g l}(\lambda). $$

Proof. We reduce to the strong derivation privacy of NIZK_sign. As the reduction is almost straight forward, here we just give a sketch. Let q_signbe an upper bound on the number of signing queries sessions the adversaries perform. Due to strong derivation privacy we know that, for each query, we have h i

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ q{\ g g}n $$

$$ \textstyle\mathbf{A d v}{\mathcal{A},\mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}}^{\tt d{r r-}p r i v}(\lambda):=\left|\operatorname*{P r}\left[\mathbf{E x p}{\mathcal{A},\mathcal{N}\mathcal{X}\mathcal{Z}\mathcal{K}}^{\tt{d e r-p}p r i v}(1^{\lambda})=1\right]-\frac{1}{2}\right|=\epsilon(\lambda)\in\sf{n e g l}(\lambda). $$

This means that jPr [H₅() = 1] Pr [H₄() = 1] j q_sign() 2 negl().

$$ |\operatorname*{P r}\left[{\mathbf{H}{5}(\lambda)=1}\right]-\operatorname*{P r}\left[{\mathbf{H}{4}(\lambda)=1}\right]|\leq q_{\mathrm{}{s i g n}}\cdot\epsilon(\lambda)\in\mathsf{n e g l}(\lambda). $$

Hybrid H₆(). Let H₆ be the same as H₅ but where, for any signature produced by honest platforms with a subverted machine, we control explicitly that [c]₁is of the right form. Specically, upon query (sign*;i;* bsn*;M;* SigRL) where (i; Mⁱ;stateⁱ;svtⁱ;) 2 L^ursand svtⁱ6=? (namely, the 0i sanitizer S is honest), the hybrid computes = ([c₀;c₁]₁;);state M_i(state_i;bsn;M; SigRL), and return*?* to the adversary if e([c₁]₁;[1]₂) 6= e([c₀]₁; [y₀]₂).

$$ \mathbf{H}_{6}(\lambda) $$

$$ \mathbf{H}_{6} $$

$$ \mathbf{H}_{5} $$

$$ [\mathbf{c}]_{1} $$

$$ \left(i, \mathcal {M} _ {i}, \mathrm {s t a t e} _ {i}, \mathrm {s v t} _ {i}, *\right) \in L _ {u r s} $$

$$ \mathsf{s v t}_{i}\neq\bot $$

$$ \mathcal{S} $$

$$ \sigma,=,([c_{0},c_{1}]_{1},\pi) $$

$$ \ :leftarrow mathcal M{}i(\mathsf{s t a t e}_{i},\mathsf{b s n},M,\mathsf{S i g R L}) $$

$$ e \left(\left[ c _ {1} \right] _ {1}, [ 1 ] _ {2}\right) \neq e \left(\left[ c _ {0} \right] _ {1}, \left[ y _ {0} \right] _ {2}\right) $$

$$ \Pr \left[ \mathbf {H} _ {6} (\lambda) = 1 \right] = \Pr \left[ \mathbf {H} _ {5} (\lambda) = 1 \right]. $$

Lemma 8. Pr [H₆() = 1] = Pr [H₅() = 1].

Proof. Recall that svt_i= [c;cy₀]₁, and that the proof proves that (svt_i;[c]₁) are of form [x;xy;z;zy] for x;y;z 2 Z_p. Therefore, if the hybrid H₆ outputs*?* but H₅ does not, then the proof veries but c does not lie in the subspace spanned by svt_i, therefore breaking the adaptive perfect soundness of NIZK_svt.

$$ {mathsf{s v t}}{i};=;[c,c y{0}]_{1} $$

$$ \pi_{\sigma} $$

$$ \left(\mathrm {s v t} _ {i}, [ \mathbf {c} ] _ {1}\right) $$

$$ [x,x y,z y,] $$

$$ x,y,z,\in,\mathbb{Z}_{p} $$

$$ \mathbf{H}_{6} $$

$$ \perp $$

$$ \mathbf{H}_{5} $$

$$ \pi_{\sigma} $$

$$ \mathsf{s v t}_{i}. $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s v t}} $$

Let Q_sp:= f[t]₁: (;;;;([t]₁;_sp;[y]₂)) 2 L_usrg. Namely, the set of signatures of the structure-preserving signature scheme computed by the challenger of the game.

$$ \mathcal{Q}{s p}\ :=\ {[t]{1}\ :\ (,,,,([t]{1},\sigma{s p},[\mathbf{y}]{2}))\ \in\ L{u s r}} $$

Hybrid H₇(). Let H₇ be the same as H₆ but where the winning condition is changed. Specically, consider the condition (7) dened below:

$$ {\bf H}_{7}(\lambda) $$

$$ \mathbf{H}_{7} $$

$$ \mathbf{H}_{6} $$

$$ (,\mathsf{b s n}^{},M^{},)\not\in L_{s g}\vee[t^{*}]{1}\not\in\mathcal{Q}{s p}. $$

The winning condition is changed to W₇ := W₆ ^ (7).

$$ W _ {7} := W _ {6} \wedge (7) $$

Lemma 9. jPr [H₇() = 1] Pr [H₆() = 1] j2 negl().

$$ |\operatorname*{P r}\left[{{H}{7}(\lambda)={1}}\right]-\operatorname*{P r}\left[{{H}{6}(\lambda)={1}}\right]|\ {\in{\ }\mathsf{n e g l}(\lambda)}. $$

Proof. We need to bound the probability of the event Bad := W₆ ^ (;bsn;M;) 2 L_msg^ [t]₁2 Q_sp, We reduce to the SXDH assumption over G₁. Clearly, this problem is equivalent to SXDH (just permute the second and forth coordinates of the challenge). Consider the following reduction:

$$ {:=\ \ W{}}{6}\wedge(,{\mathsf{b s n}}^{},M^{},){\ \in\ }}L{s g}\wedge[t^{*}]_{1}{\ \in\ } $$

$$ \mathcal {Q} _ {s p} $$

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

Adversary B(bgp;[1;x;y;z]₁):

$$ \ [,x,y,z]_{1})\colon $$

1. (Install the Challenge in the parameters.) Run the adversary A and simulate the hybrid H₇. Specically, compute the public parameter as the hybrid does but using the bgp given in input to B and setting [h]₁:= [x;y]₁.

$$ \mathbf{H}_{7} $$

$$ [\mathbf{h}]{1}:=[x,y]{1} $$

$$ \mathcal{B} $$

2.Simulate the random oracle K by making sure that no collisions will appear.

3.Eventually the adversary outputs its forgery (bsn*;M; ;* PrivRL*;SigRL ), let ([t]₁;* [_sp]₁;[y ]₂) be the extracted witness and [y ]₂= [y₀;y₁]₂.

$$ (\mathsf{b s l}^{},M^{},\sigma^{},\mathsf{P r i w R L}^{},\mathsf{S i g R L}^{*}) $$

$$ \left[[t^{}]{1},[\sigma{\mathrm{}{s p}}^{}]{1},[\mathbf{y}^{*}]{2}\right) $$

$$ [\mathbf{y}^{}]{2}=[y{0}^{},y_{1}^{*}]_{2} $$

4.Let [y]₂such that (;;;;([t]₁;;[y]₂)) 2 L_usrand (;bsn;M;) 2 L_msg. Compute [d₀]₂:= [y₀ y₀]₂and [d₁]₂:= [y₁ y₁]₂and return 1 if and only if e([z]₁; [d₁]₂) = e([h₀]₁; [d₀]₂).

$$ (*, *, *, , \left([ t ^ {} ] _ {1}, *, [ \mathbf {y} ] _ {2}\right)) \in L _ {u s r} $$

$$ (,{\mathfrak{b s n}}^{},M^{*},\sigma)\in L_{m s g}. $$

$$ [d_{0}]{2},=,[y{0}^{*}-y_{0}]_{2} $$

$$ [d_{1}]{2}:=[y{1}^{*}-y_{1}]_{2} $$

$$ e\big([z]{1},[d{1}]_{2}\big),= $$

$$ -e([h_{0}]{1},[d{0}]_{2}) $$

First notice that the simulation given by B is statistically close to the hybrid experiment H₇. In fact, the only dierence is that in H₇ there might be collisions in K, however the probability of such event is negligible in the security parameter.

$$ \mathbf{H}_{7} $$

Let parse = ([c ]₁;) and = ([c]₁;). When Bad happens, because of condition (3) then [c₁] 6= [c₁] (the signature are unlinkable), also, because of (;bsn;M;) 2 L_msg^ [t]₁2Q_spthere must exist [y]₂and as dened in step 4 of B. Thus we have that y 6= y and t = h y = h y . Therefore h₀d₀+h₁d₁ = 0, thus if z = xy = h₀h₁ then the pairing test e([z]₁; [d₁]₂) = e([h₀]₁; [d₀]₂) must hold, while if z is uniformly random in Z_pthen the test hold with negligible probability.

$$ \mathbf{H}_{7} $$

$$ \sigma^ {} = \left(\left[ \mathbf {c} ^ {} \right] _ {1}, \pi^ {*}\right) $$

$$ [c_{1}^{*}]\neq[c_{1}] $$

$$ (,\mathsf{b s n}^{},M^{},)\ L_{m s g}\wedge[t^{*}]{1}\ \in\ \ mathcal Q{}{s p} $$

$$ \sigma $$

$$ [\mathbf{y}]_{2} $$

$$ \mathbf{y}\neq\mathbf{y}^{*} $$

$$ t=\mathbf{h}\cdot\mathbf{y}=\mathbf{h}\cdot\mathbf{y}^{*} $$

$$ \ {0}d{0}!+!h_{1}d_{1}=0 $$

$$ \operatorname{i f}z=x y=h_{0}h_{1} $$

$$ e\big([z]{1},[d{1}]{2}\big)=-e\big([h{0}]{1},[d{0}]_{2}\big) $$

$$ \mathbb{Z}_{p} $$

Next, we dene two dierent classes of adversaries. Let A₁ be the class of adversaries such that the event [t]₁2Q_sphappens with noticeable probability in H₇. Similarly, let A₂ be the class of adversaries such that the same event happens with negligible probability in H₇. The two classes partition the entire class of adversaries.

$$ \mathrm{A}_{1} $$

$$ [t^{*}]{1}:\in:\mathcal{Q}{s p} $$

$$ \mathbf{H}_{7} $$

$$ \mathrm{A_{2}} $$

$$ \mathbf{H}_{7} $$

We now fork our hybrid argument in two. The rst sequence is to argue the unforgeability for the adversaries from the class A₁.

$$ \mathrm{A}_{1} $$

Hybrid H₈(). Let H₈ be the same as H₇ but where the winning condition is changed. Let q_join be a polynomial in that upper bounds the number of join that the adversary performs. Pick ^$ j [q_join] and change the winning condition to W₈ := W₈ ^ (8) where (8) is dened as described below:

$$ \mathbf {H} _ {8} (\lambda) $$

$$ \mathbf{H}_{8} $$

$$ \mathbf{H}_{7} $$

$$ q_{j o i n} $$

$$ j^{*}\stackrel{\S}{\longleftarrow}\left[q_{j o i n}\right] $$

$$ W_{8}:=W_{8}\wedge(8) $$

Check that (j;;;;([t]₁;;)) 2 L_usr. Namely, the witness [t]₁extracted from the proof in the forged signature was signed by the issuer at the j-th join protocol, and the parties S_j; M_jwere not (both) corrupted.

$$ \left(j^{},,,,([t^{}]_{1},,*)\right),\in,L_{u s r} $$

$$ \pi^{*} $$

$$ [t^{*}]_{1}^{} $$

$$ j^{*}\mathrm{-t h} $$

$$ \mathcal{S}{j^{*}},\mathcal{M}{j}, $$

Lemma 10. For any A2 A₁ there is a polynomial p such that Pr [H₈() = 1] Pr [H₇() = 1] =p().

$$ [\mathrm{H}{\ 5\}!(\lambda)!=!1]\succeq\mathrm{P r}[\mathrm{H}{7}!(\lambda)!\ 1!]\big/p!(\lambda $$

$$ \mathcal{A}\in\mathbb{A}_{1} $$

Proof. Let p⁰() be a polynomial such that Pr [[t]₁2Q_sp] 1*=p⁰*(). By the denition of A₁, this polynomial exists. Notice that the condition (8) holds when [t]₁2 M and [t]₁is the message signed by I (using SS) at the j-th join session. In particular these two events are independent, so the probability that (7) holds is 1*=q*_join1*=p⁰*() which is noticeable in.

$$ p^{\prime}(\lambda) $$

$$ [[t^{*}]{1}\in\mathcal{Q}{s p}]\geq1/p^{\prime}(\lambda) $$

$$ \mathrm{A}_{1} $$

$$ [t^{*}]_{1}\in M $$

$$ [t^{*}]] $$

$$ j^{*}\mathrm{-t h} $$

$$ 1/q_{j o i n}\cdot1/p^{\prime}(\lambda) $$

$$ {lambda\cdot} $$

Hybrid H₉(). Let H₉ be the same as H₈ but where the random oracle J is programmed dierently. Let NIZK_com: Init_zkbe the zero-knowledge common-reference string generator for NIZK_com. In particular, when the challenger is queried with either (honest join*;j;) or with (dishonestH join;* ²³$ j; I;), the challenger picks a random id f 0*;* 1g (we assume that id was not queried to J), computes crs*;tp_s NIZK_com:* Init_zk(bgp) and set the entry (J*;id ;* crs*;*tp_s) in the database D_RO. Finally it outputs the message id as the rst message of the issuer I in the join protocol.

$$ \ {\bf H}_{9}(\lambda) $$

$$ \mathbf{H}_{9} $$

$$ \mathbf{H}_{8} $$

$$ \mathcal{N I Z}\mathcal{K}{\mathsf{c o m}}.\mathsf{I n i t}{z k} $$

$$ \mathcal{N I Z}_{\mathsf{c o m}} $$

$$ \mathtt{j o i n},j^{},) $$

$$ i d ^ {*} \leftarrow^ {$} {0, 1 } ^ {\lambda} $$

$$ j^{*},\mathcal{I},\xi)^{23} $$

$$ i d^{*} $$

$$ s, t p _ {s} \leftarrow N I Z K _ {\mathrm {c o m}}. \mathrm {l i n i t} _ {z k} (\mathrm {b g p}) $$

$$ (\mathsf{J},i d^{*},\mathsf{c r s},\mathsf{t p}_{\mathsf{s}}) $$

$$ i d^{*} $$

$$ D_{\mathrm{R0}} $$

$$ \mathcal{A}\mathbf{} $$

Lemma 11. For any A2 A₁ jPr [H₉() = 1] Pr [H₈() = 1] j2 negl().

Proof. We reduce to composable zero-knowledge property. Also notice that the probability that id was queried already to J is q_RO*=*2 where q_ROupper bounds the number of queries made to the RO.

$$ i d^{*} $$

$$ q_{\mathrm{R0}}/2^{\lambda} $$

$$ q_{\mathbf{R00}} $$

²³ Recall that the rst message of the protocol is sent by the issuer, however, in the security experiment the sessions are started with a rst message from the adversary, we handle this assuming that the adversary, acting as the sanitizer in the join protocol, initiates the join protocol by sending an empty string to I.

Hybrid H₁₀(). Let H₁₀ be the same as H₉ but where the transcript output in the j-th join protocol is dierent. Let S_combe the zero-knowledge simulator of NIZK_com. Upon query (honest join*;j; M*), let be the transcript at the end of the execution of the join protocol, nd in the message ([t]₁;_S), compute ~S S_com(tp_scom; [t]₁) and set ~ be the same as but where the message ([t]₁;_S) is substituted with the message ([t]₁; ~_S). Return svt_i; ~ to the adversary.

$$ \mathrm{H}_{10}(\lambda) $$

$$ \mathbf{H}_{10} $$

$$ \mathbf{H}_{9} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{c o m}} $$

$$ j^{*}. $$

$$ S_{\mathrm{c o m}} $$

$$ {\tt o i i n},j^{*},\ \ {\mathcal M}) $$

$$ \tau $$

$$ \tilde{\tau} $$

$$ ([t]{1},\pi{\mathcal{S}}) $$

$$ \tau $$

$$ \tilde{\pi}{\mathcal{S}}\leftarrow\cal{S}{c o m}(t p_{s_{c o m}},[t]_{1}) $$

$$ ([t]{1},\pi{\mathcal{S}}) $$

$$ ([t]{1},\tilde{\pi}{\mathcal{S}}) $$

$$ \mathsf{s v t}_{i},\tilde{\tau} $$

Lemma 12. For any A2 A₁ Pr [H₁₀() = 1] = Pr [H₉() = 1].

$$ \mathcal {A} \in \mathbb {A} _ {1} \Pr [ \mathbf {H} _ {1 0} (\lambda) = 1 ] = \Pr [ \mathbf {H} _ {9} (\lambda) = 1 ]. $$

Proof. The proof of the lemma follows by the strong derivation privacy of the NIZK_com. In particular, we can perform an hybrid argument over the number of execution of the join protocol with an honest sanitizer. The reduction is straight forward therefore omitted.

$$ \mathcal {N I Z K} _ {\mathrm {c o m}} $$

Hybrid H₁₁(). Let H₁₁ be the same as H₁₀ but where at the j-th join protocol, if the adversary plays with a subverted machine and an honest sanitizer, then we substitute the subverted machine with well behaving machine. Recall that, in the description of the join protocol the machine M $ sends two messages. Consider the machine M~ that samples a random index r f 1*;* 2*;* 3g and that executes the same code of the honest machine :M but that, if r = 1 it does not send the rst message (or the message is invalid), if r = 2 it does not send the second message (or the message is invalid) and if r = 3 does complete the join protocol. If the adversary sends a query of the kind (honest jo_in*;j; M*) then the hybrid executes the query with the machine M~ instead of M. _i i

$$ {\bf H}_{11}(\lambda) $$

$$ \mathbf{H}_{10} $$

$$ \mathbf{H}_{11} $$

$$ j^{*}\mathrm{-t h} $$

$$ \mathcal{M} $$

$$ \tilde{M} $$

$$ r\xleftarrow{\ast}{1,2,3} $$

$$ r=1 $$

$$ r=2 $$

$$ r=3 $$

$$ j^{*},\mathcal{M}_{i}) $$

$$ \tilde{\mathcal M} $$

$$ \ {mathcal M M}_{i} $$

Lemma 13. For any A2 A₁ there is a polynomial p such that Pr [H₁₁() = 1] Pr [H₁₀() = 1]=3.

$$ \mathcal{A}\in\mathbb{A}_{1} $$

$$ \operatorname*{P r}\left[{\bf H}{11}(\lambda)=1\right]\geq\operatorname*{P r}\left[{\bf H}{10}(\lambda)=1\right]/3 $$

Proof. Let r⁰ be the random variable that is 1 if the machine M_idoes not send the rst message (or the message is invalid), 2 if it does not send the second (or the message is invalid) and r otherwise.

$$ r^{\prime} $$

$$ \mathcal{M}_{i} $$

We prove that for any assignment l 2f1*;* 2*;* 3g, Pr [H₁₀jr = l] = Pr [H₉jr⁰ = l]. Notice that the distribution of the transcript of the join protocol, conditioned on r⁰ = l, it is the same either if the machine _is M or M. In fact, if l = 1 then both distribution are trivially equivalent (as no messages i was sent by M or M). If l = 2 then the rst message of the transcript is ([t]; [t]; ~) where the i 1 2 S proof is simulated and therefore independent of the machine’s message, and t is a uniformly chosen vector in the span of (1*;y₀*). If l = 3 then the last message is a deterministic message (the message completed)) moreover by the Assumption 1 the machine M_inever aborts after the protocol join successfully completed.

$$ l\in{1,2,3} $$

$$ \Pr \left[ \mathbf {H} _ {1 0} | r = l \right] = \Pr \left[ \mathbf {H} _ {9} | r ^ {\prime} = l \right] $$

$$ \mathcal{M}_{i} $$

$$ \tilde{\mathcal M{}} $$

$$ r^{\prime}=l, $$

$$ l=1 $$

$$ \mathcal{M}_{i} $$

$$ \overline{{\mathcal{M}}} $$

$$ l=2 $$

$$ ([t]{1},[t]{2},\tilde{\pi}_{\mathcal{S}}) $$

$$ (1,y_{0}) $$

$$ \mathcal{M}_{i} $$

Also, if H₉ = 1 then the sanitizer S_iis honest, therefore all the signatures are re-randomized and for the correct key y₀. Specically, let ([c]₁;) be a signature output by the challenger on query (sign*;j;M;* SigRL), the vector [c]₁is a function of K and y₀ (we used the soundness of the proof sent by the machine to the S_ito state this in H₆), so independent of the machine’s messages, moreover, by the change introduced in the hybrid H₅ we simulate the proof, which is therefore independent of the machine’s messages.

$$ \mathrm{H}_{9}=1 $$

$$ S_{i} $$

$$ ([\mathbf{c}]_{1},\pi) $$

$$ (\mathtt{s i g n},j^{*},M,\mathsf{S i g R L}) $$

$$ y_{0} $$

$$ [\mathbf{c}]_{1} $$

$$ y_{0} $$

$$ \pi_{\sigma} $$

$$ \mathbf{H}_{6}) $$

$$ S_{i} $$

$$ \pi. $$

$$ \mathbf{H}_{5} $$

With the following derivation we can conclude the proof of the lemma:

$$ \begin{array}{l}{\frac{1}{3}\operatorname*{P r}\left[{\bf{H}}{10}\right]=\frac{1}{3}\sum{l=1}^{3}\operatorname*{P r}\left[{\bf{H}}{10}|r r^{\prime}=l\right]\operatorname*{P r}\left[r^{\prime}=l\right]=\frac{1}{3}\sum{l=1}^{3}\operatorname*{P r}\left[{\bf{H}}_{11}|r=l\right]\operatorname*{P r}\left[r^{\prime}=l\right]}\ {}\end{array} $$

Hybrid H₁₂(). Let H₁₂ be the same as H₁₁ but where the values are computed dierently in the j-th platform. Let S_svtbe the zero-knowledge simulator of NIZK_svtand let NIZK_svt: Init be the zero-knowledge common-reference string generator. At initialization time, the hybrid H₁₂ computes crs_svt;tp_svt NIZK_svt: Init(bgp), and, whenever the adversary queries (sign*;j;M;* SigRL) when (j;;; ?;) 2 L_usr(namely the sanitizer is corrupt but the platform is honest), the signature is computed as before but the proof is computed as S_svt(tp_svt;[svt_i]₁;[c]₁).

$$ {\bf H}_{12}(\lambda) $$

$$ \mathrm{H}_{11} $$

$$ \mathbf{H}_{12} $$

$$ \pi_{\sigma} $$

$$ \mathcal{S}_{\mathrm{s v t}} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s v t}} $$

$$ j^{*}{\mathrm{-t h}} $$

$$ \mathbf{H}_{12} $$

$$ (\mathtt{s i g n},j^{*},M,\mathsf{S i g R L}) $$

$$ \mathsf{c l s}{\mathsf{S t}},\mathsf{t p}{\mathsf{S t t}}\leftarrow\mathcal{N I}\mathcal{Z K!_{\mathsf{S t}}}.\overline{{\mathsf{N i t}}}(\mathsf{b g g}\ ) $$

$$ (left j{}^{},,,\bot,{}^{},)\in L_{u s r} $$

$$ \pi_{\sigma} $$

$$ \pi_{\sigma}\leftarrow\mathcal{S}{\mathsf{s w t}}(\mathsf{t p}{\mathsf{s v t}},[\mathsf{s v t}{i}]{1},[\mathsf{c}]_{1}) $$

Lemma 14. For any A2 A₁ jPr [H₁₂() = 1] Pr [H₁₁() = 1] j2 negl().

$$ \mathcal{A}\in\mathbb{A}{1}\ |\operatorname*{P r}\left[\mathbf{H}{12}(\lambda)=1\right]-\operatorname*{P r}\left[\mathbf{H}_{11}(\lambda)=1\right]|\in\mathsf{n e g l}(\lambda) $$

Proof. The lemma follows easily by the composable zero-knowledge property of NIZK_com.

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{c o m}} $$

We can now show that the winning probability in H₁₂ is negligible.

$$ \mathbf{H}_{12} $$

$$ \operatorname*{P r}\left[\mathrm{H}_{12}(\lambda)=1\right]\in\mathsf{n e g l l}\left(\lambda\right) $$

Lemma 15. Pr [H₁₂() = 1] 2 negl().

Proof. We reduce to the SXDH Assumption. There are two possible cases for the adversary: either the adversary sends to the challenger the message (honest join*;j; M*_i) or it sends (dishonestH join*;j; I;*). In the following we show a reduction for the rst case. A similar reduction can be given for the second case, thus we omit here the details.

$$ j^{*},\mathcal{M}_{i}) $$

$$ j^{*},\mathcal{I},\xi) $$

Consider the following reduction:

Adversary B(bgp;[1;x;y;z]₁):

$$ \mathcal{B}(\mathsf{b g p},[1,x,y,z]_{1}) $$

1.Run the adversary A and simulate the hybrid H₁₁. Specically, compute the public parameter as the hybrid does but using the bgp given in input to B.

$$ \mathbf{H}_{11} $$

2. (Install the Challenge - part 1.) Run the setup algorithm Setup but set [h]₁= $ [x;x]₁where Z_p.

$$ [\mathbf{h}]_{1},= $$

$$ \alpha \leftarrow^ {$} \mathbb {Z} _ {p}. $$

3. (Install the Challenge - part 2.) Eventually, the adversary sends the query (honest join*;* j; Mⁱ)). By the change introduced in H₁₀, the adversary B simulates an execution of the join protocol using the machine M~. In particular, it computes [t] := [h₁ y₀] +[z]. ₁ 1 1 Recall that by the change introduced in the hybrid H₉ the proof_Sis computed using the simulator, thus without the need of the witness (y₀;y).

$$ \mathbf{H}_{10}. $$

$$ j^{*},\mathcal{M}_{i})!{\big)} $$

$$ \mathbf{H}_{9} $$

$$ \pi_{\mathcal{S}} $$

$$ (y_{0},y) $$

4.At every signature query (sign*;j;bsn;M;* SigRL) if (bsn*;M*) 6= (bsn*;M*) then both the signature = ([c]₁;) and the proof can be computed using the respective simulator. Else if (bsn*;M*) = (bsn*;M*) then stop the simulation and return a random bit.

$$ \mathtt{(s i g n,j^{*}} $$

$$ (\mathsf{b s n},M)\neq(\mathsf{b s n}^{},M^{}) $$

$$ \ {boldsymbol\sigma},=,\ [[{mathbf{c}}]_{1},\pi) $$

$$ \pi_{\sigma} $$

$$ {\bigl(}{\mathsf{b s n}},M{\bigr)}={\bigl(}{\mathsf{b s n}}^{*},M{\bigr)} $$

5.Eventually the adversary outputs is forgery (bsn*;M; ;* PrivRL*;SigRL ), let ([t]₁;* [_sp]₁; [y ]₂) be the extracted witness and [y ]₂= [y₀;y₁]₂. If W₁₁ (namely, the winning condition of H₁₁) does not hold outputs a random bit. Else output 1 if and only if e([y]₁;[1]₂) = e([1]₁; [y₀ + y₁ y₀]₂).

$$ ({\sf b s n}^{},M^{},\sigma^{},{\sf P r i v R L}^{},{\sf S i g R L}^{}),\ \ {operatorname l e e};([t^{}]{1},[\sigma{s p}^{*}]_{1} $$

$$ \left[\mathbf{y}^{*}]_{2}\right) $$

$$ [\mathbf{y}^{}]{2}=[y{0}^{},y_{1}^{*}]_{2} $$

$$ W_{11} $$

$$ \mathbf{H}_{11}) $$

$$ e([y]{1},[1]{2})=e([1]{1},[\alpha y{0}^{}+y_{1}^{}-\alpha y_{0}]_{2}) $$

First we notice that if the reduction outputs a random bit (because of step 4 or step 5) then the winning condition does not hold. In particular, in step 4 the reduction outputs a random bit if (bsn*;M*) = (bsn*;M*), so a tuple (;bsn;M;) would appear in L_msgand therefore, if [t] 2Q_sp then condition (7) would not be met.

$$ {\bigl(}{\mathsf{b s n}},M{\bigr)}={\bigl(}{\mathsf{b s n}}^{*},M{\bigr)} $$

$$ \left[t^{*}\right]\in\mathcal{Q}_{s p} $$

$$ L_{m s g} $$

$$ (,\mathsf{b s n}^{},M^{},) $$

Secondly, we notice that the distribution of [t_M]₁; [t_M]₂;_Mis equivalent to the one in H₁₂, thus B perfectly simulates H₁₂. Also notice that if H₁₁ = 1 then the extracted value [y]₂is such T that [h y ]_t= [t]_t. Suppose z = xy, then rewriting the equation we have:

$$ [t_{\mathcal{M}}]{1},[t{\mathcal{M}}]{2},\pi{\mathcal{M}} $$

$$ \ {bf H}_{12}, $$

$$ \mathbf{H}_{12} $$

$$ \mathbf{H}_{11}=1 $$

$$ [\mathbf{h}^{\mathsf{T}}\cdot\mathbf{y}^{}]_{\mathfrak{t}}=[t^{}], $$

$$ [ \mathbf {y} * ] _ {2} $$

$$ z=x y $$

$$ \alpha x y_{0}^{}+x y_{1}^{}=x\alpha y_{0}+x y $$

By simplication, the equation above implies that y = y₀ + y₁ y₀, thus the reduction B will always output 1. On the other hand, if z is uniformly random, the reduction B will output 0 (with overwhelming probability).

$$ y=\alpha y_{0}^{}+y_{1}^{}-\alpha y_{0} $$

By the triangular inequalities and by putting together all the lemmas above, we have now showed that adversaries from the class A₁ can win the unforgeability game only with negligible probability. Thus, we need to show the same statement for the adversary from the class A₂. We roll back to hybrid H₇. We can now show that the winning probability in H₇ is negligible.

$$ \mathrm{A}_{1} $$

$$ \mathrm{A_{2}} $$

$$ \mathbf{H}_{7} $$

$$ \mathbf{H}_{7} $$

Lemma 16. For any adversary A2 A₂ we have Pr [H₇() = 1] 2 negl().

$$ \mathcal{A}\in\mathbb{A}_{2} $$

$$ \operatorname*{P r}\left[{\mathsf{H}}_{7}(\lambda)=1\right]\in{\mathsf{n e g l}}(\lambda) $$

Proof. We reduce to the unforgeability of structure preserving signature SS. Consider the following adversary B against the existential unforgeability against chosen-message attacks of SS:

$$ \mathcal{B}(\mathsf{p k}_{s p}) $$

$$ \mathcal{O}{\mathsf{s i g n}}(\mathsf{s k}{\mathrm{}{s p}},\cdot) $$

Adversary B(pk_sp) with oracle access to O_sign(sk_sp;)

1.Simulate the hybrid H₆, in particular use pk_spto dene the public material in the Setup.

$$ \mathbf{H}_{6}, $$

$$ {\mathsf{p}}{\mathsf{k}}_{s p} $$

2.Simulate the join protocol using the oracle access to O_sign, in particular whenever the hybrid executes the party I in a join protocol and receives the message ([t]₁; [t]₂;_S) query a signature for the message [t]₁, then proceed as the hybrid does.

$$ \mathcal{O}_{\mathsf{s i g n}} $$

$$ \mathcal{T} $$

$$ ([t]{1},[t]{2},\pi_{\mathcal{S}}) $$

3.When the adversary outputs its forgery, compute ([t]₁; [_sp]₁;[c ]₁) as the hybrid does, and output [t]₁; [_sp]₁.

$$ \left[[t^{}]{1},[\sigma{s p}^{}]{1},[\mathtt{c}^{*}]{1}\right) $$

$$ [t^{}]{1},[\sigma{s p}^{}]] $$

By the denition of H₇ = 1 we have that [t]₁62 f[t]₁: (i;;;;([t]₁;;)) 2 L_corrg. Also by the denition of A being in A₂ we have that [t]₁62 f[t]₁: (i;;;;([t]₁;;)) 2 L_usrg (with overwhelming probability). Therefore, the adversary B has not queried [t]₁to its signature oracle. Moreover, by the denition of H₇ = 1 the signature veries, thus this is a valid forgery for SS.

$$ [t^{}]{1};\not\in;{[t]{1};:;(i,,,,([t]{1},,)):\in:L{c o r r}} $$

$$ \mathbf{H}_{7},=,1 $$

$$ \mathrm{A_{2}} $$

$$ [t^{}]{1};\not\in;{[t]{1};:;(i,,,,([t]{1},,));\in;L{u s r}} $$

$$ [ t ^ {*} ] _ {1} $$

$$ \mathrm{H}_{7}=1 $$

Theorem 2. If NIZK_signand NIZK_comare strongly derivation private, adaptively extractable sound and adaptively composable perfect zero-knowledge, both the XDH assumption in G₁ holds and the Assumption 1 holds, and NIZK_svtis adaptively sound, then the SR-EPID described above is anonymous in the ROM.

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ \mathcal {N I Z K} _ {\mathrm {c o m}} $$

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

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s v t}} $$

We rst give a sketch of the proof. First we notice that adaptive corruption and selective corruption for anonymity are equivalent up to a polynomial degradation of the advantage of the adversary. In particular, we can assume that the adversary corrupts all the platforms but the i₁-th and the i₂-th platforms used for the challenge of security game.

$$ i_{1}-mathrm{t l} $$

The idea of the reduction is to switch to zero-knowledge the common reference strings used in the join protocols for the platforms i₁ and i₂ by programming the random oracle. Similarly, switch to zero-knowledge and simulate all the signatures output by the two platforms (again by programming the random oracle). Thus using the strong derivation privacy property of NIZK_sign and NIZK_comto make sure that no information about the platform keys is exltrated. Notice that at this point the machines cannot communicate any information using biased randomness, on the other hand, they could still communicate using valid/invalid signatures. Although, the denition of anonymity disallows telling apart i₁ from i₂ using this channel, for technical reasons, in the last step of the proof (when we reduce to XDH) we need to completely disconnect the subverted machines and, again, substitute them with well-behaving machines, thus here we need to rely on Assumption 1.

$$ i_{2} $$

$$ i_{1} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{c o m}} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ i_{1} $$

$$ i_{2} $$

(1) (2) (1) (2) At this point the element y₀ (resp. y₀) of the key y of the platform i₁ (resp. key y of the platform i₂) are almost hidden to the view of the adversary. However, the challenge signature (b) = ([c ]₁;) still contains the value [c₁]₁= K^(bsn ⁾ y₀. The last step of the proof of anonymity is to change the way the challenge signature is computed. In particular, the value above is computed as K(bsn ) x for a uniformly sampled x. This step is proved indistinguishable using the XDH assumption on G₁.

$$ y_{0}^{(1)}\ (\operatorname{r e s p.}\ y_{0}^{(2)}) $$

$$ \mathbf{y}^{(1)} $$

$$ \mathbf{y}^{(2)} $$

$$ i_{1} $$

$$ i_{2}) $$

$$ \sigma=([\mathbf{c}^{*}]_{1},\pi) $$

$$ [c_{1}^{}]_{1}=\ \ \mathsf{K}(\mathsf{b s n}^{})!\cdot!y_{0}^{(b)} $$

$$ x. $$

$$ {\mathsf{K}}({\mathsf{b s n}}^{*})\cdot{\ \ x} $$

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

Proof. Recall the security experiment in Fig 1. The experiment postulates adaptive corruption of the platforms, namely, the query (corrupt*;*) can be function of the view of the adversary. It is not hard to see that for any PPT adversary that adaptive corrupts the platforms there exists another adversary that commits to its corruptions at the very beginning of the experiment, and, in particular, independently of all the public parameters. More in details, given an adversary A which performs at most q dierent join protocols, let A⁰ be the adversary that (1) rst samples two $ indexes i₁;i₂ [q], then corrupts all the platforms expect that i₁-th and the i₂-th, and (2) runs the same as A but aborts and returns a random bit if the indexes chosen by A in the challenge are not i₁;i₂.

$$ q $$

$$ \mathcal{A}^{\prime} $$

$$ i _ {1} ^ {}, i _ {2} ^ {} \leftarrow^ {$} [ q ] $$

$$ i_{1}^{*-\mathrm{t h}} $$

$$ i_{2}^{*-\mathrm{t h}} $$

$$ i_{1}^{},i_{2}^{} $$

Clearly, for any b 2f0*;* 1g we have:

$$ \operatorname*{P r}\left[\mathtt{E x p}{\mathcal{A}^{\prime},\varPi}^{\mathsf{a n o n}}(\lambda,b)=b\right]=\frac{1}{q^{2}}\operatorname*{P r}\left[\mathtt{E x p}{\mathcal{A},\varPi}^{\mathsf{a n o n}}(\lambda,b)=b\right]+\big(1-\frac{1}{q^{2}}\big)/2 $$

$$ b \in {0, 1 } $$

In the following, we therefore consider adversaries that non-adaptively corrupts the platforms. We anon give a sequence of hybrid experiments, where H₀(;b) := ExpA0;(;b). Moreover, we can assume that the machines M_i1and M_i2do not abort during the join protocol. In fact, if this happened then the challenge signature would be*?* so the adversary can guess the challenge almost with 1 probability. ₂

$$ \mathrm{H}{0}(\lambda,b):=\mathtt{E x p}{A^{\prime}.I\ I I}^{\sf a n a n n}(\lambda,b) $$

$$ \mathcal{M}{i{1}} $$

$$ \mathcal{M}{i{2}} $$

$$ \frac{1}{2} $$

Hybrid H₁(;b). Let H₁ be the same as H₀ but where the random oracle J is programmed to output random common-reference strings in zero-knowledge mode. In particular, the hybrid H₁ keeps track of all the random oracle query to J recording them in a database D_RO, exactly in the same way as the extractor E of the proof of Thm. 1.

$$ \mathbf{H}_{1} $$

$$ \mathbf{H}_{0} $$

$$ \ {bf H H}_\mathrm(\lambda,b) $$

$$ \mathbf{H}_{1} $$

$$ D_{\mathrm{R0}} $$

$$ \mathcal{E} $$

$$ \mathrm{}{\bfL e m m a17.\mathrm{}{F o r}}b\in{0,1},;\vert\operatorname*{P r}\left[\mathbf{H}{1}(\lambda,b)=b\right]-\operatorname*{P r}\left[\mathbf{H}{0}(\lambda,b)=b\right]\mid\in\mathrm{}{\bf~n e g l}(\lambda). $$

The proof of the lemma follows similarly to the proof of Lemma 1 and therefore it is omitted.

Hybrid H₂(;b). Let H₂ be the same as H₁ but where the transcripts output in the i₁-th and i₂-th join protocol are dierent. Let S_combe the zero-knowledge simulator of NIZK_comand let (i1) (i2) (i1) ⁽ⁱ²⁾ tp*;tp be the trapdoor information relative the values id and id as recorded in the database D_RO. (Notice, because all the CRS are simulated such trapdoors always exist.) Upon query (i) (join;i;⁽id⁾) and i 2fi₁;i₂g (namely, the rst message in the join protocol sent by the adversary (i) (i) 0i (i) acting as the issuer) compute ⁽[t^M]¹;^M);state Mⁱ(stateⁱ;id*⁾, performs the same verication (i) (i) (i) (i) that S does and if the checks hold compute [t]₁as S does and ~ S_com(tp*;* [t]₁₎. Return (i) (^{i) (}[t]₁; ~⁾.

$$ {\bf H}_{2}(\lambda,b) $$

$$ i_{1}\mathrm{-t h} $$

$$ \mathbf{H}_{2} $$

$$ \mathbf{H}_{1} $$

$$ i _ {2} - $$

$$ S_{\mathsf{c o m}} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{c o m}} $$

$$ i d^{(i_{1})} $$

$$ {\mathfrak{t p}}^{(i_{1})},{\mathfrak{t p}}^{(i_{2})} $$

$$ i d^{(i_{2})} $$

$$ D_{\mathrm{R0}} $$

$$ (\mathtt{j o i n},i,(i d^{(i)})_{} $$

$$ i \in \left{i _ {1}, i _ {2} \right} $$

$$ ([t_{\mathcal{M}}^{(i)}]{1},\pi{\mathcal{M}}^{(i)}) $$

$$ \leftarrow\mathcal{M}{i}(\mathsf{s t a t e}{i},i d^{(i)} $$

$$ \check{\pi}^{(\tilde{i})}\leftarrow\mathcal{S}{\mathsf{c o m}}(\ {mathfrak t p p}^{(i)},[t^{(i)}]{1}) $$

$$ [t^{(i)}]_{1} $$

$$ ([t^{(i)}]_{1},\tilde{\pi}^{(i)}) $$

$$ \mathcal{S} $$

$$ \mathrm{}{\bfL e m m a18.\mathrm{}{F o r}}b\in{0,1},\mid\operatorname*{P r}\left[\ \ mathbf H{{}}{2}(lambda\ b b)=b\right]-\operatorname*{P r}\left[\mathbf H{1}(\lambda,b)=b\right]\mid\in\mathrm{}{\bf~n e g l}(\lambda). $$

The proof of the lemma follows similarly to the proof of Lemma 11 and therefore it is omitted.

Hybrid H₃(;b). Let H₃ be the same as H₂ but with a new condition on signature queries. Specically, upon oracle query (sign*;i;M;* bsn*;SigRL) and i 2 fi₁;i₂g if 9(M_j;bsn_j;_j) 2 SigRL (i) such that_j= ([c_j]₁;*_j) and ⁽ y₀;1⁾ [c_j]₁= [0]₁then output directly?.

$$ \ {mathrm H}_{3}(\lambda,b) $$

$$ \mathbf{H}_{3} $$

$$ \mathbf{H}_{2} $$

$$ i:\in:{i_{1},i_{2}}::\ \ \mathbf{i f}\ \exists(M_{j},\mathsf{b s n}{j},\sigma{j}):\in:\mathsf{S i g R L} $$

$$ \boldsymbol{\sigma}{j}=([\mathbf{c}{j}]{1},\boldsymbol{\pi}{j}) $$

$$ (-y_{0}^{(i)},1)\cdot[\mathbf{c}{j}]{1}=[0]\cdot $$

Lemma 19. For b 2f0*;* 1g, Pr [H₃(;b) = b] = Pr [H₂(;b) = b].

Proof. Recall the relation R_signin Eq. (1) states that for any tuple (M_j;bsn_j;([c_j];_j)) in SigRL we (i) (i) have that ⁽ y₀;1⁾ [c_j]₁= [0]₁(namely, c_jis not in the span of ⁽1;y₀⁾). Therefore, by correctness of the NIZK scheme, if the event checked by the hybrid happens then the honest prover would not be able to produce a valid proof because the instance is not in the language.

$$ \mathcal{R}_{\mathrm{s i g n}} $$

$$ (M_{j},\mathsf{b s n}{j},([\mathbf{c}{j}],\pi_{j})) $$

$$ \mathsf{S i g R L} $$

$$ \mathbf{c}_{j} $$

$$ \left(- y _ {0} ^ {(i)}, 1\right) \cdot \left[ \mathbf {c} _ {j} \right] _ {1} = [ 0 ] _ {1} $$

$$ (1,y_{0}^{(i)})) $$

Hybrid H₄(). Let H₄ be the same as H₃ but where we program dierently the random oracle $ H. In particular, upon a query (RO*;* H*;x*) the hybrid samples crs*;tp_s NIZK_sign:* Init_zk(bgp) and sets the tuple (H*;x;* crs*;*tp_s) into the database D_RO.

$$ {\bf H}_{4}(\lambda) $$

$$ \mathbf{H}_{4} $$

$$ \mathbf{H}_{3} $$

$$ ({\tt R0},{\tt H},x) $$

$$ \mathsf{t p}{\mathsf{s}}\overset{\ \ }{{leftarrowleftarrow}}\mathcal{N I Z}\mathcal{K}{\mathsf{s i g n}}\ \overline{{\mathsf{i n i t}}}_{z k}(\mathsf{b g p}) $$

$$ D_{\mathrm{R0}} $$

$$ (\mathsf{H},x,\mathsf{c r s},\mathsf{t p_{s}}) $$

Lemma 20. jPr [H₄() = 1] Pr [H₃() = 1] j2 negl().

$$ |\operatorname*{P r}\left[{\bf H}{4}(\lambda)=1\right]-\operatorname*{P r}\left[{\bf H}{3}(\lambda)=1\right]|\in\mathsf{n e g l}(\lambda). $$

Proof. The proof of the lemma follows by property (i) of Def. 5 (adaptive composable perfect zero-knowledge) of NIZK_sign.

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

Hybrid H₅(;b). Let H₅ be the same as H₄ but where the signatures for the platforms i₁ and i₂ are computed dierently. In particular, the hybrid H₅ upon query (sign*;i;M;* bsn*;SigRL) where $ i 2fi₁;i₂g (resp. the challenge (M;bsn;i₁;i₂;SigRL)) computes S_sign(tp_s;[c]) (resp. computes ^$ S_sign(tp_s;*[c ])).

$$ \mathbf{H}_{5} $$

$$ {\bf H}_{5}(\lambda,b) $$

$$ \mathbf{H}_{4} $$

$$ i_{1} $$

$$ i_{2} $$

$$ \mathbf{H}_{5} $$

$$ (mathtt{s i g n},i,M) $$

$$ i \in \left{i _ {1}, i _ {2} \right} $$

$$ (M^{},\mathsf{b s n}^{},i_{1},i_{2},\mathsf{S i g R L}), $$

$$ \tt\pi\stackrel{\S}{\leftarrow}\mathcal{S}{i g g}(t p{s},[c]) $$

$$ \pi^ {} \leftarrow^ {\mathrm {s}} S _ {\mathrm {s i g n}} \left(\mathrm {t p} _ {\mathrm {s}}, \left[ \mathbf {c} ^ {} \right]\right)) $$

Lemma 21. For b 2f0*;* 1g, Pr [H₅(;b) = b] = Pr [H₄(;b) = b].

$$ \cdot b\in{0,1},:\operatorname*{P r}{\left[{{\bf{H}}{5}(\lambda,b)=b}\right]}=\operatorname*{P r}{\left[{{\bf{H}}{4}(\lambda,b)=b}\right]}. $$

Proof. The additional check introduced in the hybrid experiment H₃ guarantees that if the instance [c]₁*;*SigRL is not in the language of the NIZK NIZK_signthen the challenger answers the query with ?. Thus the simulated proofs are generated only for instances in the language. Moreover, by the Assumption 1 the (possibly subverted) machines M_i1and M_i2always produce a signature (when the correctness property of the EPID is veried). The lemma follows by the perfect composable zero-knowledge property of NIZK_sign.

$$ \mathbf{H}_{3} $$

$$ [\mathbf{c}]_{1},\mathsf{S i g R L} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ {mathcal M_{{i_{1}}}} $$

$$ \mathcal{M}{i{2}} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

(i)$ Hybrid H₆(;b). Let H₆ be the same as H₅ but where t Z_pfor i 2fi₁;i₂g. (The hybrid H₅ samples the value y₀ when simulating the honest sanitizer S_i.)

$$ \ {bf H}_{6}(\lambda,b) $$

$$ \mathbf{H}_{6} $$

$$ \mathbf{H}_{5} $$

$$ t^{(i)}\xleftarrow{\mathfrak{S}}\mathbb{Z}_{p} $$

$$ i\in\left{\dot{i}{1},\dot{i}{2}\right} $$

$$ \mathbf{H}_{5} $$

$$ y_{0} $$

$$ S_{i^{*}.}) $$

$$ \mathrm{}{\bfL e m m a22.~\mathit{}F r o r};b\in{0,1},;\operatorname*{P r}\left[\mathbf{H}{6}(\lambda,b)=b\right]=\operatorname*{P r}\left[\mathbf{H}{5}(\lambda,b)=b\right]. $$

(i)$ (i) $ Proof. For i 2fi₁;i₂g the distributⁱon t Z_pand t^M+ h₁y^Swhere y^SZ^pare equivalent. (i) Moreover, conditioning on a specic value for t the v_iew of the adversary is independent of y_S because the NIZK proofs from S to I are simulated.

$$ t ^ {(i)} \leftarrow^ {$} \mathbb {Z} _ {p} $$

$$ i,\in,{i_{1},i_{2}} $$

$$ t_{\mathcal{M}}^{(i)}+h_{1}y_{\mathcal{S}} $$

$$ y_{\mathcal{S}}\xleftarrow{\S}\mathbb{Z}_{p} $$

$$ t^{(i)} $$

$$ \mathcal{S} $$

$$ y_{S} $$

$$ \mathbf {H} _ {7} (\lambda) $$

Hybrid H₇(). Let H₇ be the same as H₆ but where, for any signature produced by the platforms i₁ and i₂ we additionally control that [c]₁is of the right form. Specically, upon query 0i (sign*;i;M;* SigRL) where and i 2fi₁;i₂g, the hybrid computes = ([c₀;c₁]₁;);state M_i(state_i;M), and return*?* to the adversary if e([c₁]₁;[1]₂) 6= e([c₀]₁; [y₀]₂).

$$ \mathcal{T} $$

$$ \mathbf{H}_{6} $$

$$ \mathbf{H}_{7} $$

$$ i_{1} $$

$$ i\in{i_{1},i_{2}} $$

$$ |\mathbf{c}|_{1} $$

$$ i_{2} $$

$$ (\mathtt{s i g n},i,M,\mathsf{S i g R L}) $$

$$ \sigma=([c_{0},c_{1}]{1},\pi),\mathsf{s t a t e}{i}^{\prime}\leftarrow\mathcal{M}{i}(\mathsf{s t a t e}{i},M) $$

$$ \operatorname{f}e\big[[c_{1}]{1},[1]{2}\big)\neq e\big([c_{0}]{1},[y{0}]_{2}\big) $$

$$ \perp $$

Lemma 23. For b 2f0*;* 1g, Pr [H₇(;b) = b] = Pr [H₆(;b) = b].

The proof of the lemma follows identically to the proof of Lemma 8, therefore the proof is omitted.

$$ \mathrm{H}_{8}(\lambda,b) $$

Hybrid H₈(;b). Let H₈ be the same as H₇ but where the challenge signature is computed $ dierently. Specically, a fresh z Z_pis sampled and [c ]₁[c₀;z c₀]₁where [c₀] = K(bsn ).

$$ \mathbf{H}_{7} $$

$$ \mathbf{H}_{8} $$

$$ z\xleftarrow{\mathfrak{S}}\mathbb{Z}_{p} $$

$$ [\mathbf{c}^{}]{1}\leftarrow[c{0}^{},z\cdot c_{0}]. $$

$$ \ c[c_0{^\text{}}]=\mathsf{K}(\mathsf{b s n}^{\text{}}) $$

Lemma 24. For b 2f0*;* 1g, j Pr [H₈(;b) = b] Pr [H₇(;b) = b]j2 negl().

$$ b \in {0, 1 }, | \Pr [ \mathbf {H} _ {8} (\lambda , b) = b ] - \Pr [ \mathbf {H} _ {7} (\lambda , b) = b ] | \in \operatorname {n e g l} (\lambda) $$

Proof. We give a reduction to the SXDH problem in G₁. We assume that A does not query more than once the random oracles on the same point, also we assume that A queries the challenge basename bsn before outputting its challenge. Both the assumptions are without loss of generality. Consider the following adversary B:

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

Adversary B([1;x;y;z]1):

$$ {\mathcal{B}}([1,x,y,z]_{1}) $$

$ 1.Let q be an upper bound of the number of queries to K made by A, let j [q].

2.Simulate the experiment H₈(;b) and the random oracles H;K; J, in particular, simulate the random oracle K by maintaining a list D_ROinitially empty. At the j-th query to K, if j = j then add the tuple (bsn⁰*;* 1*;* [x]₁) and reply with [x]₁else add the entry 0$ (bsn*;* ⁰;) where Z_pand return []₁.

$$ j^{*}\xleftarrow{\sharp}[q]. $$

$$ \ \mathbf{H}_{8}(\lambda,b) $$

$$ \ {\mathcal{H}},{\mathsf{K}},{\mathcal{J}}. $$

$$ D_{\mathrm{R0}} $$

$$ j=j^{*} $$

$$ (\mathsf{b s n}^{\prime},1,[x]_{1}) $$

$$ \stackrel {$} {\leftarrow} \mathbb {Z} _ {p} $$

$$ (\mathsf{b s n}^{\prime},0,\alpha) $$

$$ [\alpha]_{1} $$

3.Upon query (sign*;i*_b;M; bsn*;SigRL), if the tuple (bsn;* 1*;) 2 D_ROstop the simulation and return a random bit, else retrieve (or create) the tuple (bsn;* 0*;) from D_RO. If it exists 0 0 (M_j;bsn_j;_j= ([c_j;0;c*_j;1]₁;_j)) in SigRL such that (bsn*;* ⁰;) 2 D_ROand [c_j;1] = [y]₁ output directly*?* (simulating the check introduced in H₄). Compute the signature by setting [c] [1*;y*]₁and compute using the simulator of NIZK_sign(according to the change introduced in H₈).

$$ \mathsf{S i g R L}) $$

$$ (\mathsf{b s n},1,*)\in D_{\mathtt{R0}} $$

$$ 0,\alpha) $$

$$ D_{\mathrm{R0}} $$

$$ \left(M_{j},{\mathfrak{b s n}}{j},\sigma{j}=\left([c_{j,0},c_{j,1}]{1},\pi{j}\right)\right) $$

$$ (\mathsf{b s n},0,\alpha^{\prime})\in D_{\mathtt{R0}} $$

$$ [c_{j,1}]=\alpha^{\prime}[y]_{1} $$

$$ \mathbf{H}_{4}) $$

$$ [\mathbf{c}]\leftarrow\alpha\cdot[1,y]_{!} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ \mathbf{H}_{8}, $$

4.Let (M;bsn;i₀;i₁;SigRL) be the output of A as in step 3 of Fig. 1. Retrieve the tuple (bsn;) from the list D_RO(or create it if it does not exist). Compute the signature by setting [c ] [x;z]₁and computing using the simulator of NIZK_sign(according to the change introduced in H₈).

$$ (M^{},{\mathsf{b s n}}^{},i_{0},i_{1},{\mathsf{S i g R L}}) $$

$$ (\mathsf{b s n}^{*},\alpha) $$

$$ D_{\mathrm{R0}} $$

$$ [\mathbf{c}^{*}]\leftarrow\cdot[x,z]_{!} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ \mathbf{H}_{8}, $$

5.Continue simulating the experiment H₈ and output what A outputs.

$$ \mathbf{H}_{8} $$

(ib) First we notice that given the transcript of the join protocol for the platform i_bthe value y₀ ^(ib) is uniformly distributed. In particular, the distribution of [y]₁and [y₀]₁are the same, so the signatures for i_bproduced by B are distributed equivalently to the signatures in H₇ (and H₈). Secondly notice that, if z = xy then the distribution of the challenge signature is exactly as in H₇, while if z is uniformly random then the distribution is exactly as in H₈. This concludes the proof.

$$ i_{b} $$

$$ y_{0}^{(i_{b})} $$

$$ [y]_{1} $$

$$ [y_{0}^{(i_{b})}]_{]} $$

$$ i_{b} $$

$$ \mathbf{H}_{7} $$

$$ \mathbf{H}_{8}) $$

$$ {\mathrm{i f}},z=x y $$

$$ \mathbf{H}_{7}, $$

$$ \mathrm{i~f f~~}z $$

$$ \mathbf{H}_{8} $$

Lemma 25. For any b 2f0; 1g, Pr [H₈(;b) = 0] = 1=2

$$ b\in{0,1},\operatorname*{P r}\left[\mathrm{H}_{\ }(\lambda,b)=0\right]=1\big/2 $$

Proof. Let us analyze the view of the adversary in the hybrid H₈. Notice that the adversary cannot get any extra information about the bit b using the signature oracle and dierent SigRL, because the denition of anonymity implies that if one of the two platform (i₁ or i₂) would output*?* then the output of the oracle is*?*. Also, notice that for both the challenge signature is made with a value y₀ that is uncorrelated to both the transcript of the join protocol and the signatures released by the two platform. Therefore the full view of the adversary is independent of the bit b, thus the winning probability.

$$ \mathbf{H}_{8} $$

$$ (i_{1} $$

$$ idot{}_{2}) $$

$$ y_{0} $$

$$ b, $$

Theorem 3. If NIZK_signand NIZK_comare strongly derivation private, adaptively extractable sound and adaptively composable perfect zero-knowledge, both the XDH assumption in G₁ holds and the Assumption 1 holds, and NIZK_svtis adaptively sound, then our SR-EPID is non-frameable in the ROM.

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{c o m}} $$

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

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s v t}} $$

Similarly to anonymity, adaptive corruption and selective corruption for non-frameability are equivalent up to a polynomial degradation of the advantage of the adversary. So we can assume that the challenger knows the honest platform that will be attacked by the adversary, let such platform be the i-th platform. Again, similarly to the proof of anonymity and the proof of unforgeability of our scheme, we switch, thanks to the strong derivation privacy of the NIZK schemes, to an hybrid experiment where all the messages, both during the join protocol and the signature queries, are simulated by challenger and where, moreover, the signature forged by the adversary is extractable. Also, similarly to the proof of unforgeability, thanks to Assumption 1, we substitute the machine of the i-th platform with a well-behaving machine.

$$ i ^ {*} - \mathrm {t h} $$

At this point we can reduce the security to the computational problem of nding [x]₂given [x]₁, which directly implies the XDH assumption in G₁. The idea of the reduction is that, given the challenge [x]₁we can (implicitly) install the element x as the rst element of the platform key of the i-th platform. Notice that given [x]₁, by programming the random oracle and thanks to the simulation trapdoors, we can faithfully run this hybrid-version of the non-frameability game. Moreover, we do not need to explicitly communicate the platform key to the machine of the i-th platform because we substituted it with a well-behaving one. Once the adversary output its forgery, we can use the extraction trapdoor to extract the witness from the signature. A successful adversary forges a signature ([c ];) that links to another signature ([c]₁;) produced by the i-th platform, recall that the linking procedure, given the two signatures on the same basename bsn , checks that [c ]₁= [c]₁and veries the signatures, thus we have [c₁] = K(bsn) x and the reduction must have extracted the value [x]₂from proof of the forged signature.

$$ [x]_{1} $$

$$ |x|_{2} $$

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

$$ [x]_{1} $$

$$ \ ^{*}\mathrm{-t h} $$

$$ [x]_{1} $$

$$ i^{*}- $$

$$ ([\mathbf{c}^{}],\pi^{}) $$

$$ (\mathbf{[c]}_{1},\pi) $$

$$ i^{*} $$

$$ \mathsf{b s n^{*}} $$

$$ [\mathtt{c}^{*}]{1}=[\mathtt{c}]{1} $$

$$ [\mathbf{c}_{1}^{*}]=\mathsf{K}(\mathsf{b s n})\cdot x $$

$$ [x]_{2} $$

$$ \pi^{*} $$

Proof. Recall the security experiment in Fig 3. The experiment postulates adaptive corruption of the platforms, namely, the query (corrupt*;*) can be function of the view of the adversary. As for anonymity, it is not hard to see that for any PPT adversary that adaptive corrupts the platforms there exists another adversary that commits to its corruptions at the very beginning of the experiment, and, in particular, independently of all the public parameters. More in details, given an adversary A which performs at most q dierent join protocols, let A⁰ be the adversary 0$0 that (1) rst samples an index i [q], then corrupts all the platforms expect that i-th, and (2) runs the same as A but aborts if the index i chosen by A in the forgery is not equal to i⁰.

$$ \mathcal{A}^{\prime} $$

$$ q $$

$$ i^{\prime}\xleftarrow{\S}[q] $$

$$ i^{\prime}{\mathrm{-t h}}. $$

$$ i^{*} $$

$$ i^{\prime} $$

Clearly, for any b 2f0*;* 1g we have: h

$$ b \in {0, 1 } $$

$$ \Pr \left[ \mathbf {E x p} _ {\mathcal {A} ^ {\prime}, \Pi} ^ {\mathrm {n o n - f r a m e}} (\lambda) = 1 \right] = \frac {1}{q} \Pr \left[ \mathbf {E x p} _ {\mathcal {A}, \Pi} ^ {\mathrm {n o n - f r a m e}} (\lambda) = 1 \right] $$

In the following, we therefore consider adversaries that non-adaptively corrupts the platforms. We non-frame give a sequence of hybrid experiments, where H₀() := Exp_A0;(). Moreover, we can assume that the machines M_idoes not abort during the join protocol. In fact, if this happened then the winning condition (3) would not be satised.

$$ \ {mathrm H}{0}(\lambda):={\tt E x p}{\mathcal{A}^{\prime},\mathcal{I}}^{{\tt n o n-\dagger r a m e}}(\lambda) $$

$$ \mathcal{M}_{i^{*}} $$

The rst step of the hybrid argument proceed exactly the same as in the hybrid step H₂ and H₃ of the proof of Theorem 1. In the next hybrid we summarize the change. As in the proof of Theorem 1, we call W_ithe winning condition in the hybrid experiment H_i, we set W₁ := (1) ^ (2) ^ (3) ^ (4) and, whenever we don’t mention it explicitly, we set W_i+1:= W_i.

$$ \mathbf{H}_{2} $$

$$ \mathrm{H}_{3} $$

$$ W_{i} $$

$$ \mathbf{H}_{i}. $$

$$ W_{1}\ := $$

$$ (1)\wedge(2)\wedge(3)\wedge(4) $$

$$ W_{i+1}:=W_{i} $$

Hybrid H₁(). Let H₁ be the same as H₀ but where the winning condition is changed and random $ oracle H is programmed. In particular, the hybrid samples an index j [q_H] where q_His an upper bound on the number of oracle queries made by A to H, and upon the j-th query (RO*;* H*;x*) to the

$$ \mathbf{H}_{1}(\lambda) $$

$$ \mathbf{H}_{0} $$

$$ \mathbf{H}_{1} $$

$$ j^{*}\xleftarrow{\mathfrak{S}}[q_{\mathsf{H}}] $$

$$ q_{H} $$

$$ (\mathsf{R0},\mathsf{H},x) $$ random oracle (w.l.g. we assume the adversary does not query twice the RO with the same input) $ if j = j then the hybrid samples crs*;tp_eInit_snd(bgp) and sets the tuple (H;x;* crs*;tp_e) in D_RO, $ else it samples crs;tp_sInit_zk(bgp) and sets the tuple (H;x;* crs*;*tp_s) in D_RO.

$$ \ {\mathrm{w{w.}}{{lbfbf.g}}. $$

$$ \mathsf{t p}{\mathsf{e}}\xleftarrow{{\ mathsf}}}\ \overline{{\mathsf{I n i t}}}{\mathrm{}{s n d}}(\mathsf{b g p}) $$

$$ j=j^{*} $$

$$ (\mathsf{H},x,\mathsf{c r s},\mathsf{t p}_{\mathsf{e}}) $$

$$ D_{\mathrm{R0}} $$

$$ (\mathsf{H},x,\mathsf{c r s},\mathsf{t p_{s}}) $$

$$ \mathrm {t p} _ {\mathrm {s}} \leftarrow^ {$} \overline {{\mathrm {I n i t}}} _ {z k} (\mathrm {b g p}) $$

$$ D_{\mathrm{R0}} $$

Moreover, the new winning condition is set to be W₂ := W₁ ^ (5), where (5) is dened as:

$$ W_{2}:=W_{1}\wedge(5) $$

(bsn*;M*) (the basename-message tuple of the forgery) is queried to the random oracle H at the j-th query.

$$ (\mathsf{b s n}^{},M^{}) $$

$$ j^{*}\mathrm{-t h} $$

Lemma 26. Pr [H₁() = 1] Pr [H₀() = 1] =q_Hnegl().

$$ \operatorname*{P r}\left[{\ {\bf{H}}{1}(\lambda)=1}\right]\geq\operatorname*{P r}\left[{{\bf{H}}{0}(\lambda)=1}\right]/q_{\ {\sf{H}}}-{\sf{n e g l}}(\lambda) $$

The proof of the lemma follows similarly to the proof of Lemmas 4 and 6, therefore it is omitted.

The second step of the hybrid argument proceed similar to the proof of Theorem 2. In particular, we apply the same modications as in the hybrids H₁, H₂ and H₃ of Theorem 2. We summarize in the next hybrid the changes.

$$ \mathbf{H}{1},\mathbf{H}{2} $$

$$ \mathbf{H}_{3} $$

$$ {\bf H}_{2}(\lambda) $$

Hybrid H₂(). Let H₁ be the same as H₀ but where:

$$ \mathbf{H}_{1} $$

$$ \mathbf{H}_{0} $$

1.The random oracle J is programmed to output random common-reference strings in zeroknowledge mode.

2.Let S_combe the zero-knowledge simulator of NIZK_comand let tp_ibe the trapdoor information relative the value id_ias recorded in the database D_RO. Upon query (join*;i ;(id)) (namely, the (i)$ rst message in the join protocol sent by the adversary acting as the issuer) pick t Z_p ⁽ⁱ⁾ (i) (i) (i) and ~ S_com⁽tpⁱ;* [t]₁⁾, and send ⁽[t]₁; ~⁾.

$$ \ \mathsf{t p}_{i}; $$

$$ \mathcal{N I Z K}{}_{\mathsf{c o m}} $$

$$ S_{\mathrm{c o m}} $$

$$ \ d_{i^{*}} $$

$$ D_{\mathrm{R0}} $$

$$ ({\tt j o i n},i^{*},(i d)) $$

$$ t^{(i^{*})}\xleftarrow{\S}\mathbb{Z}_{p} $$

$$ \tilde {\pi} ^ {(i ^ {})} \leftarrow \mathcal {S} _ {\mathrm {c o m}} \left(\mathrm {t p} _ {i ^ {}}, \left[ t ^ {(i ^ {*})} \right] _ {1}\right) $$

$$ ([t^{(i^{})}|_{1},\tilde{\pi}^{(i^{})}) $$

3.Upon oracle query (sign*;i ;M;* bsn*;SigRL) if 9(M_j;bsn_j;_j) 2 SigRL such that_j= ([c]₁;*) (i) and ⁽ y₀;1⁾ [c]₁= [0]₁then output directly?.

$$ \sigma_{j}=([\mathbf{c}]_{1},\pi) $$

$$ \exists(M_{j},{\mathfrak{b s n}}{j},\sigma{j})\in{\mathsf{S i g R L}} $$

$$ (-y_{0}^{(i^{*})},1)\cdot[\ \ {bf c c}]{1}=[0]{1} $$

4.Upon oracle query (sign*;i ;M;* bsn*;SigRL) let = ([c₀;c₁]₁;);* be the output of M_i, if ⁽ⁱ⁾ [c₀y₀]₁6= [c₁] then output directly*?*.

$$ (\mathtt{s i g n},i^{*},M,\mathtt{b s n},\mathsf{S i g R L}) $$

$$ \sigma,=,\bigl([c_{0},c_{1}]{1},\pi\bigr),\pi{\sigma} $$

$$ \ {mathcal M}_{i}, $$

$$ [c_{0}y_{0}^{(i)}]{1}\neq[c{1}] $$

Lemma 27. jPr [H₂() = 1] Pr [H₁() = 1] j2 negl().

$$ |\operatorname*{P r}\left[{\ H}{2}(\lambda)=1\right]-\operatorname*{P r}\left[{\bf H}{1}(\lambda)=1\right]|\in\mathsf{n e g l}(\lambda). $$

The proof of the lemma follows very similar to the conjunction of Lemmas 8,17,18,20 and 19 therefore it is omitted.

Hybrid H₃(). Let H₃ be the same as H₂ but where the signatures are computed dierently. Specically, upon oracle query (sign*;i ;* bsn*;M;* SigRL) the hybrid experiment H₃ computes [c]₁:= (i) $ (K(bsn);K⁽bsn⁾y₀), retrieve the tuple (H;(bsn*;M*);crs;tp_s) from D_ROand computes S_sign(tp_s;[c]) $ (resp. computes S_sign(tp_s;[c ])).

$$ \ {\bf H}_{3}(\lambda) $$

$$ \mathbf{H}_{3} $$

$$ \mathbf{H}_{2} $$

$$ \mathtt{(s i g n,i^{*}} $$

$$ M,\mathsf{S i g R L}) $$

$$ \mathbf{H}_{3} $$

$$ [\mathbf{c}]_{1}:= $$

$$ (\mathsf{K}(\mathsf{b s n}),\mathsf{K}(\mathsf{b s n})y_{0}^{(i^{*})}) $$

$$ (\mathsf{H},(\mathsf{b s n},M),\mathsf{c r s},\mathsf{t p_{s}}) $$

$$ \leftarrow^ {$} \mathcal {S} _ {\mathrm {s i g n}} \left(\mathrm {t p} _ {\mathrm {s}}, [ \mathbf {c} ]\right) $$

$$ D_{\mathrm{R0}} $$

$$ \pi^ {} \leftarrow^ {$} \mathcal {S} _ {\mathrm {s i g n}} \left(\mathrm {t p} _ {\mathrm {s}}, \left[ \mathbf {c} ^ {} \right]\right)) $$

$$ \Pr \left[ \mathbf {H} _ {3} (\lambda) = 1 \right] = \Pr \left[ \mathbf {H} _ {2} (\lambda) = 1 \right]. $$

Lemma 28. Pr [H₃() = 1] = Pr [H₂() = 1].

Proof. The additional check introduced in the hybrid experiment H₂ guarantees that if the instance [c]₁;SigRL is not in the language of the NIZK NIZK_signthen the challenger answers the query with ?. Thus the simulated proofs are generated only for instances in the language. Also by the winning conditions, the adversary would never query a signature for bsn;M, so the retrieved trapdoors tp_s allow for zero-knowledge. The lemma follows by the adaptive composable perfect zero-knowledge property (Def. 5) of NIZK_sign.

$$ \mathbf{H}_{2} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ [\mathbf{c}]_{1},\dot{\mathsf{S i g R L}} $$

$$ {\mathsf{b s n}}^{},M^{} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

Lemma 29. Pr [H₃() = 1] 2 negl().

$$ \operatorname*{P r}\left[{\mathrm{H}}_{3}(\lambda)=1\right]\in{\mathsf{n e g l l}}(\lambda) $$

Proof. We reduce to the SXDH Assumption in G₁. Consider the following adversary B:

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

$$ \ : $$

Adversary B([1;x;y;z]₁):

$$ {\mathcal{B}}([1,x,y,z]_{1}) $$

1.Simulate the experiment H₃(;b) and the random oracles H*;* K*;J, in particular, simulate the random oracle K by maintaining a list D_ROinitially empty and whenever A sends 0 0 0$ the query bsn if (K;bsn;) 62 D_ROthen add the entry (K;bsn;*) where Z_pand return []₁.

$$ \mathbf{H}_{3}(\lambda,b) $$

$$ D_{\mathrm{R0}} $$

$$ (\mathsf{K},\mathsf{b s n}^{\prime},\alpha) $$

$$ \alpha \leftarrow^ {$} \mathbb {Z} _ {p} $$

$$ (\mathsf{K},\mathsf{b s n}^{\prime},*)\not\subseteq D_{\mathtt{R0}} $$

$$ [\alpha]_{1} $$

2.Upon query (sign*;i ;* bsn*;M;* SigRL) Retrieve the tuple (K*;bsn;) from the list D_RO(or create it if it does not exist). Compute the signature by setting [c] [;x*]₁and computing using the simulator of NIZK_sign(according to the change introduced in H₆).

$$ (\mathtt{s i g n},i^{*},\mathtt{b s n},M,\mathsf{S i g R L}) $$

$$ D_{\mathrm{R0}} $$

$$ [\mathbf{c}],\leftarrow,\cdot[\alpha,\alpha x]_{1} $$

$$ \mathcal{N}\mathcal{I}\mathcal{Z}\mathcal{K}_{\mathsf{s i g n}} $$

$$ \mathbf{H}_{6}) $$

3.Let (M;bsn;) be forgery of A. Retrieve the tuple (K*;bsn;) from the list D_RO. If the winning condition W₃ holds, parse = ([c];), extract the proof, computing ([t]₁;* [_sp]₁; [y₀;y₁]₂) E (tp_e;) and output 1 if and only if e([y]₁; [y₀]₂) = e([z]₁;[1]₂).

$$ (M^{},\ \ \mathsf{b s n}^{},\sigma^{*}) $$

$$ (\mathsf{K},\mathsf{b s n}^{*},\alpha) $$

$$ D_{\mathrm{R0}} $$

$$ W_{3} $$

$$ \boldsymbol{\sigma}^{}=(|\mathbf{c}|^{},\boldsymbol{\pi}^{*}) $$

$$ \ ,, $$

$$ \big([t]{1},[\sigma{s p}]{1},[y{0},y_{1}]{2}\big)\leftarrow\mathcal{E}\big(\mathsf{t p}{\mathsf{e}},\pi\big) $$

$$ e\big([y]{1},[y{0}]{2}\big)=e\big([z]{1},[1]_{2}\big) $$

First we notice that, similarly to the proof of Thm 2, given the transcript of the join protocol for the (i) (i) platform i the value y₀ ⁱs uniformly distributed. In particular, the distribution of [x]₁and [y₀]₁ are the same, so the signatures for i produced by B are distributed equivalently to the signatures in H₃. Notice that by the winning condition W₃ we have that (bsn*;M*) is queried at the j-th oracle query, so we can use the trapdoor tp_eand by adaptive knowledge-soundness of NIZK_signthe proof can be extracted and for the extracted value [y₀]₂it holds that [c₂]₁= [y₀ c]₁. Because the signature links to a signature produced by the platform i it must be the case that y₀ = x, thus, when z = xy the equation e([y]₁; [y₀]₂) = e([z]₁;[1]₂) will always hold, while when z is uniformly random the equation will be false (with overwhelming probability). This concludes the proof.

$$ i^{*} $$

$$ y_{0}^{(i^{*})} $$

$$ [x]_{1} $$

$$ \big[y_{0}^{(i^{*})}\big]. $$

$$ i^{*} $$

$$ \mathbf{H}_{3} $$

$$ W_{3} $$

$$ (\mathsf{b s n}^{},M^{}) $$

$$ \pi^{*} $$

$$ \mathcal{N I Z!}_{\mathsf{s i g n}} $$

$$ \mathsf{t p}_{\mathrm{e}} $$

$$ [ y _ {0} ] _ {2} $$

$$ \sigma^{*} $$

$$ [\mathbf{c}{2}]{1}=[y_{0}\cdot!{\mathbf{c}}]_{1} $$

$$ i^{*} $$

$$ y_{0}=x. $$

$$ z=x y $$

$$ e\big([y]{1},[y{0}]{2}\big)=e\big([z]{1},[1]_{2}\big) $$

Acknowledgements

Research leading to these results has been partially supported by the Spanish Government under projects SCUM (ref. RTI2018-102043-B-I00), CRYPTOEPIC (ref. EUR2019-103816), and SECURI- TAS (ref. RED2018-102321-T), and by the Madrid Regional Government under project BLOQUES (ref. S2018/TCS-4339). The rst author was partially supported by the before mentioned projects when he was a postdoctoral fellow at IMDEA Software Institute where he performed the research leading to this paper.

References

1.Abe, M., Fuchsbauer, G., Groth, J., Haralambiev, K., Ohkubo, M.: Structure-preserving signatures and commitments to group elements. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 209{236. Springer, Heidelberg (Aug 2010). doi:10.1007/978-3-642-14623-7 12 2.Ateniese, G., Magri, B., Venturi, D.: Subversion-resilient signature schemes. In: Ray, I., Li, N., Kruegel:, C. (eds.) ACM CCS 15. pp. 364{375. ACM Press (Oct 2015). doi:10.1145/2810103.2813635 3.Bellare, M., Fuchsbauer, G., Scafuro, A.: NIZKs with an untrusted CRS: Security in the face of parameter subversion. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 777{804. Springer, Heidelberg (Dec 2016). doi:10.1007/978-3-662-53890-6 26

2017). doi:10.1007/978-3-319-63697-9 15 https://doi.org/10.1007/978-3-319-63697-9_15

doi:10.1007/978-3-662-48000-7 13 https://doi.org/10.1007/978-3-662-48000-7_13

4.Bellare, M., Micciancio, D., Warinschi, B.: Foundations of group signatures: Formal denitions, simplied requirements, and a construction based on general assumptions. In: Biham, E. (ed.) EURO- CRYPT 2003. LNCS, vol. 2656, pp. 614{629. Springer, Heidelberg (May 2003). doi:10.1007/3-540- 39200-9 38 5.Bellare, M., Sandhu, R.: The security of practical two-party RSA signature schemes. Cryptology ePrint Archive, Report 2001/060 (2001), http://eprint.iacr.org/2001/060 6.Bernhard, D., Fuchsbauer, G., Ghada, E., Smart, N.P., Warinschi, B.: Anonymous attestation with user-controlled linkability. Int. J. Inf. Secur. 12(3) (Jun 2013) 7.Brickell, E., Li, J.: Enhanced privacy ID: A direct anonymous attestation scheme with enhanced revocation capabilities. IEEE Trans. Dependable Sec. Comput. 9(3) 8.Brickell, E., Li, J.: Enhanced privacy id: a direct anonymous attestation scheme with enhanced revocation capabilities. In: ACM WPES (2007) 9.Camenisch, J., Chen, L., Drijvers, M., Lehmann, A., Novick, D., Urian, R.: One TPM to bind them all: Fixing TPM 2.0 for provably secure anonymous attestation. In: 2017 IEEE S&P). pp. 901{920 (2017) 10.Camenisch, J., Drijvers, M., Lehmann, A.: Anonymous attestation with subverted TPMs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 427{461. Springer, Heidelberg (Aug 2017). doi:10.1007/978-3-319-63697-9 15 11.Camenisch, J., Lehmann, A.: (Un)linkable pseudonyms for governmental databases. In: Ray, I., Li, N., Kruegel:, C. (eds.) ACM CCS 15. pp. 1467{1479. ACM Press (Oct 2015). doi:10.1145/2810103.2813658 12.Catalano, D., Fiore, D., Nizzardo, L.: Programmable hash functions go private: Constructions and applications to (homomorphic) signatures with shorter public keys. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part II. LNCS, vol. 9216, pp. 254{274. Springer, Heidelberg (Aug 2015). doi:10.1007/978-3-662-48000-7 13 13.Chase, M., Kohlweiss, M., Lysyanskaya, A., Meiklejohn, S.: Malleable proof systems and applications. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 281{300. Springer, Heidelberg (Apr 2012). doi:10.1007/978-3-642-29011-4 18 14.Chatterjee, S., Menezes, A.: Type 2 structure-preserving signature schemes revisited. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015, Part I. LNCS, vol. 9452, pp. 286{310. Springer, Heidelberg (Nov / Dec 2015). doi:10.1007/978-3-662-48797-6 13 15.Escala, A., Herold, G., Kiltz, E., Rafols, C., Villar, J.: An algebraic framework for Die-Hellman assumptions. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 129{147. Springer, Heidelberg (Aug 2013). doi:10.1007/978-3-642-40084-1 8 16.Faust, S., Kohlweiss, M., Marson, G.A., Venturi, D.: On the non-malleability of the Fiat-Shamir transform. In: Galbraith, S.D., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 60{79. Springer, Heidelberg (Dec 2012). doi:10.1007/978-3-642-34931-7 5 17.Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Discrete Applied Mathematics 156(16) (2008) 18.Groth, J., Sahai, A.: Ecient non-interactive proof systems for bilinear groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415{432. Springer, Heidelberg (Apr 2008). doi:10.1007/978- 3-540-78967-3 24 19.Hofheinz, D., Kiltz, E.: Programmable hash functions and their applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 21{38. Springer, Heidelberg (Aug 2008). doi:10.1007/978-3-540- 85174-5 2 20.Libert, B., Peters, T., Joye, M., Yung, M.: Non-malleability from malleability: Simulation-sound quasiadaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 514{532. Springer, Heidelberg (May 2014). doi:10.1007/978-3-642-55220-5 29 21.Mavroudis, V., Cerulli, A., Svenda, P., Cvrcek, D., Klinec, D., Danezis, G.: A touch of evil: Highassurance cryptographic hardware from untrusted components. In: ACM CCS. pp. 1583{1600 (2017) 22.Mironov, I., Stephens-Davidowitz, N.: Cryptographic reverse rewalls. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 657{686. Springer, Heidelberg (Apr 2015). doi:10.1007/978-3-662-46803-6 22

doi:10.1007/978-3-642-55220-5 29 https://doi.org/10.1007/978-3-642-55220-5_29

doi:10.1007/978-3-662-46803-6 22 https://doi.org/10.1007/978-3-662-46803-6_22