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

Jisuanji gongcheng

Zero Knowledge Argument System in Bare Public Key Model Set

Yiming Zhao

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

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.

Related papers

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•12 citations

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

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 Cryptography in Constant Rounds - the Case of Zero Knowledge.

Yi Deng, Dengguo Feng, Vipul Goyal +3 more

A fundamental question in cryptography deals with understanding the role that randomness plays in cryptographic protocols and to what extent it is necessary. One particular line of works was initiated by Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) who introduced the notion of resettable zero-knowledge, where the protocol must be zeroknowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the setting where the verifier uses a fixed random tape in multiple interactions. Subsequent to these works, a number of papers studied the notion of resettable protocols in the setting where only one of the participating parties uses a fixed random tape multiple times. The notion of resettable security has been studied in two main models: the plain model and the bare public key model (also introduced in the above paper by Canetti et. al.). In a recent work, Deng, Goyal and Sahai (FOCS 2009) gave the first construction of a simultaneous resettable zero-knowledge protocol where both participants of the protocol can reuse a fixed random tape in any (polynomial) number of executions. Their construction however required O(nɛ) rounds of interaction between the prover and the verifier. Both in the plain as well as the BPK model, this construction remain the only known simultaneous resettable zero-knowledge protocols. In this work, we study the question of round complexity of simultaneous resettable zeroknowledge in the BPK model. We present a constant round protocol in such a setting based on standard cryptographic assumptions. Our techniques are significantly different from the ones used by Deng, Goyal and Sahai. 1

•Jan 1, 2011•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•4 citations
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.
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 .
A fundamental question in cryptography deals with understanding the role that randomness plays in cryptographic protocols and to what extent it is necessary. One particular line of works was initiated by Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) who introduced the notion of resettable zero-knowledge, where the protocol must be zeroknowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the setting where the verifier uses a fixed random tape in multiple interactions. Subsequent to these works, a number of papers studied the notion of resettable protocols in the setting where only one of the participating parties uses a fixed random tape multiple times. The notion of resettable security has been studied in two main models: the plain model and the bare public key model (also introduced in the above paper by Canetti et. al.). In a recent work, Deng, Goyal and Sahai (FOCS 2009) gave the first construction of a simultaneous resettable zero-knowledge protocol where both participants of the protocol can reuse a fixed random tape in any (polynomial) number of executions. Their construction however required O(nɛ) rounds of interaction between the prover and the verifier. Both in the plain as well as the BPK model, this construction remain the only known simultaneous resettable zero-knowledge protocols. In this work, we study the question of round complexity of simultaneous resettable zeroknowledge in the BPK model. We present a constant round protocol in such a setting based on standard cryptographic assumptions. Our techniques are significantly different from the ones used by Deng, Goyal and Sahai. 1
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.