# Subversion-Resilient Enhanced Privacy ID
Antonio Faonio¹, Dario Fiore², Luca Nizzardo⁴, and Claudio Soriente³
1
EURECOM, Sophia Antipolis, France.
faonio@eurecom.fr
2
IMDEA Software Institute, Madrid, Spain.
*f*antonio.faonio, dario.fiore*g*@imdea.org
3
NEC Labs Europe, Madrid, Spain.
claudio.soriente@neclab.eu
4
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
5
https://www.intel.com/content/www/us/en/architecture-and-technology/
software-guard-extensions.html
6
https://trustedcomputinggroup.org/resource/tpm-library-specification/
7 https://snowdenarchive.cjfe.org/ https://snowdenarchive.cjfe.org/
7
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.
8
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 signatureyon a value *y* private to the prospective
group member, and both and *y* are the group member’s secret key; (III) a signatureMon
message *M* is a signature of knowledge for *M* of aythat veries for *y* and the group public
key. (IV) Finally, to support revocation and linkability, a signatureMis 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
*M*produced 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⁰;*y*0*. 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 signatureM, 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 ofM. 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 + 2*n* group elements whereas EPID signatures have 8 + 5*n*, 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.
9
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.
10
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;C*ha;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)
$$
11
In practical deployments a sanitizer may sanitize signatures of multiple signers and a single signer may
have multiple sanitizers.
12
For example, the anonymity denition focuses on an adversary that must tell which, out of two platforms,
output the challenge signature.
13
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 *i*ssuer *I*.
JoinI;Si;Mi*h*(gpk*;*isk)*;*gpk*;*gpk)*i ! hb;*(*b;* svti)*;*sk*i*i. 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 ski, and *S*iobtains a sanitizer verication token svtiand
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*;*ski*;*bsn*;M;* SigRL)*! ?=*(*;*). The signing algorithm takes as input the group public
key gpk, a private key ski, 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 ski).
$$
(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*;*svti)*! ?=*. 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 svti. 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₁;*1*;M₂;*2)*!* 0*=*1. The linking algorithm takes as input the group public key
gpk, a basename bsn, and two message-signature-SigRL triples *M₁;*1and *M₂;*2. 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 *f*ski*g*i, and SigRL to be a set of triples
*f*(bsni*;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)*;*sk*i* Join*h*(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)*;*sk*i* Join*h*(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₁*)*;:::;* (bsnq*;M*q), let *hb;*(*b⁰;*svt)*;*state₁*i* be a possible output of the join protocol JoinA;S;M*h*(gpk*;aux*)*;*gpk*;*(gpk*;aux*)*i* conditioned on *b⁰* = 1 or a possible output of the
join protocol JoinI;A;M*h*(gpk*;aux*)*;*gpk*;*(gpk*;aux*)*i* conditioned on *b* = 1 and leti*;*statei
*M*i(statei 1*;M*i*;*bsni) 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;* stateS*;*stateM*;*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 stateS, the state of the machine stateMand the message sent by the issuerI, 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; stateS;stateM;I):
0 0S
1.(S*;*state) *S :* Join(gpk*;*stateS*;*I);
0M 0
2.(M*;*state) *M :* Join(gpk*;*stateM*;*S);
0M
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; stateM;svt;bsn;M; SigRL):
0 0 0M
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}.
$$
0
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 skiobtained 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 ExpA;(;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;*stateij*;*svt*ij;Bij*) from *Lusr*;
8 : if bsn *2 Bij* then Bad true
0ij
9 : (state*;j*) Sig(*Mij;*stateij*;*svt*ij;*bsn*;M;* SigRL);
0ij
10 : Update (*ij; Mij;*state*;*svt*ij;Bij [f*bsn *g*) in *Lusr*;
11 : if*?2f* 0*;*1*g* then Bad true else*b*;
C(gpk;)
12 : *b⁰ A* ();
13 : if Bad = false return *b⁰*; else return ~*b* $ *f*0*;* 1*g:*
Oracle *C*(gsk*;*)
1 : Upon query (join*;i;I*) :
2 : Retrieve (*i; Mi;*stateS*;*stateM) from *Ljoin;*;
3 : If not nd parse *I* = *Mi* and add (*i; Mi; ?; ?*) in *Ljoin* and return ;
0M
4 : (state⁰⁰S*;*state*;*S) Join(*M*i*;*stateS*;*stateM*;I*);
0M
5 : Store (*i; M*i*;*state⁰⁰S*;*state) in *L*join;
6 : if *S* = concluded then
0M
7 : svt*i* state⁰⁰S*;* store (*i; Mi;*state*;*svt*i;;*) in *Lusr*; return ( *S;*svt*i*);
8 : else return *S :*
9 : Upon query (sign*;i;* bsn*;M;* SigRL) :
10 : if (*i;;;;*) *2= Lusr* then Bad true;
11 : else retrieve (*i; M*i*;*statei*;*svti*;B*i) *2 L*usr;
0i
12 : (state*;*) Sig(*M*i*;*statei*;*svti*;*bsn*;M;* SigRL);
0i
13 : Update (*i; M*i*;*state*;*svti*;B*i *[f*bsn*g*);
14 : if *post* = 0 or *i 62fi₀;i₁g* return else let *i* = *i* and *2f*0*;* 1*g*;
15 : if bsn = bsn then Bad true;
16 : Let *i* = *i₁;* and retrieve tuple (*i; Mi;*statei*;*svt*i;Bi*) *2 Lusr*;
0i
17 : (state*;* ~) Sig(*Mi;*statei*;*svt*i;*bsn*;M;* SigRL);
0i
18 : Update (*i; Mi;*state*;*svt*i;Bi [f*bsn*g*) 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;*statei*;*svt*i*) from *Lusr*;
23 : move the tuple from *Lusr* to *Lcor*;
24 : return (statei*;*svt*i*)*:*
$$
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 ExpA;(*;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 ExpA;(*;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 2 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
*f*sk~ *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 skiobtained 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 skifrom the signer *M*iat the end of the Join protocol, but *M*i
15
is subverted and thus we have no guarantee that skiis 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}
$$
14
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.
15
For instance, *Mi* may store locally only an obfuscated or encrypted version of the secret key.
$$
\mathcal{M}_{i}
$$
16
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*[f*sk*g*) = 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,* AdvA;E;() := Pr ExpA;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 f*pub Init(1)*g*2N*and f*pub*j*pub*;*tp *E*0(1)*g*2N*are 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}
$$
17
Precisely, *E* extracts a token tk linked to sk.
$$
\mathcal{E}
$$ unf
Experiment ExpA;E;():
$
1 : *L*join*;L*usr*;L*corr;Lmsg ;; (pub*;*tp) *E* 0(1)*;* (gpk;gsk) Setup(pub);
C(sk;)
2 : (bsn*;M;;*PrivRL*;*SigRL ) *A* (gpk);
3 : *R f* tk*i* : (*i;;;;*tk*i*) *2 Lcorrg*;
4 : return 1 if and only if ((1) *^* (2) *^* (3)) *_* (4) :
5 : (1) *8*tk*2 R* : (*9*sk*2*PrivRL : 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) *9*sk *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;* svt*i*)*;*state*i*i Join*C;C;Mih*(gpk*;*isk)*;*gpk*;*gpk*i*;
4 : let be the issuer-sanitizer transcript
5 : if *b* = 1 then tk*i E₁*(tp*;*); *Lusr Lusr [* (*i; Mi;*statei*;*svt*i;*tk*i*);
6 : return svt*i*
7 : Upon query (dishonestP join*;i;*) :
8 : if (*i;;;*) *62 Ljoin;* then *Ljoin Ljoin [* (*i;* (gpk*;*gsk)*;;*);
9 : Retrieve (*i;* stateI*;;*) from *L*join;
0I 0I
10 : ( I*;*state) *I :* Join(stateI*;*); stateIstate; *k*(*;I*);
11 : Update (*i;* stateI*;;*) in *Ljoin*;
12 : if *I* = concluded*;* then tk*i E* 1(tp*;*); store (*i; ?; ?; ?;* tk*i*) 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;* stateI*;*stateM*;*) from *L*join;
0U 0U
16 : ( U*;*state) *U :* Join(stateU*;*); stateUstate; if *U* = *I* then *k*(*;I*);
17 : Update (*i;* stateI*;*stateM*;*) in *Ljoin*;
18 : if *U* = *I^ I* = concluded*;* then :
19 : tk*i E* 1(tp*;*); skistateM; store (*i;:M;* ski*; ?;* tk*i*) in *Lusr:*
20 : Upon query (sign*;i;* bsn*;M;* SigRL) :
21 : Retrieve the tuple (*i; M*i*;*statei*;*svti*;*tki) from *L*usr; if not found return*?*;
0i
22 : (state*;*) Sig(*M*i*;*statei*;*svti*;*bsn*;M;* SigRL);
0i
23 : *Lmsg L*msg *[* (*i;* bsn*;M;*); update(*i; M*i*;*state*;*svti*;*tki); return *:*
24 : Upon query (corrupt*;i*) :
25 : Retrieve (*i; Mi;*statei*;*svt*i;*tk*i*) from *Lusr*; move the tuple from *Lusr* to *Lcor*;
26 : return statei*:*
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 tkifrom 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 svtiis 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 tkifrom 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 tkifrom 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
svti6=*?* the signature is sanitized and given to the adversary, otherwise a non-sanitized signature is
returned. Notice that the case svti=*?* (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* ExpA;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 skiobtained 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₂*;* GT*;e; P₁; P₂*), where G₁*;*G₂ and GTare groups of prime
order *p* 2, the elements *P₁; P₂* are generators of G₁*;*G₂ respectively, *e* : G₁ G₂*!* GTis
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 Gi, are denoted in implicit notation
as [*a*]i:= *aP*i, where *i 2 f*1*;* 2*;T g* and *P*T:= *e*(*P₁; P₂*). Every element in Gican be written as
[*a*]ifor some *a 2* Zq, but note that given [*a*]i, it is in general hard to compute *a 2* Zq(discrete
logarithm problem). Given *a;b 2* Zqwe distinguish between [*ab*]i, namely the group element whose
discrete logarithm base *P*iis *ab*, and [*a*]i*b*, namely the execution of the multiplication of [*a*]i
and *b*, and [*a*]1[*b*]2= [*a b*]T, namely the execution of a pairing between [*a*]1and [*b*]2. Vectors
and matrices are denoted in boldface. We extend the pairing operation to vectors and matrices as
>
*e*([A]1*;*[B]2) = [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 ExpA;()
1 : pub Init(1); gpk *A* (pub); *Ljoin;Lusr;Lcorr ;*;
C(gpk;)
2 : (*i ;* bsn*;M;*) *A* (gpk);
3 : Retrieve the tuple (*i ; Mi;*statei*;*svt*i;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;*stateS*;*stateM) from *Ljoin;*;
3 : If not nd parse *I* = *Mi* and add (*i; Mi; ?; ?*) in *Ljoin* and return ;
0M
4 : (state⁰⁰S*;*state*;*S) Join(*M*i*;*stateS*;*stateM*;I*);
0M
5 : Store (*i; M*i*;*state⁰⁰S*;*state) in *L*join;
6 : if *S* = concluded then
0M
7 : svt*i* state⁰⁰S*;* store (*i; Mi;*state*;*svt*i;;*) in *Lusr*; return ( *S;*svt*i*);
8 : else return *S :*
9 : Upon query (sign*;i;* bsn*;M;* SigRL) :
10 : Retrieve (*i; M*i*;*statei*;*svti*;B*i) *2 L*usr;
0i
11 : (state*;*) Sig(*M*i*;*statei*;*svti*;*bsn*;M;* SigRL);
0i
12 : Update (*i; M*i*;*state*;*svti*;L*i *[fh*bsn*;M;ig*);
13 : return;
14 : Upon query (corrupt*;i*) :
15 : Retrieve (*i; Mi;*statei*;*svt*i*) from *Lusr*; move the tuple from *Lusr* to *Lcor*;
16 : return (statei*;*svt*i*)*:*
$$
\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 *2f*0*;* 1*g*; 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* Initzk*that outputs* crs*, and a simulation trapdoor* tps*such that for*
*any sequence f*bgp *G* (1)*g*0*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*;*tps)
$ $
Initzk(bgp)*, the proofs generated via S* (tps*;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* Initsnd*that outputs* crs *and an extraction trapdoor* tpe*such that for*
*any sequence f*bgp *G* (1)*g*0*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*(tpe*;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.*
---
| ExpderprivA,NTZK(λ):bgp$leftarrow $G(1^{\lambda});b$leftarrow $\{0,1\}$; (crs,tp_s)$leftarrow \overline{\mathrm{Init}}_{zk}(bgp);(L,x,\pi,T)$leftarrow A(crs,tp_s);Assert V(crs,L,x,\pi)=1;If b=0 then $\pi^{\prime}$leftarrow S(tp_s,L,T_x(x));else $\pi^{\prime}$leftarrow ZKEval(crs,L,\pi,T);b'leftarrow A(\pi');Output b'=b. | Ext-soundA,NTZK,E(λ):bgp$leftarrow $G(1^{\lambda});(crs,tp_e)$leftarrow $\overline{\mathrm{Init}}_{snd}(bgp)(x,L,\pi)$leftarrow A(crs);w\leftarrow E(tp_e,L,x,\pi);Output V(crs,L,x,\pi)=1\land(x,w)\notin R. |
| --- | --- |
$$
\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 signaturespon a Pedersen commitment [*t*]1whose opening y is known to the signer only.
Following the description given in Sec. 1.1, the conjunction ofspand [*t*]1forms 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 signaturespmade by *I* on message a commitment
[*t*]1and 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 thesp, the commitment [*t*]1and 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₁*]1:= 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₁*]1, while for (signature-based) revocation we additionally let the signer
0 0
prove that all the revoked signatures contain a [*c₁*]1of 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* = (KGensp*;*Sigsp*;*Versp) where messages are elements
‘1 ‘2
of G₁ and signatures are in G1G2.
$$
{\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*[bi]1*g*i=1, gpk = ([h]1*;*pksp), 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]1*;*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]1. 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*]1*;y* : *x;y;z 2* Zp*g*.
$$
\{0,1\}^{*}\rightarrow
$$
{ Three cryptographic hash functions H*;*J and K modeled as random oracles, where H : *f*0*;* 1*g!*
*f*0*;* 1*g*,J: *f*0*;* 1*g!f*0*;* 1*g* and K : *f*0*;* 1*g!* 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 crssvt *NIZK*svt*:* Init(bgp), and sample h Zp. Output
18
pub = (bgp*;*crssvt*;*[h]1)
$
Setup(pub)*!* (gpk*;*isk): sample (sksp*;*pksp) KGensp(bgp), and set isk := sksp, gpk := pksp.
JoinI;H;M*h*(gpk*;*isk)*;*gpk*;*gpk*i!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*;* 1*g* and send *id* to *H* and *M*. All the parties compute crscomJ(*id*).
$
2. *H* samples *y₀;c* Zp, sets svt := [*c;cy₀*]1and sends (*y₀;*svt) to *M*.
3. *M* does as described below:
$
{ Sample *y*MZpand compute [*t*M]1:= (*y₀;y*M) [h]1;
{M *NIZK*com*:* P(crscom*;*([h]1*;* [*t*M]1)*;* [*y₀;y*M]2);
{ Send ([*t*M]1*;*M) to *H*.
4. *H* checks *NIZK*com*:* V(crscom*;*([h]1*;* [*t*M]1)*;*M) = 1; if the check passes:
$
{ Sample *y*HZpand set [*t*]1:= [*t*M+ *h₂ y*H]1;
{ ComputeH *NIZK*com*:* ZKEval(crscom*;*M*;* [*y*H]1);
{ Send *y*Hto *M* and ([*t*]1*;*H) to *I*.
5. *I* checks *NIZK*com*:* V(crscom*;*([h]1*;* [*t*]1)*;*H) = 1, and if the check passes then *I* computes
spSigsp(sksp*;* [*t*]1) and sendsspto *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]1y = [*t*]1and (2) Versp(pksp*;* [*t*]1*;*sp) = 1
{ If so, send the special message completed to *I* (through *H*) and output sk := ([*t*]1*;*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*]1*;*sp*;*y), the base name
m
bsn *2f*0*;* 1*g*, the message *M 2f*0*;* 1*g*, and a signature revocation list
SigRL = *f*(bsni*;M*i*;*i)*g*i2[n], generate a signature and a proof as follows:
1.Set [*c*]1K(bsn) and set [c]1:= [*c;c y₀*]1;
2.Computesign*:* P(H(bsn*;M*)*;*([c]1*;*SigRL)*;*([*t*]1*;* [sp]1*;*[y]2));
3.Computesvt*:* P(crssvt*;*(svt*;*[c]1)*;y₀*);
4.Output := ([c]1*;*) and.
Sanitize(gpk*;*bsn*;M;*(*;*)*;*SigRL*;*svt): Parse = ([c]1*;*) and proceed as follows:
1.Ifsign*:* V(crssign*;*H(bsn*;M*)*;*([c]1*;*SigRL)*;*) = 0 orsvt*:* V(crssvt*;*(svt*;*[c]1)*;*) = 0 then
output*?*.
0
2.Re-randomize by computingsign*:* ZKEval(H(bsn*;M*)*;*([c]1*;*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 *NIZK*svt 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]1*;*) and PrivRL := *ff₁;:::;f*n1*g*. 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*]1,
$$
{\mathsf{K}}({\mathsf{b s n}})=[c]_{1}
$$
2.sign*:* V(H(bsn*;M*)*;*([c]1*;*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 *8*sk *2* PrivRL : let sk = ([*t*]1*;*sp*;* (*y₀;y₁*)) check ( *y₀;*1) [c]16= [0]1.
Link(gpk*;*bsn*;M₁;*1*;M₂;*2)*!* 0*=*1. Parsei= ([ci]1*;*i) for *i* = 1*;*2. Return 1 if and only if
[c₁]1= [c₂]1and both signatures are valid, i.e., Ver(gpk*;*bsn*;M₁;*1) = 1 and
Ver(gpk*;*bsn*;M₂;*2) = 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]1*;*
SigRL) and if *NIZK*sign*:V*(crs*;*(gpk*;*[b]1*;*SigRL)*;*) = 1 then *NIZK*sign*:V*(crs*;*(gpk*;*[b]1*;;*)*;*) =
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²1G₂ and verication requires 2 PPEs and 6 pairings. To evaluate
r
eciency of our construction we look at *R*signwhere we have SigRL = *f*[bi]1*g*i=1, gpk = ([h]1*;*pksp),
T
and y = (*y₀;y₁*) and we rely on [15] (Table 1, where we consider *‘* = 2 and *k* = 1). We are
committing to [*t*]1*;*sp*;*[y]2: sincesphas size 3 and [y]2has 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]1*2 span*([1*;y₀*]1) 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,
Versp(pksp*;* [*t*]1*;*sp) = 1 is the verication of a signature which requires 2 PPEs to be veried, for
T
a total of 8 elements. Finally, *8i* : [bi]1*62 span*([1*;y₀*]1) consists in *n* linear equations, for a total
of 2*n* elements (2 elements for each signature in SigRL). It follows that the resulting SR-EPID has
signatures of size 28+2*n* group elements, where *n* is the number of signatures in SigRL. The original
EPID scheme [8] has signatures of size 8 + 5*n*. 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 *j*SigRL*j* (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 *2f*1*;* 2*g* if the distribution
$3
[*x;y;xy*] and the distribution [*x;y;z*] where (*x;y;z*) Zpare 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*sign*and NIZK*com*are adaptive extractable*
*sound, perfect composable zero-knowledge and strong derivation private, NIZK*svt*is 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]2. Finally, looking at the transcript of the join protocol, the extractor can produce the
token tk = ([*t*]1*;*sp*;*[y]2). 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*]1signed 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*]1that 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*]1is in *Q*spand the ones where [*t*]1is 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^{*})
$$
19
In our concrete instantiation we use GS-NIZK proof system, for which extraction in the source groups is
more natural and ecient.
20
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*;* 1*g*, 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*;*tpe) exists in *D*ROand if so return crs₁, else
$
sample crs*;*tpe *NIZK*com*:* Initsnd(bgp), add the tuple (J*;x;* crs*;*tpe) 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*;*tpe) into the database
*D*RO, and if it does not exist then it output*?*. Else, nd the message ([*t*]1*;*S) from *S*,
run the extractor [y]2 *E*com(tpe*;*S), nd the messagespsent from the issuer *I*, and
output tk = ([*t*]1*;*sp*;*[y]2).
$$
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*]1*;* [sp]1*;*y) and check if tk = ([*t*]1*;* [sp]1*;*[y]2). We dene the CheckSig algorithm. The algorithm
given in input gpk, tk and a signature, parses tk = ([*t*]1*;* [sp]1*;* [*y₀;y₁*]2) and = ([*c₀;c₁*]1*;*) and
return 1 if and only if *e*([*c₀*]1*;* [*y₀*]2) = *e*([*c₁*]1*;*[1]2). The property 1 is obviously true, in fact, the
function that map *x 2* Zpto [*x*]*2*2 G is injective, moreover, the property 2 is true too, in fact,
the step (3) of the verication algorithm checks that [*c₀*]1*y₀* = [*c₁*]1, which is the same of verifying
*e*([*c₀*]1*;* [*y₀*]2) = *e*([*c₁*]1*;*[1]2).
$$
\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}
$$
21
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⁰0() := 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;E*0*;(), 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⁰2(). Let H⁰2() := ExpA;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 Hi, we set *W₀* := *W* and, whenever we don’t mention it explicitly, we set
unf
*W*i+1:= *W*i. Let H₀() := ExpA;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. *j*Pr [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]2using the knowledge extractor of *NIZK*comand output tk = ([*t*]1*;*sp*;*[y]2),
since [*t*]1*;*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*]1*;*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]1*;*) 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*;*tpe *NIZK*sign*:* Initsnd(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}}
$$
22
Recall that condition (4) states that *9*sk *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
*j*Pr [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*]1*;* [sp]1*;*[y ]2) *E*sign(tpe*;*), where (*;*[c ]1) 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 Versp(pksp*;* [*t*]1*;* [sp]1) = 1 and [*t*]t= [h y ]tand for any ([*c⁰*0*;c⁰*1]1*;*) *2*
SigRL we have [*c⁰*1]t6= [*c⁰*0*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 ]1*;*SigRL
and with label *y* does verify but (by the condition *:*(6) ) either the Versp(gpk*;* [*t*]1*;*sp) = 0 or
T 0
[*t*]t= [h y]texists ([*c⁰*0*;c⁰*1]1*;*) *2* SigRL where [*c⁰*1]t= [*c⁰*0*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*;*tps *NIZK*sign*:* Initzk(bgp)
and set the tuple (H*;x;* crs*;*tps) 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. *j*Pr [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*;*statei*;*svti*;*tki) *2 L*ursand svti6=*?* (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]1*;*)*;*state *M*i(statei*;*bsn*;M;* SigRL), retrieve the tuple (H*;*(bsn*;M;* crs*;*tps) from *D*RO
(or create it if it does not exist), computes ~ *S* (tps*;*([c]1*;*SigRL)) and outputs ([c]1*;* ~).
$$
{\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. *j*Pr [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 *j*Pr [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]1is of the right form. Specically,
upon query (sign*;i;* bsn*;M;* SigRL) where (*i; M*i*;*statei*;*svti*;*) *2 L*ursand svti6=*?* (namely, the
0i
sanitizer *S* is honest), the hybrid computes = ([*c₀;c₁*]1*;*)*;*state *M*i(statei*;*bsn*;M;* SigRL),
and return*?* to the adversary if *e*([*c₁*]1*;*[1]2) 6= *e*([*c₀*]1*;* [*y₀*]2).
$$
\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 svti= [*c;cy₀*]1, and that the proof proves that (svti*;*[c]1) are of form
[*x;xy;z;zy*] for *x;y;z 2* Zp. Therefore, if the hybrid H₆ outputs*?* but H₅ does not, then the
proof veries but c does not lie in the subspace spanned by svti, 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*]1: (*;;;;*([*t*]1*;*sp*;*[y]2)) *2 L*usr*g*. 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. *j*Pr [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*]1*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]1):
$$
\ [,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]1:= [*x;y*]1.
$$
\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*]1*;* [sp]1*;*[y ]2)
be the extracted witness and [y ]2= [*y₀;y₁*]2.
$$
(\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]2such that (*;;;;*([*t*]1*;;*[y]2)) *2 L*usrand (*;*bsn*;M;*) *2 L*msg. Compute
[*d₀*]2:= [*y₀ y₀*]2and [*d₁*]2:= [*y₁ y₁*]2and return 1 if and only if *e*([*z*]1*;* [*d₁*]2) =
*e*([*h₀*]1*;* [*d₀*]2).
$$
(*, *, *, *, \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 ]1*;*) and = ([c]1*;*). When Bad happens, because of condition (3) then
[*c₁*] 6= [*c₁*] (the signature are unlinkable), also, because of (*;*bsn*;M;*) *2 L*msg*^* [*t*]1*2Q*spthere
must exist [y]2and 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*]1*;* [*d₁*]2) = *e*([*h₀*]1*;* [*d₀*]2)
must hold, while if *z* is uniformly random in Zpthen 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*]1*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*]1*;;*)) *2 L*usr. Namely, the witness [*t*]1extracted 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*]1*2Q*sp] 1*=p⁰*(). By the denition of A₁, this
polynomial exists. Notice that the condition (8) holds when [*t*]1*2 M* and [*t*]1is 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*:* Initzkbe 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*;*
23$
*j; I;*), the challenger picks a random *id f* 0*;* 1*g* (we assume that *id* was not queried to J),
computes crs*;*tps *NIZK*com*:* Initzk(bgp) and set the entry (J*;id ;* crs*;*tps) 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₁ *j*Pr [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}}
$$
23
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*]1*;*S), compute ~*S* Scom(tpscom*;* [*t*]1) and set ~ be the same as but where
the message ([*t*]1*;*S) is substituted with the message ([*t*]1*;* ~S). Return svti*;* ~ 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*;* 3*g* 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 join*;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 2f*1*;* 2*;* 3*g*, 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]1*;*) be a signature output by the challenger on query
(sign*;j;M;* SigRL), the vector [c]1is 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
crssvt*;*tpsvt *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(tpsvt*;*[svti]1*;*[c]1).
$$
{\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₁ *j*Pr [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]1):
$$
\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]1=
$
[*x;x*]1where Zp.
$$
[\mathbf{h}]_{1}\,=
$$
$$
\alpha \leftarrow^ {\$} \mathbb {Z} _ {p}.
$$
3. (Install the Challenge - part 2.) Eventually, the adversary sends the query (honest join*;*
*j; M*i)). 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 1
Recall that by the change introduced in the hybrid H₉ the proofSis 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]1*;*) 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*]1*;* [sp]1*;*
[y ]2) be the extracted witness and [y ]2= [*y₀;y₁*]2.
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*;*[1]2) = *e*([1]1*;* [*y₀* + *y₁ y₀*]2).
$$
({\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]1*;* [*t*M]2*;*Mis equivalent to the one in H₁₂,
thus *B* perfectly simulates H₁₂. Also notice that if H₁₁ = 1 then the extracted value [y]2is 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(pksp) with oracle access to Osign(sksp;)
1.Simulate the hybrid H₆, in particular use pkspto 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*]1*;* [*t*]2*;*S)
query a signature for the message [*t*]1, 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*]1*;* [sp]1*;*[c ]1) as the hybrid does,
and output [*t*]1*;* [sp]1.
$$
\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*]1*62 f*[*t*]1: (*i;;;;*([*t*]1*;;*)) *2 L*corr*g*. Also by
the denition of *A* being in A₂ we have that [*t*]1*62 f*[*t*]1: (*i;;;;*([*t*]1*;;*)) *2 L*usr*g* (with
overwhelming probability). Therefore, the adversary *B* has not queried [*t*]1to 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*sign*and NIZK*com*are 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*svt*is 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 ]1*;*) still contains the value [*c₁*]1= 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 2f*0*;* 1*g* 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*) := ExpA*0*;(*;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.
2
$$
\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{}{\bf~L e m m a~17.~\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) (i2)
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]1*;*M)*;*state *M*i(statei*;id*), performs the same verication
(i) (i) (i) (i)
that *S* does and if the checks hold compute [*t*]1as *S* does and ~ *S*com(tp*;* [*t*]1). Return
(i) (i)
([*t*]1*;* ~).
$$
{\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{}{\bf~L e m m a~18.~\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*;*bsnj*;*j) *2* SigRL
(i)
such thatj= ([cj]1*;*j) and ( *y₀;*1) [cj]1= [0]1then 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 2f*0*;* 1*g,* Pr [H₃(*;b*) = *b*] = Pr [H₂(*;b*) = *b*]*.*
*Proof.* Recall the relation *R*signin Eq. (1) states that for any tuple (*M*j*;*bsnj*;*([cj]*;*j)) in SigRL we
(i) (i)
have that ( *y₀;*1) [cj]1= [0]1(namely, cjis 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*;*tps *NIZK*sign*:* Initzk(bgp) and
sets the tuple (H*;x;* crs*;*tps) 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. *j*Pr [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(tps*;*[c]) (resp. computes
$
*S*sign(tps*;*[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 2f*0*;* 1*g,* 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]1*;*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* Zpfor *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{}{\bf~L e m m a~22.~\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 distribution *t* Zpand *t*M+ h₁*y*Swhere *y*SZpare equivalent.
(i)
Moreover, conditioning on a specic value for *t* the view 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]1is of the right form. Specically, upon query
0i
(sign*;i;M;* SigRL) where and *i 2fi₁;i₂g*, the hybrid computes = ([*c₀;c₁*]1*;*)*;*state *M*i(statei*;M*),
and return*?* to the adversary if *e*([*c₁*]1*;*[1]2) 6= *e*([*c₀*]1*;* [*y₀*]2).
$$
\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 2f*0*;* 1*g,* 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* Zpis sampled and [c ]1[*c₀;z c₀*]1where [*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 2f*0*;* 1*g, 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*]1) and reply with [*x*]1else add the entry
0$
(bsn*;* 0*;*) where Zpand return []1.
$$
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*;*bsnj*;*j= ([*c*j;0*;c*j;1]1*;*j)) in SigRL such that (bsn*;* 0*;*) *2 D*ROand [*c*j;1] = [*y*]1
output directly*?* (simulating the check introduced in H₄). Compute the signature by
setting [c] [1*;y*]1and 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*]1and 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*]1and [*y₀*]1are 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*sign*and NIZK*com*are 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*svt*is 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*]2given
[*x*]1, which directly implies the XDH assumption in G₁. The idea of the reduction is that, given
the challenge [*x*]1we can (implicitly) install the element *x* as the rst element of the platform key
of the *i*-th platform. Notice that given [*x*]1, 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]1*;*) produced by the *i*-th platform,
recall that the linking procedure, given the two signatures on the same basename bsn , checks that
[c ]1= [c]1and veries the signatures, thus we have [c₁] = K(bsn) *x* and the reduction must have
extracted the value [*x*]2from 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 2f*0*;* 1*g* 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₀() := ExpA0;(). 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 Hi, 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*;*tpeInitsnd(bgp) and sets the tuple (H*;x;* crs*;*tpe) in *D*RO,
$
else it samples crs*;*tpsInitzk(bgp) and sets the tuple (H*;x;* crs*;*tps) 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 tpibe 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* Zp
(i) (i) (i) (i)
and ~ *S*com(tpi*;* [*t*]1), and send ([*t*]1*;* ~).
$$
\ \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*;*bsnj*;*j) *2* SigRL such thatj= ([c]1*;*)
(i)
and ( *y₀;*1) [c]1= [0]1then 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₁*]1*;*)*;* be the output of *M*i, if
(i)
[*c₀y₀*]16= [*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. *j*Pr [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]1:=
(i) $
(K(bsn)*;*K(bsn)*y₀*), retrieve the tuple (H*;*(bsn*;M*)*;*crs*;*tps) from *D*ROand computes *S*sign(tps*;*[c])
$
(resp. computes *S*sign(tps*;*[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]1*;*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 tps
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]1):
$$
{\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 Zpand
return []1.
$$
\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*]1and
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*]1*;* [sp]1*;* [*y₀;y₁*]2) *E* (tpe*;*) and output 1 if and only if *e*([*y*]1*;* [*y₀*]2) = *e*([*z*]1*;*[1]2).
$$
(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₀* is uniformly distributed. In particular, the distribution of [*x*]1and [*y₀*]1
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 tpeand by adaptive knowledge-soundness of *NIZK*signthe
proof can be extracted and for the extracted value [*y₀*]2it holds that [c₂]1= [*y₀* c]1. 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*]1*;* [*y₀*]2) = *e*([*z*]1*;*[1]2) 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