<<

. 8
( 19)



>>


Rosario Gennaro
IBM T.J.Watson Research Center
P.O.Box 704, Yorktown Heights NY 10598
rosario@watson.ibm.com




Abstract. We introduce the notion of multi-trapdoor commitments
which is a stronger form of trapdoor commitment schemes. We then
construct two very efficient instantiations of multi-trapdoor commitment
schemes, one based on the Strong RSA Assumption and the other on the
Strong Diffie-Hellman Assumption.
The main application of our new notion is the construction of a compiler
that takes any proof of knowledge and transforms it into one which is
secure against a concurrent man-in-the-middle attack (in the common
reference string model). When using our specific implementations, this
compiler is very efficient (requires no more than four exponentiations)
and maintains the round complexity of the original proof of knowledge.
The main practical applications of our results are concurrently secure
identification protocols. For these applications our results are the first
simple and efficient solutions based on the Strong RSA or Diffie-Hellman
Assumption.


1 Introduction

A proof of knowledge allows a Prover to convince a Verifier that he knows some
secret information (for example a witness for an N P-statement Since
must remain secret, one must ensure that the proof does not reveal any informa-
tion about to the Verifier (who may not necessarily act honestly and follow the
protocol). Proofs of knowledge have several applications, chief among them iden-
tification protocols where a party, who is associated with a public key, identifies
himself by proving knowledge of the matching secret key.
However when proofs of knowledge are performed on an open network, like
the Internet, one has to worry about an active attacker manipulating the con-
versation between honest parties. In such a network, also, we cannot expect to
control the timing of message delivery, thus we should assume that the adversary
has control on when messages are delivered to honest parties.
Extended Abstract. The full version of the paper is available at
*

http://eprint.iacr.org/2003/214/

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 220“236, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
Multi-trapdoor Commitments 221

The adversary could play the “man-in-the-middle” role, between honest
provers and verifiers. In such an attack the adversary will act as a prover with
an honest verifier, trying to make her accept a proof, even if the adversary does
not know the corresponding secret information. During this attack, the adver-
sary will have access to honest provers proving other statements. In the most
powerful attack, the adversary will start several such sessions at the same time,
and interleave the messages in any arbitrary way.
Informally, we say that a proof of knowledge is concurrently non-malleable,
if such an adversary will never be able to convince a verifier when she does not
know the relevant secret information (unless, of course, the adversary simply
relays messages unchanged from an honest prover to an honest verifier).
OUR MAIN CONTRIBUTION. We present a general transformation that takes any
proof of knowledge and makes it concurrently non-malleable. The transformation
preserves the round complexity of the original scheme and it requires a common
reference string shared by all parties.
The crucial technical tool to construct such compiler is the notion of multi-
trapdoor commitments (MTC) which we introduce in this paper. After defining
the notion we show specific number-theoretic constructions based on the Strong
RSA Assumption and the recently introduced Strong Diffie-Hellman Assump-
tion. These constructions are very efficient, and when applied to the concurrent
compiler described above, this is the whole overhead.
MULTI-TRAPDOOR COMMITMENTS. Recall that a commitment scheme consist
of two phases, the first one in which a sender commits to a message (think of it
as putting it inside a sealed envelope on the table) and a second one in which
the sender reveals the committed message (opens the envelope).
A trapdoor commitment scheme allows a sender to commit to a message with
information-theoretic privacy. I.e., given the transcript of the commitment phase
the receiver, even with infinite computing power, cannot guess the committed
message better than at random. On the other hand when it comes to open-
ing the message, the sender is only computationally bound to the committed
message. Indeed the scheme admits a trapdoor whose knowledge allows to open
a commitment in any possible way. This trapdoor should be hard to compute
efficiently.
A multi-trapdoor commitment scheme consists of a family of trapdoor com-
mitments. Each scheme in the family is information-theoretically private. The
family admits a master trapdoor whose knowledge allows to open any commit-
ment in the family in any way it is desired. Moreover each commitment scheme
in the family admits its own specific trapdoor. The crucial property in the def-
inition of multi-trapdoor commitments is that when given the trapdoor of one
scheme in the family it is infeasible to compute the trapdoor of another scheme
(unless the master trapdoor is known).
CONCURRENT COMPOSITION IN DETAIL. When considering a man-in-the-middle
attacker for proofs of knowledge we must be careful to define exactly what kind
of concurrent composition we allow.
TEAM LinG
222 Rosario Gennaro

Above we described the case in which the attacker acts as a verifier in sev-
eral concurrent executions of the proof, with several provers. We call this left-
concurrency (as usually the provers are positioned on the left of the picture). On
the other hand right-concurrency means that the adversary could start several
concurrent executions as a prover with several verifiers.
Under these attacks, we need to prove that the protocols are zero-knowledge
(i.e. simulatable) and also proofs of knowledge (i.e. one can extract the wit-
ness from the adversary). When it comes to extraction one also has to make
the distinction between on-line and post-protocol extraction [27]. In an on-line
extraction, the witness is extracted as soon as the prover successfully convinces
the verifier. In a post-protocol extraction procedure, the extractor waits for the
end of all the concurrent executions to extract the witnesses of the successful
executions.
In the common reference string it is well known how to fully (i.e. both left and
right) simulate proofs of knowledge efficiently, using the result of Damgård [16].
We use his techniques, so our protocols are fully concurrently zero-knowledge.
Extraction is more complicated. Lindell in [30] shows how to do post-protocol
extraction for the case of right concurrency. We can use his techniques as well.
But for many applications what really matters is on-line extraction. We are able
to do that only under left-concurrency1. This is however enough to build fully
concurrently secure applications like identification protocols.
PRIOR WORK. Zero-knowledge protocols were introduced in [24]. The notion of
proof of knowledge (already implicit in [24]) was formalized in [21,6].
Concurrent zero-knowledge was introduced in [20]. They point out that the
typical simulation paradigm to prove that a protocol is zero-knowledge fails to
work in a concurrent model. This work sparked a long series of papers culmi-
nating in the discovery of non-constant upper and lower bounds on the round
complexity of concurrent zero-knowledge in the black-box model [13,34], unless
extra assumptions are used such as a common reference string. Moreover, in a
breakthrough result, Barak [2] shows a constant round non-black-box concurrent
zero-knowledge protocol, which however is very inefficient in practice.
If one is willing to augment the computational model with a common refer-
ence string, Damgård [16] shows how to construct very efficient 3-round protocols
which are concurrent (black-box) zero-knowledge.
However all these works focus only on the issue of zero-knowledge, where one
has to prove that a verifier who may engage with several provers in a concurrent
fashion, does not learn any information. Our work focuses more on the issue
of malleability in proofs of knowledge, i.e. security against a man-in-the-middle
who may start concurrent sessions.
The problem of malleability in cryptographic algorithms, and specifically
in zero-knowledge proofs, was formalized by Dolev et al. in [19], where a non-
malleable ZK proof with a polylogarithmic number of rounds is presented. This
protocol, however, is only sequentially non-malleable, i.e. the adversary can only
1
However, as we explain later in the Introduction, we could achieve also right-
concurrency if we use so-called

TEAM LinG
Multi-trapdoor Commitments 223

start sessions sequentially (and non concurrently) with the prover. Barak in [3]
shows a constant round non-malleable ZK proof in the non-black-box model (and
thus very inefficient).
Using the taxonomy introduced by Lindell [29], we can think of concurrent
composition as the most general form of composition of a protocol with itself
(i.e. in a world where only this protocol is run). On the other hand it would
be desirable to have protocols that arbitrarily compose, not only with them-
selves, but with any other “secure” protocol in the environment they run in.
This is the notion of universal composable security as defined by Canetti [11].
Universally composable zero-knowledge protocols are in particular concurrently
non-malleable. In the common reference string model (which is necessary as
proven in [11]), a UCZK protocols for Hamiltonian Cycle was presented in [12].
Thus UCZK protocols for any NP problem can be constructed, but they are
usually inefficient in practice since they require a reduction to the Hamiltonian
Cycle problem.
As it turns out, the common reference string model is necessary also to
achieve concurrent non-malleability (see [30]). In this model, the first theoretical
solution to our problem was presented in [17]. Following on the ideas presented
in [17] more efficient solutions were presented in [27,22,31].
Our compiler uses ideas from both the works of Damgård [16] and Katz [27],
with the only difference that it uses multi-trapdoor instead of regular trapdoor
commitments in order to achieve concurrent non-malleability.
SIMULATION-SOUND TRAPDOOR COMMITMENTS. The notion of Simulation-
Sound Trapdoor Commitments (SSTC), introduced in [22] and later refined and
improved in [31], is very related to our notion of MTC. The notion was introduced
for analogue purposes: to compile (in a way similar to ours) any into
one which is left-concurrently non-malleable. They show generic constructions
of SSTC and specific direct constructions based on the Strong RSA Assumption
and the security of the DSA signature algorithm.
The concept of SSTC is related to ours, though we define a weaker notion
of commitment (we elaborate on the difference in Section 3). The important
contribution of our paper with respect to [22,31] is twofold: (i) we show that
this weaker notion is sufficient to construct concurrently non-malleable proofs;
(ii) because our notion is weaker, we are able to construct more efficient number
theoretic instantiations. Indeed our Strong RSA construction is about a factor of
2 faster than the one presented in [31]. This efficiency improvement is inherited
by the concurrently non-malleable proof of knowledge, since in both cases the
computation of the commitment is the whole overhead2.
2
In [22,31] are introduced, which dispense of the need for rewinding when
extracting and thus can be proven to be left and right-concurrently non-malleable
(and with some extra modification even universally composable). It should be noted
that if we apply our transformation to the so-called introduced by [22],
then we obtain on-line extraction under both left and right concurrency. However we
know how to construct efficient direct constructions of only for knowl-
edge of discrete logarithms, and even that is not particularly efficient. Since for the
applications we had in mind left-concurrency was sufficient, we did not follow this
path in this paper. TEAM LinG
224 Rosario Gennaro

REMARK. Because of space limitations, all the proofs of the Theorems, and
various technical details are omitted and can be found in the full version of the
paper.

2 Preliminaries
In the following we say that function is negligible if for every polynomial
Q(·) there exists an index such that for all
Also if A(·) is a randomized algorithm, with we denote the event
that A outputs the string With we denote the probability
of event B happening after

2.1 One-Time Signatures
Our construction requires a strong one-time signature scheme which is secure
against chosen message attack. Informally this means that the adversary is given
the public key and signatures on any messages of her choice (adaptively chosen
after seeing the public key). Then it is infeasible for the adversary to compute a
signature of a new message, or a different signature on a message already asked.
The following definition is adapted from [25].
Definition 1. (SG,Sig, Ver) is a strong one-time secure signature if for every
probabilistic polynomial time forger the following




is negligible in
One-time signatures can be constructed more efficiently than general signatures
since they do not require public key operations (see [7, 8, 28]). Virtually all the
efficient one-time signature schemes are strong.

2.2 The Strong RSA Assumption
Let N be the product of two primes, N = pq. With we denote the Euler
function of N, i.e. With we denote the set of integers
between 0 and N “ 1 and relatively prime to N.
Let be an integer relatively prime to The RSA Assumption [35]
states that it is infeasible to compute in I.e. given a random element
it is hard to find such that
The Strong RSA Assumption (introduced in [4]) states that given a random
element in it is hard to find such that The
assumption differs from the traditional RSA assumption in that we allow the
adversary to freely choose the exponent for which she will be able to compute

We now give formal definitions. Let be the set of integers N, such
that N is the product of two primes.
TEAM LinG
Multi-trapdoor Commitments 225

Assumption 1 We say that the Strong RSA Assumption holds, if for all prob-
abilistic polynomial time adversaries the following probability


is negligible in
A more efficient variant of our protocol requires that N is selected as the product
of two safe primes, i.e. N = pq where and both
are primes. We denote with the set of integers N, such that N is the
product of two safe primes. In this case the assumptions above must be
restated replacing with

2.3 The Strong Diffie-Hellman Assumption
We now briefly recall the Strong Diffie-Hellman (SDH) Assumption, recently
introduced by Boneh and Boyen in [9].
Let G be cyclic group of prime order generated by The SDH Assumption
can be thought as an equivalent of the Strong RSA Assumption over cyclic
groups. It basically says that no attacker on input for some
random should be able to come up with a pair such that
Assumption 2 We say that the Assumption holds over a cyclic group
G of prime order generated by if for all probabilistic polynomial time adver-
saries the following probability


is negligible in
Notice that, depending on the group G, there may not be an efficient way to
determine if succeeded in outputting as above. Indeed in order to check
if when all we have is we need to solve the Decisional Diffie-
Hellman (DDH) problem on the triple Thus, although Assumption
2 is well defined on any cyclic group G, we are going to use it on the so-called
gap-DDH groups, i.e. groups in which there is an efficient test to determine (with
probability 1) on input if or not. The gap-DDH property
will also be required by our construction of multi-trapdoor commitments that
uses the SDH Assumption3.

2.4 Definition of Concurrent Proofs of Knowledge
POLYNOMIAL TIME RELATIONSHIPS. Let be a polynomial time computable
relationship, i.e. a language of pairs such that it can be decided in polyno-
mial time in if or not. With we denote the language induced
by i.e.
3
Gap-DDH groups where Assumption 2 is believed to hold can be constructed using
bilinear maps introduced in the cryptographic literature by [10].

TEAM LinG
226 Rosario Gennaro

More formally an ensemble of polynomial time relationships consists
of a collection of families where each is a family of
polynomial time relationships To an ensemble we associate a random-
ized instance generator algorithm IG that on input outputs the description of
a relationship In the following we will drop the suffix when obvious from
the context.
PROOFS OF KNOWLEDGE. In a proof of knowledge for a relationship two
parties, Prover P and Verifier V, interact on a common input P also holds a
The goal of the protocol is to convince V
secret input such that
that P indeed knows such Ideally this proof should not reveal any information
about to the verifier, i.e. be zero-knowledge.
The protocol should thus satisfy certain constraints. In particular it must be
complete: if the Prover knows then the Verifier should accept. It should be
sound: for any (possibly dishonest) prover who does not know the verifier
should almost always reject. Finally it should be zero-knowledge: no (poly-time)
verifier (no matter what possibly dishonest strategy she follows during the proof)
can learn any information about
Many proofs of knowledge belong to a class of protocols called
These are 3-move protocols for a polynomial time relationship in
which the prover sends the first message the verifier answers with a random
challenge and the prover answers with a third message Then the verifier
applies a local decision test on to accept or not.
satisfy two special constraints:
Special soundness. A cheating prover can only answer one possible challenge
In other words we can compute the witness from two accepting conver-
sations of the form and
Special zero-knowledge. Given the statement and a challenge we can
produce (in polynomial time) an accepting conversation with the
same distribution of real accepting conversations, without knowing the wit-
ness Special zero-knowledge implies zero-knowledge with respect to the
honest verifier.
All the most important proofs of knowledge used in cryptographic applications
are (e.g. [36, 26]).
We will denote with the process of selecting the first message
according to the protocol Similarly we denote and
MAN-IN-THE-MIDDLE ATTACKS. Consider now an adversary that engages
with a verifier V in a proof of knowledge. At the same time acts as the verifier
in another proof with a prover P. Even if the protocol is a proof of knowledge
according to the definition in [6], it is still possible for to make the verifier
accept even without knowing the relevant secret information, by using P as an
oracle. Of course could always copy the messages from P to V, but it is not
hard to show (see for example [27]) that she can actually prove even a different
statement to V.
TEAM LinG
Multi-trapdoor Commitments 227

In a concurrent attack, the adversary is activating several sessions with
several provers, in any arbitrary interleaving. We call such an adversary a con-
current man-in-the-middle. We say that a proof of knowledge is concurrently
non-malleable if such an adversary fails to convince the verifier in a proof in
which he does not know the secret information. In other words a proof of knowl-
edge is concurrently non-malleable, if for any such adversary that makes the
verifier accept with non-negligible probability we can extract a witness.
Since we work in the common reference string model we define a proof sys-
tem as tuple (crsG,P,V), where crsG is a randomized algorithm that on input
the security parameter outputs the common reference string crs. In our def-
inition we limit the prover to be a probabilistic polynomial time machine, thus
technically our protocols are arguments and not proofs. But for the rest of the
paper we will refer to them as proofs.
If is a concurrent man-in-the-middle adversary, let be the probability
that the verifier V accepts. That is


where the statements are adaptively chosen by Also we denote
the view of at the end of the interaction with P and V
with
on common reference string crs.
Definition 2. We say that (crsG,P,V) is a concurrently non-malleable proof of
knowledge for a relationship if the following properties are satisfied:
Completeness. For all (for all we have that
Witness Extraction. There exist a probabilistic polynomial time knowledge
extractor KE, a function and a negligible function
such that for all probabilistic polynomial time concurrent man-in-the-middle
then KE, given rewind access to
adversary if computes
such that with probability at least
Zero-Knowledge. There exist a probabilistic polynomial time simulator
such that the two random variables



are indistinguishable.
Notice that in the definition of zero-knowledge the simulator does not have the
power to rewind the adversary. This will guarantee that the zero-knowledge
property will hold in a concurrent scenario. Notice also that the definition of
witness extraction assumes only left-concurrency (i.e. the adversary has access
to many provers but only to one verifier).

3 Multi-trapdoor Commitment Schemes
A trapdoor commitment scheme allows a sender to commit to a message with
information-theoretic privacy. I.e., given the transcript of the commitment phase
TEAM LinG
228 Rosario Gennaro

the receiver, even with infinite computing power, cannot guess the committed
message better than at random. On the other hand when it comes to opening
the message, the sender is only computationally bound to the committed mes-
sage. Indeed the scheme admits a trapdoor whose knowledge allows to open a
commitment in any possible way (we will refer to this also as equivocate the
commitment). This trapdoor should be hard to compute efficiently.
A multi-trapdoor commitment scheme consists of a family of trapdoor com-
mitments. Each scheme in the family is information-theoretically private. We
require the following properties from a multi-trapdoor commitment scheme:

1. The family admits a master trapdoor whose knowledge allows to open any
commitment in the family in any way it is desired.
2. Each commitment scheme in the family admits its own specific trapdoor,
which allows to equivocate that specific scheme.
3. For any commitment scheme in the family, it is infeasible to open it in
two different ways, unless the trapdoor is known. However we do allow the
adversary to equivocate on a few schemes in the family, by giving it access
to an oracle that opens a given committed value in any desired way. The
adversary must selects this schemes, before seeing the definition of the whole
family. It should remain infeasible for the adversary to equivocate any other
scheme in the family.

The main difference between our definition and the notion of SSTC [22,31]
is that SSTC allow the adversary to choose the schemes in which it wants to
equivocate even after seeing the definition of the family. Clearly SSTC are a
stronger requirement, which is probably why we are able to obtain more efficient
constructions.
We now give a formal definition. A (non-interactive) multi-trapdoor com-
mitment scheme consists of five algorithms: CKG, Sel, Tkg, Com, Open with the
following properties.
CKG is the master key generation algorithm, on input the security parameter
it outputs a pair PK, TK where PK is the master public key associated with the
family of commitment schemes, and TK is called the master trapdoor.
The algorithm Sel selects a commitment in the family. On input PK it outputs
a specific public key pk that identifies one of the schemes.
Tkg is the specific trapdoor generation algorithm. On input PK,TK,pk it
outputs the specific trapdoor information tk relative to pk.
Com is the commitment algorithm. On input PK,pk and a message M it
outputs C(M) = Com(PK, pk, M, R) where R are the coin tosses. To open a
commitment the sender reveals M, R and the receiver recomputes C.
Open is the algorithm that opens a commitment in any possible way given
the trapdoor information. It takes as input the keys PK,pk, a commitment C(M)
and a string T. If T = TK or T = tk
and its opening M, R, a message
then Open outputs such that
We require the following properties. Assume PK and all the pk™s are chosen
according to the distributions induced by CKG and Tkg.
TEAM LinG
Multi-trapdoor Commitments 229

Information Theoretic Security. For every message pair M, the distri-
butions C(M) and are statistically close.
Secure Binding. Consider the following game. The adversary selects
It is then given a public key PK for a multi-trapdoor
strings
commitment family, generated with the same distribution as the ones gen-
erated by CKG. Also, is given access to an oracle (for Equivocator),
which is queried on the following string C = Com(PK, pk, M, R), M, R, pk
and a message If for some and is a valid public key,
then answers with such that otherwise it
outputs nil. We say that wins if it outputs C, M, R, pk such that
and for
all We require that for all efficient algorithms the probability that
wins is negligible in the security parameter.
We can define a stronger version of the Secure Binding property by requiring
that the adversary receives the trapdoors matching the public keys
instead of access to the equivocator oracle In this case we say that the
4
multi-trapdoor commitment family is strong .

3.1 A Scheme Based on the Strong RSA Assumption
The starting point for the our construction of multi-trapdoor commitments based
on the Strong RSA Assumption, is a commitment scheme based on the (regular)
RSA Assumption, which has been widely used in the literature before (e.g. [14,
15]).
The master public key is a number N product of two large primes and
a random element of The master trapdoor is the factorization of N, i.e. the
integers The public key of a scheme in the family is an prime number
such that The specific trapdoor of the scheme with public
key is the of i.e. a value such that
To commit to the sender chooses and computes
To decommit the sender reveals and the previous equation is
verified by the receiver.
Proposition 1. Under the Strong RSA Assumption the scheme described above
is a multi-trapdoor commitment scheme.
Sketch of Proof: Each scheme in the family is unconditionally secret. Given a
value we note that for each value there exists a unique value
such that Indeed this value is the of Observe,
moreover that can be computed efficiently as thus knowledge of
allows to open a commitment (for which we know an opening) in any desired
way.
4
This was actually our original definition of multi-trapdoor commitments. Phil
MacKenzie suggested the possibility of using the weaker approach of giving access to
an equivocator oracle (as done in [31]) and we decided to modify our main definition
to the weaker one, since it suffices for our application. However the strong definition
may also have applications, so we decided to present it as well.
TEAM LinG
230 Rosario Gennaro

We now argue the Secure Binding property under the Strong RSA As-
sumption. Assume we are given a Strong RSA problem istance N, Let™s now
run the Secure Binding game. The adversary is going to select public keys
which in this case are primes, where
We set
and return N, as the public key of the multi-trapdoor commitment family. This
will easily allow us to simulate the oracle as we know the of i.e.
the trapdoors of the schemes identified by
Assume now that the adversary equivocates a commitment scheme in the
family identified by a prime The adversary returns a commitment A and
two distinct openings of it and Thus




Let Since and and the are all distinct primes we have
that We can find integers such that Now
we can compute (using Shamir™s GCD trick [37] and Eq.(1))




By taking on both sides we find that
Remark: The commitment scheme can be easily extended to any message do-
main by using a collision-resistant hash function H from to In
this case the commitment is computed as In our application we will use
a collision resistant function like SHA-1 that maps inputs to 160-bit integers and
then choose larger than

3.2 A Scheme Based on the SDH Assumption
Let G be a cyclic group of prime order generated by We assume that G
is a gap-DDH group, i.e. a group such that deciding Diffie-Hellman triplets is
easy. More formally we assume the existence of an efficient algorithm DDH-Test
which on input a triplet of elements in G outputs 1 if and only if,
We also assume that the Assumption 2 holds in G.
The master key generation algorithm selects a random which will be
the master trapdoor. The master public key will be the pair where
in G. Each commitment in the family will be identified by a specific public key
pk which is simply an element The specific trapdoor tk of this scheme is
the value in G, such that
To commit to a message with public key the sender chooses at
random and computes It then runs Pedersen™s commitment
[33] with bases i.e., it selects a random and computes
The commitment to is the value A.
To open a commitment the sender reveals and The receiver
accepts the opening if
TEAM LinG
231
Multi-trapdoor Commitments


Proposition 2. Under the SDH Assumption the scheme described above is a
multi-trapdoor commitment scheme.

Sketch of Proof: Each scheme in the family is easily seen to be unconditionally
secret. The proof of the Secure Binding property follows from the proof of
Lemma 1 in [9], where it is proven that the trapdoors can be considered
“weak signatures”. In other words the adversary can obtain several
for values chosen before seeing the public key and still will not be
able (under the to compute for a new
The proof is then completed if we can show that opening a commitment in
two different ways for a specific is equivalent to finding
Assume we can open a committment in two ways and
The DDH-Test tells us that
with and
thus or




By the same reasoning, if we know and we have an opening F, and we want
to open it as we need to set


4 The Protocol
In this section we describe our full solution for non-malleable proofs of knowledge
secure under concurrent composition using multi-trapdoor commitments.
INFORMAL DESCRIPTION. We start from a as described in Section
2. That is the prover P wants to prove to a verifier V that he knows a witness
for some statement The prover sends a first message The verifier challenges
the prover with a random value and the prover answers with his response
We modify this in the following way. We assume that the parties
share a common reference string that contains the master public key PK for a
multi-trapdoor commitment scheme. The common reference string also contains
a collision-resistant hash function H from the set of verification keys vk of the
one-time signature scheme, to the set of public keys pk in the multi-trapdoor
commitment scheme determined by the master public key PK.
The prover chooses a key pair (sk, vk) for a one-time strong signature scheme.
The prover computes pk= H(vk) and where is the first
message of the and is chosen at random (as prescribed by the
definition of Com). The prover sends vk, A to the verifier. The crucial trick is that
we use the verification key vk to determine the value pk used in the commitment
scheme.
The verifier sends the challenge The prover sends back as an opening
It also sends sig a signature over the
of A and the answer of the
whole transcript, computed using sk. The verifier checks that is a correct
opening of A, that sig is a valid signature over the transcript using vk and also
TEAM LinG
232 Rosario Gennaro




Fig. 1. A Concurrently Non-malleable Proof of Knowledge


that is an accepting conversation for the The protocol is
described in Figure 1.
Theorem 1. If multi-trapdoor commitments exist, if H is a collision-resistant
hash function, and if (SG,Sig,Ver) is a strong one-time signature scheme, then
CNM-POK is a concurrently non-malleable proof of knowledge (see Definition 2).

4.1 The Strong RSA Version
In this section we are going to add a few comments on the specific implementa-
tions of our protocol, when using the number-theoretic constructions described
in Sections 3.1 and 3.2. The main technical question is how to implement the
collision resistant hash function H which maps inputs to public keys for the
multi-trapdoor commitment scheme.
The SDH implementation is basically ready to use “as is”. Indeed the public
keys pk of the multi-trapdoor commitment scheme are simply elements of
thus all is needed is a collision-resistant hash function with output in
On the other hand, for the Strong RSA based multi-trapdoor commitment,
the public keys are prime numbers of the appropriate length. A prime-outputting
TEAM LinG
233
Multi-trapdoor Commitments


collision-resistant hash function is described in [23]. However we can do better
than that, by modifying slightly the whole protocol. We describe the modifica-
tions (inspired by [32, 15]) in this section.
MODIFYING THE ONE-TIME SIGNATURES. First of all, we require the one-time
signature scheme (SG,Sig,Ver) to have an extra property: i.e. that the distribution
induced by SG over the verification keys vk is the uniform one5. Virtually all the
known efficient one-time signature schemes have this property.
Then we assume that the collision resistant hash function used in the pro-
tocol is drawn from a family which is both a collision-resistant collection and a
collection of families of universal hash functions6.
Assume that we have a randomly chosen hash function H from such a collec-
tion mapping strings (the verification keys) into strings and a prime

We modify the key generation of our signature scheme as follows. We run
SG repeatedly until we get a verification key vk such that
is a prime. Notice that Let us denote with this modified key
generation algorithm.
We note the following facts:
H(vk) follows a distribution over strings which is statistically close to
uniform; thus using results on the density of primes in arithmetic progres-
sions (see [1], the results hold under the Generalized Riemann Hypothesis)
we know that this process will stop in polynomial time, i.e. after an expected
iterations.
Since is of the form 2PR + 1, and primality testing of all the
candidates can be done deterministically and very efficiently (see Lemma 2
in [32]).
Thus this is quite an efficient way to associate primes to the verification keys.
Notice that we are not compromising the security of the modified signature
scheme. Indeed the keys of the modified scheme are a polynomially large fraction
of the original universe of keys. Thus if a forger could forge signature on this
modified scheme, then the original scheme is not secure as well.
ON THE LENGTH OF THE PRIMES. In our application we need the prime to
be relatively prime to where N is the RSA modulus used in the protocol.
This can be achieved by setting (i.e. In typical applications
(i.e. this is about 512 bits (we can obtain this by setting
and the length of the hash function output, to 160). Since the number of
iterations to choose vk depends on the length of it would be nice to find a way
to shorten it.
5
This requirement can be relaxed to asking that the distribution has enough min-
entropy.
6
This is a reasonable assumption that can be made on families built out of a collision-
resistant hash function (such as SHA-1). See also [18] for analysis of this type of
function families.

TEAM LinG
Rosario Gennaro
234

If we use safe RSA moduli, then we can enforce that by
choosing small enough (for 1024-bit safe moduli we need them to be smaller
than 500 bits). In this case the collision-resistant property will become the limit-
ing factor in choosing the length. By today™s standards we need to be at least
160. So the resulting primes will be bits long.

4.2 Identification Protocols
The main application of our result is the construction of concurrently secure
identification protocols. In an identification protocol, a prover, associated with
a public key pk, communicates with a verifier and tries to convince her to be
the legitimate prover (i.e. the person knowing the matching secret key sk.) An
adversary tries to mount an impersonation attack, i.e. tries to make the verifier
accept without knowing the secret key sk.
The adversary could be limited to interact with the real prover only before
mounting the actual impersonation attack [21]. On the other hand a more re-
alistic approach is to consider the adversary a “man-in-the-middle” possibly in
a concurrent fashion [5]. Clearly such an attacker can always relays messages
unchanged between the prover and the verifier. In order to make a security def-
inition meaningful, one defines a successful impersonation attack as one with a
transcript different from the ones between the attacker and the real prover7.
It is not hard to see that CNM-POK is indeed a concurrently secure identifi-
cation protocol. It is important to notice that we achieve full concurrency here,
indeed the extraction procedure in the proof of Theorem 1 does not “care” if
there are many other executions in which the adversary is acting as a prover.
Indeed we do not need to rewind all executions, but only one in order to extract
the one witness we need. Thus if there are other such executions “nested” inside
the one we are rewinding, we just run them as the honest verifier.

Acknowledgments
I would like to thank Hugo Krawczyk for conversations that started the research
on this paper. Thanks also to Dario Catalano, Shai Halevi, Jonathan Katz, Dah-
Yoh Lim, Yehuda Lindell and especially Phil MacKenzie for helpful conversations
and advice.

References
1. E. Bach and J. Shallit. Algorithmic Number Theory - Volume 1. MIT Press, 1996.
2. B. Barak. How to go beyond the black-box simulation barrier. Proc. of IEEE
Symp. on Foundations of Computer Science (FOCS™01), pp.106“115, 2001.
7
In [5] an even more powerful adversary is considered, one that can even reset the
internal state of the prover. The resulting notion of security implies security in the
concurrent model. We do not consider the resettable scenario, but our protocols are
more efficient than the ones proposed in [5].

TEAM LinG
Multi-trapdoor Commitments 235

3. B. Barak. Constant-round Coin Tossing with a Man in the Middle or Realizing
the Shared Random String Model. Proc. of IEEE Symp. on Foundations of
Computer Science (FOCS™02), pp.345“355, 2001.
and B. Pfitzmann. Collision-free accumulators and Fail-stop signa-
4.
ture schemes without trees. Proc. of EUROCRYPT™97 (LNCS 1233), pp.480“494,
Springer 1997.
5. M. Bellare, M. Fischlin, S. Goldwasser and S. Micali. Identification Protocols Se-
cure against Reset Attacks. Proc. of EUROCRYPT™01 (LNCS 2045), pp.495“511,
Springer 2001.
6. M. Bellare and O. Goldreich. On defining proofs of knowledge. Proc. of CRYPTO™92
(LNCS 740), Springer 1993.
7. D. Bleichenbacher and U. Maurer. Optimal Tree-Based One-time Digital Signature
Schemes. STACS™96, LNCS, Vol. 1046, pp.363“374, Springer-Verlag.
8. D. Bleichenbacher and U. Maurer. On the efficiency of one-time digital signatures.
Proc. of ASIACRYPT™96 (LNCS 1163), pp.145“158, Springer 1996.
9. D. Boneh and X. Boyen. Short Signatures without Random Oracles. Proc. of EU-
ROCRYPT™04 (LNCS 3027), pp.382“400, Springer 2004.
10. D. Boneh and M. Franklin. Identity-Based Encryption from the Weill Pairing.
SIAM J. Comp. 32(3):586“615, 2003.
11. R. Canetti. Universally Composable Security: A new paradigm for cryptographic
protocols. Proc. of IEEE Symp. on Foundations of Computer Science
(FOCS™01), pp.136“145, 2001.
12. R. Canetti and M. Fischlin. Universally Composable Commitments. Proc. of
CRYPTO™01 (LNCS 2139), pp.19“40, Springer 2001.
13. R. Canetti, J. Kilian, E. Petrank and A. Rosen. Concurrent Zero-Knowledge
requires rounds. Proc. of ACM Symp. on Theory of Computing
(STOC™01), pp.570“579, 2001.
14. R. Cramer and I. Damgård. New Generation of Secure and Practical RSA-based
signatures. Proc. of Crypto ™96 LNCS no. 1109, pages 173-185.
15. R. Cramer and V. Shoup. Signature schemes based on the Strong RSA assumption.
Proc. of ACM Conference on Computer and Communication Security 1999.
16. I. Damgård. Efficient Concurrent Zero-Knowledge in the Auxiliary String Model.
Proc. of EUROCYPT™00 (LNCS 1807), pp.174“187, Springer 2000.
17. A. De Santis, G. Di Crescenzo, R. Ostrovsky, G. Persiano and A. Sahai. Robust
Non-Interactive Zero Knowledge. Proc. of CRYPTO™01, (LNCS 2139), pp.566-598,
Springer 2001.
18. Y. Dodis, R. Gennaro, J. Håstad, H. krawczyk and T. Rabin. Randomness Ex-
traction and Key Derivation using the CBC, Cascade and HMAC Modes. This
proceedings.
19. D. Dolev, C. Dwork and M. Naor. Non-malleable Cryptography. SIAM J. Comp.
30(2):391“437, 2000.
20. C. Dwork, M. Naor and A. Sahai. Concurrent Zero-Knowledge. Proc. of ACM
Symp. on Theory of Computing (STOC™98), pp.409“418, 1998.
21. U. Feige, A. Fiat and A. Shamir. Zero-Knowledge Proofs of Identity. J. of Crypt.
1(2):77“94, Springer 1988.
22. J. Garay, P. MacKenzie and K. Yang. Strengthening Zero-Knowledge Protocols
Using Signatures. Proc. of EUROCRYPT™03 (LNCS 2656), pp.177“194, Springer
2003. Final version at eprint.iacr.org
23. R. Gennaro, S. Halevi and T. Rabin. Secure Hash-and-Sign Signatures Without
the Random Oracle. Proc. of Eurocrypt ™99 LNCS no. 1592, pages 123-139.

TEAM LinG
Rosario Gennaro
236

24. S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive
proof-systems. SIAM. J. Computing, 18(1):186“208, February 1989.
25. S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against
adaptive chosen-message attacks. SIAM J. Computing, 17(2):281“308, April 1988.
26. L.C. Guillou and J.J. Quisquater. A Practical Zero-Knowledge Protocol Fitted to
Security Microprocessors Minimizing both Transmission and Memory. Proc. of EU-
ROCRYPT™88 (LNCS 330), pp.123“128, Springer 1989.
27. J. Katz. Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applica-
tions. Proc. of EUROCRYPT™03 (LNCS 2656), pp.211-228, Springer 2003.
28. L. Lamport. Constructing Digital Signatures from a One-Way Function. Technical
Report SRI Intl. CSL 98, 1979.
29. Y. Lindell. Composition of Secure Multi-Party Protocols. Lecture Notes in Com-
puter Science vol.2815, Springer 2003.
30. Y. Lindell. Lower Bounds for Concurrent Self Composition. Proc of the 1st Theory
of Cryptography Conference (TCC™04), LNCS 2951, pp.203“222, Springer 2004.
31. P. MacKenzie and K. Yang. On Simulation-Sound Trapdoor Commitments. Proc.
of EUROCRYPT™04 (LNCS 3027), pp.382“400, Springer 2004.
32. U. Maurer. Fast Generation of Prime Numbers and Secure Public-Key Crypto-
graphic Parameters. J. of Crypt. 8(3):123“156, Springer 1995.
33. T. Pedersen. Non-interactive and information-theoretic secure verifiable secret
sharing. In Crypto ™91, pages 129“140, 1991. LNCS No. 576.
34. M. Prabhakaran, A. Rosen and A. Sahai. Concurrent Zero-Knowledge with loga-
rithmic round complexity. Proc. of IEEE Symp. on Foundations of Computer
Science (FOGS™02), pp.366“375, 2002.
35. R. Rivest, A. Shamir and L. Adelman. A Method for Obtaining Digital Signature
and Public Key Cryptosystems. Comm. of ACM, 21 (1978), pp. 120“126
36. C. P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology,
4:161“174, 1991.
37. A. Shamir. On the generation of cryptographically strong pseudorandom sequences.
ACM Trans. on Computer Systems, 1(1), 1983, pages 38-44.




TEAM LinG
Constant-Round Resettable Zero Knowledge
with Concurrent Soundness
in the Bare Public-Key Model

Giovanni Di Crescenzo1, Giuseppe Persiano2, and Ivan Visconti3
1
Telcordia Technologies, Piscataway, NJ, USA
giovanni@research.telcordia.com
2
Dip. di Informatica ed Appl., Univ. di Salerno, Baronissi, Italy
giuper@dia.unisa.it
3
D©partement d™Informatique, École Normale Sup©rieure, Paris, France
ivan.visconti@ens.fr




Abstract. In the bare public-key model (BPK in short), each verifier
is assumed to have deposited a public key in a file that is accessible by
all users at all times. In this model, introduced by Canetti et al. [STOC
2000], constant-round black-box concurrent and resettable zero knowl-
edge is possible as opposed to the standard model for zero knowledge. As
pointed out by Micali and Reyzin [Crypto 2001], the notion of soundness
in this model is more subtle and complex than in the classical model
and indeed four distinct notions have been introduced (from weakest to
strongest): one-time, sequential, concurrent and resettable soundness.
In this paper we present the first constant-round concurrently sound re-
settable zero-knowledge argument system in the bare public-key model
for More specifically, we present a 4-round protocol, which is opti-
mal as far as the number of rounds is concerned. Our result solves the
main open problem on resettable zero knowledge in the BPK model and
improves the previous works of Micali and Reyzin [EuroCrypt 2001] and
Zhao et al. [EuroCrypt 2003] since they achieved concurrent soundness
in stronger models.


1 Introduction

The classical notion of a zero-knowledge proof has been introduced in [1]. Roughly
speaking, in a zero-knowledge proof a prover can prove to a verifier the validity of
a statement without releasing any additional information. In order to prove that
a zero-knowledge protocol does not leak information it is required to show the
existence of a probabilistic polynomial-time algorithm, referred to as Simulator,
whose output is indistinguishable from the output of the interaction between the
prover and the verifier. Since its introduction, the concept of a zero-knowledge
proof and the simulation paradigm have been widely used to prove the security
of many protocols. More recently, it has been recognized that in several practical
settings the original notion of zero knowledge (which in its original formulation

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 237“253, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
238 Giovanni Di Crescenzo, Giuseppe Persiano, and Ivan Visconti

only considered one prover and one verifier that carried out the proof proce-
dure in isolation) was insufficient. For example, the notion of concurrent zero
knowledge [2] formalizes security in a scenario in which several verifiers access
concurrently the same prover and maliciously coordinate their actions so to ex-
tract information from the prover. Motivated by considerations regarding smart
cards, the notion of resettable zero knowledge (rZK, in short) was introduced
in [3]. An rZK proof remains “secure” even if the verifier is allowed to tamper
with the prover and to reset the prover in the middle of a proof to any previous
state and then asks different questions. It is easy to see that concurrent zero
knowledge is a special case of resettable zero knowledge and, currently, rZK is
the strongest notion of zero knowledge that has been studied. Unfortunately,
if we only consider black-box zero knowledge, constant-round concurrent zero
knowledge is only possible for trivial languages (see [4]). Moreover, the existence
of a constant-round concurrent zero-knowledge argument in the non-black-box
model (see [5] for the main results in the non-black-box model) is currently an
open question. Such negative results have motivated the introduction of the bare
public-key model [3] (BPK, in short). Here each possible verifier deposits a public
key pk in a public file and keeps private the associated secret information sk.
From then on, all provers interacting with such a verifier will use pk and the
verifier cannot change pk from proof to proof. Canetti et al. [3] showed that
constant-round rZK is possible in the BPK model. However, the fact that the
verifier has a public key means that it is vulnerable to an attack by a mali-
cious prover that opens several sessions with the same verifier in order to violate
the soundness condition. This is to be contrasted with the standard models for
interactive zero knowledge [1] or non-interactive zero knowledge [6] where, as
far as soundness is concerned, it does not matter whether a malicious prover is
interacting once or multiple times with the same verifier.
Indeed, in [7], Micali and Reyzin pointed out, among other contributions,
that the known constant-round rZK arguments in the BPK model did not seem
to be sound if a prover was allowed to concurrently interact with several instances
of the same verifier. In other words, the known rZK arguments in the BPK were
not concurrently sound.
Micali and Reyzin gave in [7] a 4-round argument system which is sequentially
sound (i.e., the soundness holds if a prover can play only sequential sessions)
and probably is not concurrently sound, and they also showed that the same
holds for the five-round protocol of Canetti et al. [3]. Moreover they proved that
resettable soundness cannot be achieved in the black-box model. In [8], Barak
et al. used non-black-box techniques in order to obtain a constant-round rZK
argument of knowledge but their protocol enjoys only sequential soundness.
In order to design a concurrently sound resettable zero-knowledge argument
system, Micali and Reyzin proposed (see [9]) the upper bounded public-key
(UPK, in short) model in which a honest verifier possesses a counter and uses
the same private key no more than a fixed polynomial number of times. A weaker
model than the UPK model but still stronger than the BPK model is the weak
public-key (WPK, in short) model introduced in [10]. In this model an honest

TEAM LinG
Constant-Round Resettable Zero Knowledge with Concurrent Soundness 239

verifier can use the same key no more than a fixed polynomial number of times
for each statement to be proved.
Other models were proposed in order to achieve constant-round concur-
rent zero knowledge. In particular, in [2, 11] a constant-round concurrent zero-
knowledge proof system is presented by relaxing the asynchrony of the model or
the zero-knowledge property. In [12] a constant-round concurrent zero-knowledge
proof system is presented by requiring a pre-processing stage in which both the
provers and the verifiers are involved. In [13] a constant-round concurrent zero-
knowledge proof is presented assuming the existence of a trusted auxiliary string.
All these models are considered stronger than the BPK model.
Our results. In this paper we present the first constant-round concurrently sound
resettable zero-knowledge argument system in the BPK model for In par-
ticular we show a 4-round argument that is optimal in light of a lower bound for
concurrent soundness proved in [7]. We stress that our result is the best one can
hope for in terms of combined security against malicious provers and verifiers if
we restrict ourselves to black-box zero knowledge, since in this setting simulta-
neously achieving resettable soundness and zero knowledge has been shown to
be possible only for languages in BPP by [7]. Our construction employs the tech-
nique of complexity leveraging used in the previous results [3,7, 10] in order to
prove the soundness of their protocols and is based on the existence of a verifiably
binding cryptosystem semantically secure against subexponential adversaries.
The existence of cryptographic primitives secure against subexponential adver-
saries is used also in [3,7, 10] and the existence of a constant-round black-box
rZK argument system in the BPK model assuming only cryptographic primitives
secure against polynomial-time adversaries is an interesting open question.
Finally, we describe a simple 3-round sequentially sound and sequential zero-
knowledge argument system in the BPK model for all

2 Definitions
The BPK model. The Bare Public-Key (BPK, in short) model assumes that:
1. there exists a public file F that is a collection of records, each containing a
public key;
2. an (honest) prover is an interactive deterministic polynomial-time algorithm
that takes as input a security parameter F, an string such that
and L is an NP-language, an auxiliary input a reference to an entry
of F and a random tape;
3. an (honest) verifier V is an interactive deterministic polynomial-time algo-
rithm that works in the following two stages: 1) in a first stage on input a
security parameter and a random tape, V generates a key pair (pk, sk)
and stores pk in one entry of the file F; 2) in the second stage, V takes as
input sk, a statement and a random string, V performs an interactive
protocol with a prover, and outputs “accept” or “reject”;
4. the first interaction of each prover starts after that all verifiers have com-
pleted their first stage.
TEAM LinG
240 Giovanni Di Crescenzo, Giuseppe Persiano, and Ivan Visconti

Definition 1. Given an NP-language L and its corresponding relation we
say that a pair is complete for L, if for all strings and any
witness such that the probability that V interacting with P on
input outputs “reject”is negligible in

Malicious provers in the BPK model. Let be a positive polynomial and P* be
a probabilistic polynomial-time algorithm that takes as first input
P* is an malicious prover if it runs in at most stages in the
following way: in stage 1, P* receives a public key pk and outputs an string
In every even stage, P* starts from the final configuration of the previous
stage, sends and receives messages of a single interactive protocol on input pk
and can decide to abort the stage in any moment and to start the next one.
In every odd stage P* starts from the final configuration of the previous
stage and outputs an string
P* is an malicious prover if on input a public key pk of V,
can perform the following interactive protocols with V: 1) if P* is already
running protocols he can start a new protocol with V choosing
the new statement to be proved; 2) he can output a message for any running
protocol, receive immediately the response from V and continue.

Attacks in the BPK model. In [7] the following attacks have been defined.
Given an malicious prover P* and an honest verifier V, a se-
quential attack is performed in the following way: 1) the first stage of V is run
on input and a random string so that a pair (pk, sk) is obtained; 2) the first
stage of P* is run on input and pk and is obtained; 3) for
the stage of P* is run letting it interact with V that receives as input sk,
and a random string while the stage of P* is run to obtain
Given an malicious prover P* and an honest verifier V, a con-
current attack is performed in the following way: 1) the first stage of V is run on
input and a random string so that a pair (pk, sk) is obtained; 2) P* is run on
input and pk; 3) whenever P* starts a new protocol choosing a statement, V
is run on inputs the new statement, a new random string and sk.

Definition 2. Given a complete pair for an NP-language L in the BPK
model, then is a concurrently (resp. sequentially) sound interactive ar-
gument system for L if for all positive polynomial for all (resp
malicious prover P*, for any false statement the proba-
bility that in an execution of a concurrent (resp. sequential) attack V outputs
“accept” for such a statement is negligible in

The strongest notion of zero knowledge, referred to as resettable zero knowledge,
gives to a verifier the ability to rewind the prover to a previous state. This is
significantly different from a scenario of multiple interactions between prover
and verifier since after a rewinding the prover uses the same random bits.
We now give the formal definition of a black-box resettable zero-knowledge
argument system for in the bare public-key model.
TEAM LinG
Constant-Round Resettable Zero Knowledge with Concurrent Soundness 241

Definition 3. An interactive argument system in the BPK model is
black-box resettable zero-knowledge if there exists a probabilistic polynomial-time
algorithm S such that for any probabilistic polynomial time V*, for any polyno-
mials for any V* runs in at most steps
and the following two distributions are indistinguishable:
1. the output of V* that generates F with entries and interacts (even
concurrently) a polynomial number of times with each where
is a witness for and is a random tape for

2. the output of S interacting with V* on input
Moreover we define such an adversarial verifier V* as an mali-
cious verifier.
An important tool used this paper is that of a non-interactive zero-knowledge
argument system.
Definition 4. A pair of probabilistic polynomial-time algorithms (NIPK,NIVK)
is a non-interactive zero-knowledge argument system for an language L if
there exists a polynomial
1. (Completeness) for all with and NP-witness for



2. (Soundness) for all



is negligible.
3. (Simulatability) there exists a probabilistic polynomial-time algorithm S such
that the family of distributions


are computationally indistinguishable.
We assume, without loss of generality, that a random reference string of length
is sufficient for proving theorems of length (that is, we assume

3 Concurrently Sound rZK Argument System for
in the BPK Model
In this section we present a constant-round concurrently sound resettable zero-
knowledge argument in the BPK model for all languages.
In our construction we assume the existence of an encryption scheme that is
secure with respect to sub-exponential adversaries and that is verifiably binding.
We next review the notion of semantic security adapted for sub-exponential
adversaries and present the notion of a verifiably binding cryptosystem.
TEAM LinG
242 Giovanni Di Crescenzo, Giuseppe Persiano, and Ivan Visconti

An encryption scheme is a triple of efficient algorithms PK = (G,E,D). The key
generator algorithm G on input a random string (the security parameter)
outputs a pair (pk,sk) of public and private key. The public key pk is used to
encrypt a string by computing where is a random string of length

Semantic security [14] is defined by considering the following experiment for
encryption scheme PK = (G,E,D) involving a two-part adversary
The key generator G is run on a random string and keys (pk,sk) are given
in output. Two strings and are returned by on input pk.
Then is taken at random from {0,1} and an encryption of is computed. We
say that adversary is successful for PK if the probability that outputs on
input pk, and is non-negligibly (in greater than 1/2. We say that PK is
if no adversary running in time is successful. The classical notion
of semantic security is instead obtained by requiring that no polynomial-time
adversary is successful.
Roughly speaking, a verifiably binding cryptosystem PK is a cryptosystem for
which 1) given a string pk and an integer it is easy to verify that pk is a legal
public key with security parameter and 2) to each ciphertext corresponds at
most one plaintext.
More formally,

Definition 5. An encryption scheme PK = (G,E,D) is verifiably bind-
ing iff:
1. (binding): for any probabilistic polynomial-time algorithm it holds that



is negligible in
2. (verifiability): there exists a probabilistic polynomial-time algorithm VER
such that if pk belongs to the output space of G on input a string then
otherwise.

Assumptions. To prove the properties of our protocol we make the following
complexity theoretic assumptions:

1. The existence of an verifiably binding encryption scheme PK =
(G,E,D) for some
We briefly note that the El Gamal encryption scheme [15] is verifiably bind-
ing since an exponentiation in is one to one and it can be easily verified
that a positive integer is a prime.
2. The existence of a one-to-one length-preserving one-way function
which, in turn, implies the existence of a pseudo-random family of
functions
3. The existence of a non-interactive zero-knowledge proof system (NIZK, in
short) (NIPM, NIVM) for an language.
TEAM LinG
Constant-Round Resettable Zero Knowledge with Concurrent Soundness 243

4. The existence of a 3-round witness indistinguishable argument of knowledge
for a specific polynomial-time relation that we define
in the following way. Let be a one-to-one length-preserving one-way func-
tion and let PK be an verifiably binding encryption scheme. Then
define the polynomial-time relation as consisting of all pairs
where pk is a public key of the output space of G and is a
string and either wit = sk and (pk,sk) is in the output space of G or
and
Before describing our protocol formally, let us try to convey the main idea
behind it. Fix an language L and let be the input statement. The prover
generates a puzzle (in our construction, the puzzle consists of a string and
solving the puzzle consists in finding the inverse of the one-to-one length-
preserving one-way function and sends it to the verifier. The verifier uses WI
to prove knowledge of the private key associated to her public key or
knowledge of the solution of the puzzle given to her by the prover. Moreover,
the prover and the verifier play a coin tossing protocol, based on the encryption
scheme PK to generate a reference string for the NIZK proof that
In our implementation of the FLS-paradigm [16], in the interaction between
the prover and the verifier, the verifier will use his knowledge of the private key
to run WI. In order to prove concurrent soundness, we show an algorithm that
interacts with a (possibly) cheating prover P* and breaks an encryption
scheme in time The puzzle helps algorithm in simulating the verifier
with respect to a challenge public key pk for which it does not have access to the
private key. Indeed, instead of proving knowledge of the private key associated
to pk proves knowledge of the solution of the puzzle by performing exhaustive
search. By carefully picking the size of the puzzle (and thus the time required
to solve it) we can make sure runs in time
Note that when inverts the one-to-one length-preserving one-way function
and computes the witness-indistinguishable argument of knowledge, it runs in
subexponential time in order to simulate the verifier without performing rewinds.
Straight-line quasi-polynomial time simulatable argument systems were studied
in detail in [17], where this relaxed simulation notion is used to decrease the
round complexity of argument systems. We use a similar technique but for sub-
exponential time simulation of arguments of knowledge.
If the steps described above were executed sequentially, we would have an
8-round protocol (one round for the prover to send the puzzle, three rounds
for the coin tossing, three rounds for the witness-indistinguishable argument of
knowledge, and one round for the NIZK). However, observe that the coin-tossing
protocol and the 3-round witness-indistinguishable argument of knowledge can
be performed in parallel thus reducing the the round complexity to 5 rounds.
Moreover, we can save one more round, by letting the prover send the puzzle
in parallel with the second round of the witness indistinguishable argument of
knowledge. To do so, we need a special implementation of this primitive since,
when the protocol starts, only the size of the statement is known and the state-
ment itself is part of the second round. Let us now give the details of our con-
struction.
TEAM LinG
244 Giovanni Di Crescenzo, Giuseppe Persiano, and Ivan Visconti

The public file. The public file F contains entries consisting in public keys with
security parameter for the public-key cryptosystem PK.

Private inputs. The private input of the prover consists of a witness for
The private input of the verifier consists of the secret key corresponding to
the public key

The protocol. Suppose that the prover wants to prove that and denote
by the length of We denote by the index of the verifier in the
public file so that the verifier knows the private key associated with the
public key of the public file F.
In the first round V randomly picks an string that will be used as
V™s contribution to the reference string for the non-interactive zero-knowledge
protocol. V compute the encryption of using an string as random-
ness and by using public key Moreover, V runs in order to compute the
first message of the witness-indistinguishable argument of knowledge. Then
V sends to P. In the second round P verifies that is a legal public key
for PK with as security parameter and then computes its contribution to the
random string to be used for the non-interactive argument by picking a random
seed and computing denotes concate-
nation) where is a family of pseudorandom functions. The string has
length (to be determined later) whereas has length and is P™s con-
tribution for the reference string. P runs to compute the second message
of the witness-indistinguishable argument of knowledge. Moreover P computes
where is a one-to-one length-preserving one-way function and sends
to the verifier. In the third round of the protocol V uses his knowledge
of the private key to run obtaining so that she proves that she knows ei-
ther the private key associated with or V then sends and to
P. In the last round of the protocol P verifies that the witness-indistinguishable
argument of knowledge is correct and that is an encryption of Then P runs
algorithm NIPM on input and using as reference string obtaining
a proof that is sent to V. A more formal description of the protocols is found
in Figure 1.

Theorem 1. If there exists an verifiably binding encryption scheme,
a one-to-one length-preserving one-way function then there exists a constant-
round concurrently sound resettable zero-knowledge argument for all languages
in in the BPK model.

Proof. Consider the protocol found in Figure 1.

Completeness. If then P can always compute the proof and V accepts
it.

Concurrent soundness. Assume by contradiction that the protocol is not con-
currently sound. Thus there exists an malicious prover P* that by,
TEAM LinG
Constant-Round Resettable Zero Knowledge with Concurrent Soundness 245




Fig. 1. The 4-round concurrently sound rZK argument system for in the BPK
model. The values and are determined as functions of in the proof of concurrent
soundness.


concurrently interacting with V, has non-negligible probability of making
the verifier accept some of length We assume we know the index of
the session in which the prover will succeed in cheating (this assumption will
be later removed) and exhibit an algorithm that has black-box access to P*
(i.e., simulates the work of a verifier V) and breaks the encryption scheme PK
in steps, thus reaching a contradiction.
We now describe algorithm runs in two stages. First, on input the
challenge public key pk, randomly picks two strings and of the same
TEAM LinG
246 Giovanni Di Crescenzo, Giuseppe Persiano, and Ivan Visconti

length as the length of the reference string used by (NIPM,NIVM) for inputs of
length Then receives as a challenge an encryption of computed using
public key pk and task is to guess with a non-negligible
advantage over 1/2 (we assume that is randomly chosen).
For all the sessions, interacts with the an prover P* mounting
a concurrent attack, and simulates the verifier by computing the two messages
as explained below. When reaches session outputs her guess for bit

1. Session
At V-round-1, sends an encryption of a randomly chosen string
computed with as randomness and sends the first round of the witness-
indistinguishable argument of knowledge Upon receiving message
from P*, inverts the one-to-one length-preserving one-way function
on obtaining by performing exhaustive search in
then computes by running on input instance and witness
and sends to P* the triple
Note that plays round V-round-1 identically to the honest verifier while
plays round V-round-3 by using a different witness w.r.t. V for the non-
interactive zero-knowledge argument of knowledge that however is concur-
rent witness indistinguishable.
2. Session
At V-round-1, computes the first message of the witness-indistinguishable
argument of knowledge and sets equal to the challenge encryption
Then sends to V.
At V-round-3, cannot continue with this session since she does not know
the decryption of (remember that and thus can not play the third
round. However, by assumption P* can produce with non-negligible prob-
ability a string that is accepted by NIVM on input and reference
string Let be an upper bound on the length of such a
non-interactive zero-knowledge argument. checks, by exhaustive search, if
there exists such that NIVM accepts on input and as
reference string. Then searches for a string by considering
as reference string. If a proof is found and no proof is found then
outputs 0; in the opposite case outputs 1; otherwise (that is, if both or
neither proof exists) randomly guesses the bit
We note that the distribution of the first message of session is still identical
to the distribution of the honest verifier™s message.

Let us now show that the probability that correctly guesses is non-
negligibly larger that 1/2. We have that




TEAM LinG
Constant-Round Resettable Zero Knowledge with Concurrent Soundness 247

The last equality follows from the observation that, by the completeness of the
NIZK, the events and can happen only if Now, we have




Now, since the string is picked at random and P* has no information
about it, the string is random and thus, by the soundness of (NIPM,NIVM),
is negligible. Therefore, the probability that correctly
guesses is non-negligibly larger than 1/2.
We note that algorithm takes time Writing as
for some constant we pick and so that and We thus
have that breaks an verifiably binding cryptosystem in time bounded
by
Therefore the existence of contradicts the of the cryptosystem.
In our proof we assumed that knows the value If this is not the case that
can simply guess the values and the same analysis applies and the probability
that correctly guesses decreases by a polynomial factor.

Resettable Zero Knowledge. Let V* be an verifier. We now present
a probabilistic polynomial-time algorithm that has black-box access to
V* and whose output is computationally indistinguishable from the view of the
interactions between P and V*.
We start with an informal discussion. The construction of S is very similar
to the construction of the simulator for the constant-round (sequentially sound)
resettable zero-knowledge argument for any NP language and in the BPK model,
given in [3] (protocol 6.2). In particular, note that both the protocol of Figure 1
and protocol 6.2 in [3] can be abstractly described as follows. The prover and
the verifier run a 3-round argument of knowledge, where the verifier, acting as
a prover, proves knowledge to the prover, acting as verifier, of some trapdoor
information. Knowledge of the trapdoor information allows for efficient simula-
tion of the interaction between the prover and the verifier. In [3], the trapdoor
information is the private key associated with the verifier™s public key. In our
protocol, the trapdoor information is either the private key associated with the
verifier™s public key (for the real verifier) or the inverse of an output of a one-to-
one length-preserving one-way function sent from the prover to the verifier. Note
that just to obtain round optimality we use a special witness-indistinguishable
argument of knowledge where the statement is known only after that the second
round is played while its size is known from the beginning. Due to this difference,
our simulator only differs from the one of [3] in the fact that we need to prove
that when the simulator runs the extractor of the argument of knowledge, with
high probability it extracts the verifier™s private key (rather than The
rest of the construction of our simulator is conceptually identical to that of [3],
but we still review a more precise description here for completeness.
TEAM LinG
248 Giovanni Di Crescenzo, Giuseppe Persiano, and Ivan Visconti

First of all, without loss of generality, we make the following two simplifying
assumptions. Recall that, since our protocol is a resettable zero-knowledge ar-
gument system, V* is allowed to reset the prover. However, in [3] Canetti et al.
proved that in such a setting a verifier that concurrently interacts with many in-
carnations of the prover does not get any advantage with respect to a sequential
(resetting) verifier (that is, a verifier that runs a new session only after having
terminated the previous one). Thus in this proof we will consider V* as a se-
quential (resetting) verifier. A second assumption is that we can define S for a
modification of our protocol in which the prover uses a truly random function
rather than a pseudo-random one to compute her random bits. Proving that the
two views are computationally indistinguishable is rather standard.
S runs the first stage of V* so that the public file composed by entries
is obtained. In the second stage, the aim of the simulator is to obtain the private
keys corresponding to the public keys of the public file. Let V*(F) be the state
of V* at the end of the first stage.
In the following, we say that a session is solved by S if S has the private key
corresponding to the public key used by V* in this session. The work of S in the
second stage of the simulation is composed by at most sequential phases.
In each phase, either S has a chance of terminating the simulation or S learns
one more private key. At the end of each phase 5 rewinds V* to state V*(F).
The simulation ends as soon as S manages to solve all sessions of a phase.
We describe now the work of S during a phase. Once a session is started,
S receives the first message from V*. Then there are two cases. If the session
is solved by S then S can simulate the prover; otherwise, S tries to obtain the
private key used in this session so that all future sessions involving this verifier
will be solved by 5.
Specifically, first consider the simpler case of a solved session. We distinguish
two sub-cases. First, we consider the sub-case where the first message in the
session has not appeared before for the same incarnation of the prover,
i.e., has not appeared before for the same prover oracle accessed by V*
with the same random tape, same witness and same theorem. Then S runs the
simulator for (NIPM,NIVM) on input and obtains a pair and then
forces equal to in the following way. Since S knows the verifier™s secret-key
(we are assuming in this sub-case that the session is solved), S can decrypt
and thus obtain the string computed by the verifier at the first round. Thus
S sets Consequently, in round P-round-4, S will send “proof”
(that is computationally indistinguishable from the proof computed by the
real prover). We use here the binding property of the encryption scheme since
S must decrypt obtaining the same value that will be sent by V* in round
V-round-3.
Now we consider the sub-case where the first message in the session
has already appeared in such a phase for the same incarnation of the prover. Here
S sends the same strings and the same string that was sent in the
previous session containing as first message for the same incarnation of
the prover. Even for the case of the third message of a session that has already

TEAM LinG
Constant-Round Resettable Zero Knowledge with Concurrent Soundness 249

appeared for the same incarnation of the prover, S replies with the same round
P-round-4 played before.
We now consider the harder case of a session which is not solved by S. In this
case S uses the argument of knowledge of V* to obtain the private key used in
this session. Specifically, in any unsolved session, the simulator uses the extractor
E associated with the witness-indistinguishable argument of knowledge used by
the verifier.
Recall that we denote by the first message sent by the verifier in the
current session, by the verifier™s public key and by the puzzle sent
by the simulator when simulating the prover™s first message. We now distinguish
three possible cases.
Case 1: The message has not yet appeared in a previous session for
the same incarnation of the prover and the extractor E obtains as witness.
Note that S obtains the verifier™s private key by running E. This is the most
benign of the three cases since the session is now solved.
Case 2: The message has not yet appeared in a previous session for the
same incarnation of the prover and the extractor E obtains as witness.
Note however that the value has been chosen by S itself. If this case happens
with non-negligible probability then we can use V* to invert the one-way function
We stress that this case is the only conceptual difference between our proof
and the proof of rZK of protocol 6.2 in [3].
Case 3: The message has already appeared in a previous session for the
same incarnation of the prover. Note that since we are assuming that the current
session is not solved by S, this means that in at least one previous session, V*
sent but then did not continue with such a session. This prevents S from
simulating as in case 2 since the simulation would not be correct. (Specifically, as
discussed in [3], in a real execution of the argument, the pseudo-random string
used as random string for the prover™s first message is determined by the previous
uncompleted session (the input of is the same in both cases and the seed
is taken from the same random string) and therefore cannot be reset by S to
simulate this case by running an independent execution of E.) This problem is
bypassed precisely as in [3]. That is, S tries to continue the simulation from the
maximal sequence of executions which does not contain as a first step of
the verifier for such an incarnation of the prover, using a new random function.
The same analysis in [3] shows that this simulation strategy ends in expected
polynomial time and returns a distribution indistinguishable from a real execu-
tion of the argument.

3-Round WI Argument of Knowledge. As already pointed out above, we can save
one round (and thus obtain a 4-round argument system instead of 5-round one)
by having the prover send the puzzle after the verifier has started the witness-
indistinguishable argument of knowledge. In this argument of knowledge, the
verifier acts as a prover and shows knowledge of either the secret key associated
with his private key or of a solution of the puzzle. Consequently, the input
statement of such an argument of knowledge is not known from the start and
actually, when the first message is produced, only its length is known.
TEAM LinG
250 Giovanni Di Crescenzo, Giuseppe Persiano, and Ivan Visconti

Next we briefly describe such an argument of knowledge by adapting to our
needs the technique used by [16] to obtain a non-interactive zero-knowledge proof
system for Hamiltonicity.
1. The prover commits to randomly generated Hamiltonian cycles (each edge
is hidden in a committed adjacency matrix of degree
2. the graph G is presented to the prover and the verifier and verifier sends an
random challenge;
3. if the bit of the challenge is 0 then the prover opens the Hamiltonian
cycle;
4. if the bit of the challenge is 1 then the prover sends a permutation
and shows that each edge that is missing in the graph corresponds to
a commitment of 0 in the committed Hamiltonian cycle.
Completeness, soundness and witness indistinguishability can be easily verified.
The protocol is an argument of knowledge since an extractor that rewinds the
prover and changes the challenge obtains a Hamiltonian cycle of G.

4 Sequentially Sound Sequential Zero Knowledge for
in the BPK Model
In this section we give a 3-round sequentially sound sequential zero-knowledge
argument in the BPK model for any language in

Assumptions. We start by listing the tools and the complexity-theoretic assump-
tions we need for the construction of this section.
1. We assume the existence of an signature scheme SS = (SigG,Sig,
Ver). Here SigG denotes the key generator algorithm that receives the secu-
rity parameter (in unary) and returns a pair (pk,sk) of public keys; Sig
is the signature algorithm that takes as input a message and a private
key sk and returns a signature of and Ver is the signature verification
algorithm that takes a message a signature and a public key pk and
verifies that is a valid signature.
The scheme SS is in the sense that no algorithm running in time
that has access to a signature oracle but not to the private key can
forge the signature of a message for which it has not queried the oracle.
It is well known that if sub-exponentially strong one-way functions exist then
it is possible to construct secure signature schemes [18].
We assume that signatures of messages produced by using keys with
security parameter have length This is not generally true as for each
signature scheme we have a constant such that signatures of messages
have length but this has the advantage of not overburdening the notation.
It is understood that all our proofs continue to hold if this assumption is
removed.



TEAM LinG
Constant-Round Resettable Zero Knowledge with Concurrent Soundness 251

2. We assume the existence of a one-round perfectly binding computationally
hiding commitment scheme. The scheme is in the
sense that there exists an extractor algorithm E that on input a commitment,
computes in time the committed value.
Such a commitment schemes are known to exist under the assumption of the
existence of sub-exponentially strong one-to-one length-preserving one-way
functions.
3. We also assume the existence of ZAPs for all (see [19]).
In sums, our construction is based on the existence of subexponentially strong
one-to-one length preserving one-way functions and one-way trapdoor permuta-
tions.
We start by briefly describing the main idea of our protocol. The prover
and the verifier play the following game: the prover picks a random message
computes a commitment of and asks the verifier to sign the
verifier signs the commitment and sends back to the prover such a signature
and a message Finally the prover, constructs an extractable commitment
com of a random message and proves to the verifier using a ZAP that either
or com is the extractable commitment of a signature of a commitment
of Let us now informally argue about sequential soundness and sequential
zero-knowledge of the argument system described. For the sequential soundness,
we observe that, since is chosen at random by the verifier for each sequential
execution of the protocol, it is unlikely that the prover knows the signature of
a commitment of For the zero-knowledge property instead, the simulator,
once is received, rewinds V* and opens a new session with the verifier in
which he sets computes a commitment of and sends it to
the verifier that thus produces a signature of a commitment of Going back
to the original session, the simulator has a witness for the ZAP and can thus
complete the simulation.
Theorem 2. If there exist subexponentially strong one-to-one length-preserving
one-way functions and trapdoor permutations then there exists a 3-round sequen-
tially sound sequential zero-knowledge argument for in the BPK model.
Proof. Completeness and Sequential soundness can be easily proved. For the
Sequential Zero Knowledge, we now describe a simulator S. We consider a ma-
licious verifier V* that in the first stage outputs the public file F and in the
second stage interacts with P by considering possible theorems and
possible entries of F. However V* is now a sequential verifier and thus he cannot
run twice the same incarnation of P, neither he can run two concurrent sessions
with P. Thus the simulation proceeds session by session and we can focus only
in the simulation of a generic session.
Let be the state of V* at the beginning of a given session. The simulator
sends in the first round a message that is distributed identically w.r.t. the one
of the prover. Then V* replies by sending a message let the state of V*
in such a step. The simulator rewinds V* to state and plays again the first
round but this time he sets The simulator repeats this first round
TEAM LinG
Giovanni Di Crescenzo, Giuseppe Persiano, and Ivan Visconti
252

with a different randomness as long as the verifier sends a valid second message
that therefore contains a signature of a commitment of The simulator can

<<

. 8
( 19)



>>