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
registrations.
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
added.
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)
Malicious
Prover
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
knowledge-extractibility.
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:
PK=fV(xV).
Let y0P=fP(x0P) and y1P=fP(x1P). The pair
(y0P, y1P) is then fixed for P.
The rough protocol structure
x L
Phase-1:
P(w)
RWI(y0
P
y1
P)
PK
V(xV)
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.
N
c
n
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
OWF.
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
assumption.
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
n-cycle).
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
c




Super-polynomial-time knowledge-extraction is intrinsic for black-box
RZK
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
Thanks
Agenda
1.
2.
3.
4.
5.
6.
7.
Resettable zero-knowledge (RZK)
The bare public-key (BPK) model
Concurrent verifier security in the public-key
model
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
Descargar

PowerPoint 演示文稿