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

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

Yunlei Zhao

Published Jan 1, 2003• 11 citations
OpenAlex

Abstract

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.

Related papers

Resettable Zero Knowledge in the Bare Public-Key Model under Standard Assumption

Yi Deng, Dongdai Lin

In this paper we resolve an open problem regarding resettable zero knowledge in the bare public-key (BPK for short) model: Does there exist constant round resettable zero knowledge argument with concurrent soundness for $\mathcal{NP}$ in BPK model without assuming \emph{sub-exponential hardness}? We give a positive answer to this question by presenting such a protocol for any language in $\mathcal{NP}$ in the bare public-key model assuming only collision-resistant hash functions against \emph{polynomial-time} adversaries.

arXiv:cs/0607035•Jul 10, 2006•2 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

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

Simultaneously resettable zero knowledge protocol in Public Key model

Wei Zhu, Yi Deng

Abstract In this paper, we construct a 6-round simultaneously resettable sound resettable $$(T, \epsilon )$$ ( T , ϵ ) -zero knowledge protocol for $$\mathsf {NP \cap coNP}$$ NP ∩ coNP in the Public Key model under standard assumptions, comparing with the 27-round simultaneously resettable zero knowledge protocol in the BPK model by Deng et al. in 2011, we have achieved a significant reduction in the round complexity. Our model assumes that both prover and verifier hold public keys, we call it the Public Key model. It is a variation of the traditional BPK model where only the verifier is assumed to hold public keys. In the original BPK model, under the sub-exponential hardness assumption of factoring, we construct a 2-round simultaneously resettable sound resettable $$(T,\epsilon )$$ ( T , ϵ ) -zero knowledge protocol for $$\textsf{NP}$$ NP .

Cybersecurity•Nov 17, 2024•0 citations

Resettable zero-knowledge (extended abstract)

Ran Canetti, Oded Goldreich, Shafi Goldwasser +1 more

We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge.In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape.All known examples of zero-knowledge proofs and arguments are trivially breakable in this setting.Moreover, by definition, all zero-knowledge proofs of knowledge are breakable in this setting.Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct: • Resettable Zero-Knowledge proof-systems for NP with non-constant number of rounds.* Five-round Resettable Witness-Indistinguishable proofsystems for NP. e Four-round Resettabie Zero-Knowledge arguments for NP in the public key model: where verifiers have fixed, public keys associated with them.In addition to shedding new light on what makes zero knowledge possible (by constructing ZK protocols that use randomness in a dramatically weaker way than before), rZK has great relevance to applications.Firstly, rZK protocols are closed under parallel and concurrent execution and thus are guaranteed to be secure when implemented in fully asynchronous networks, even if an adversary schedules the arrival of every message sent so as to foil security.Secondly, rZK protocols enlarge the range of physical ways in which provers of ZK protocols can be securely implemented, including devices which cannot reliably toss coins on line, nor keep state *A subset of this work is included in patent application [21].

ACM Symposium on Theory of Computing (STOC)•May 1, 2000•204 citations

Concurrent Knowledge-Extraction in the Public-Key Model.

Moti M. Yung, Yunlei Zhao

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

Electronic colloquium on computational complexity•Jan 1, 2007•5 citations
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.
In this paper we resolve an open problem regarding resettable zero knowledge in the bare public-key (BPK for short) model: Does there exist constant round resettable zero knowledge argument with concurrent soundness for NP\mathcal{NP}NP in BPK model without assuming \emph{sub-exponential hardness}? We give a positive answer to this question by presenting such a protocol for any language in NP\mathcal{NP}NP in the bare public-key model assuming only collision-resistant hash functions against \emph{polynomial-time} adversaries.
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.
Abstract In this paper, we construct a 6-round simultaneously resettable sound resettable (T,ϵ)(T, \epsilon )(T,ϵ) ( T , ϵ ) -zero knowledge protocol for NP∩coNP\mathsf {NP \cap coNP}NP∩coNP NP ∩ coNP in the Public Key model under standard assumptions, comparing with the 27-round simultaneously resettable zero knowledge protocol in the BPK model by Deng et al. in 2011, we have achieved a significant reduction in the round complexity. Our model assumes that both prover and verifier hold public keys, we call it the Public Key model. It is a variation of the traditional BPK model where only the verifier is assumed to hold public keys. In the original BPK model, under the sub-exponential hardness assumption of factoring, we construct a 2-round simultaneously resettable sound resettable (T,ϵ)(T,\epsilon )(T,ϵ) ( T , ϵ ) -zero knowledge protocol for NP\textsf{NP}NP NP .
We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge.In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape.All known examples of zero-knowledge proofs and arguments are trivially breakable in this setting.Moreover, by definition, all zero-knowledge proofs of knowledge are breakable in this setting.Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct: • Resettable Zero-Knowledge proof-systems for NP with non-constant number of rounds.* Five-round Resettable Witness-Indistinguishable proofsystems for NP. e Four-round Resettabie Zero-Knowledge arguments for NP in the public key model: where verifiers have fixed, public keys associated with them.In addition to shedding new light on what makes zero knowledge possible (by constructing ZK protocols that use randomness in a dramatically weaker way than before), rZK has great relevance to applications.Firstly, rZK protocols are closed under parallel and concurrent execution and thus are guaranteed to be secure when implemented in fully asynchronous networks, even if an adversary schedules the arrival of every message sent so as to foil security.Secondly, rZK protocols enlarge the range of physical ways in which provers of ZK protocols can be securely implemented, including devices which cannot reliably toss coins on line, nor keep state *A subset of this work is included in patent application [21].
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