original proof, that can be given by rewinding V* to state More precisely,

S rewinds V* to state and computes as a commitment of a commitment

of and as a commitment of the previously received signature. Then S has

a witness for playing the ZAP.

The previously described rewind strategy allows the simulator to complete

the simulation in expected polynomial-time and, moreover, the indistinguisha-

bility of the ZAP and the hiding of the commitment scheme guarantee that the

distribution of the output is computationally indistinguishable from an interac-

tion between a real prover and V*.

We remark that it is possible to base our construction on primitives secure

against polynomial-time adversaries by employing a 3-round witness indistin-

guishable argument where the statement is chosen by the prover before produc-

ing the third message.

5 Conclusions

In an asynchronous environment like the Internet resettable zero-knowledge pro-

tocols that are not concurrently sound in the BPK model cannot be considered

secure and previous concurrently sound protocols required stronger assumptions

than the BPK model.

In this work we have positively closed one of the main open problems regard-

ing zero knowledge in the BPK model. We have shown that a constant-round con-

currently sound resettable zero-knowledge argument system in the BPK model

exists. In particular, we have shown a 4-round protocol which is optimal for the

black-box model.

Acknowledgments

We would like to thank the anonymous referee for his/her very useful remarks

on our submission.

References

1. Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive

Proof-Systems. SIAM J. on Computing 18 (1989) 186“208

2. Dwork, C., Naor, M., Sahai, A.: Concurrent Zero-Knowledge. In: Proceedings of

the 30th ACM Symposium on Theory of Computing (STOC ™98), 409“418

3. Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable Zero-Knowledge.

In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC

™00), 235“244

4. Canetti, R., Kilian, J., Petrank, E., Rosen, A.: Black-Box Concurrent Zero-

Knowledge Requires Rounds. In: Proceedings of the 33st ACM Symposium

on Theory of Computing (STOC ™01), 570“579

TEAM LinG

Constant-Round Resettable Zero Knowledge with Concurrent Soundness 253

5. Barak, B.: How to Go Beyond the Black-Box Simulation Barrier. In: Proceeding of

the 42nd Symposium on Foundations of Computer Science, (FOCS ™01), 106“115

6. Blum, M., De Santis, A., Micali, S., Persiano, G.: Non-Interactive Zero-Knowledge.

SIAM J. on Computing 20 (1991) 1084“1118

7. Micali, S., Reyzin, L.: Soundness in the Public-Key Model. In: Advances in Cryp-

tology “ Crypto ™01. Volume 2139 of Lecture Notes in Computer Science. Springer-

Verlag, 542“565

8. Barak, B., Goldreich, O., Goldwasser, S., Lindell, Y.: Resettably-Sound Zero-

Znowledge and its Applications. In: Proceeding of the 42nd Symposium on Foun-

dations of Computer Science, (FOCS ™01), 116“125

9. Micali, S., Reyzin, L.: Min-round Resettable Zero-Knowledge in the Public-key

Model. In: Advances in Cryptology “ Eurocrypt ™01. Volume 2045 of Lecture

Notes in Computer Science. Springer-Verlag (2001) 373“393

10. Zhao, Y., Deng, X., Lee, C., Zhu, H.: Resettable Zero-Knowledge in the Weak

Public-Key Model. In: Advances in Cryptology “ Eurocrypt ™03. Volume 2045 of

Lecture Notes in Computer Science. Springer-Verlag (2003) 123“139

11. Goldreich, O.: Concurrent Zero-Knowledge with Timing, Revisited. In: Proceed-

ings of the 34th ACM Symposium on Theory of Computing (STOC ™02), ACM

(2002) 332“340

12. Di Crescenzo, G., Ostrovsky, R.: On Concurrent Zero-Knowledge with Pre-

processing. In: Advances in Cryptology “ Crypto ™99. Volume 1666 of Lecture

Notes in Computer Science. Springer-Verlag (1999) 485“502

13. Damgard, I.: Efficient Concurrent Zero-Knowledge in the Auxiliary String Model.

In: Advances in Cryptology “ Eurocrypt ™00. Volume 1807 of Lecture Notes in

Computer Science. Springer-Verlag (2000) 418“430

14. Goldwasser, S., Micali, S.: Probabilistic encryption. J. of Comp. and Sys. Sci. 28

(1984) 270“299

15. El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete

logarithms. In: Advances in Cryptology “ Crypto ™84. Volume 196 of Lecture Notes

in Computer Science. Springer Verlag (1984) 10“18

16. Feige, U., Lapidot, D., Shamir, A.: Multiple Non-Interactive Zero Knowledge

Proofs Under General Assumptions. SIAM J. on Computing 29 (1999) 1“28

17. Pass, R.: Simulation in Quasi-Polynomial Time and Its Applications to Protocol

Composition. In: Advances in Cryptology “ Eurocrypt ™03. Volume 2045 of Lecture

Notes in Computer Science. Springer-Verlag (2003) 160“176

18. Rompel, J.: One-Way Functions are Necessary and Sufficient for Digital Signa-

tures. In: Proceedings of the 22nd ACM Symposium on Theory of Computing

(STOC ™90). (1990) 12“19

19. Dwork, C., Naor, M.: Zaps and their applications. In: IEEE Symposium on Foun-

dations of Computer Science. (2000) 283“293

TEAM LinG

Zero-Knowledge Proofs and String

Commitments Withstanding Quantum Attacks

Ivan Damgård1, Serge Fehr2,*, and Louis Salvail1

1

BRICS, FICS, Aarhus University, Denmark**

{ivan,salvail}@brics.dk

2

CWI, Amsterdam, The Netherlands

fehr@cwi.nl

Abstract. The concept of zero-knowledge (ZK) has become of funda-

mental importance in cryptography. However, in a setting where entities

are modeled by quantum computers, classical arguments for proving ZK

fail to hold since, in the quantum setting, the concept of rewinding is

not generally applicable. Moreover, known classical techniques that avoid

rewinding have various shortcomings in the quantum setting.

We propose new techniques for building quantum zero-knowledge (QZK)

protocols, which remain secure even under (active) quantum attacks.

We obtain computational QZK proofs and perfect QZK arguments for

any NP language in the common reference string model. This is based

on a general method converting an important class of classical honest-

verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical

protocols if the underlying HVZK proof is efficient. These are the first

proof protocols enjoying these properties, in particular the first to achieve

perfect QZK.

As part of our construction, we propose a general framework for building

unconditionally hiding (trapdoor) string commitment schemes, secure

against quantum attacks, as well as concrete instantiations based on

specific (believed to be) hard problems. This is of independent interest,

as these are the first unconditionally hiding string commitment schemes

withstanding quantum attacks.

Finally, we give a partial answer to the question whether QZK is possible

in the plain model. We propose a new notion of QZK, non-oblivious

verifier QZK, which is strictly stronger than honest-verifier QZK but

weaker than full QZK, and we show that this notion can be achieved by

means of efficient (quantum) protocols.

1 Introduction

Since its introduction by Goldwasser, Micali and Rackoff [14], the concept of

zero-knowledge (ZK) proof has become a fundamental tool in cryptography. In-

Research was carried out while at the Centre for Advanced Computing - Algorithms

*

and Cryptography, Department of Computing, Macquarie University, Australia.

** BRICS stands for Basic Research in Computer Science (www.brics.dk) and FICS

for Foundations in Cryptography and Security, both funded by the Danish Natural

Sciences Research Council.

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 254“272, 2004.

© International Association for Cryptologic Research 2004

TEAM LinG

Zero-Knowledge Proofs 255

formally, in a ZK proof of a statement, the verifier learns nothing beyond the

validity of the statement. In particular, everything the verifier can do as a result

of the interaction with the prover during the ZK proof, the verifier could also

do “from scratch”, i.e., without interacting with the prover. This is argued by

the existence of an efficient simulator which produces a simulated transcript of

the execution, indistinguishable from a real transcript. ZK protocols exist for

any NP language if one-way functions exist [2,3,15], also more efficient solu-

tions are known for specific languages like Quadratic-Residuosity [14] or Graph-

Isomorphism [15].

From a theoretical point of view, it is natural to ask whether such classical

protocols are still secure if cheating players are allowed to run (polynomial time

bounded) quantum computers. But the question also has some practical rele-

vance: although quantum computers may not be available to the general public

in any foreseeable future, even a single large scale quantum computer could be

used to attack the security of existing protocols.

To study this question, two issues are important. First, the computational

assumption on which the protocol is based must remain true even if the adversary

is quantum. This rules out many assumptions such as hardness of factoring or

extracting discrete logs [23], but a few candidates still remain, for instance some

problems related to lattices or error correcting codes. In general, it is widely

believed that quantum one-way functions exist, i.e., functions that are easy to

compute classically, but hard to invert, even on a quantum computer.

A second and more difficult question is whether the proof of security remains

valid against a quantum adversary. A major problem in this context comes from

the fact that in the classical definition of ZK, the simulator is allowed to rewind

the verifier in order to generate a simulated transcript of the protocol execution.

However, if prover and verifier are allowed to run quantum computers, rewinding

is not generally applicable, as it was originally pointed out by Van de Graaf [27].

We discuss this in more detail later, but intuitively, the reason is that when

a quantum computer must produce a classical output, such as a message to

be sent, a (partial) measurement on its state must be done. This causes an

irreversible collapse of the state, so that it is not generally possible to reconstruct

the original state. Moreover, copying the verifier™s state before the measurement

is forbidden by the no-cloning theorem. Therefore, protocols that are proven

ZK in the classical sense using rewinding of the verifier may not be secure with

respect to a quantum verifier. This severe breakdown of the classical concept of

ZK in a quantum world is the motivation of this work.

It is well known that rewinding can cause “problems” already in a classi-

cal setting. In particular, it has been realized that rewinding the verifier limits

the composability of ZK protocols. As a result, techniques have been proposed

that avoid rewinding the verifier, for instance the non-black-box ZK technique

from [1], or “ in the common reference string model “ techniques providing con-

current ZK [13,22,9], non-interactive ZK [4] or universally-composable (UC)

ZK [5,6,11] and related models [21]. One might hope that some of these ideas

would translate easily to the quantum setting.

TEAM LinG

256 Ivan Damgård, Serge Fehr, and Louis Salvail

However, the non-black box technique from [1] is based on the simulator us-

ing the verifier™s program and current state to predict its reaction to a given

message. Doing so for a quantum verifier will collapse its state when a measure-

ment is done to determine its next message, so it is not clear that this technique

will generalize to a quantum setting. The known constructions of UCZK pro-

tocols and non-interactive ZK are all based on computational assumptions that

are either false in a quantum setting or for which we have no good candidate

for concrete instantiations: the most general sufficient assumption is the exis-

tence of one-way trapdoor permutations (i.e. as far as we know) but all known

candidates are easy to invert on a quantum computer. Regardless of this type

of problem, great care has to be taken with the security proof: despite the fact

that the simulator in the UC model must not use rewinding, it is not true that

a security proof in the UC model automatically implies security against quan-

tum adversaries - we discuss this in more details later in the paper. Finally, the

technique for concurrent ZK from [9] avoids rewinding the verifier but instead

rewinds the prover to prove soundness, leading to similar problems.

Before describing our results, we note that quantum zero-knowledge proof

systems were already studied from a complexity theoretic point of view by Wa-

trous in [26]. The proof systems considered there all assume the prover to be

computationally unbounded and the zero-knowledge condition is only enforced

against honest verifiers. Clearly, these restrictions make those proof systems

unsuitable for cryptographic applications. In this paper, we focus on efficient

quantum zero-knowledge protocols in a cryptographic setting.

We propose three distinct techniques applicable to an important class of

(classical) honest-verifier ZK (HVZK) proofs (in which the verifier is guaranteed

to follow the protocol), namely so-called (3-move public-coin pro-

tocols). We convert such protocols into quantum zero-knowledge (QZK) proofs,

which are ZK (as well as sound) even with respect to (active) quantum attacks.

In all cases, the new proof protocol proceeds in three moves like the underly-

ing and its overhead in terms of communication is reasonable. To

the best of our knowledge, these are the first (practical) zero-knowledge proofs

withstanding active quantum attacks.

The first technique assumes the existence of an unconditionally hiding trap-

door string commitment scheme (secure against quantum attacks) and can be

proven secure in the common-reference-string (CRS) model. It requires only clas-

sical computation and communication and achieves perfect or statistical QZK,

assuming the underlying was perfect or statistical HVZK, and is an

interactive argument (computationally sound). The communication overhead of

the new QZK protocol in comparison with the underlying is essen-

tially given by communicating and opening one string commitment. The tech-

nique directly implies perfect or statistical QZK arguments for NP.

This first approach requires addressing the problem of constructing uncondi-

tionally hiding and computationally binding trapdoor string commitment

schemes withstanding quantum attacks. This is non-trivial since the classical

definition of computational binding cannot be used for a quantum adversary as

TEAM LinG

Zero-Knowledge Proofs 257

it was pointed out in [12] with respect to bit commitments and in [8] with respect

to string commitments. In fact, it was not even clear how computational binding

for a string commitment should be defined. In [8], a computational binding con-

dition was introduced with their application in mind but no concrete instance

was proposed.

We propose a new definition of computational binding that is strong enough

for our (and other) applications. On the other hand, we propose a generic

construction for schemes satisfying our definition based on special-sound

for hard-to-decide languages, and we give examples based on concrete

intractability assumptions. Our construction yields the first unconditionally hid-

ing string commitment schemes withstanding quantum attacks, under concrete

as well as under general intractability assumptions. Moreover, since our defini-

tion implies the one from [8], our schemes can be used to provide secure quantum

oblivious transfer.

The second technique assumes the existence of any quantum one-way func-

tion and is also secure in the CRS model. It requires classical communication

and computation and produces computational QZK interactive proofs for any

NP language. It can be efficiently instantiated under more specific complexity

assumptions.

The last technique requires no computational assumption and is provably se-

cure in the plain model (no CRS). However, it requires quantum computation and

communication and does not achieve full QZK but what we call non-oblivious

verifier QZK. This new notion is weaker than QZK but strictly stronger than

honest-verifier QZK (as defined in [26]). Essentially, a non-oblivious verifier may

arbitrarily deviate from the protocol but still generates all private and pub-

lic classical random variables available to the honest verifier according the same

distribution. The (quantum) communication complexity of the non-oblivious ver-

ifier QZK proof essentially equals the (classical) communication complexity of

the underlying

The paper is organized as follows. In Sect. 2, we introduce some relevant

notations. We also argue why rewinding causes a problem in a quantum setting

and why UCZK does not imply QZK. In Sect. 3, we define and construct the

unconditionally hiding (trapdoor) commitment schemes used in Sect. 4 for QZK

proofs in the common-reference-string model. Finally, the non-oblivious verifier

QZK proof in the plain model is presented in Sect. 5.

Due to space limitations, some descriptions and discussions appear in a short-

ened form in this proceedings version, they appear in full in the full version [10].

2 Preliminaries

2.1 Zero-Knowledge Interactive Proofs

The Classical Case: We assume the reader to be familiar with the classical

notions of (HV)ZK interactive proofs (and arguments) and of (special-sound)

We merely fix some notation and terminology here. For an intro-

duction to these concepts we refer to the full version of this paper [10] or to the

literature.

TEAM LinG

258 Ivan Damgård, Serge Fehr, and Louis Salvail

Let be a binary relation. Write for

the language defined by R. For any such that is called

a witness (for and we write for the set of

witnesses for We assume that the size of the witnesses for are

polynomially bounded by the size of and that R is poly-time testable.

(P, V) for a language L by a triple (a, c,z), where we

We refer to a

understand a, c and z as the processes of choosing/computing the first message

the (random) challenge and the corresponding answer respectively, as

specified by the protocol (with some input and we write

and respectively, for the execution of these processes. Furthermore,

for the verification predicate which is applied by V and whose

we write

output accept or reject, respectively 0 or 1, determines whether V should

accept the proof or not. We stress that when considering a computationally

bounded (honest) prover P as we do here the answer is typically not computed

by P as a function of and (as the notation might suggest),

but rather as a function of the randomness used to generate of the challenge

and of a witness Per default, we understand a to

be unconditionally sound. Clearly, for a fixed the soundness error of

such a is given by the maximum over all possible first messages of

the fraction of the possible challenges for that allow an answer which is

accepted by V.

It is known that statistical ZK only exist for languages

Most of the well-known are proof-system for languages that

are trivial on a quantum computers. However, some languages like graph isomor-

phism (i.e. GI) have special sound and are not known to be trivial

on a quantum computer. This is also the case for some recently proposed lattice

problems [19]. It is not known whether co-AM can be efficiently recognized by

a quantum computer.

The Quantum Case: ZK quantum interactive proof systems are defined as the

natural generalization of their classical counterpart and were introduced and first

studied by Watrous [24,26]. Quantum ZK (QZK) is defined as for the classical

case except that the quantum simulator is required to produce a state that

is exponentially close, in the trace-norm sense, to the verifier™s view. Formal

definitions for QZK proof systems can be found in the full version [10].

2.2 The Problem with Quantum Rewinding

Rewinding a party to a previous state is a common proof technique for showing

the security of many different kinds of protocols in the computational model.

In general, this technique cannot be applied when the party is modeled by a

quantum computer. Originally observed by Van de Graaf [27], this implies that

security proofs of many well-established classical protocols do not hold if one

party is running a quantum computer even if the underlying assumption under

which the security proof holds withstands quantum attacks.

Rewinding is in general not possible since taking a snapshot of a quantum

memory is tantamount to quantum cloning. Unlike in the classical case, there

TEAM LinG

Zero-Knowledge Proofs 259

is no way to copy a quantum memory regardless of what the memory contains.

The only generic way to restore a quantum memory requires to re-generate it

from scratch. Proceeding that way may not be possible efficiently.

One consequence of the no quantum rewinding paradigm is particularly rel-

evant to us. Sequential repetitions of an HVZK for a language L

results in a ZK protocol for L with negligible soundness error. It follows that

this straightforward construction is not guaranteed to be secure against quantum

verifiers.

Another example is the use of rewinding for proving secure applications of

computationally binding commitment schemes. Such a security proof is done by

showing that an attacker that breaks the application can be used to compute two

different openings of a commitment and thus to break the binding property of

the commitment scheme. This reduction, however, requires typically to rewind

of the attacker, and thus by the no quantum rewinding paradigm does not yield

a valid security proof in a quantum setting.

More details can be found in the full version [10].

2.3 UCZK Does Not Imply QZK

In [5], Canetti proposes a new framework for defining and proving cryptographic

protocols secure: the universal composability (UC) framework. This framework

allows to define and prove secure cryptographic protocols as stand-alone proto-

cols, while at the same time guaranteeing security in any application by means

of a general composition theorem. The UC security definition essentially requires

that the view of any adversary attacking the protocol can be simulated while

in fact running an idealized version of the protocol, which essentially consists

of a trusted party called ideal functionality. The simulation should be indistin-

guishable for any distinguisher, called environment, which may be on-line, and

provides the inputs and receives the outputs. Furthermore, the UC definition

explicitly prohibits rewinding of the environment and thus of the adversary (as

it may communicate with the environment). This restriction is crucial for the

proof of the composition theorem. We refer to [5] for more details.

Since the UC framework forbids rewinding the adversary, it seems that UCZK

implies QZK, assuming the underlying computational assumption withstands

quantum attacks. This intuition is false in general. The reason being that even

though the UC framework does not allow the simulator to rewind the adversary,

it is still allowed to use rewinding as a proof-technique in order to show that the

simulator produces a “good” simulation. For instance, it is allowed to argue that

if an environment can distinguish the simulation from a real protocol execution,

then by rewinding the environment together with the adversary one can solve

efficiently a problem assumed to be hard. We illustrate this on a concrete example

in [10].

3 Unconditionally Hiding (Trapdoor) Commitments

In this section we study and construct classical (trapdoor) commitment schemes

secure against quantum attacks. In contrast to quantum commitment schemes,

TEAM LinG

260 Ivan Damgård, Serge Fehr, and Louis Salvail

such schemes do not require quantum computation (in order to compute, open

or verify commitments), but they are guaranteed to remain secure even under

quantum attacks. Our construction, which is based on hard-to-decide languages

with special-sound yields the first unconditionally hiding string

commitment schemes withstanding quantum attacks. In Sect. 4, we use these

commitments to construct QZK proofs. A further application of our commitment

schemes is given in [10], where it is shown how they give rise to quantumly secure

oblivious transfer.

3.1 Defining Security in a Quantum Setting

Informally, by publishing a commitment for a random

a commitment scheme allows a party to commit to a secret such that the

commitment C reveals nothing about the secret (hiding property) while on the

other hand the committed party can open C to by publishing but only

to (binding property).

Formally, a commitment scheme (of the kind we consider) consists of two

poly-time algorithms: A key-generation algorithm which takes as input the se-

curity parameter and specifies an instance of the scheme by generating a public-

key pk, and an algorithm commit which allows to compute

given a public-key pk as well as and chosen from appropriate finite sets and

(specified by pk). is called the domain of the commitment scheme. Classi-

cally, the hiding property is formalized by the non-existence of a distinguisher

which is able to distinguish from with

non-negligible advantage, where are chosen by the distinguisher and

are random. On the other hand, the binding property is formalized by

the non-existence of a forger able to compute and such that

but If the distinguisher respectively the

forger is restricted to be poly-time, then the scheme is said to be computation-

ally hiding respectively binding, while without restriction on the distinguisher

respectively the forger, it is said to be unconditionally hiding respectively bind-

ing.

commit) in a

In order to define security of such a commitment scheme

quantum setting, the (computational or unconditional) hiding property can be

adapted in a straightforward manner by allowing the distinguisher to be quan-

tum. The same holds for the unconditional binding property, which is equivalent

to requiring that every C uniquely defines such that for

some However, adapting the computational binding property in a similar man-

ner simply by allowing the forger to be quantum results in a too weak definition.

The reason being that in order to prove secure an application of a commitment

scheme, which is done by showing that an attacker that breaks the application

can be transformed in a black-box manner into a forger that violates the binding

property, the attacker typically needs to be rewound, which cannot be justified

in a quantum setting by the no-quantum-rewinding paradigm as discussed in

Sect. 2.2. The following definition for the computational binding property of a

commitment scheme with respect to quantum attacks is strong enough to prove

TEAM LinG

Zero-Knowledge Proofs 261

secure applications (as in Sect. 4 and in [10]) based on the security of the un-

derlying commitment scheme, but it is still weak enough in order to prove the

binding property for concrete commitment schemes (see Sect. 3.2 and 3.3).

commit) be a commitment scheme as introduced above, and let

Let

denote its domain. Informally, we require that it is infeasible to produce a

list of commitments and then open (a subset of) them in a certain specified

way with a probability significantly greater than expected. We formalize this

as follows. Let Q be a predicate of the following form. Q takes three inputs:

(1) a non-empty set where N is upper bounded by a polyno-

mial in (2) a tuple with and (3) an element

where is some finite set; and it outputs We do not

require Q to be efficiently computable. Consider a polynomially bounded quan-

tum forger in the following game: takes as input pk, generated by

and announces commitments Then, it is given a random

and it outputs A, and is said to win the

game if and for every We re-

quire that every forger has essentially the same success probability in win-

ning the game as when using an ideal (meaning unconditionally binding) com-

mitment scheme (where every uniquely defines In the latter case, the

success probability is obviously given by with

where stands for the restriction of

to its coordinates with In this definition, Q models a condition that

must be satisfied by the opened value in order for the opening to be useful for

the committer. For each application scenario, such a predicate can be defined.

commit) is called computational Q-

Definition 1. A commitment scheme

binding if for every predicate Q, every polynomially bounded quantum forger

wins the above game with probability where adv, the advantage

of is (negative or) negligible (in

It is not hard to verify that in a classical setting (where is allowed to

be rewound), the classical computational binding property is equivalent to the

above computational Q-binding property. Furthermore, it is rather obvious that

the computational Q-binding property for a commitment scheme with domain

implies the computational Q-binding property for the natural extension of the

scheme to the domain (for any by committing componentwise. Note that

this desirable preservation of the binding property does not hold for the binding

property introduced in [8].

Finally, we define a trapdoor commitment scheme1 as a commitment scheme

in the above sense with the following additional property. Besides the public-

key pk, the generator also outputs a trapdoor which allows to break either

the hiding or the binding property. Specifically, if the scheme is unconditionally

binding, then allows to efficiently compute from and if

it is unconditionally hiding, then allows to efficiently compute commitments

C and correctly open them to any

1

Depending on its flavor, a trapdoor commitment scheme is also known as an ex-

tractable respectively as an equivocable or a chameleon commitment scheme.

TEAM LinG

262 Ivan Damgård, Serge Fehr, and Louis Salvail

3.2 A General Framework

In this section, we propose a general framework for constructing unconditionally

hiding and computationally Q-binding (trapdoor) string commitment schemes.

For that, consider a language and assume that

2

1. L admits a (statistical) HVZK special-sound ,

2. there exists an efficient generator generating together with a

witness (more precisely, takes as input security parameter

and outputs of bit size and and

3. for all poly-size quantum circuits and polynomials if is large

enough then there exists of bit size such that for generated by

(on input

Note that 3. only requires that for every distinguisher it is hard to distinguish

a randomly generated yes-instance from some no-instance which

in particular may depend on

Given such L, the construction in Fig. 1 provides an unconditionally hiding

trapdoor commitment scheme. We assume that c samples challenge randomly

from for some

commit).

Fig. 1. Trapdoor commitment scheme

If is special HVZK, meaning that can be simulated for a given

then the commitment scheme can be slightly simplified: is generated

such that and C is simply set to be

commit) in Fig. 1 is an unconditionally

Theorem 1. Under assumption 3.,

hiding and computationally Q-binding trapdoor commitment scheme.

2

As will become clear, the prover™s efficiency in the does not influence

the efficiency of the resulting commitment scheme as far as the committer and the

receiver are concerned. An efficient prover is only required if one wants to take

advantage of the trapdoor.

TEAM LinG

Zero-Knowledge Proofs 263

As will become clear from the proof below, if the underlying

commit) is perfectly binding in the sense that there

is perfect HVZK, then

exists no distinguisher with non-zero advantage, meaning that a commitment C

for is statistically independent of

Proof. It is clear that a correct opening is accepted. It is also rather obvious that

the scheme is unconditionally hiding: The distribution of generated by

the HVZK simulator is statistically close to the distribution of generated

by the protocol. There, however, is chosen independently of Therefore,

gives essentially no information on and thus gives essentially no

information on (as acts as a one-time pad). The trapdoor property can

be seen as follows. Knowing the trapdoor put where

and is randomly sampled from Given arbitrary compute

and using the witness (and the randomness for the

generation of It is obvious that opens C correctly to

It remains to show the computational Q-binding property. We show that if

there exists a forger that can break the Q-binding property of the commit-

ment scheme (without knowing the trapdoor) for some predicate Q according to

Definition 1, then there exists a circuit that contradicts assumption 3. is

illustrated in Figure 2 and is quantum if and only if is.

Fig. 2. Distinguisher for versus

If is generated by then is a valid public-key for the commitment

scheme with the right distribution and thus

where adv is advantage. On the other hand, if then by the special

soundness property of given there is only one that allows an answer

such that Hence, for any there is only one to

which can be successfully opened. Therefore, If adv

is (positive and) non-negligible, then this contradicts 3.

We would like to point out once more that our definition of the (computa-

tional) binding property inherits the following feature. If a commitment scheme

with domain is computational Q-binding, then its natural extension to a

commitment scheme with domain by committing componentwise (with the

TEAM LinG

264 Ivan Damgård, Serge Fehr, and Louis Salvail

same pk) is also computational Q-binding. In particular, any computational Q-

binding bit commitment scheme gives rise to a computational Q-binding string

commitment scheme.

3.3 Concrete Instantiations

We propose three concrete languages which are believed to be hard to de-

cide as required in the above section and which admit HVZK special-sound

The first language is based on a problem from coding theory: the

Code-Equivalence (CE) problem. It requires to decide whether two generator

matrices generate the same code up to a permutation of the coordinates, and it

is known to be at least as hard (in the worst case) as the Graph-Isomorphism

(GI) problem. Furthermore, it admits a similar as GI. Finally, and

in contrast to GI, there is a generator believed to produce hard yes-instances.

More details are given in [10].

The next two languages are gap versions of the famous lattice problems

Shortest-Vector and Closest-Vector, where the no-instances are promised to be

“not too close” to the yes-instances. for these problems were recently

proposed in [19], where the generation of hard instances is also addressed. Again,

more details are given in [10].

These languages give rise to concrete instantiations of the commitment

scheme developed in the above section, based on concrete computational as-

sumptions.

4 Quantum Zero-Knowledge Proofs

4.1 Common-Reference-String Model

The common-reference-string (CRS) model assumes that there is a string (hon-

estly) generated according to some distribution and available to all parties from

the start of the protocol. In the CRS model, an interactive proof (or argument)

is (Q)ZK if there exists a simulator which can simulate the (possibly dishonest)

verifier™s view of the protocol execution together with a CRS having correct

joint distribution as in a real execution.

4.2 Efficient QZK Arguments

We show how to convert any HVZK into a quantum zero-knowledge

(QZK) argument. The construction is based on a trapdoor commitment scheme

and can be proven secure in the CRS model.

It is actually very simple. P and V simply execute the but instead

of sending message in the first move, P sends a commitment to which he

then opens when he sends the answer to the challenge in the third move. The

zero-knowledge property then follows essentially by observing that the simulator

(who knows the trapdoor of the commitment scheme) can cheat in the opening

TEAM LinG

Zero-Knowledge Proofs 265

of the commitment. So far, the strategy for the QZK proof is the same as in

Damgård™s concurrent ZK proof [9]; the proof of soundness however will be

different since [9] requires to rewind the prover, which cannot be justified in

our case by the no-quantum-rewinding paradigm. In order not to rely on the

special HVZK property (as introduced and explained in Sect. 3.2), the protocol

is slightly more involved than sketched here, though the idea remains.

Let a HVZK for a language be given. Let

denote its soundness error. We assume without loss of generality that a and c

sample first messages and challenges of fixed bit lengths and respectively.

Furthermore, let an unconditionally hiding and computationally Q-binding trap-

commit) be given (where the knowledge of the

door commitment scheme

trapdoor allows to break the binding property of the scheme). We assume that

its domain contains Consider Protocol 1 illustrated in Fig. 3.

Fig. 3. QZK proof protocol in the CRS model.

As mentioned above, Protocol 1 can be slightly simplified in case is special

HVZK in that P commits to (rather than to and computes with respect

provided by V.

to the challenge

commit) is an unconditionally hid-

Theorem 2. Under the assumption that

ing and computationally Q-binding trapdoor commitment scheme, Protocol 2 is

a QZK (quantum) argument for L in the CRS model. Its soundness error is

where negl is negligible (in the security parameter).

Concerning the flavor of QZK, Protocol 2 is computational QZK if the under-

lying is computational HVZK, and it is statistical QZK provided

commit) is perfectly (rather

that is statistical or perfect HVZK. In case

than unconditionally) hiding, the flavor of QZK of Protocol 2 is exactly given

by the flavor of HVZK of

Proof. As mentioned above, the zero-knowledge property is rather straight for-

ward: The simulator generates a public-key for the commitment scheme together

with a trapdoor and outputs the public-key as CRS. Then, on input it

generates a commitment C (which he can open to an arbitrary value using the

trapdoor) and sends it to On receiving from the simulator simulates

TEAM LinG

266 Ivan Damgård, Serge Fehr, and Louis Salvail

an accepting conversation for the original using the HVZK

property, it sets and computes such that

using the trapdoor, and it sends and to

For the soundness property, it has to be shown that given a (quantum) prover

which succeeds in making (honest) V accept the proof for an with a

probability exceeding by a non-negligible amount, can be used to break

the Q-binding property of the commitment scheme for some predicate Q. Fix

We define Q as follows. N = 1, and is given by the set of all possible

sampled by c. For

challenges and where is parsed as

with and we set if and only

if the challenge for the first message allows an answer such

that Note that A = {1} is the only legitimate choice

for A. By construction of Q, making V accept the proof means that opens C

(correctly) to such that Furthermore, It

follows that if succeeds in making V accept the proof with probability greater

that by a non-negligible amount, then is a forger that breaks the Q-binding

commit). This completes the proof.

property of

4.3 QZK Arguments for All of NP

Consider a (generic) ZK argument for an A/P-complete language using (ordinary)

unconditionally hiding commitments. For instance, consider the classical inter-

active proof for Circuit-Satisfiability due to Brassard, Chaum and Cr©peau [3]:

the prover “scrambles” the wires and the gates™ truth tables of the circuit and

commits upon it, and he answers the challenge by opening all commit-

ments and showing that the scrambling is done correctly and the challenge

by opening the (scrambled) wires and rows of the gates™ truth tables that are

activated by the satisfying input. Following the lines of the proof of Theorem 2

above, it is straightforward to prove that replacing the commitment scheme in

this construction by an unconditionally hiding and computationally Q-binding

commitment scheme results in a QZK argument in the CRS model for Circuit-

Satisfiability, and thus for all languages in NP.

4.4 Computational QZK Proofs

We sketch how to construct rather efficient computational QZK proofs for lan-

guages that allow (computational) HVZK based on specific in-

tractability assumptions, as well as computational QZK proofs for all of NP

based on any quantum one-way function.

Consider any of the languages with HVZK on which

the commitment construction from Sect. 3.2 is based, except that we allow the

to be computational HVZK. Assume in addition that there is also a

generator that produces no-instances that cannot be distinguished from the

yes-instances produced by

Then, put a no-instance in the reference string. The prover can now

prove any statement S that can be proved by an HVZK by us-

TEAM LinG

Zero-Knowledge Proofs 267

ing a standard witness-indistinguishable HVZK proof for proving that S is true

or [7]. Here, we allow the to be computational HVZK,

in particular might be the for Circuit-Satisfiability sketched in

Sect. 4.3 above but based on an unconditionally binding and computationally

hiding commitment scheme (secure against quantum attacks), which can be con-

structed from any (quantum) one-way function (see below).

This is clearly unconditionally sound, and can be simulated, where the sim-

ulator uses a yes-instance in place of and uses its witness

to complete the protocol without rewinding. A distinguisher would have to con-

tradict the HVZK property of one of the underlying or the indis-

tinguishability of yes- and no-instances.

This can be instantiated efficiently if we are willing to assume about the

coding or lattice problem or some other candidate problem that it also satisfies

this stronger version of indistinguishability of yes- and no-instances. But it can

also be instantiated in a version that can be be based on any one-way function:

First, the (unconditionally binding and computationally hiding) commitment

scheme of Naor [20] is also secure against quantum adversaries, and exists if

any one-way function exists. So consider the language of pairs (pk, O) where pk

is a public-key for the commitment scheme and O is a commitment of 0. This

language has a computational HVZK using generic ZK techniques,

driven by Naor™s commitments. Furthermore, the set of no-instances (pk, E)

where E is a commitment to 1 is easy to generate and hard to distinguish from

the yes-instances.

5 Relaxed Honest-Verifier Quantum Proofs

It is a natural question whether QZK proof systems exist without having to

rely upon common reference strings. In this section, we answer this question

partially. We define a quantum interactive proof system associated to any

Our scheme is QZK against a relaxed version of honest verifiers that

we call non-oblivious. Intuitively, a non-oblivious verifier is a verifier having

access to the same classical variables than the honest verifier. We show that any

HVZK can be turned into a non-oblivious verifier QZK proof using

quantum communication.

5.1 Quantum Circuits for

Assume has a classical HVZK We specify

unitary transforms and depending on which implement

quantum versions of the computations specified by z and verify. Throughout, we

assume without loss of generality that c samples uniformly from for

some

The answer to challenge when was announced during the

first round can be computed quantumly through some unitary transform

depending upon the initial announcement That is, provided quantum registers

P and X, we have:

TEAM LinG

268 Ivan Damgård, Serge Fehr, and Louis Salvail

Similarly, the testing process performed by V can also be executed by a quan-

tum circuit depending on the announcement of Transformation

stores the output of the verification process in an extra one-qubit register T:

If and can be classically computed in polynomial time

(given the randomness of the computation of and a witness for

the former), circuits and can be implemented by poly-size quantum

circuits.

5.2 EPR-Pairs Based Proofs

The idea behind the protocol is as follows. P chooses and sends the

answer to all possible challenges in quantum superposition to V. V then verifies

quantumly that all answers in the superposition are correct. In a further step,

P convinces V that the state contains the answer to more than one challenge.

Since is assumed to be special sound, it follows that

Concretely, P starts by choosing and by preparing EPR pairs in

state:

The two equivalent ways of writing shows that it exhibits the same corre-

lation between registers P and V in both the computational and the diagonal

bases. This property will be used later in the protocol. Now, P adds an extra

register X initially in state before applying upon registers P and X.

This results in state,

P then announces

where every in the superposition is computed as

and sends registers V and X to V allowing him to apply the verification

quantum circuit after adding an extra register T initially in state

That is,

V then measures register T in the computational basis and rejects if is not

observed. Provided P was honest, the test will always be successful by assumption

on the original and the verification process does not affect the

V then returns register X back to P, who can recover shared EPR

state

Finally, P measures register P in

pairs by running the inverse of

TEAM LinG

Zero-Knowledge Proofs 269

the diagonal basis and announces the outcome to V. V does the same to register

V and verifies that the same outcome is obtained. By the properties of EPR

pairs (1), it follows that the measurements coincide provided P was honest. A

compact description of the protocol is given by Protocol 2 in Fig. 4.

Fig. 4. Non-oblivious verifier QZK proof.

5.3 Soundness

Consider We show that in Protocol 2, any prover has probability at

to convince V, given that

most is special sound. Let be announced

by at step 1. By the special soundness property of if passes the test

and V is of the following form:

at step 2. then the state shared between

where is the unique challenge that can be answered

given the announcement of Since after register X has been sent back to

register V is in pure state, it follows that only one answer is possible when V is

measured in the computational basis. That is, is guaranteed to be observed.

However, V™s final test involves a measurement of that same register in the

diagonal basis, and it is easy to see that the outcome of a measurement in the

diagonal basis applied to is uniformly distributed over This is a special

case of the entropic uncertainty relations [18]. It follows:

Theorem 3. If is a special-sound HVZK for language

where c samples in then Protocol 2 is a quantum interactive proof for L

with soundness error

It should be mentioned that being special sound is not a strict necessary

condition for Protocol 2 to be sound. A more careful analysis can handle the

case where is “not too far away” from special sound. For simplicity, in this

paper we only address the case of special sound

5.4 Non-oblivious Verifier Quantum Zero-Knowledge

Classical with large challenges are not known to be ZK against a

dishonest verifier. This is due to the fact that rewinding allows the simulator

TEAM LinG

270 Ivan Damgård, Serge Fehr, and Louis Salvail

to succeed only if it has a non-negligible probability to guess the challenge that

the verifier will pick. This is true even with respect to verifiers that submit a

uniformly distributed challenge and are able to do the verification

be a one-way permutation

test as prescribed. To see this, let

and a samples from

and let us assume for simplicity that If

announces challenge for random and announced

by P as first message, then the simulator must generate since it is

part of view. However, the simulator typically can compute only after

having picked which means that it has to compute as Note

that even though is not necessarily uniformly distributed, it seems that

the simulator has typically not enough control over the value in order to

compute

Notice that a verifier acting as described above rejects a false statement

with the same probability and chooses the challenge with the same distribution

as an honest verifier, yet there is no known efficient simulator for In this

section we show that Protocol 2 is quantum zero-knowledge provided that is

non-oblivious of the value needed for the verification at step 4. More generally,

we define non-oblivious verifiers the following way:

Definition 2. A verifier is said to be non-oblivious if it produces the same

(public and private) variables as honest V according the same distribution.

As illustrated above, in contrast to an honest verifier a non-oblivious verifier

can produce his variables in an arbitrary manner, as long as they are correctly

distributed.

In Protocol 2, a non-oblivious verifier has access to the string so it can

be made available to the simulator. Indeed, this allows to produce a simulation of

the interaction between P and It is straightforward to verify that the simulator

described in Fig. 5 generates the same view as when interacts with P:

Fig. 5. Simulator for Protocol 2.

Theorem 4. Protocol 2 built from a special-sound (statistical/perfect) HVZK

is (statistical/perfect) QZK provided is non-oblivious.

A weaker assumption about behavior would be obtained if the only con-

straint was that detects false statements with the same probability as the

honest verifier V. Let us say that such a verifier is verification-enabled. In gen-

eral, a verification-enabled verifier is not necessarily non-oblivious since in

TEAM LinG

Zero-Knowledge Proofs 271

order to verify announcement, does not necessarily have to be deter-

mined by without P™s help. However, it can be shown that for

with challenges of polylogarithmic size, any verification-enabled in Protocol 2

is also non-oblivious.

Acknowledgements

The authors are grateful to Claude Cr©peau for having introduced the problem

to one of us and discussed its relevance. We would also like to thank Jesper

Nielsen for enlightening discussions.

References

1. BARAK, B., How to Go Beyond the Black-box Simulation Barrier, in 42th Annual

Symposium on Foundations of Computer Science (FOCS), 2001.

BRASSARD, G., and C. CRÉPEAU, Zero-Knowledge Simulation for Boolean Cir-

2.

cuits, in Advances in Cryptology - CRYPTO 86, Lecture Notes in Computer

Science, vol. 263, Springer-Verlag, 1987.

BRASSARD, G., D. CHAUM, and C. CRÉPEAU, Minimum Disclosure Proofs of

3.

Knowledge, JCSS, 37(2), 1988.

BLUM, M., P. FELDMAN and S. MICALI, Non-Interactive Zero-Knowledge and

4.

Its Applications, in 20th Annual Symposium on Theory Of Computing (STOC),

1988.

CANETTI, R., Universally Composable Security: A New Paradigm for Crypto-

5.

graphic Protocols, in 42th Annual Symposium on Foundations of Computer Sci-

ence (FOCS), 2001.

CANETTI, R., and M. FISCHLIN, Universally Composable Commitments, in Ad-

6.

vances in Cryptology - CRYPTO 01, Lecture Notes in Computer Science,

vol. 2139, Springer-Verlag, 2001.

CRAMER, R., I. DAMGåRD, and B. SCHOENMAKERS, Proofs of Partial Knowledge

7.

and Simplified Design of Witness Hiding Protocols, in Advances in Cryptology -

CRYPTO 94, Lecture Notes in Computer Science, vol. 839, Springer-Verlag, 1994.

CRÉPEAU, C., P. DUMAIS D. MAYERS and L. SALVAIL,Computational Collapse of

8.

Quantum State with Application to Oblivious Transfer, in Advances in Cryptology

“ TCC 04, Lecture Notes in Computer Science, vol. 2951, Springer-Verlag, 2004.

DAMGåRD, I., Efficient Concurrent Zero-Knowledge in the Auxiliary String

9.

Model, in Advances in Cryptology - EUROCRYPT 00, Lecture Notes in Com-

puter Science, vol. 1807, Springer-Verlag, 2000.

DAMGåRD, I.,S. FEHR, and L. SALVAIL, Zero-Knowledge Proofs and String Com-

10.

mitments Withstanding Quantum Attacks, full version of this paper, BRICS report

nr. RS-04-9, available at www.brics.dk/RS/04/9, 2004.

DAMG…RD, I., and J. NIELSEN, Perfect Hiding and Perfect Binding Universally

11.

Composable Commitment Schemes with Constant Expansion Factor, in Advances

in Cryptology - CRYPTO 02, Lecture Notes in Computer Science, vol. 2442,

Springer-Verlag, 2002.

DUMAIS, P., D. MAYERS, and L. SALVAIL, Perfectly Concealing Quantum Bit

12.

Commitment From Any Quantum One-Way Permutation, in Advances in Cryp-

tology - EUROCRYPT 00, Lecture Notes in Computer Science, vol. 1807,

Springer-Verlag, 2000.

TEAM LinG

Ivan Damgård, Serge Fehr, and Louis Salvail

272

13. DWORK, C., M. NAOR, and A. SAHAI, Concurrent Zero-Knowledge, in 30th An-

nual Symposium on Theory Of Computing (STOC), 1998.

14. GOLDWASSER, S., S. MICALI, and C. RACKOFF, The Knowledge Complexity of

Interactive Proof Systems, in 17th Annual Symposium on Theory Of Computing

(STOC), 1985.

15. GOLDREICH, O., S. MICALI, and A. WIGDERSON, Proofs that Yield Nothing

but their Validity, or All Languages in NP Have Zero-Knowledge Proof Systems,

J. ACM., 38(3), 1991.

16. FIAT, A., and A. SHAMIR, How to Prove Yourself: Practical Solutions to the

Identification and Signature Problem, in Advances in Cryptology - CRYPTO 86,

Lecture Notes in Computer Science, vol. 263, Springer-Verlag, 1987.

17. KITAEV, A., and J. WATROUS, Parallelization, Amplification, and Exponential

Time Simulation of Quantum Interactive Proof Systems, in 32nd Annual Sympo-

sium on Theory of Computing (STOC), 2000.

18. MAASSEN, H., and J.B.M. UFFINK, Generalized Entropic Uncertainty Relations,

Phys. Rev. Letters, vol. 60, 1988.

19. MICCIANCIO, D., and S. P. VADHAN, Statistical Zero-Knowledge Proofs with

Efficient Provers: Lattice Problems and More, in Advances in Cryptology -

CRYPTO 03, Lecture Notes in Computer Science, vol. 2729, Springer-Verlag,

2003.

20. NAOR, M., Bit Commitment Using Pseudorandomness, Journal of Cryptology,

vol. 4, no. 2, 1991.

21. PFITZMANN, B., and M. WAIDNER,Composition and Integrity Preservation of

Secure Reactive Systems, in 7th ACM Conference on Computer and Communica-

tions Security, 2000.

22. RICHARDSON, R. and J. KILIAN, On the Concurrent Composition of Zero-

Knowledge Proofs, in Advances in Cryptology - EUROCRYPT 99, Lecture Notes

in Computer Science, vol. 1592, Springer-Verlag, 1999.

23. SHOR, P., Algorithms for Quantum Computation: Discrete Logarithms and Fac-

toring, in 35th Annual Symposium on Foundations of Computer Science (FOCS),

1994.

24. WATROUS, J,PSPACE has Constant-Round Quantum Interactive Proof Systems,

in 40th Annual Symposium on Foundations of Computer Science (FOCS), 1999.

25. WATROUS, J.,Succinct Quantum Proofs for Properties of Finite Groups, Proceed-

ings of the 41st Annual Symposium on Foundations of Computer Science, 2000.

26. WATROUS, J., Limits on the Power of Quantum Statistical Zero-Knowledge, in

43rd Annual Symposium on the Foundations of Computer Science (FOCS), 2002.

27. VAN DE GRAAF, J., Towards a Formal Definition of Security for Quantum Pro-

tocols, Ph.D. thesis, Computer Science and Operational Research Department,

Universit© de Montr©al, 1997.

TEAM LinG

The Knowledge-of-Exponent Assumptions

and 3-Round Zero-Knowledge Protocols

Mihir Bellare and Adriana Palacio

Dept. of Computer Science & Engineering, University of California, San Diego

9500 Gilman Drive, La Jolla, CA 92093, USA

{mihir,apalacio}@cs.ucsd.edu

http://www-cse.ucsd.edu/users/{mihir,apalacio}

Abstract. Hada and Tanaka [11,12] showed the existence of 3-round,

negligible-error zero-knowledge arguments for NP based on a pair of

non-standard assumptions, here called KEA1 and KEA2. In this paper

we show that KEA2 is false. This renders vacuous the results of [11,

12]. We recover these results, however, under a suitably modified new

assumption called KEA3. What we believe is most interesting is that we

show that it is possible to “falsify” assumptions like KEA2 that, due to

their nature and quantifier-structure, do not lend themselves easily to

“efficient falsification” (Naor [15]).

1 Introduction

A classical question in the theory of zero knowledge (ZK) [10] is whether there

exist 3-round, negligible-error ZK proofs or arguments for NP. The difficulty in

answering this question stems from the fact that such protocols would have to

be non-black-box simulation ZK [9], and there are few approaches or techniques

to this end. A positive answer has, however, been provided, by Hada and Tanaka

[11,12]. Their result (a negligible-error, 3-round ZK argument for NP) requires

a pair of non-standard assumptions that we will denote by KEA1 and KEA2.

THE ASSUMPTIONS, ROUGHLY. Let be a prime such that is also prime,

and let be a generator of the order subgroup of Suppose we are given

input and want to output a pair (C, Y) such that One way to

do this is to pick some let and let Intuitively, KEA1

can be viewed as saying that this is the “only” way to produce such a pair. The

assumption captures this by saying that any adversary outputting such a pair

must “know” an exponent such that The formalization asks that there

be an “extractor” that can return Roughly:

KEA1: For any adversary A that takes input and returns (C, Y)

with there exists an “extractor” which given the same

inputs as A returns such that

Suppose we are given input and want to output a pair (C, Y )

such that One way to do this is to pick some let

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 273“289, 2004.

© International Association for Cryptologic Research 2004

TEAM LinG

274 Mihir Bellare and Adriana Palacio

and let Another way is to pick some let and let

Intuitively, KEA2 can be viewed as saying that these are the “only”

ways to produce such a pair. The assumption captures this by saying that any

adversary outputting such a pair must “know” an exponent such that either

or The formalization asks that there be an “extractor” that

can return Roughly:

KEA2: For any adversary A that takes input and returns

(C, Y) with there exists an “extractor” which given the

same inputs as A returns such that either or

As per [11,12], adversaries and extractors are poly-size families of (deterministic)

circuits. See Assumption 2 for a formalization of KEA2, and Assumption 4 for

a formalization of KEA1.

HISTORY AND NOMENCLATURE OF THE ASSUMPTIONS. KEA1 is due to Damgård

[7], and is used by [11,12] to prove their protocol is ZK. To prove soundness of

their protocol, Hada and Tanaka [11,12] introduce and use KEA2. (In addition,

they make the Discrete Logarithm Assumption, DLA.) The preliminary version

of their work [11] referred to the assumptions as SDHA1 and SDHA2 (Strong

Diffie-Hellman Assumptions 1 and 2), respectively. However, the full version

[12] points out that the formalizations in the preliminary version are flawed, and

provides corrected versions called non-uniform-DA1 and non-uniform-DA2. The

latter are the assumptions considered in this paper, but we use the terminol-

ogy of Naor [15] which we feel is more reflective of the content of the assump-

tion: “KEA” stands for “Knowledge of Exponent Assumption”, the exponent

being the value above.

FALSIFYING KEA2. In this paper we show that KEA2 is false. What is interest-

ing about this ”besides the fact that it renders the results of [11,12] vacuous”

is that we are able to “falsify” an assumption whose nature, as pointed out by

Naor [15], does not lend itself easily to “efficient falsification.” Let us explain

this issue before expanding more on the result itself.

The most standard format for an assumption is to ask that the probabil-

ity that an adversary produces a certain output on certain inputs is negligible.

For example, the Factoring assumption is of this type, asking that the probabil-

ity that a polynomial-time adversary can output the prime factors of an integer

(chosen by multipling a pair of random primes) is negligible. To show such an as-

sumption is false, we can present an “attack,” in the form of an adversary whose

success probability is not negligible. (For example, a polynomial-time factoring

algorithm.) KEA1 and KEA2 are not of this standard format. They involve a

more complex quantification: “For every adversary there exists an extractor such

that ...”. To show KEA2 is false, we must show there is an adversary for which

there exists no extractor. As we will see later, it is relatively simple to identify an

adversary for which there does not appear to exist an extractor, but how can we

actually show that none of the infinite number of possible extractors succeeds?

TEAM LinG

The Knowledge-of-Exponent Assumptions 275

AN ANALOGY. The difficulty of falsifying an assumption with the quantifier

format of KEA2 may be better appreciated via an analogy. The definition of

ZK has a similar quantifier format: “For every (cheating) verifier there exists

a simulator such that ...”. This makes it hard to show a protocol is not ZK,

for, even though we may be able to identify a cheating verifier strategy that

appears hard to simulate, it is not clear how we can actually show no simulator

exists. (For example, it is hard to imagine how one could find a simulator for the

cheating verifier, for Blum™s ZK proof of Hamiltonian Cycle [5], that produces its

challenges by hashing the permuted graphs sent by the prover in the first step.

But there is to date no proof that such a simulator does not exist). However it

has been possible to show protocols are not black-box simulation ZK [9], taking

advantage of the fact that the quantification in this definition is different from

that of ZK itself. It has also been possible to show conditional results, for example

that the parallel version of the Fiat-Shamir [8] protocol is not ZK, unless there is

no hash function that, when applied to collapse this protocol, results in a secure

signature scheme [16]. Our result too is conditional.

FALSIFICATION RESULT. At an intuitive level, the weakness in KEA2 is easy

to see, and indeed it is surprising this was not noted before. Namely, consider

an adversary A that on input picks in some fashion, and

outputs (C, Y) where and Then

but this adversary does not appear to “know” such that either or

The difficulty, however, as indicated above, is to prove that there

does not exist an extractor. We do this by first specifying a particular strategy

for choosing and and then showing that if there exists an extractor for

the resulting adversary, then this extractor can be used to solve the discrete

logarithm problem (DLP). Thus, our result (cf. Theorem 1) is that if the DLP

is hard then KEA2 is false. Note that if the DLP is easy, then KEA2 is true, for

the extractor can simply compute a discrete logarithm of C and output it, and

thus the assumption that it is hard is necessary to falsify KEA2.

REMARK. We emphasize that we have not found any weaknesses in KEA1, an

assumption used not only in [7,11,12] but also elsewhere.

KEA3. Providing a 3-round, negligible-error ZK protocol for NP is a challenging

problem that has attracted considerable research effort. The fact that KEA2 is

false means that we “lose” one of the only positive results [11,12] that we had

on this subject. Accordingly, we would like to “recover” it. To this end, we

propose a modification of KEA2 that addresses the weakness we found. The

new assumption is, roughly, as follows:

KEA3: For any adversary A that takes input and returns

(C, Y) with there exists an “extractor” which given

the same inputs as A returns such that

TEAM LinG

276 Mihir Bellare and Adriana Palacio

Before proceeding to use this assumption, we note a relation that we consider

interesting, namely, that KEA3 implies KEA1 (cf. Proposition 2)1. The relation

means that KEA3 is a natural extension of KEA1. It also allows us to simplify

result statements, assuming only KEA3 rather than both this assumption and

KEA1.

RECOVERING THE ZK RESULT. Let HTP denote the 3-round protocol of Hada

and Tanaka, which they claim to be sound (i.e., have negligible error) and ZK.

The falsity of KEA2 invalidates their proof of soundness. However, this does

not mean that HTP is not sound: perhaps it is and this could be proved under

another assumption, such as KEA3. This turns out to be almost, but not quite,

true. We identify a small bug in HTP based on which we can present a successful

cheating prover strategy, showing that HTP is not sound. This is easily fixed,

however, to yield a protocol we call pHTP (patched HTP). This protocol is

close enough to HTP that the proof of ZK (based on KEA1) is unchanged. On

the other hand, the proof of soundness of HTP provided in [12] extends with

very minor modifications to prove soundness of pHTP based on KEA3 and DLA

(cf. Theorem 2). In summary, assuming KEA3 and DLA, there exists a 3-round,

negligible error ZK argument for NP.

STRENGTH OF THE ASSUMPTIONS. The knowledge-of-exponent assumptions are

strong and non-standard ones, and have been criticized for assuming that one

can perform what some people call “reverse engineering” of an adversary. These

critiques are certainly valid. Our falsification of KEA2 does not provide infor-

mation on this aspect of the assumptions, uncovering, rather, other kinds of

problems. However, by showing that such assumptions can be falsified, we open

the door to further analyses.

We also stress that in recovering the result of [12] on 3-round ZK we have not

succeeded in weakening the assumptions on which it is based, for KEA3 certainly

remains a strong assumption of the same non-standard nature as KEA1.

RELATED WORK. Since [11,12] there has been more progress with regard to the

design of non-black-box simulation ZK protocols [1]. However, this work does

not provide a 3-round, negligible-error ZK protocol for NP. To date, there have

been only two positive results. One is that of [11,12], broken and recovered in

this paper. The other, which builds a proof system rather than an argument, is

reported in [14] and further documented in [13]. It also relies on non-standard

assumptions, but different from the Knowledge of Exponent type ones. Roughly,

they assume the existence of a hash function such that a certain discrete-log-

based protocol, that uses this hash function and is related to the non-interactive

OT of [3], is a proof of knowledge.

1

KEA2 was not shown by [12] to imply KEA1. Our proof of Proposition 2 does extend

to establish it, but the point is moot since KEA2 is false and hence of course implies

everything anyway.

TEAM LinG

The Knowledge-of-Exponent Assumptions 277

2 Preliminaries

If is a binary string, then denotes its length, and if is an integer, then

denotes the length of its binary encoding, meaning the unique integer such

that The empty string is denoted We let be the

set of positive integers. If is a prime number such that is also prime, then

we denote by the subgroup of quadratic residues of (Operations are

modulo but we will omit writing for simplicity.) Recall this is

a cyclic subgroup of order If is a generator of then we let

denote the associated discrete logarithm function, meaning

for any We let

are primes and is a generator of

For any we let be the set of all such that the length of

the binary representation of is bits, i.e.,

Assumptions and problems in [11,12] involve circuits. A family of circuits

contains one circuit for each value of It is poly-size if there is

a polynomial such that the size of is at most for all Unless

otherwise stated, circuits are deterministic. If they are randomized, we will say

so explicitly. We now recall the DLA following [12].

Assumption 1. [DLA] Let be a family of randomized circuits,

and v: a function. We associate to any and any

the following experiment:

Experiment

If then return 1 else return 0

We let

denote the advantage of I on inputs the probability being over the random

choice of and the coins of if any. We say that I has success bound v if

We say that the Discrete Logarithm Assumption (DLA) holds if for every poly-

size family of circuits I there exists a negligible function v such that I has success

bound v.

The above formulation of the DLA, which, as we have indicated, follows [12], has

some non-standard features that are important for their results. Let us discuss

these briefly.

First, we note that the definition of the success bound is not with respect

to being chosen according to some distribution as is standard, but rather

makes the stronger requirement that the advantage of I is small for all

TEAM LinG

278 Mihir Bellare and Adriana Palacio

Second, we stress that the assumption only requires poly-size families of de-

terministic circuits to have a negligible success bound. However, in their proofs,

which aim to contradict the DLA, Hada and Tanaka [11,12] build adversaries

that are poly-size families of randomized circuits, and then argue that these can

be converted to related poly-size families of deterministic circuits that do not

have a negligible success bound. We will also need to build such randomized

adversaries, but, rather than using ad hoc conversion arguments repeated across

proofs, we note the following more general Proposition, which simply says that

DLA, as per Assumption 1, implies that poly-size families of randomized circuits

also have a negligible success bound. We will appeal to this in several later places

in this paper.

Proposition 1. Assume the DLA, and let be a poly-size family

of randomized circuits. Then there exists a negligible function v such that J has

success bound v.

As is typical in such claims, the proof proceeds by showing that for every there

exists a “good” choice of coins for and by embedding these coins we get a

deterministic circuit. For completeness, we provide the proof in the full version

of this paper [4].

3 KEA2 Is False

We begin by recalling the assumption. Our presentation is slightly different from,

but clearly equivalent to, that of [12]: we have merged the two separate condi-

tions of their formalization into one. Recall that they refer to this assumption

as “non-uniform-DA2,” and it was referred to, under a different and incorrect

formalization, as SDHA2 in [11].

Assumption 2. [KEA2] Let and be families of

circuits, and a function. We associate to any any

and any the following experiment:

Experiment

If AND AND then return 1 else return 0

We let

denote the advantage of A relative to on inputs A. We say that is a

kea2-extractor for A with error bound v if

We say that KEA2 holds if for every poly-size family of circuits A there exists

a poly-size family of circuits and a negligible function v such that is a

kea2-extractor for A with error bound v.

TEAM LinG

279

The Knowledge-of-Exponent Assumptions

We stress again that in the above formulations, following [12], both the adversary

and the extractor are families of deterministic circuits. One can consider various

variants of the assumptions, including an extension to families of randomized

ciruits, and we discuss these variants following the theorem below.

Theorem 1. If the DLA holds then KEA2 is false.

The basic idea behind the failure of the assumption, as sketched in Section 1,

is simple. Consider an adversary given input A,B,X, where

and The assumption says that there are only two ways for the

adversary to output a pair C, Y satisfying One way is to pick some

let and let The other way is to pick some let and

let The assumption thus states that the adversary “knows” c such that

either (i.e., or (i.e., This

ignores the possibility of performing a linear combination of the two steps above.

In other words, an adversary might pick let and

In this case, but the adversary does not appear to necessarily know

or

However, going from this intuition to an actual proof that the assumption

is false takes some work, for several reasons. The above may be intuition that

there exists an adversary for which there would not exist an extractor, but we

need to prove that there is no extractor. This cannot be done unconditionally,

since certainly if the discrete logarithm problem (DLP) is easy, then in fact there

is an extractor: it simply computes and returns it. Accordingly, our

strategy will be to present an adversary A for which we can prove that if there

exists an extractor then there is a method to efficiently compute the discrete

logarithm of A.

An issue in implementing this is that the natural adversary A arising from

the above intuition is randomized, picking at random and forming C, Y as

indicated, but our adversaries must be deterministic. We resolve this by designing

an adversary that makes certain specific choices of We now proceed to the

formal proof.

PROOF OF THEOREM 1. Assume to the contrary that KEA2 is true. We show

that the DLP is easy.

The outline of the proof is as follows. We first construct an adversary A

for the KEA2 problem. By assumption, there exists for it an extractor with

negligible error bound. Using we then present a poly-size family of randomized

circuits and show that it does not have a negligible success bound.

By Proposition 1, this contradicts the DLA.

The poly-size family of circuits is presented in Figure 1. Now,

under KEA2, there exists a poly-size family of circuits and a

negligible function v such that is an extractor for A with error bound v. Using

we define the poly-size family of circuits shown in Figure 1.

Claim 1. For all all and all

TEAM LinG

280 Mihir Bellare and Adriana Palacio

Fig. 1. Adversary for the KEA2 problem and adversary

for the DLP, for the proof of Theorem 1.

Note the claim shows much more than we need. Namely, J does not merely have

a success bound that is not negligible. In fact, it succeeds with probability almost

one.

Proof (Claim 1). We let Pr[·] denote the probability in the experiment of exe-

cuting We first write some inequalities leading to the claim and then

justify them:

We justify Equation (1) by showing that if or then First

assume Since we have whence Since we

set we have Next assume Since

we have whence Now observe that because otherwise

(Since is a generator, it is not equal to 1). Since and is

prime, has an inverse modulo which we have denoted by Raising both

sides of the equation to the power we get

returns 1 exactly when and and

By construction of A, we have and Y = BX, and thus so

returns 1 exactly when and This justifies

Equation (2).

Equation (3) is justified by the assumption that is an extractor for A with

error bound v.

Claim 1 implies that J does not have a negligible success bound, which, by

Proposition 1, shows that the DLP is not hard, contradicting the assumption

made in this Theorem. This completes the proof of Theorem 1.

EXTENSIONS AND VARIANTS. There are many ways in which the formalization

of Assumption 2 can be varied to capture the same basic intuition. However,

Theorem 1 extends to these variants as well. Let us discuss this briefly.

TEAM LinG

The Knowledge-of-Exponent Assumptions 281

As mentioned above, we might want to allow the adversary to be randomized.

(In that case, it is important that the extractor get the coins of the adversary as

an additional input, since otherwise the assumption is clearly false.) Theorem 1

remains true for the resulting assumption, in particular because it is stronger

than the original assumption. (Note however that the proof of the theorem would

be easier for this stronger assumption.)

Another variant is that adversaries and extractors are uniform, namely stan-

dard algorithms, not circuits. (In this case we should certainly allow both to

be randomized, and should again give the extractor the coins of the adversary.)

Again, it is easy to see that Theorem 1 extends to show that the assumption

remains false.

4 The KEA3 Assumption

The obvious fix to KEA2 is to take into account the possibility of linear combi-

nations by saying this is the only thing the adversary can do. This leads to the

following.

Assumption 3. [KEA3] Let and be families of

circuits, and v: a function. We associate to any any

and any the following experiment:

Experiment

If then return 1 else return 0

We let

denote the advantage of A relative to on inputs A. We say that is a

kea3-extractor for A with error bound v if

We say that KEA3 holds if for every poly-size family of circuits A there exists

a poly-size family of circuits and a negligible function v such that is a

kea3-extractor for A with error bound v.

We have formulated this assumption in the style of the formalization of KEA2

of [12] given in Assumption 2. Naturally, variants such as discussed above are

possible. Namely, we could strengthen the assumption to allow the adversary

to be a family of randomized circuits, of course then giving the extractor the

adversary™s coins as an additional input. We do not do this because we do not

need it for what follows. We could also formulate a uniform-complexity version

of the assumption. We do not do this because it does not suffice to prove the

results that follow. However, these extensions or variations might be useful in

other contexts.

TEAM LinG

282 Mihir Bellare and Adriana Palacio

In Appendix A we recall the formalization of KEA1 and prove the following:

Proposition 2. KEA3 implies KEA1.

This indicates that KEA3 is a natural extension of KEA1.

5 Three-Round Zero Knowledge

The falsity of KEA2 renders vacuous the result of [11,12] saying that there

exists a negligible-error, 3-round ZK argument for NP. In this section we look

at recovering this result.

We first consider the protocol of [11,12], here called HTP. What has been

lost is the proof of soundness (i.e., of negligible error). The simplest thing one

could hope for is to re-prove soundness of HTP under KEA3 without modifying

the protocol. However, we identify a bug in HTP that renders it unsound. This

bug has nothing to do with the assumptions on which the proof of soundness

was or can be based.

The bug is, however, small and easily fixed. We consider a modified protocol

which we call pHTP. We are able to show it is sound (i.e., has negligible error)

under KEA3. Since we have modified the protocol we need to re-establish ZK

under KEA1 as well, but this is easily done.

ARGUMENTS. We begin by recalling some definitions. An argument for an NP

language L [6] is a two-party protocol in which a polynomial-time prover tries

to “convince” a polynomial-time verifier that their common input belongs to

L. (A party is said to be polynomial time if its running time is polynomial in

the length of the common input.) In addition to the prover has an auxiliary

input The protocol is a message exchange at the end of which the verifier

outputs a bit indicating its decision to accept or reject. The probability (over

the coin tosses of both parties) that the verifier accepts is denoted

The formal definition follows.

Definition 1. A two-party protocol (P, V), where P and V are both polynomial

time, is an argument for L with error probability if the following

conditions are satisfied:

COMPLETENESS: For all there exists such that

SOUNDNESS: For all probabilistic polynomial-time algorithms all sufficiently

long and all

We say (P, V) is a negligible-error argument for L if there exists a negligible func-

tion such that (P, V) is an argument for L with error probability

CANONICAL PROTOCOLS. The 3-round protocol proposed by [11,12], which we

call HTP, is based on a 3-round argument for an NP-complete language

L with the following properties:

TEAM LinG

The Knowledge-of-Exponent Assumptions 283

Fig. 2. A 3-round argument. The common input is Prover has auxiliary input

and random tape R, and maintains state St. Verifier V returns boolean decision

(1) The protocol is of the form depicted in Figure 2. The prover is identified with

a function that given an incoming message (this is when the prover is

initiating the protocol) and its current state St, returns an outgoing message

and an updated state. The initial state of the prover is where

is the common input, is an auxiliary input and R is a random tape. The

prover™s first message is called its commitment. This is a tuple consisting of

a string CMT, a prime number and an element where

The verifier selects a challenge CH uniformly at random from and, upon

receiving a response Rsp from the prover, applies a deterministic decision

predicate CH, RSP) to compute a boolean decision.