. 9
( 19)


use the signature of a commitment of as witness for the third round of the
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.

We would like to thank the anonymous referee for his/her very useful remarks
on our submission.

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

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

Zero-Knowledge Proofs and String
Commitments Withstanding Quantum Attacks

Ivan Damgård1, Serge Fehr2,*, and Louis Salvail1
BRICS, FICS, Aarhus University, Denmark**
CWI, Amsterdam, The Netherlands

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
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.

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

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
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
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
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
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,
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-
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
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
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
Depending on its flavor, a trapdoor commitment scheme is also known as an ex-
tractable respectively as an equivocable or a chameleon commitment scheme.
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
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

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.
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.

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
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-

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
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
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-
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
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:

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

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

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
Finally, P measures register P in
pairs by running the inverse of
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
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
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
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
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.

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.

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-
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
Knowledge, JCSS, 37(2), 1988.
BLUM, M., P. FELDMAN and S. MICALI, Non-Interactive Zero-Knowledge and
Its Applications, in 20th Annual Symposium on Theory Of Computing (STOC),
CANETTI, R., Universally Composable Security: A New Paradigm for Crypto-
graphic Protocols, in 42th Annual Symposium on Foundations of Computer Sci-
ence (FOCS), 2001.
CANETTI, R., and M. FISCHLIN, Universally Composable Commitments, in Ad-
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
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
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
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-
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
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
Commitment From Any Quantum One-Way Permutation, in Advances in Cryp-
tology - EUROCRYPT 00, Lecture Notes in Computer Science, vol. 1807,
Springer-Verlag, 2000.

Ivan Damgård, Serge Fehr, and Louis Salvail

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,
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),
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.

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

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
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.
[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?

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

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
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.

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.

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:
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
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:

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.
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
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

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
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.
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
Assumption 3. [KEA3] Let and be families of
circuits, and v: a function. We associate to any any
and any the following 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.
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:
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.


. 9
( 19)