Generic and Practical Resettable ZeroKnowledge in the Bare Public-Key Model
Moti Yung
RSA Laboratories and CS Dept. of Columbia University
Yunlei Zhao
Software School, Fudan University, Shanghai, P. R. China
1. Resettable Zero-Knowledge RZK
RZK is introduced by Canetti, Goldreich,
Goldwasser and Micali (STOC 2000).
Motivated by implementing ZK provers using
smart-cards or other devices that may be
(maliciously) reset to their initial conditions and/or
cannot afford to generate fresh randomness for
each new invocation.
A generalization and strengthening of CZK
intruduced by Dwork, Naor and Sahai [DNS98] .
2. The Bare Public-Key (BPK) Model
No constant-round (black-box) RZK/CZK
protocols in the standard model [CKPR01].
To get constant-round RZK/CZK protocols,
several computational models have been
introduced: the timing model, the
preprocessing model, the common reference
string model, and the BPK model, etc.
The BPK model [CGGM00]
A protocol in BPK model simply assumes
that all verifiers have deposited a public
key in a public file before any interaction
takes place among the users
The BPK model also allows dynamic key
No assumption is made on whether the
public-keys deposited are unique or
``nonsensical" or ``bad" public-keys (e.g.,
for which no corresponding secret-keys
exist or are known).
Note that an adversary may deposit many
(possibly invalid or fake) public keys
without any guarantee on the validities of
the registered public-keys.
That is, no trusted third party is assumed in
the BPK model; the preprocessing is
reduced to verifiers minimally register a
public-key in a public file; and the
communication network is assumed to be
adversarially asynchronous;
Weaker than PKI, where authentic
association of user ID and its public-key is
3. Concurrent Verifier-Security in
the Public-Key Model
Verifier security in public-key models turns
out to be much more complicated and
subtler than that of the standard model.
In public-key model, a verifier V possesses a
secret key SK, corresponding to its public-key PK.
A malicious prover P* could potentially gain
some knowledge about SK from a session with
the verifier.
This extra gained knowledge may help this prover:
Violate concurrent soundness: i.e., convincing the
verifier of a false theorem in another concurrent session;
Or: violate concurrent knowledge extractability: i.e.,
convincing the honest verifier of a true statement in
another concurrent session but without knowing
corresponding witness.
Verifier (PK)
Verifier (PK)
Verifier (PK)
Four notions of soundness in the public-key model, i.e.,
from weaker to stronger: one-time, sequential, concurrent
and resettable soundness.
Concurrent soundness (CS): a malicious prover P* cannot
convince the honest verifier V of a false statement even
when P* is allowed multiple interleaving interactions with
V in the public-key model.
Concurrent knowledge-extractability (CKE): a malicious
P* can convince the honest V of a statement only if it
knows the corresponding witness
Some facts about concurrent verifier
security in the public-key model
Any (resettable or not) black-box ZK protocols
with concurrent soundness in the BPK model (for
non-trivial languages) must run at least four
rounds [MR01].
Any (whether resettable or not) black-box ZK
arguments with resettable soundness only exist for
trivial (i.e, BPP) languages (whether in the BPK
model or not) [BGGL01,MR01].
Concurrent knowledge-extractability is (strictly)
stronger than concurrent soundness.
4. Related Works and Our Contributions
The first constant-round RZK-CS protocol
in the BPK model [DPV00]
Constant-round (black-box) RZK-CS argument for NP was first
established by Di Crescenzo, Persiano and Visconti [Crypto 2000]
 Round-optimal
 Based on NIZK for NP and a special form of sub-exponentially
secure PKE (e.g., the sub-exponentially secure version of the
ElGamal scheme that is based on the sub-exponentially strong
DDH assumption), etc.
 The security analysis seems to be not extended to the case of CKE
(CKE is not the issue considered in [DPV00] )
Problems left in [DPV00]:
 Can constant-round (in particular, round-optimal) RZK-CS can be
based on general hardness assumption?
 Can RZK-CKE be provably achieved?
 Can RZK-CS/CKE be implemented practically, say, with a very
small constant number of exponentiations?
This work
Constant-round (7-round) RZK-CS argument for NP in the
BPK model based on any sub-exponentially-strong OWF.
Round-optimal (i.e., 4-round) RZK-CS based on any
certified OWP.
 One-round trapdoor commitments
Generic yet practical transformation for achieving 5-round
RZK-CS arugments:
 Applicable to all languages admitting ∑-protocol
 Without going through NP-reduction, and can be
implemented with several exponentiations
Satisfy a reasonable (weak) black-box concurrent
5. The General RZK Construction Based
on Any Subexponentially-Strong OWF
Common input xL.
Let fP be any (standard polynomial secure)
OWF, and fV be any sub-exponentially
secure OWFs.
The public-key of the honest verifier V is:
Let y0P=fP(x0P) and y1P=fP(x1P). The pair
(y0P, y1P) is then fixed for P.
The rough protocol structure
x L
Phase-2: (Resettably-sound)
WIPOK(y0P y1P  PK)
Phase-3: RWI(x  PK)
Complexity leveraging
The system parameter is N, the prover uses a
relatively smaller parameter n (still polynomially
related to N), such that:
Breaking fP by brute-forth in 2n-time does not
compromise the security fV (i.e., PK) that is subexponentially secure in N, specifically, secure
againt 2  poly ( n )  2 -time algorithm.
Two types of OWF-based constantround rWI argument for NP
The CGGM transformation from Blum’s WI proof for NP
to RWI proof for NP
The verifier is required to first commit its random challenge on the
top by running a perfectly-hiding commitment scheme
Randomness of prover is got by applying PRF on the transcript.
Phase-1 RWI arguments for NP:
The challenge is committed with Naor’s OWF-based statisticallybinding and sub-exponentially hiding commitments, which can be
implemented from any sub-exponentially strong OWF
Phase-3 RWI for NP:
The challenge is committed with a OWF-based trapdoor
commitment scheme (by combining Naor’s OWF-based
commitment scheme and Feige-Shamir trapdoor commitments),
such that the binding property can be broken in 2n-time.
The dual role of Phase-1 RWI argument in
RZK proof and in CS/CKE proof
To deal with the subtlety with extracting xV in RZK simulation:
 We want to argue that Phase-2 WIPOK(y0P y1P  PK) is actually
POK of the secret-key xV . But, Phase-2 begins after V* resettingly
interacting with instances of P in Phase-1 RWI on fixed (y0P y1P).
In general , in this case, normal POK and even CS do not
guarantee concurrent knowledge-extractability of xV .
 By statistically-binding of Naor’s commitments, reduce resetting
interactions of V* with honest P in Phase-1 into concurrent
interactions, which guarantees witness-hiding of (x0P, x1P) and in
turn guarantees of POK of xV of Phase-2.
To guarantee preimage-verifiability of (y0P y1P) in CS/CKE proof ,
following the simulation/extraction approach:
 Honest verifier always continues its interactions after successful
Phase-1 RWI even on false (y0P y1P) , i.e., no preimage of either
y0P or y1P exists, but the sub-exponential-time CS/CKE simulator
always aborts by brute-force searching in this case.
But, using statistically-binding commitments in
Phase-1 RWI makes the proof of concurrent
soundness complicated and subtle.
Idea: reduce to sub-exponentially hiding of Naor’s
commitments based on sub-exponentially strong
The role of Phase-3 RWI
On one hand, it is used for establishing
RZK (the RZK simulator uses xV as the
Phase-3 witness in simulation);
On the other hand, committing random
challenge with trapdoor commitments (that
can be broken within 2n-time) enables the
simulation/extraction approach for proving
(weak) CKE
6. Simplified, Practical, and RoundOptimal Implementations
An Observation
Recall that the Phase-1 RWI argument on (y0P ,
y1P) plays a dual role: one-waynessness in RZK
proof; and preimage-verifiability of either y0P or
y1P in CS/CKE proof.
Suppose fP is preimage-verfiable, then Phase-1
RWI can be removed, and the prover only needs to
send a unique value yP=f(xP) on the top.
This renders us 5-round simplified implementation
Preimage-verifiable OWF is a quite weak hardness
Generic yet Practical Transformation
Building tools:
 ∑-protocol and ∑OR-protocol (WI without NP-reduction)
 Naor-Reingold practical PRF: needs only 2 exponentiations and
can be reduced to only 2 multiple products modulo a prime
(without any exponentiaitions!) with natural preprocessing.
 Preimage-verifiable OWFs admitting ∑-protocol, from which
perfectly-hiding trapdoor commitments can be established
(Damgard Crypto’89)
With all above tools, the preimage-verfiable OWF-based simplified
implementation can be further converted into generic yet practical
implementation for any language admitting ∑-protocols without NPreductions.
With RSA and DLP as examples, the implementations only need
several modular exponentiations.
Round-Optimal Implementation.
In the 5-round simplified implementation, the unique value yP=f(xP),
sent by P on the top, is used by the verifier V in two ways:
 It serves as a part of the inputs to the Phase-2 (resettably-sound)
WIPOK proof on (yP, yV);
 It serves the trapdoor commitment public-key (TCPK) for the
verifier to make trapdoor commitments in the second round.
We want to merge yP into the third-round message from P to V. To this
end, we need:
 Lapidot-Shamir WI for NP
 A special kind of trapdoor commitment scheme: commitment
phase is non-interactive without knowing TCPK, which is only
sent in the decommitment phase.
OWP-Based One-round TC
One-round commitment stage:
To commit to 0, the committer P sends an n-by-n adjacency matrix of
(OWP-based one-round perfectly-binding) commitments with each entry
committing to 0.
To commit to 1, the committer sends an n-by-n adjacency matrix of
commitments such that the entries committing to 1 constitute a randomly
n-cycle C.
Two-round decommitment stage: The receiver V sends a
Hamiltonian graph G=(V, E) with size n=|V| to P.
To decommit to 0, P sends a random permutation , and for each nonedge of G , (i, j) E, P reveals the value (that is 0) committed to the ( (i),
 (j))-entry of the adjacency matrix sent in the commitment stage (and V
checks all revealed values are 0 and the unrevealed entries constitute a
graph that is isomorphic to G via ).
To decommit to 1, P only reveals the committed cycle (and the receiver
checks that all revealed values are 1 and the revealed entries constitute an
7. Weak Concurrent Knowledge-Extractability
Black-box sub-exponential-time CKE: for any x, suppoe P* can
convince of ``xL” with non-negligible probability, with almost the
same probability a black-box poly(n)2n-time extractor can extract a
witness w for xL
Suppose L is 2 N  poly ( n )  2 n -hard, 0<c<1, then this means that
P* does know the witness w (rather than only convincing NPmembership)
Still reasonable
Super-polynomial-time knowledge-extraction is intrinsic for black-box
Most practical OWFs are essentially sub-exponentially hard.
Allow highly practical implementation, which are within reach for coming
smart-card environment
Highly practical efficiency and the CKE property are important for RZK
to be used as smart-card based Identification, which is the original
motivation of RZK
Resettable zero-knowledge (RZK)
The bare public-key (BPK) model
Concurrent verifier security in the public-key
Related works and our contributions
The general RZK construction based on any subexponentially secure OWF
Simplified, practical, and round-optimal variants
On the weak concurrent knowledgeextractability

PowerPoint 演示文稿