IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.8 AUGUST 2012

1390

PAPER

A Constant-Round Resettably-Sound Resettable Zero-Knowledge
Argument in the BPK Model
Seiko ARITA†a) , Member

SUMMARY
In resetting attacks against a proof system, a prover or averifier is reset and enforced to use the same random tape on various inputs
as many times as an adversary may want. Recent deployment of cloudcomputing gives these attacks a new importance. This paper shows thatargument systems for any NP language that are both resettably-sound andresettable zero-knowledge are possible by a constant-round protocol in the
BPK model. For that sake, we define and construct a resettably-extractableconditional commitment scheme.
key words: resettable zero-knowledge, resettable soundness, conditional
commitment, resettably extractable

1.

Introduction(1)

Resettable zero-knowledge proofs.

The notion of resettable zero-knowledge of proof systems
was proposed by Canetti, Goldreich, Goldwasser and Micali [4]. It requires that proofs be zero-knowledge even if aprover is reset and enforced to use the same random tape on
various inputs as many times as an adversarial verifier may
want. This resetting attack is motivated by attacks against
smart cards, where a stolen card can be reset as many times
as an attacker wants. Recent deployment of cloud computing gives the notion new importance, because virtual machines in a cloud are far more easier for adversaries to reset
than real machines in the user’s perimeter [10], [13], [14].
[4] shows that assuming the existence of 2-roundperfectly-hiding commitments, there exist resettable zeroknowledge proofs with a polynomial number of rounds for
all NP languages. Later, the round complexity is improved
to poly-logarithmic number by Kilian and Petrank [11].
[4] also presented the notion of the bare public key(BPK) model. The only requirement in the BPK model isthat all verifiers deposit some public-key in a public file
before the prover begins the interaction. They constructed
constant-round resettable zero-knowledge arguments in the
BPK model, assuming some sub-exponential hardness assumption.
(2)

Resettably-soundness.

Barak, Goldreich, Goldwasser and Lindell [3] proposed thenotion of resettably-soundness, the dual notion of resettablezero-knowledge. It requires that proofs be sound even if a
verifier is reset and enforced to use the same random tape on
Manuscript received March 22, 2012.
The author is with Institute of Information Security,
Yokohama-shi, 221-0835 Japan.
a) E-mail: arita@iisec.ac.jp
DOI: 10.1587/transfun.E95.A.1390†

various inputs as many times as an adversarial prover may
want. Resettably-sound zero-knowledge proofs exist only
for languages in non-uniform P. Even for arguments noresettably-sound zero-knowledge arguments exist for language outside BPP if the simulator is black-box.
[3] constructed a constant-round resettably-sound zeroknowledge argument for NP only assuming collisionresistant hash functions. In the construction, the Barak’s
non-black-box constant-round zero-knowledge argument[1], especially the fact that it has only constant-round, plays
the essential role.
By utilizing that resettably-sound zero-knowledge argument, [3] also constructed a constant-round sequentiallysound resettable zero-knowledge argument in the BPK
model. (We note that soundness in the BPK model is divided
into four subcategories; stand-alone, sequential, concurrent
and resettable soundness [12].)(3)

Resettably-sound resettable zero-knowledge argument.

How about simultaneous resettability ? Crescenzo, Persiano
and Visconti [5] showed that a constant-round concurrentsound resettable zero-knowledge argument is possible in
the BPK model assuming some sub-exponential hardness
assumption. Moreover, Deng and Lin [8] constructed aconstant-round concurrent-sound resettable ZK argument in
the BPK model only assuming collision resistant (against
polynomial-time adversaries) hash functions.
In the plain model, Deng and Lin [7] showed that
if there exist public-coin concurrent zero knowledge arguments for NP, then there exist resettably-sound resettablezero knowledge arguments for NP. However, it is not known
whether there exist public-coin concurrent zero knowledge
arguments for NP.
Recently, Deng, Goyal and Sahai [6] gave a breakthrough. They gave a new non-back-box strategy based on
the Barak’s simulator and showed that there exists a both
resettably-sound and resettable zero-knowledge argument
system for all languages in NP in the plain model, assuming trapdoor permutations and collision-resistant hash function families. Its round-complexity is square in the security
parameter.
Table 1 gives the summary of related proof/argument
systems.
(4)

Our contribution.

This paper gives the first constant-round argument sys-c 2012 The Institute of Electronics, Information and Communication Engineers
Copyright ARITA: A CONSTANT-ROUND RESETTABLY-SOUND RESETTABLE ZERO-KNOWLEDGE ARGUMENT IN THE BPK MODEL

1391
Table 1 Summary of related proof/argument systems. In the table, rZKP
or rZKA denotes a resettable zero-knowledge proof or argument system,
respectively. ss , cs or rs for “sequentially sound”, “concurrently sound”
or “resettably sound”, respectively.
Reference

SystemRoundsModel

Canetti et al. [4]Kilian and Petrank [11]Canetti et al. [4]Barak et al. [3]Barak et al. [3]Crescenzo et al. [5]Deng and Lin [8]Deng et al. [6]
Ours

rZKP
rZKP
rZKA
rs ZKA
ss rZKA
cs rZKA
cs rZKA
rs rZKA
rs rZKA

polynomial
poly-log
constant
constant
constant
constant
constantsquareconstant

plain
plain
BPK
plain
BPK
BPK
BPK
plain
BPK

tem for all NP languages in the BPK model that is both
resettably-sound and resettable zero-knowledge.
To realize both resettably-sound and resettable zeroknowledge argument system, we also rely on the Feige andShamir paradigm (as [5], [6], [8]). First, Verifier proves toProver that he knows some secret s (about his public key),by using zero-knowledge AoK (Argument of Knowledge).
Then, Prover proves to Verifier that he knows a witness w
to the statement x to be proved or knows that secret s, also
by using zero-knowledge AoK. Since s is known only to
Verifier, Verifier is convinced that Prover should know thewitness w and the statement x is true.
To prove zero-knowledge or soundness property ofsuch scheme, the point is in the use of knowledge extractorsof the two AoKs. In the proof of zero-knowledge property,
a prover-simulator extracts the secret s from the first AoK.
Then this s is used as a fake witness by the prover-simulator
in the second AoK. On a while, in the proof of soundness,a verifier-simulator extracts another secret s from the second AoK claimed by a hypothetical cheating prover. This
leads to some contradiction to assumed security of secretkeys in the BPK model. (This is why the Feige and Shamirparadigm requires the second proof also to be AoK in thecase of BPK model as well as the first proof. In the caseof plain model, it is possible that the second proof is just a
membership proof.)
Here, we recall that we are in a resettable situation.
Such extractors must extract some knowledge even if theyreceive resetting operations. Those resetting operations
bring serious problem to the strategy of extractors: ordinal
rewinding strategy causes contradictions in the simulated
adversary’s view, because many messages in diﬀerent sessions have related randomness in a resettable situation.
We need to provide “resettable-extractors” for the two
AoKs that tolerate resetting operations and enable to extract
secrets even in resetting situation. ([6] derives a new rewinding strategy that works and tolerates resetting operations in
the plain model, but it requires square-round complexity.)
For the first AoK, since we are in the BPK model,
the diﬃculty turns out to be some technical one (and we
can keep constant-round). However, for the second AoK in
which the statement to be proved involves the original statement x, the diﬃculty is essential. To sanitize resetting op-

erations in the second AoK, we define and construct a newvariant of commitment scheme, resettably-extractable conditional commitment scheme. In the commitment scheme, areceiver-simulator can extract the cheating sender’s commitment value even if receiving resetting operations at arbitrary
moments under some “condition”. By using the resettablyextractable conditional commitment scheme plugged into
the second AoK, a verifier-simulator can extract knowledge
from a cheating prover even if receiving resetting operations at arbitrary moments also under some “condition”.
We will see the introduction of such “condition” enables us
to use ZAPs (two-round public-coin witness indistinguishable proof [9]) eﬀectively to control adversary’s behavior
with respect to its use of randomness, resulting sanitizationof its resetting operations. Then we will see that depending on such “condition” can be justified and will arrive at aconstant-round resettably-sound resettable zero-knowledge
argument in the BPK model.
2.

DefinitionsFirst, we recall some definitions regarding security against
resetting attacks, following [3], [4].
Let (P, V) be an interactive proof or argument system for an NP-language L. We denote the possible number of sessions between P and V as t = poly(n). Let [t]denote a range {1, 2, . . . , t}. We denote statements to be
proved as x = (x1 , . . . , xt ) with their corresponding witnesses y = (y1 , . . . , yt ) (each yi witnesses xi ∈ L).
2.1 Resetting Attack by Cheating Verifiers
A resetting attack by a cheating verifier V ∗ goes as follows.
1. We choose t independent random tapes ω1 , . . . , ωt .
(These random tapes are supposed to be used in thecorresponding independent concurrent sessions by anhonest prover P, each of which can be reset by a cheating verifier V ∗ .) For i ∈ [t] and j ∈ [t], let P(i, j) :=P(xi , yi ; ω j ) denote a prover on input a statement xi , its
witness yi and a random tape ω j . We call each P(i, j) an
incarnation of prover P.
2. A cheating verifier V ∗ performs a polynomial numberof sessions with the incarnations P(i, j) in a sequential
manner. Here, V ∗ can adaptively select which incarnation P(i, j) it has a session with. Incarnations P(∗, j) thatshares same j can be selected many times. (This models the resetting operations by V ∗ .)3. V ∗ halts with an output based on its view. We denotethe output as (P(x, y), V ∗ (x)).
Definition 1 (resettable WI) An interactive proof or argument system (P, V) for an NP language L is said to be resettable witness indistinguishable, if the following two ensemble are computationally indistinguishable in all resetting attacks by arbitrary feasible cheating verifier V ∗ :• {(P(x, y1 ), V ∗ (x))}(x,y1 ,y2 ) ,IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.8 AUGUST 20121392

• {(P(x, y2 ), V ∗ (x))}(x,y1 ,y2 ) .

• Verifier V, at the first stage, generates its key pair
(pk, sk) and records the public key pk in the public file
F. Then, at the second stage, V receives a statementx, its secret key sk and its random tape w as inputs andperforms the protocol with P, resulting in an output of
accept or reject.

Here, both y = (y1i ) and y2 = (y2i ) are sets of witnesses for
x = (xi ) to be xi ∈ L.
1

Definition 2 (resettable ZK) An interactive proof or argument system (P, V) for an NP language L is said to be resettable zero-knowledge, if for any feasible cheating verifierV ∗ in a resetting attack there exists a feasible simulator M
and the following two ensemble are computationally indistinguishable :• {(P(x, y), V ∗ (x))}(x,y) ,• {M(x)}(x,y) .
Here, y = (yi ) is a set of witnesses for x = (xi ) to be xi ∈ L.
2.2 Resetting Attack by Cheating Provers
A resetting attack by a cheating prover P∗ goes as follows.
1. We choose t independent random tapes ω1 , . . . , ωt .
(These random tapes are supposed to be used in the corresponding independent concurrent sessions by an honest verifier V, each of which can be reset by a cheating
prover P∗ .) For j ∈ [t], let V( j) (x) := V(x; ω j ) denotea verifier on input a statement x and a random tape ω j .
We call each V( j) (x) an incarnation of verifier V.
2. A cheating prover P∗ performs a polynomial numberof sessions with the incarnations V( j) (x) in a sequential manner. P∗ can adaptively select a statement x (notnecessary in L) to be proved and which incarnation V( j)it has a session with. Same incarnation V( j) can be selected many times on various statements x. (This models the resetting operations by P∗ .)Definition 3 (resettably-sound) An interactive proof or argument system (P, V) for an NP language L is said to beresettably-sound if for any feasible cheating prover P∗ ina resetting attack, the probability that some incarnation
V( j) (x) accepts a false statement x ( L) in some session invoked by P∗ is negligible.

3.

Known Constructions

Here, we briefly review what is known about constant-roundresettable arguments and constant-round resettably-soundarguments.
3.1 Constant-Round Resettable Arguments
By using the resettably-sound zero-knowledge argument (asseen below), it is shown that there exists a constant-round resettable witness-indistinguishable argument of knowledge,
assuming the existence of collision-resistant hash functions(in the plain model) [3].
In the BPK model, there exists a constant-round(concurrent-sound) resettable zero-knowledge argument for
all NP languages, assuming collision-resistant hash functions [8].
3.2 Constant-Round Resettably-Sound Arguments
Every constant-round public-coin argument can be converted to a resettably-sound version, preserving prover’s
property such as witness-indistinguishability and zeroknowledge [3].
It is known that there exists a constant-roundpublic-coin witness-indistinguishable argument (or zeroknowledge argument) for all NP languages assuming oneway functions (or collision-resistant hash-functions [1]).
Especially, we know that in the plain model:• there exists a constant-round resettably-sound witnessindistinguishable argument assuming one-way functions, and• there exists a constant-round resettably-sound zeroknowledge argument assuming collision-resistant hashfunctions.

2.3 The BPK Model
The BPK (bare public key) model is a kind of setup assumption for proof systems proposed by [4], aiming to make iteasier to construct a simulator for concurrent or resettablezero-knowledge proof systems.
The only requirement in the BPK model is that all verifiers deposit their public-keys in a public file before any
interaction occurs. That is,• A public file F is a collection of records, each of which
is a pair of an index and a public key of a verifier.
• Prover P receives as inputs a statement x, its witness y,a random tape r and the public file F with a verifier’s
index.

4.

Resettably-Extractable Conditional Commitment

Now, we introduce a new variant of commitment scheme,
conditional commitment scheme.
Then we see that
resettably-extractable conditional commitments are possible by a constant-round protocol in the plain model.
4.1 Conditional Commitment
In a conditional commitment scheme, a sender takes a condition x as input in addition to a string v to be committed. For
some given language L, hiding property of conditional commitment is guaranteed only if its condition x is in L, and its

ARITA: A CONSTANT-ROUND RESETTABLY-SOUND RESETTABLE ZERO-KNOWLEDGE ARGUMENT IN THE BPK MODEL

1393

binding property is assured only if its condition x is outsidefrom L.
More precisely, it is defined as follows. (In the sequel,
notation (y1 , y2 ) ← (P1 (x1 ), P2 (x2 )) means that by running
an interactive protocol (P1 , P2 ) on input x1 for P1 and x2
for P2 , parties P1 and P2 obtains local outputs y1 and y2 ,respectively.)
Definition 4 (Conditional commitment) A pair of interactive eﬃcient algorithms (S , R) is said to be conditional commitment scheme with respect to a language L if the following three conditions are satisfied : (In the below, “(o1 , o2 ) ←(P1 , P2 )” means that party Pi gets a local output oi by running the protocol (i = 1, 2). When oi is “-”, it denotes that anull output is gotten by an honest party, or that an output of
which we do not care is gotten by a cheating party.)• (Correctness) For any v ∈ {0, 1}n and any x ∈ {0, 1}n , itholds that
Pr[ (d, c) ← (S (v, x), R(x)),(−, v ) ← (S (d), R(c)): v = v ] = 1.
• (Conditional Hiding) For any non-uniform eﬃcientcheating receiver R∗ and any x ∈ L ∩ {0, 1}n , it holdsthat
Pr[ (v0 , v1 , s) ← R∗ (x),b ← {0, 1},(−, b ) ← (S (vb , x), R∗ (s)): b = b ] ≤ 1/2 + negl(n).
• (Conditional Binding) For any eﬃcient cheating senderS ∗ and any x ∈ {0, 1}n that is not in L, it holds that
Pr[ ((d1 , d2 ), c) ← (S ∗ (x), R(x)),(−, v1 ) ← (S ∗ (d1 ), R(c)),(−, v2 ) ← (S ∗ (d2 ), R(c)): v1  ⊥, v2  ⊥, v1  v2 ]≤ negl(n).
4.2 Resettable-Extractability
Our motivation for introducing conditional commitment
is in enabling resettably-extractable commitment. The
resettably-extractable conditional commitment scheme demands that there should be a simulator which can extract
a value committed to even by a cheating sender who canmount a resetting attack against a victim receiver, under theconstraint that the adversarial commitment is made with respect to the condition x that is not in language L.
First, we define a resetting attack for conditional commitment schemes. For a conditional commitment scheme(S , R), a resetting attack by a cheating sender S ∗ goes as follows. (In our argument system in Sect. 5, we use conditional

commitment schemes without using explicit decommitment
phases. So, in the following definition it is suﬃcient to deal
with only commitment phases.)
1. We choose t independent random tapes ω1 , . . . , ωt .
(These random tapes are supposed to be used in the corresponding independent concurrent sessions by an honest receiver R, each of which can be reset by a cheating
sender S ∗ .) For j ∈ [t], let R( j) := R(ω j ) denote anhonest receiver on input random tape ω j . We call eachR( j) an incarnation of receiver R.
2. A cheating sender S ∗ performs a polynomial number ofsessions, composed of only commitment phases, with
the incarnations R( j) in a sequential manner with respect to some conditions. Here, S ∗ is supposed to beable to adaptively select a value v and a condition x
for commitments and is supposed to be able to choose
which incarnation R( j) it has a session with. Same incarnation R( j) can be selected many times on various
values v and conditions x. (This models the resetting
operations by S ∗ .)Definition 5 (Resettable-extractability) A
conditional
commitment scheme (S , R) with respect to language L is
said to be resettably-extractable if for every feasible cheating sender S ∗ mounting a resetting attack against an honest
receiver R there exists a feasible resettable-extractor E with
output(view, value) ← E(1n ),satisfying that
1. the output view is computationally indistinguishable
from the real view of S ∗ , and2. the output value contains one of the committed values
by S ∗ with respect to some condition x that is not in
L in the simulated view view of S ∗ with a noticeable
probability 1/poly(n) (if such a terminated commitment
with condition outside of L exists).
4.3 Construction of Resettably-Extractable Conditional
Commitment Scheme
Our construction of resettably-extractable conditional commitment scheme is based on the commit-with-extract commitment scheme of Barak [2], that is designed to enable astraight-line extractor of strict polynomial time.
We enhances the Barak’s commitment scheme so as tobe extractable even against a cheating sender who can perform a resetting attack to a victim receiver, as follows.
Protocol 1• Building Blocks:– an NP language L,– a pseudorandom function F,– a trapdoor permutation f with a hardcore predicate h,

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.8 AUGUST 20121394

– a (computationally-hiding statistically-binding)
non-interactive commitment scheme Com,– a ZAP (two-round public-coin witness indistinguishable proof [9]) and– a (stand-alone) constant-round zero-knowledge
argument.
• Input for sender S : a condition x (∈ {0, 1} ), a value
v (∈ {0, 1}n ) and a random tape ωS .
• Input for receiver R : a condition x and a random tapeωR .
• The Protocol (Commitment Phase) :n

1. S → R : S selects a trapdoor permutation f witha hardcore predicate h and commits to its randomtape ωS : cS ← Com(ωS ). S sends f, cS to R.
2. S ← R : R computes ω∗R = FωR (x, f, cS ). (Fromnow on to the end of the protocol, R uses ω∗R as its
random tape instead of ωR .) R selects a random
string r2 of length n2 and commits to it : c2 ←Com(r2 ). R generates a first-round message σR ofa ZAP. R sends c2 , σR to S .
3. S → R : S selects a random string r1 of length n2and sends to R the string r1 attached with a ZAP
showing that “r1 is taken from ωS (that is committed to under cS ), or x ∈ L.” If the attached ZAP isinvalid, R aborts the protocol immediately.
4. S ← R : R sends r2 to S .
5. S ⇐ R : R proves to S using the zero-knowledge
argument that “there exists a w satisfying c2 =Com(r2 ; w),” where– every S ’s message (as a verifier) is coupledwith a ZAP claiming that “the sent message
is computed using ωS as a random tape according to the protocol, or x ∈ L.” If anyof the attached ZAPs is invalid, R aborts the
protocol.
6. S → R : (If R’s proof is valid) S computes(r1 , . . . , rn ) = r = r1 ⊕ r2 and takes those inverses
si = f −1 (ri ) for i = 1 to n. S computes and sends
C = (v1 ⊕ h(s1 ), . . . , vn ⊕ h(sn )) to R.
• The Protocol (Decommitment Phase) :1. S → R : S sends s = (s1 , . . . , sn ) and v =(v1 , . . . , vn ) to R.
2. R : R checks whether ri = f (si ) for all i = 1 to n
and whether C = (v1 ⊕ h(s1 ), . . . , vn ⊕ h(sn )) or not.
If all of the equations hold R outputs v, otherwise
outputs ⊥.
Theorem 1 Under the assumption that the primitives described in Building Blocks exist, Protocol 1 is resettablyextractable conditional commitment scheme.
Proof of conditional hiding:
The hiding property of Protocol 1 is inherited from thehiding property of the commit-with-extract commitment

scheme of Barak [2]. First we review the Barak’s commitment scheme (S  , R ) (in a slightly changed form (in an
unessential way) for our purpose):• Building Blocks:– a trapdoor permutation f with a hardcore predicate h,– a (computationally-hiding statistically-binding)
non-interactive commitment scheme Com and– a (stand-alone) constant-round zero-knowledge
argument.
• Input for sender S  : a value v (∈ {0, 1}n ).
• Input for receiver R : a security parameter 1n .
• The Protocol (Commitment Phase) :1. S  → R : S  selects a trapdoor permutation fwith a hardcore predicate h. S  sends f to R .
2. S  ← R : R selects a random string r2 of lengthn2 and commits to it : c2 ← Com(r2 ). R sends c2
to S  .
3. S  → R : S  selects a random string r1 of lengthn2 . S  sends r1 to R .
4. S  ← R : R sends r2 to S  .
5. S  ⇐ R : R proves to S  using the zeroknowledge argument that “there exists a w satisfying c2 = Com(r2 ; w).”
6. S  → R : S  computes (r1 , . . . , rn ) = r = r1 ⊕ r2
and takes those inverses si = f −1 (ri ) for i = 1 to n.
S  computes and sends C = (v1 ⊕ h(s1 ), . . . , vn ⊕h(sn )) to R .
• The Protocol (Decommitment Phase) :1. S  → R : S  sends s = (s1 , . . . , sn ) and v =(v1 , . . . , vn ) to R .
2. R : R checks whether ri = f (si ) for all i = 1 to n
and whether C = (v1 ⊕ h(s1 ), . . . , vn ⊕ h(sn )) or not.
If all of the equations hold R outputs v, otherwise
outputs ⊥.
Suppose some eﬃcient cheating receiver R∗ breaks thehiding property of Protocol 1 on some condition x ∈ L.
We construct a non-uniform eﬃcient cheating receiver (R )∗that breaks the hiding property of the Barak’s commitment
scheme (S  , R ) as follows.
Cheating receiver (R )∗ on auxiliary input x and w (w is awitness to x ∈ L) works as follows :• Invoke a copy of R∗ and receive its challenge v0 , v1 .
Send v0 , v1 as its own challenge to its challenger S  .
• Receiving f from S  , commit to a dummy string (ofsuﬃcient length) : cS ← Com(0∗ ). Send cS , f to theinternal R∗ .
• Receiving c2 , σR from R∗ , forward c2 to S  .
• Receiving r1 from S  , forward it to R∗ , appending to it
the corresponding ZAP computed from the witness w(instead of the random tape of S  ).
• Receiving r2 from R∗ , forward it to S  . Then, relay the

ARITA: A CONSTANT-ROUND RESETTABLY-SOUND RESETTABLE ZERO-KNOWLEDGE ARGUMENT IN THE BPK MODEL

1395

following zero-knowledge argument between R∗ andS  . In the relay of argument, append to every message
from S  (to R∗ ) the corresponding ZAP computed fromthe witness w (instead of the random tape of S  ).
• Receiving the final commitment C from S  , forward it
to R∗ .
• When R∗ halts, halt with an output that R∗ output.
By the hiding property of Com and the witnessindistinguishability of ZAP, it is easy to see that the simulated view of R∗ is indistinguishable from its real view.
Here, we note that since the statement x is true, i.e., x isin the language L, the ZAP accompanying the last zeroknowledge proof in step 5 can be trivially generated using
the witness w for x ∈ L (that is being given to (R )∗ as anonuniform hint information). Therefore, the ZAP actuallyputs no restriction to the simulated zero-knowledge proof instep 5, i.e., any proof of R∗ can be utilized by (R )∗ by adding
the trivial ZAP.
So, the advantage of R∗ against S (w.r.t. x) to break thehiding property is essentially the same as the one of (R )∗against S  . But this must be negligible by the hiding property of (S  , R ).
Proof of conditional binding:
The scheme uses the Blum commitment for the final commitment C and clearly it is “unconditionally” (that is, even
if x ∈ L or not) statistically binding.
Proof sketch of resettable-extractability:
For any feasible cheating sender S ∗ with respect to conditions x  L in a resetting attack, we construct an eﬃcient
resettable-extractor E as follows.
Resettable-Extractor E on a security parameter 1n works
as follows:• Choose t independent random tapes ω1R , . . . , ωtR . Forj ∈ [t], let R( j) := R(ωRj )• Select a random index α that indicates a pair of someincarnation R( j) and its some first message f msg.
• Invoke a copy of S ∗ .
• For each incarnation R( j) , receiving the first message
f msg = (x, f, cS ) from S ∗ , simulate R( j) as follows:– If the current (R( j) , f msg) does not correspond to
the selected index α, simulate the behavior of R( j)completely honestly as in a real run.
– If the current (R( j) , f msg) corresponds to the selected index α, do as follows.
∗ Check whether f msg is fresh with respect toj or not. If it is not fresh, retrieve the transcript of the past session between S ∗ and R( j)that shares the same first message f msg andsimulate this session by taking-and-replaying
or by resuming-and-continuing the corresponding messages from the transcript. In
the following, we assume f msg is fresh.

∗ Generate a new random tape ω∗ . Use ω∗ as arandom tape for the following simulation ofR( j) for this interaction. Commit to a dummy
22string 0n : c2 ← Com(0n ). Send c2 , σR to
S ∗.
∗ Receiving r1 with a valid ZAP (abort this interaction if any of the ZAPs is invalid), generate a random string s = s1 , . . . , sn of lengthn2 . Compute ri = f (si ) for i = 1 to n andsend r2 = r ⊕ r1 to S ∗ with r = r1 , . . . , rn .
Then “prove” that the already-sent c2 is acommitment to r2 using the zero-knowledge
simulator, while checking the ZAPs attachedto each S ∗ ’s message. (Abort this interaction
if any of the ZAPs is invalid.)∗ Receiving a final commitment C, computevi = Ci ⊕ h(si ) for i = 1, . . . , n, and set
value = (v1 , . . . , vn ).
• When S ∗ halts, output its simulated view and value.
Only diﬀerence between E’s simulation and a real run
is in the interaction indexed by α = (R( j) , f msg).
When the first message f msg = (x, f, cS ) is not freshwith respect to j, in the real sessions, the random tapeω∗R = Fω j ( f msg) used by R( j) is the same as the one usedRin the past session between S ∗ and R( j) that shares the samefirst message f msg. So, c2 , r2 are replays of the ones sentin that session. Here, we see that r1 sent from S ∗ also must
be a replay. In fact, since x  L, r1 must be taken fromωS that is bound by cS in f msg by the soundness of the attached ZAPs. (Note that ZAPs are always resettably-sound.)Similarly, all of the messages in the zero-knowledge argument must be also replays by the eﬀect of the attached ZAPs.
(Since x  L, the messages from S ∗ must be computed using
ωS that is bound by cS in f msg by the soundness of the attached ZAPs.) Thus, we know that the above E’s simulation
by taking-and-replaying or by resuming-and-continuing thetranscript of the corresponding past session is valid in thecase of non-fresh f msg. (The point is that S ∗ cannot change
her messages as long as R( j) does not change his messages,
due to the attached ZAPs, even in the resetting attack. So,even if R( j) uses an independent random r2 (of c2 ), the resetting S ∗ cannot detect it, as long as R( j) uses the same r2
consistently. And this is the behavior of our simulated R( j) .
(Note that an honest receiver also chooses random r2 consistently from ω∗R = FωR (x, f, cS ).))
When the first message f msg = (x, f, cS ) is fresh withrespect to j, the incarnation R( j) uses a fresh random tapeω∗R = Fω j ( f msg) by pseudorandomness of F. Therefore, byR
the hiding property of Com and the zero-knowledge property of the argument, it is easy to see the above simulation
by E is indistinguishable from the real cases. Note that thestand-alone zero-knowledge suﬃces here.
Thus, the simulated view of S ∗ produced by E is indistinguishable from the real view of S ∗ .
Finally, in the interaction indexed by α = (R( j) , f msg),

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.8 AUGUST 20121396

E knows the inverses s = (s1 , . . . , sn ) of ri = f (si ) and E
can trivially extract value = (vi = Ci ⊕ h(si )) from the final
commitment C.
A detailed proof of the resettable-extractability of Protocol 1 is given in the appendix.
Since the primitives in Building Blocks of Protocol
1 exist if trapdoor permutations (for ZAPs) and collisionresistant hash functions (for constant-round ZKA) exist, wehave :

mount a resetting attack against a verifier (beyond a concurrent attack), such rewinding strategy does not work: theextractor must rewind P∗ while being get itself rewound.
We address the problem by employing the resettablyextractable conditional commitment scheme from the lastsection in place of the commitment c.
Let L be an NP language. Our argument system for L
in the BPK model works as follows.
Protocol 2

Corollary 1 If trapdoor permutations and collision-resistant hash functions exist, then a constant-round resettablyextractable conditional commitment scheme exists in theplain model.
5.

A Constant-Round Resettably-Sound Resettable
Zero-Knowledge Argument in the BPK Model

Here we construct a constant-round argument system for
all NP languages in the BPK model that is both resettablysound and resettable zero-knowledge.
First, making use of the resettably-extractable commitment scheme of the last section, we construct a constantround resettably-sound concurrent zero-knowledge argument system in the BPK model, following the design principle of Deng and Lin [8]. (They constructed a constant-round
concurrent-sound resettable zero-knowledge argument system.)Then, we apply to the constructed argument system the transformation of [6] that transforms resettablysound relaxed-concurrent zero-knowledge arguments into
resettably-sound resettable zero-knowledge arguments.
That results in a constant-round resettably-sound resettablezero-knowledge argument system for any NP languages in
the BPK model.
5.1 Construction of Constant-Round Resettably-Sound
Concurrent Zero-Knowledge Argument in the BPK
Model
Our resettably-sound concurrent zero-knowledge argument
follows the design principle of Deng and Lin [8]. A roughsketch of their principle follows. First, a verifier proves toa prover that it knows its own secret key (or a dummy secret) in a witness-indistinguishable way. Then, the provercommits to a dummy value for the verifier: c ← Com(0n ).
Finally, the prover proves that it knows the witness to theclaimed statement or the last commitment c was to the verifier’s secret key (or the dummy secret) also in a witnessindistinguishable manner.
In the proof of concurrent-soundness of their argument,a knowledge-extractor (played by verifier-simulator) of thesecond argument plays a crucial role [8]. It extracts some
witness from the cheating prover by rewinding strategy.
However, in our situation where a cheating prover P∗ can• Building Blocks:– a one-way function f ,– a constant-round resettably-extractable conditional commitment scheme rCom with respect to
L (Sect. 4),– a constant-round resettable witness-indistinguishable argument of knowledge for language{(y0 , y1 ) : ∃α, y0 = f (α) OR y1 = f (α)}(Sect. 3.1),– a constant-round resettably-sound witness-indistinguishable argument for language {(x, c, y0 , y1 ) :∃β, β is a witness to x ∈ L OR β = (β , r), c =rCom(x, β ; r), y0 = f (β ) OR β = (β , r), c =f (β )} (Here, c =rCom(x, β ; r), y1 =rCom(x, β ; r) means that the commitment c is acommitment to β with random tape r under condition x).
• Input for prover P : a statement x (∈ L), its witness
w, a public file F and an index i of a verifier (pki =( f, y0 , y1 ) ∈ F).
• Input for verifier V : x and a secret key α (satisfying
yb = f (α)).
• The protocol :1. P ⇐ V : V proves to P using the resettable
witness-indistinguishable argument of knowledge
that “there exists α satisfying y0 = f (α) OR
y1 = f (α)”.
2. P ⇒ V : P commits to 0n for V under condition
x with transcript c using the resettably-extractableconditional commitment scheme rCom.
3. P ⇒ V : P proves to V using the resettably-soundwitness-indistinguishable argument with witness
β = w that “there exists β satisfying that β
is a witness to x ∈ L OR β = (β , r), c =rCom(x, β ; r), y0 = f (β ) OR β = (β , r), c =rCom(x, β ; r), y1 = f (β ).”Theorem 2 Under the assumption that the primitives listed
in Building Blocks exist, Protocol 2 is a constant-roundresettably-sound concurrent zero-knowledge argument of L
in the BPK model.
Proof Completeness of the protocol is immediate.
Concurrent zero-knowledge property of the protocol isproved by a standard argument in the BPK model. Let V ∗ARITA: A CONSTANT-ROUND RESETTABLY-SOUND RESETTABLE ZERO-KNOWLEDGE ARGUMENT IN THE BPK MODEL1397

be any feasible cheating verifier in a concurrent attack. We
construct an eﬃcient simulator S im for V ∗ as follows.
Simulator S im :• Run the first phase of V ∗ and receive the public file F.
• Run the second phase of V ∗ :– When V ∗ passes the first argument in some interaction I with public key pki , run the stand-alone
non-black-box extractor of the resettable witnessindistinguishable argument of knowledge to extract the corresponding knowledge αi as to pki if
not yet extracted. (Note that the stand-alone extractor suﬃces since the target statement is only
pki that is fixed in the first phase. See [4] for thefull formal argument.)– When it is time for S im (as a prover) to make acommitment c for some interaction I, commit to
the extracted value αi under condition x (that is aclaimed statement) with transcript c using rCom.
– When it is time for S im (as a prover) to performthe second argument for some interaction I, run
the prover algorithm for the second argument using β = (αi , ri ) as a witness.
Since F is a polynomial size, the number of invocationof the extractor by S im is also a polynomial. Hence, S imruns in a polynomial time. By the conditional hiding property of rCom (note that x ∈ L) and the witness indistinguishable property of the second argument, the simulated view ofV ∗ by S im is easy to see indistinguishable from real viewof V ∗ . (Use a hybrid experiment where c is a commitment
to αi under x but the second argument uses the real witnessw.) This completes proof of the concurrent zero-knowledge
property.
Now we prove the resettably-soundness of the protocol.
Let P∗ be a supposed feasible cheating prover in a resetting
attack that convinces some verifier incarnation V(x) on somex  L with a non-negligible probability. Using P∗ we construct an algorithm A that breaks one-wayness of one-way
function f . We can suppose that P∗ invokes verifier incarnations V(x) only on x’s that are not in L. (We can simulate
V(x) honestly if x ∈ L and we can guess randomly whichincarnation V(x) is invoked with respect to x  L.)
Algorithm A: on input y (= f (β)),• Choose a random b ← {0, 1} and set yb = y. (Thisdefines βb = β implicitly.)• Select a random β1−b ← {0, 1}n and set y1−b = f (β1−b ).
• Invoke P∗ and give a public file F = (id, y0 , y1 ) to it.
• For every incarnation V(x) that P∗ invokes, do as follows:– Run the prover algorithm of the first argument using β1−b as a witness.
– For P∗ ’s commitment c under condition x ( L)with rCom, invoke the resettable-extractor E andsimulate its receiver using the view output by E.
– Run the honest verifier algorithm for the second
argument.
• Select a random incarnation V j∗ (x∗ ) (with x∗  L) thathas accepted in the above simulation. The committed
value β under commitment c in the interaction with
V j∗ (x∗ ) is being extracted as the value output by E witha noticeable probability.
• For the first component β1 of β check whether f (β1 ) =y or not. If so output β1 otherwise output ⊥ and halt.
It is obvious that A runs in a polynomial time.
Since the coin b is hidden from P∗ , the simulated firstargument is the same as the real first argument. Since theview output by the resettable extractor E of rCom is indistinguishable from the real view even for a resetting sender, thesimulated commitment c is indistinguishable from the realcommitment. The second argument is simulated honestly.
Hence, the simulated view of P∗ by A is indistinguishable
from its real view.
We evaluate the output by A. By the contradictive assumption, the incarnation V j∗ (x∗ ) selected by A is being convinced by P∗ on x∗  L with a non-negligible probability.
Since x∗  L, the resettably-soundness of the second argument means that its witness β must be the second or third
type : β includes the inverse images β0 or β1 of y0 or y1 ,respectively (as its first component β1 ) and means that β0 or
β1 must be committed to under c with respect to conditionx∗ . Therefore, the extracted value β from c by resettableextractor E must include β0 or β1 . By the resettable witnessindistinguishability of the first argument, we can see that
this extracted value is equal to βb at probability 1/2 except
with a negligible error. Thus, we know that A outputs βb = βwith a non-negligible probability, contradicting to the onewayness of fThe primitives listed in Building Blocks of Protocol 2
exist if trapdoor permutations and collision-resistant hashfunctions exist. So, we have:
Corollary 2 Under the assumption that trapdoor permutations and collision-resistant hash functions exist, there
exists a constant-round resettably-sound concurrent zeroknowledge argument for any NP language in the BPK
model.
5.2 Transformation to Resettably-Sound Resettable ZeroKnowledge Argument
Deng, Goyal and Sahai showed a transformation thattransforms any resettably-sound relaxed-concurrent zeroknowledge argument into a resettably-sound resettablezero-knowledge argument (The relaxed-concurrent zeroknowledge is a property that weakens concurrent zeroknowledge in some way) [6]. The transformation works in

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.8 AUGUST 20121398

the plain model and preserves the property of being constant rounds. (The transformation uses a resettably-soundzero-knowledge argument as a main building block, that is
implemented by a constant-round protocol in a plain model.)Therefore, by applying the Deng-Goyal-Sahai transformation to Protocol 2, we see that:
Corollary 3 Under the assumption that trapdoor permutations and collision-resistant hash functions exist, there
exists a constant-round resettably-sound resettable zeroknowledge argument for any NP language in the BPK
model.
6.

Conclusion

This paper has shown that argument systems for any NP
language that are both resettably-sound and resettable zeroknowledge are possible by a constant-round protocol in the
BPK model. For that sake, we defined and constructed aresettably-extractable conditional commitment scheme.

Appendix:

We prove the resettable-extractability of Protocol 1. We define a sequence of experiments Real, Hyb1, . . . , Hyb4, preserving indistinguishability among their outputs. The firstexperiment Real corresponds to a real resetting attack by acheating sender S ∗ against Protocol 1 and the final experiment Hyb4 gives us the claimed resettable-extractor for the
protocol. (In the sequel ‘≡c ’ (or ‘≡ s ’) denotes computational(or statistical) indistinguishability of both hands.)
Real :• Choose t independent random tapes ω1R , . . . , ωtR . Forj ∈ [t], let R( j) := R(ωRj ).
• Invoke a copy of S ∗ .
• For each incarnation R( j) that S ∗ invokes, simulate it asfollows:– Receiving the first message f msg = (x, f, cS )from S ∗ , compute ω∗R = FωR( j) ( f msg). Use ω∗R
as a random tape for the following simulation ofR( j) for this interaction. Take a random string r2 oflength n2 and commit to it : c2 ← Com(r2 ). Send
c2 , σR to S ∗ .
– Receiving r1 with a valid ZAP (abort this interaction if the ZAP is invalid), send r2 to S ∗ andprove that c2 is a commitment to r2 using the zeroknowledge argument, while checking the ZAPs
attached to each S ∗ ’s message. (Abort this interaction if any of the ZAPs is invalid.)– Receive C = v1 ⊕ h(s1 ), . . . , vn ⊕ h(sn ).

References[1] B. Barak, “How to go beyond the black-box simulation barrier,”
42nd FOCS, pp.106–115, 2001.
[2] B. Barak, Non-Black-Box Techniques in Cryptography, Thesis for
the Ph.D. Degree, The Weizmann Institute of Science, 2004.
[3] B. Barak, O. Goldreich, S. Goldwasser, and Y. Lindell, “Resettablysound zero-knowledge and its applications,” FOCS 2001, IEEE
Computer Society, 2001.
[4] Ran Canetti, Oded Goldreich, Shafi Goldwasser, and Silvio Micali,“Resettable zero-knowledge,” STOC, pp.235–244, 2000.
[5] G.D. Crescenzo, G. Persiano, and I. Visconti, “Constant-round resettable zero knowledge with concurrent soundness in the bare publickey model,” CRYPTO 2004, LNCS 3152, pp.237–253, 2004.
[6] Y. Deng, V. Goyal, and A. Sahai, “Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy,”
FOCS 09, pp.251–260, 2009.
[7] Y. Deng and D. Lin, “Instance-dependent verifiable random functions and their application to simultaneous resettability,” EUROCRYPT 2007, LNCS 4515, pp.148–168, 2007.
[8] Y. Deng and D. Lin, “Resettable zero knowledge with concurrent
soundness in the bare public-key model under standard assumption,”
Inscrypt 2007, LNCS 4990, pp.123–137, 2008.
[9] C. Dwork and M. Naor, “Zaps and their applications,” FOCS,
pp.283–293, 2000.
[10] T. Garfinkel and M. Rosenblum, “When virtual is harder than real:
Security challenges in virtual machine based computing environments,” HOTOS’05, vol.10, p.20, 2005.
[11] J. Kilian and E. Petrank, “Concurrent and resettable zero-knowledge
in poly-logarithmic rounds,” STOC 01, pp.560–569, 2001.
[12] S. Micali and L. Reyzin, “Soundness in the public-key model,” EUROCRYPT 2001, LNCS 2139, pp.542–565, 2001.
[13] T. Ristenpart and S. Yilek, “When good randomness goes bad:
Virtual machine reset vulnerabilities and hedging deployed cryptography,” Proc. Network and Distributed Security Symposium —NDSS’10, 2010.
[14] S. Yilek, “Resettable public-key encryption: How to encrypt on a
virtual machine,” CT-RSA 2010, LNCS 5985, pp.41–56, 2010.

Detailed Proof of the Resettable-Extractability of Protocol 1• When S ∗ halts, output its simulated view.
The following Hyb1 diﬀers from Real only around thetreatment of receiver random-tape for some selected interactions.
Hyb1 :• Choose t independent random tapes ω1R , . . . , ωtR . Forj ∈ [t], let R( j) := R(ωRj ).
• Select a random index α that indicates a pair of someincarnation R( j) and its some first message f msg.
• Invoke a copy of S ∗ .
• For each incarnation R( j) receiving the first message
f msg = (x, f, cS ) from S ∗ , simulate it as follows:– If the current (R( j) , f msg) does not correspond to
the selected index α, simulate the behavior of R( j)honestly as in Real.
– If the current (R( j) , f msg) corresponds to the selected index α, do as follows.
∗ Check whether f msg is fresh with respect toj or not. If it is not fresh, retrieve the transcript of the past session between S ∗ and R( j)ARITA: A CONSTANT-ROUND RESETTABLY-SOUND RESETTABLE ZERO-KNOWLEDGE ARGUMENT IN THE BPK MODEL

1399

that shares the first message f msg and simulate this session by taking-and-replaying orby resuming-and-continuing the corresponding messages from the transcript. In the following, we assume f msg is fresh.
∗ Generate a new random tape ω∗ . Use ω∗ asa random tape for the following simulationof R( j) for this interaction. Take a random
string r2 of length n2 and commit to it : c2 ←Com(r2 ). Send c2 , σR to S ∗ .
∗ Receiving r1 with a valid ZAP (abort thisinteraction if any of the ZAPs is invalid),
send r2 to S ∗ and prove that c2 is a commitment to r2 using the zero-knowledge argument, while checking the ZAPs attached toeach S ∗ ’s message. (Abort this interaction if
any of the ZAPs is invalid.)∗ Receive C = v1 ⊕ h(s1 ), . . . , vn ⊕ h(sn ).

• Select a random index α that indicates a pair of someincarnation R( j) and its some first message f msg.
• Invoke a copy of S ∗ .
• For each incarnation R( j) , receiving the first message
f msg = (x, f, cS ) from S ∗ , simulate it as follows:– If the current (R( j) , f msg) does not correspond to
the selected index α, simulate the behavior of R( j)honestly as in Real– If the current (R( j) , f msg) corresponds to the selected index α, do as follows.
∗ Check whether f msg is fresh with respect toj or not. If it is not fresh, retrieve the transcript of the past session between S ∗ and R( j)that shares the first message f msg and simulate this session by taking-and-replaying orby resuming-and-continuing the corresponding messages from the transcript. In the following, we assume f msg is fresh.
∗ Generate a new random tape ω∗ . Use ω∗ asa random tape for the following simulationof R( j) for this interaction. Take a random
string r2 of length n2 and commit to it: c2 ←Com(r2 ). Send c2 , σR to S ∗ .
∗ Receiving r1 with a valid ZAP (abort this interaction if any of the ZAPs is invalid), send
r2 to S ∗ and “prove” that c2 is a commitment
to r2 using the zero-knowledge simulator,
while checking the ZAPs attached to eachS ∗ ’s message. (Abort this interaction if anyof the ZAPs is invalid.)∗ Receive C = v1 ⊕ h(s1 ), . . . , vn ⊕ h(sn ).

• When S ∗ halts, output its simulated view.
Claim 1
Hyb1 ≡c Real.
Proof Only diﬀerence between Hyb1 and Real is in thesimulation of the interaction indexed by α = (R( j) , f msg).
Suppose f msg is fresh with respect to j. Then, ω∗R =Fω( j) ( f msg) is indistinguishable from a fresh random-tapeRby pseudorandomness of F in Real. So, the simulation ofHyb1 is indistinguishable from the simulation of Real.
Consider the cases where f msg is not fresh for j. In
Real, the random tape ω∗R = Fω( j) ( f msg) used by R( j) is theRsame as the one used in the past session between S ∗ and R( j)that shares the first message f msg. So, c2 , r2 , that are chosenfrom ω∗R , are replays of the ones sent in that session.
We see that r1 sent from S ∗ must be also a replay. In
fact, since x  L, r1 must be taken from ωS that is boundby cS in f msg by the soundness of the attached ZAPs. Notethat ZAPs are always resettably-sound.
Similarly, all of the messages in the zero-knowledge
argument must be also replays. Since x  L, the messages
from S ∗ must be computed using ωS that is bound by cS in
f msg by the soundness of the attached ZAPs.
Thus, also in non-fresh f msg case we know that thesimulation by Hyb1 (that replays R( j) ’s messages in the corresponding past transcript) is indistinguishable from Real.
The next Hyb2 diﬀers from Hyb1 only in that Hyb2
uses the zero-knowledge simulator instead of the real argument to prove that c2 commits to r2 for the interaction indexed by α = (R( j) , f msg).
Hyb2 :• Choose t independent random tapes ω1R , . . . , ωtR . Forj ∈ [t], let R( j) := R(ωRj ).

• When S ∗ halts, output its simulated view.
The stand-alone zero-knowledge property shows :Claim 2
Hyb2 ≡c Hyb1.
Proof Suppose towards the contradiction that Hyb2 andHyb1 is distinguishable by some distinguisher D. UsingD, we construct a following cheating verifier V ∗ against thezero-knowledge property of the argument.
V∗ :• Choose t independent random tapes ω1R , . . . , ωtR . Forj ∈ [t], let R( j) := R(ωRj ).
• Select a random index α that indicates a pair of someincarnation R( j) and its some first message f msg.
• Invoke a copy of S ∗ .
• For each incarnation R( j) , receiving the first message
f msg = (x, f, cS ) from S ∗ , simulate it as follows:– If the current (R( j) , f msg) does not correspond to
the selected index α, simulate the behavior of R( j)honestly as in Real using the tape ωRj .

IEICE TRANS. FUNDAMENTALS, VOL.E95–A, NO.8 AUGUST 2012

1400

∗ Generate a new random tape ω∗ . Useω∗ as a random tape for the following simulation of R( j) for this interaction.
2
2
Commit to string 0n : c2 ← Com(0n ).
Send c2 , σR to S ∗ .
∗ Receiving r1 with a valid ZAP (abort thisinteraction if any of the ZAPs is invalid),
generate and send r2 of length n2 to S ∗ and“prove” that c2 is a commitment to r2 using
the zero-knowledge simulator, while checking the ZAPs attached to each S ∗ ’s message.
(Abort this interaction if any of the ZAPs isinvalid.)∗ Receive C = v1 ⊕ h(s1 ), . . . , vn ⊕ h(sn ).

– If the current (R( j) , f msg) corresponds to the selected index α, do as follows.
∗ Check whether f msg is fresh with respect toj or not. If it is not fresh, retrieve the transcript of the past session between S ∗ and R( j)that shares the first message f msg and simulate this session by taking-and-replaying orby resuming-and-continuing the corresponding messages from the transcript. In the following, we assume f msg is fresh.
∗ Take a random string r2 of length n2 andcommit to it: c2 ← Com(r2 ). Send c2 , σR
to S ∗ .
∗ Receiving r1 with a valid ZAP (abort thisinteraction if the ZAP is invalid), send astatement that c2 is a commitment to r2 towards its challenger (a prover or a simulator) and transfer to S ∗ the received proof,
while checking the ZAPs attached to eachS ∗ ’s message. (Abort this interaction if anyof the ZAPs is invalid.)∗ Receive C = v1 ⊕ h(s1 ), . . . , vn ⊕ h(sn ).
• When S ∗ halts, invoke the assumed distinguisher D on
input S ∗ ’s simulated view and output its output.
In the above, if the proof that V ∗ receives from its challenger is a real proof (or a simulated proof respectively),
then the simulated view of S ∗ is the same as the one in Hyb1
(or in Hyb2). This implies that the above V ∗ violates thezero-knowledge property of the argument.
The next Hyb3 diﬀers from Hyb2 only in that Hyb3
2
commits to a dummy string 0n for c2 instead of r2 for theinteraction indexed by α = (R( j) , f msg).
Hyb3 :• Choose t independent random tapes ω1R , . . . , ωtR . Forj ∈ [t], let R( j) := R(ωRj ).
• Select a random index α that indicates a pair of someincarnation R( j) and its some first message f msg.
• Invoke a copy of S ∗ .
• For each incarnation R( j) , receiving the first message
f msg = (x, f, cS ) from S ∗ , simulate it as follows:– If the current (R( j) , f msg) does not correspond to
the selected index α, simulate the behavior of R( j)honestly as in Real– If the current (R( j) , f msg) corresponds to the selected index α, do as follows.
∗ Check whether f msg is fresh with respect toj or not. If it is not fresh, retrieve the transcript of the past session between S ∗ and R( j)that shares the first message f msg and simulate this session by taking-and-replaying orby resuming-and-continuing the corresponding messages from the transcript. In the following, we assume f msg is fresh.

• When S ∗ halts, output its simulated view.
As usual, the hiding property of Com means :Claim 3
Hyb3 ≡c Hyb2.
The final Hyb4 diﬀers from Hyb3 only in the way ofgenerating the random string r2 for the interaction indexedby α = (R( j) , f msg).
Hyb4 :• Choose t independent random tapes ω1R , . . . , ωtR . Forj ∈ [t], let R( j) := R(ωRj ).
• Select a random index α that indicates a pair of someincarnation R( j) and its some first message f msg.
• Invoke a copy of S ∗ .
• For each incarnation R( j) , receiving the first message
f msg = (x, f, cS ) from S ∗ , simulate it as follows:– If the current (R( j) , f msg) does not correspond to
the selected index α, simulate the behavior of R( j)honestly as in Real– If the current (R( j) , f msg) corresponds to the selected index α, do as follows.
∗ Check whether f msg is fresh with respect toj or not. If it is not fresh, retrieve the transcript of the past session between S ∗ and R( j)that shares the first message f msg and simulate this session by taking-and-replaying orby resuming-and-continuing the corresponding messages from the transcript. In the following, we assume f msg is fresh.
∗ Generate a new random tape ω∗ . Use ω∗ as arandom tape for the following simulation ofR( j) for this interaction. Commit to a dummy
22string 0n : c2 ← Com(0n ). Send c2 , σR to∗
S .
∗ Receiving r1 with a valid ZAP (abort thisinteraction if any of the ZAPs is invalid),
generate a random string s = s1 , . . . , sn oflength n2 . Compute ri = f (si ) for i = 1 to n

ARITA: A CONSTANT-ROUND RESETTABLY-SOUND RESETTABLE ZERO-KNOWLEDGE ARGUMENT IN THE BPK MODEL

1401

and send r2 = r ⊕ r1 to S ∗ with r = r1 , . . . , rn .
Then “prove” that c2 is a commitment to r2
using the zero-knowledge simulator, while
checking the ZAPs attached to each S ∗ ’s
message. (Abort this interaction if any of the
ZAPs is invalid.)∗ Receive C = v1 ⊕ h(s1 ), . . . , vn ⊕ h(sn ).
• When S ∗ halts, output its simulated view.
2

Since r2 distributes uniformly over {0, 1}n also in
Hyb4, we have
Claim 4
Hyb4 ≡ s Hyb3.
Now it is immediate that the simulation in Hyb4 gives
the claimed resettable-extractor of Protocol 1. In fact, in
Hyb4 we can eﬃciently extract the values committed under final commitments C using the knowledge of si =f −1 (ri ) (i = 1, . . . , n) for the interaction indexed by α =(R( j) , f msg). That completes the proof.

Seiko Arita
received his B.S. and M.S. degrees from Kyoto University and his Doctor ofEngineering degree from Chuo University. Before joining Institute of Information Security at
April 2004, he worked for NEC from 1990 to
2003.