Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-002 | 8th November 2006 00:00

Concurrent Knowledge-Extraction in the Public-Key Model


Authors: Moti Yung, Yunlei Zhao
Publication: 6th January 2007 23:47
Downloads: 1609


Knowledge extraction is a fundamental notion, modeling knowledge possession in a computational complexity sense. The notion provides a tool for cryptographic protocol design and analysis, enabling one to argue about the internal state of protocol players. We define and
investigate the relative power of the notion of ``concurrent knowledge-extraction'' (CKE) in the concurrent zero-knowledge (CZK) bare public-key (BPK) model, namely we investigate how to
formally treat knowledge possessions for parties interacting over the Internet (say). We further investigate the implementation of a generic scheme for this new notion of CKE concurrent zero-knowledge (CZK-CKE) arguments for $\mathcal{NP}$ in this model.

Concurrent knowledge-extraction in the public-key model essentially means that for any $\mathcal{NP}$ statement whose validation is successfully conveyed by a possibly malicious prover to an honest verifier (with registered public-key) employing concurrent interactions, the prover ``must know" the corresponding witness. It is shown that under any one-way function (OWF), concurrent knowledge-extraction is strictly stronger than concurrent soundness in the BPK model (as is demonstrated by concrete attacks). Then, in light of our concurrent interleaving and malleating attacks, we formalize CKE in the bare public-key model.

We then present, both general scheme (round-optimal or minimal hardness assumption based for $\mathcal{NP}$) and practical scheme (based on the DDH assumption for specific number-theoretic language). Both schemes are constant-round CZK-CKE arguments in the BPK model. We note that both the ZK simulation and the knowledge extraction in our model and proofs are efficient (i.e., expected polynomial-time).

Then, we discuss an extended notion of CKE, called joint CKE (JCKE), which essentially requires that the malicious prover ``knows" the corresponding \emph{joint} witnesses to all statements successfully convinced in its concurrent interactions. We show that our practical CZK-CKE scheme also satisfies this seemingly stronger notion, and further show how to slightly modify the general scheme to satisfy this extended notion as well.


Comment #1 to TR07-002 | 15th February 2007 06:50

Preliminary Version -- to Be Improved

Comment #1
Authors: Andrew Chi-Chih Yao, Moti Yung, Yunlei Zhao
Accepted on: 15th February 2007 06:50
Downloads: 799


An improved (corrected) version coming soon.

Comment #2 to TR07-002 | 22nd August 2009 16:54

Revision of TR07-002

Comment #2
Authors: Yunlei Zhao, Andrew Chi-Chih Yao, Moti Yung
Accepted on: 22nd August 2009 16:54
Downloads: 1256


This is the corrected version of the TR07-002

ISSN 1433-8092 | Imprint