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.
An improved (corrected) version coming soon.
This is the corrected version of the TR07-002
