Concurrent Knowledge Extraction in the Public-Key Model

Andrew C. Yao, Moti Yung, and Yunlei Zhao

Abstract

Knowledge extraction is a fundamental notion, modeling machine possession of values (witnesses) in a computational complexity sense and enabling one to argue about the internal state of a party in a protocol without probing its internal secret state. However, when transactions are concurrent (e.g., over the Internet) with players possessing public-keys (as is common in cryptography), assuring that entities know" what they claim to know, where adversaries may be well coordinated across different transactions, turns out to be much more subtle and in need of re-examination. Here, we investigate how to formally treat knowledge possession by parties (with registered public-keys) interacting over the Internet. Stated more technically, we look into the relative power of the notion of concurrent knowledge-extraction" (CKE) in the concurrent zero-knowledge (CZK) bare public-key (BPK) model where statements being proven can be dynamically and adaptively chosen by the prover. We show the potential vulnerability of man-in-the-middle (MIM) attacks turn out to be a real security threat to existing natural protocols running concurrently in the public-key model, which motivates us to introduce and formalize the notion of CKE, alone with clarification of various subtleties. Then, both generic (based on standard polynomial assumptions), and efficient (employing complexity leveraging in a novel way) implementations for NP are presented for constant-round (in particular, round-optimal) concurrently knowledge-extractable concurrent zero-knowledge (CZK-CKE) arguments in the BPK model. The efficient implementation can be further practically instantiated for specific number-theoretic language.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
ylzhao @ fudan edu cn
History
Short URL
https://ia.cr/2010/074

CC BY

BibTeX

@misc{cryptoeprint:2010/074,
author = {Andrew C.  Yao and Moti Yung and Yunlei Zhao},
title = {Concurrent Knowledge Extraction in the Public-Key Model},
howpublished = {Cryptology ePrint Archive, Paper 2010/074},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/074}},
url = {https://eprint.iacr.org/2010/074}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.