Concurrent Knowledge-Extraction in the Public-Key Model.
Moti M. Yung, Yunlei Zhao · 2007
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 N P in this model. Concurrent knowledge-extraction in the public-key model essentially means that for any N P 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