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