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

arXiv:cs/0609057

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

Yi Deng, Giovanni Di Crescenzo, Dongdai Lin

Published Sep 12, 2006• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.cs/0609057

Related papers

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 Concurrent NMWI and its relation to NMZK

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

One of the central questions in Cryptography is to design round-efficient protocols that are secure under man-in-the-middle attacks. In this paper we introduce and study the notion of non-malleable witness indistinguishability (NMWI) and examine its relation with the classic notion of non-malleable zero knowledge (NMZK). Indeed, despite tremendous applicability of witness indistinguishability, while a lot of attention has been given to NMZK, very little attention has been given to witness indistinguishability in case of man-in-the-middle attacks. We initiate this study, with several (perhaps somewhat surprising) results: • We give the first definition of NMWI proof systems. Just like every NMZK proof is a zero-knowledge proof which aims to attain a very strong proof independence property, we require (and formalize) the notion that every NMWI proof is a witness indistinguishable proof system which enjoys a very strong witness independence property against any man-in-the-middle attack. • We show the existence of a constant-round NMWI argument system for NP in the standard model (i.e. without any trusted or any other setup assumptions).

•Jan 1, 2006•7 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

Concurrent Non-Malleable Zero Knowledge

Boaz Barak, Manoj Prabhakaran, Amit Sahai

We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowledge protocol Pi such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of Pi, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities {including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties' inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC2004). We obtain an Otilde(n) -round protocol under the assumption that one-to-one one-way functions exist. This can be improved to Otilde(k log n) rounds under the assumption that there exist k-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol

Annual Symposium on Foundations of Computer Science•Oct 1, 2006•86 citations

Concurrent Non-Malleable Zero Knowledge.

Boaz Barak, Manoj Prabhakaran, Amit Sahai

We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language inNP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowl-edge protocol Π such that for every polynomial-time adver-sary that can adaptively and concurrently schedule polyno-mially many executions of Π, and corrupt some of the ver-ifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all state-ments proven by a corrupt prover to an honest verifier. Our security model is the traditional model for concur-rent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the state-ments adaptively. We also prove that there exists some func-tionality F (a combination of zero knowledge and obliv-ious transfer) such that it is impossible to obtain a con-current non-malleable protocol for F in this model. Pre-vious impossibility results for composable protocols ruled out existence of protocols for a wider class of functionali-ties (including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties ’ inputs in each execution are cho-sen adaptively based on the results of previous executions

•Jan 1, 2006•4 citations

Concurrent non-malleable zero-knowledge and simultaneous resettable non-malleable zero-knowledge in constant rounds

Zhenbin Yan, Yi Deng, Yiru Sun

Concurrent non-malleable zero-knowledge ( CNMZK ) considers the concurrent execution of zero-knowledge protocols in a setting even when adversaries can simultaneously corrupt multiple provers and verifiers. As far as we know, the round complexity of all the constructions of CNMZK arguments for NP is at least ω (log n ). In this paper, we provide the first construction of a constant-round concurrent non-malleable zero-knowledge argument for every language in NP . Our protocol relies on the existence of families of collision-resistant hash functions , one-way permutations and indistinguishability obfuscators . As an additional contribution, we study the composition of two central notions in zero knowledge, the simultaneously resettable zero-knowledge and non-malleable zero-knowledge , which seemingly have stronger proved security guarantees. We give the first construction of a constant-round simultaneously-resettable non-malleable zero-knowledge . To the best of our knowledge, this is the first study to combine the two security concepts described above together in the zero-knowledge protocols.

Cybersecurity•Sep 29, 2018•2 citations
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.
One of the central questions in Cryptography is to design round-efficient protocols that are secure under man-in-the-middle attacks. In this paper we introduce and study the notion of non-malleable witness indistinguishability (NMWI) and examine its relation with the classic notion of non-malleable zero knowledge (NMZK). Indeed, despite tremendous applicability of witness indistinguishability, while a lot of attention has been given to NMZK, very little attention has been given to witness indistinguishability in case of man-in-the-middle attacks. We initiate this study, with several (perhaps somewhat surprising) results: • We give the first definition of NMWI proof systems. Just like every NMZK proof is a zero-knowledge proof which aims to attain a very strong proof independence property, we require (and formalize) the notion that every NMWI proof is a witness indistinguishable proof system which enjoys a very strong witness independence property against any man-in-the-middle attack. • We show the existence of a constant-round NMWI argument system for NP in the standard model (i.e. without any trusted or any other setup assumptions).
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
We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowledge protocol Pi such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of Pi, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities {including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties' inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC2004). We obtain an Otilde(n) -round protocol under the assumption that one-to-one one-way functions exist. This can be improved to Otilde(k log n) rounds under the assumption that there exist k-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol
We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language inNP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowl-edge protocol Π such that for every polynomial-time adver-sary that can adaptively and concurrently schedule polyno-mially many executions of Π, and corrupt some of the ver-ifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all state-ments proven by a corrupt prover to an honest verifier. Our security model is the traditional model for concur-rent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the state-ments adaptively. We also prove that there exists some func-tionality F (a combination of zero knowledge and obliv-ious transfer) such that it is impossible to obtain a con-current non-malleable protocol for F in this model. Pre-vious impossibility results for composable protocols ruled out existence of protocols for a wider class of functionali-ties (including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties ’ inputs in each execution are cho-sen adaptively based on the results of previous executions
Concurrent non-malleable zero-knowledge ( CNMZK ) considers the concurrent execution of zero-knowledge protocols in a setting even when adversaries can simultaneously corrupt multiple provers and verifiers. As far as we know, the round complexity of all the constructions of CNMZK arguments for NP is at least ω (log n ). In this paper, we provide the first construction of a constant-round concurrent non-malleable zero-knowledge argument for every language in NP . Our protocol relies on the existence of families of collision-resistant hash functions , one-way permutations and indistinguishability obfuscators . As an additional contribution, we study the composition of two central notions in zero knowledge, the simultaneously resettable zero-knowledge and non-malleable zero-knowledge , which seemingly have stronger proved security guarantees. We give the first construction of a constant-round simultaneously-resettable non-malleable zero-knowledge . To the best of our knowledge, this is the first study to combine the two security concepts described above together in the zero-knowledge protocols.