Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR05-048 | 2nd May 2006 00:00

Concurrently Knowledge-Extractable Resettable-ZK in the Bare Public-Key Model

RSS-Feed




Revision #3
Authors: Yunlei Zhao, Moti Yung
Accepted on: 2nd May 2006 00:00
Downloads: 2114
Keywords: 


Abstract:


We present constant-round \emph{concurrently knowledge-extractable} black-box resettable zero-knowledge (rZK-CKE) arguments for NP in the bare public-key (BPK) model. We give minimal (sub-exponential) hardness assumption based protocols as well as round-optimal protocols (still under general hardness assumptions). To our knowledge, our protocols are the first ZK protocols that provably provide both resettable/concurrent prover security and concurrent verifier security in public-key models. Here, the notion of {\em concurrent knowledge-extractability} roughly means that no malicious polynomial-time prover can convince an honest verifier of any (whether false or true) statement without ``knowing" a corresponding NP-witness even by concurrently interleaving interactions in public-key models when verifiers register public-keys. We show that concurrent
knowledge-extractability is \emph{strictly} stronger than ``concurrent soundness" (under any sub-exponentially strong one-way permutation) for concurrently proving NP statements to honest verifiers with public-keys. In particular, we show that previous concurrent zero-knowledge protocols in the BPK model that achieved concurrent soundness security and are also traditional arguments of knowledge actually fail to satisfy this stronger security notion (this is demonstrated by concrete attacks). Our work deepens the understanding of the subtleties of concurrent verifier security in public-key settings, and may serve as building blocks in designing other round-efficient concurrently secure protocols in public-key models that use, in particular, argument of knowledge (AOK) protocols as building blocks.


Revision #2 to TR05-048 | 10th July 2005 00:00

Constant-Round Concurrently-Secure rZK with (Real) Bare Public-Keys





Revision #2
Authors: Zhao Yunlei, Yung Moti
Accepted on: 10th July 2005 00:00
Downloads: 3089
Keywords: 


Abstract:

We present constant-round concurrently secure (sound) resettable
zero-knowledge (rZK-CS) arguments with real bare public-keys (i.e.,
public keys based on reduced complexity assumptions). In
particular, for general NP ZK-arguments we give round-optimal protocols as well as minimal hardness assumption based protocols. We also give highly efficient ZK-arguments for number-theoretic languages. Our constructions employ a number of new techniques/tools which are of possibly independent interest.


Revision #1 to TR05-048 | 6th May 2005 00:00

Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model





Revision #1
Authors: Yunlei Zhao
Accepted on: 6th May 2005 00:00
Downloads: 3166
Keywords: 


Abstract:

We present constant-round concurrently secure (sound) resettable
zero-knowledge (rZK-CS) arguments in the bare public-key (BPK)
model. Our constructions deal with general NP ZK-arguments as well
as with highly efficient ZK-arguments for number-theoretic
languages, most relevant to identification scenarios. These are the
first constant-round protocols of this type in the original
real BPK model, where nothing is assured about public-keys
generated by malicious verifiers. As part of this work, we
develop a one-round trapdoor commitment scheme that is based on any
one-way permutation, which is of independent interest and, in
particular, can be used to reduce the round-complexity of other
cryptographic protocols involving trapdoor commitments.


Paper:

TR05-048 | 11th April 2005 00:00

Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model





TR05-048
Authors: Moti Yung, Yunlei Zhao
Publication: 26th April 2005 00:46
Downloads: 3201
Keywords: 


Abstract:

We present constant-round concurrently secure (sound) resettable
zero-knowledge (rZK-CS) arguments in the bare public-key (BPK)
model. Our constructions deal with general NP ZK-arguments as well
as with highly efficient ZK-arguments for number-theoretic
languages, most relevant to identification scenarios. These are the
first constant-round protocols of this type in the original
\emph{real} BPK model, where nothing is assured about public-keys
generated by malicious verifiers. As part of this work, we
develop a one-round trapdoor commitment scheme that is based on any
one-way permutation, which is of independent interest and, in
particular, can be used to reduce the round-complexity of other
cryptographic protocols involving trapdoor commitments.



ISSN 1433-8092 | Imprint