Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic colloquium on computational complexity

Concurrent Knowledge-Extraction in the Public-Key Model.

Moti M. Yung, Yunlei Zhao

Published Jan 1, 2007• 5 citations
OpenAlex

Abstract

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

Related papers

Concurrent Knowledge-Extraction in the Public-Key Model

Andrew Chi-Chih Yao, Moti M. Yung, Yunlei Zhao

Knowledge extraction is a fundamental notion, modelling machine possession of values (witnesses) in a computational complexity sense. The notion provides an essential tool for cryptographic protocol design and analysis, enabling one to argue about the internal state of protocol players without ever looking at this supposedly 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.

arXiv:0908.2476•Aug 18, 2009•0 citations

Concurrently Non-Malleable Zero Knowledge in the Authenticated Public-Key Model

Yi Deng, Giovanni Di Crescenzo, Dongdai Lin

We consider a type of zero-knowledge protocols that are of interest for their practical applications within networks like the Internet: efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks. In an effort to reduce the setup assumptions required for efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks, we consider a model, which we call the Authenticated Public-Key (APK) model. The APK model seems to significantly reduce the setup assumptions made by the CRS model (as no trusted party or honest execution of a centralized algorithm are required), and can be seen as a slightly stronger variation of the Bare Public-Key (BPK) model from \cite{CGGM,MR}, and a weaker variation of the registered public-key model used in \cite{BCNP}. We then define and study man-in-the-middle attacks in the APK model. Our main result is a constant-round concurrent non-malleable zero-knowledge argument of knowledge for any polynomial-time relation (associated to a language in $\mathcal{NP}$), under the (minimal) assumption of the existence of a one-way function family. Furthermore,We show time-efficient instantiations of our protocol based on known number-theoretic assumptions. We also note a negative result with respect to further reducing the setup assumptions of our protocol to those in the (unauthenticated) BPK model, by showing that concurrently non-malleable zero-knowledge arguments of knowledge in the BPK model are only possible for trivial languages.

arXiv:cs/0609057•Sep 12, 2006•5 citations

Concurrent/Resettable Zero-Knowledge With Concurrent Soundness in the Bare Public-Key Model and Its Applications.

Yunlei Zhao

In this paper, we present both practical and general 4-round concurrent and resettable zeroknowledge arguments with concurrent soundness in the bare public-key (BPK) model. To our knowledge, our result is the first work that achieves concurrent soundness for ZK protocols in the BPK model and stands for the current state-of-the-art of concurrent zero-knowledge with setup assumptions.

•Jan 1, 2003•11 citations

Zero Knowledge Argument System in Bare Public Key Model Set

Yiming Zhao

This paper analyzes the development and properties of zero knowledge argument systems in Bare Public Key(BPK) model set, according to the researches and applications of recent years. The generic 4-round mode and 3-round mode are proposed for the constructions of zero knowledge protocols with optimal round complexity, following explorations on the proof techniques of (concurrent) soundness and (resettable) zero knowledge of the protocols. Possible focuses of the near future are discussed.

Jisuanji gongcheng•Jan 1, 2009•0 citations

Adaptive Security of Concurrent Non-Malleable Zero-Knowledge.

Zhenfu Cao, Zongyang Zhang, Yunlei Zhao

A zero-knowledge protocol allows a prover to convince a verifier of the correctness of a statement without disclosing any other information to the verifier. It is a basic tool and widely used in many other cryptographic applications. However, when stand-alone zero-knowledge protocols are used in complex environments, e.g., the Internet, the basic properties may not be sufficient. This is why researchers considered security of zero-knowledge protocols under concurrent composition and manin-the-middle attacks. Moreover, it is very likely that an adversary might break computers that run the protocol and get internal information of the parties. It is thus necessary to take account of the security of zero-knowledge protocols when adaptive corruptions are allowed. Previous adaptively secure zero-knowledge protocols work either in a stand-alone setting, or in a concurrent setting with trusted setup assumptions. In this paper, we study adaptive security of zero-knowledge protocols under both concurrent self composition and man-in-the-middle attacks in the plain model (i.e., without any set-up assumptions). We provide a construction of adaptively secure concurrent non-malleable zero-knowledge proof/argument for every language in NP.

•Jan 1, 2011•0 citations

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

Public-Key Model

We present constant-round concurrently secure (sound) resettable zero-knowledge (rZK-CS) arguments in the bare public-key (BPK) model. Our constructions deal with generalNP ZK-arguments as well as with highly ecien t ZK-arguments for number-theoretic languages, most relevant to identication scenarios. These are the rst constant-round protocols of this type in the original real BPK model, where nothing is assured about public-keys generated by malicious veriers. 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.

•Jan 1, 2005•0 citations
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
Knowledge extraction is a fundamental notion, modelling machine possession of values (witnesses) in a computational complexity sense. The notion provides an essential tool for cryptographic protocol design and analysis, enabling one to argue about the internal state of protocol players without ever looking at this supposedly 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.
We consider a type of zero-knowledge protocols that are of interest for their practical applications within networks like the Internet: efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks. In an effort to reduce the setup assumptions required for efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks, we consider a model, which we call the Authenticated Public-Key (APK) model. The APK model seems to significantly reduce the setup assumptions made by the CRS model (as no trusted party or honest execution of a centralized algorithm are required), and can be seen as a slightly stronger variation of the Bare Public-Key (BPK) model from \cite{CGGM,MR}, and a weaker variation of the registered public-key model used in \cite{BCNP}. We then define and study man-in-the-middle attacks in the APK model. Our main result is a constant-round concurrent non-malleable zero-knowledge argument of knowledge for any polynomial-time relation (associated to a language in NP\mathcal{NP}NP), under the (minimal) assumption of the existence of a one-way function family. Furthermore,We show time-efficient instantiations of our protocol based on known number-theoretic assumptions. We also note a negative result with respect to further reducing the setup assumptions of our protocol to those in the (unauthenticated) BPK model, by showing that concurrently non-malleable zero-knowledge arguments of knowledge in the BPK model are only possible for trivial languages.
A zero-knowledge protocol allows a prover to convince a verifier of the correctness of a statement without disclosing any other information to the verifier. It is a basic tool and widely used in many other cryptographic applications. However, when stand-alone zero-knowledge protocols are used in complex environments, e.g., the Internet, the basic properties may not be sufficient. This is why researchers considered security of zero-knowledge protocols under concurrent composition and manin-the-middle attacks. Moreover, it is very likely that an adversary might break computers that run the protocol and get internal information of the parties. It is thus necessary to take account of the security of zero-knowledge protocols when adaptive corruptions are allowed. Previous adaptively secure zero-knowledge protocols work either in a stand-alone setting, or in a concurrent setting with trusted setup assumptions. In this paper, we study adaptive security of zero-knowledge protocols under both concurrent self composition and man-in-the-middle attacks in the plain model (i.e., without any set-up assumptions). We provide a construction of adaptively secure concurrent non-malleable zero-knowledge proof/argument for every language in NP.
We present constant-round concurrently secure (sound) resettable zero-knowledge (rZK-CS) arguments in the bare public-key (BPK) model. Our constructions deal with generalNP ZK-arguments as well as with highly ecien t ZK-arguments for number-theoretic languages, most relevant to identication scenarios. These are the rst constant-round protocols of this type in the original real BPK model, where nothing is assured about public-keys generated by malicious veriers. 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.