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

Constant-round Non-Malleable Commitments from Any One-Way Function.

Huijia Lin, Rafael Pass

Published Jan 1, 2010• 0 citations
OpenAlex

Abstract

We show unconditionally that the existence of commitment schemes implies the existence of constant-round non-malleable commitments; earlier protocols required additional assumptions such as collision resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent non-malleability and robustness. As a corollary, we establish that constant-round non-malleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multi-party computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.

Related papers

Constant-round non-malleable commitments from any one-way function

Huijia Lin, Rafael Pass

We show unconditionally that the existence of commitment schemes implies the existence of constant-round non-malleable commitments; earlier protocols required additional assumptions such as collision resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent non-malleability and robustness. As a corollary, we establish that constant-round non-malleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multi-party computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.

ACM Symposium on Theory of Computing (STOC)•Jun 6, 2011•76 citations

Constant-Round Nonmalleable Commitments from Any One-Way Function

Huijia Lin, Rafael Pass

We show unconditionally that the existence of commitment schemes implies the existence of constant-round nonmalleable commitments; earlier protocols required additional assumptions such as collision-resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent nonmalleability and robustness. As a corollary, we establish that constant-round nonmalleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multiparty computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.

Journal of the ACM•Mar 2, 2015•10 citations

Constant Round Non-Malleable Protocols using One Way Functions.

Vipul Goyal

We provide the first constant round constructions of non-malleable commitment and zero-knowledge protocols based only on one-way functions. This improves upon several previous (incomparable) works which required either: (a) super-constant number of rounds, or, (b) non-standard or sub-exponential hardness assumptions, or, (c) non-black-box simulation and collision resistant hash functions. These constructions also allow us to obtain the first constant round multi-party computation protocol relying only on the existence of constant round oblivious transfer protocols. Our primary technique can be seen as a means of implementing the previous “two-slot simulation ” idea in the area of non-malleability with only black-box simulation. A simple modification of our commitment scheme gives a construction which makes use of the underlying one-way function in a black-box way. The modified construction satisfies the notion of what we call nonmalleability w.r.t. replacement. Non-malleability w.r.t. replacement is a slightly weaker yet natural notion of non-malleability which we believe suffices for many application of non-malleable commitments. We show that a commitment scheme which is non-malleable only w.r.t. replacement is sufficient to obtain a (fully) black-box multi-party computation protocol. This allows us to obtain a constant round multi-party computation protocol making only a black-box use of the standard cryptographic primitives with polynomial-time hardness thus directly improving upon the recent work of Wee (FOCS’10). 0 1

•Jan 1, 2010•0 citations

Constant round non-malleable protocols using one way functions

Vipul Goyal

We provide the first constant round constructions of non-malleable commitment and zero-knowledge protocols based only on one-way functions. This improves upon several previous (incomparable) works which required either: (a) super-constant number of rounds, or, (b) non-standard or sub-exponential hardness assumptions, or, (c) non-black-box simulation and collision resistant hash functions. These constructions also allow us to obtain the first constant round multi-party computation protocol relying only on the existence of constant round oblivious transfer protocols. Our primary technique can be seen as a means of implementing the previous "two-slot simulation" idea in the area of non-malleability with only black-box simulation.

ACM Symposium on Theory of Computing (STOC)•Jun 6, 2011•119 citations

New and improved constructions of non-malleable cryptographic protocols

Rafael Pass, Alon Rosen

We present a new constant round protocol for non-malleable zero-knowledge. Using this protocol as a subroutine, we obtain a new constant-round protocol for non-malleable commitments. Our constructions rely on the existence of (standard) collision resistant hash functions. Previous constructions either relied on the existence of trapdoor permutations and hash functions that are collision resistant against sub-exponential sized circuits, or required a super-constant number of rounds.Additional results are the first construction of a non-malleable commitment scheme that is statistically hiding (with respect to opening), and the first non-malleable protocols that satisfy a strict polynomial-time simulation requirement. The latter are constructed by additionally assuming the existence of trapdoor permutations.Our approach differs from the approaches taken in previous works in that we view non-malleable zero-knowledge as a building-block rather than an end goal. This gives rise to a modular construction of non-malleable commitments and results in a somewhat simpler analysis.The techniques that we use to construct our zero-knowl-edge protocol are non black-box, but are different than the non black-box techniques previously used in the context of non-malleable coin-tossing.

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•147 citations

New and Improved Constructions of Nonmalleable Cryptographic Protocols

Rafael Pass, Alon Rosen

We present a new constant-round protocol for nonmalleable zero-knowledge. Using this protocol as a subroutine, we obtain a new constant-round protocol for nonmalleable commitments. Our constructions rely on the existence of (standard) collision-resistant hash functions. Previous constructions either relied on the existence of trapdoor permutations and hash functions that are collision resistant against subexponential-sized circuits or required a superconstant number of rounds. Additional results are the first construction of a nonmalleable commitment scheme that is statistically hiding (with respect to opening) and the first nonmalleable commitments that satisfy a strict polynomial-time simulation requirement. Our approach differs from the approaches taken in previous works in that we view nonmalleable zero-knowledge as a building block rather than an end goal. This gives rise to a modular construction of nonmalleable commitments and results in a somewhat simpler analysis.

SIAM Journal on Computing•Jan 1, 2008•47 citations
We show unconditionally that the existence of commitment schemes implies the existence of constant-round non-malleable commitments; earlier protocols required additional assumptions such as collision resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent non-malleability and robustness. As a corollary, we establish that constant-round non-malleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multi-party computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.
We show unconditionally that the existence of commitment schemes implies the existence of constant-round non-malleable commitments; earlier protocols required additional assumptions such as collision resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent non-malleability and robustness. As a corollary, we establish that constant-round non-malleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multi-party computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.
We show unconditionally that the existence of commitment schemes implies the existence of constant-round nonmalleable commitments; earlier protocols required additional assumptions such as collision-resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent nonmalleability and robustness. As a corollary, we establish that constant-round nonmalleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multiparty computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.
We provide the first constant round constructions of non-malleable commitment and zero-knowledge protocols based only on one-way functions. This improves upon several previous (incomparable) works which required either: (a) super-constant number of rounds, or, (b) non-standard or sub-exponential hardness assumptions, or, (c) non-black-box simulation and collision resistant hash functions. These constructions also allow us to obtain the first constant round multi-party computation protocol relying only on the existence of constant round oblivious transfer protocols. Our primary technique can be seen as a means of implementing the previous “two-slot simulation ” idea in the area of non-malleability with only black-box simulation. A simple modification of our commitment scheme gives a construction which makes use of the underlying one-way function in a black-box way. The modified construction satisfies the notion of what we call nonmalleability w.r.t. replacement. Non-malleability w.r.t. replacement is a slightly weaker yet natural notion of non-malleability which we believe suffices for many application of non-malleable commitments. We show that a commitment scheme which is non-malleable only w.r.t. replacement is sufficient to obtain a (fully) black-box multi-party computation protocol. This allows us to obtain a constant round multi-party computation protocol making only a black-box use of the standard cryptographic primitives with polynomial-time hardness thus directly improving upon the recent work of Wee (FOCS’10). 0 1
We provide the first constant round constructions of non-malleable commitment and zero-knowledge protocols based only on one-way functions. This improves upon several previous (incomparable) works which required either: (a) super-constant number of rounds, or, (b) non-standard or sub-exponential hardness assumptions, or, (c) non-black-box simulation and collision resistant hash functions. These constructions also allow us to obtain the first constant round multi-party computation protocol relying only on the existence of constant round oblivious transfer protocols. Our primary technique can be seen as a means of implementing the previous "two-slot simulation" idea in the area of non-malleability with only black-box simulation.
We present a new constant round protocol for non-malleable zero-knowledge. Using this protocol as a subroutine, we obtain a new constant-round protocol for non-malleable commitments. Our constructions rely on the existence of (standard) collision resistant hash functions. Previous constructions either relied on the existence of trapdoor permutations and hash functions that are collision resistant against sub-exponential sized circuits, or required a super-constant number of rounds.Additional results are the first construction of a non-malleable commitment scheme that is statistically hiding (with respect to opening), and the first non-malleable protocols that satisfy a strict polynomial-time simulation requirement. The latter are constructed by additionally assuming the existence of trapdoor permutations.Our approach differs from the approaches taken in previous works in that we view non-malleable zero-knowledge as a building-block rather than an end goal. This gives rise to a modular construction of non-malleable commitments and results in a somewhat simpler analysis.The techniques that we use to construct our zero-knowl-edge protocol are non black-box, but are different than the non black-box techniques previously used in the context of non-malleable coin-tossing.
We present a new constant-round protocol for nonmalleable zero-knowledge. Using this protocol as a subroutine, we obtain a new constant-round protocol for nonmalleable commitments. Our constructions rely on the existence of (standard) collision-resistant hash functions. Previous constructions either relied on the existence of trapdoor permutations and hash functions that are collision resistant against subexponential-sized circuits or required a superconstant number of rounds. Additional results are the first construction of a nonmalleable commitment scheme that is statistically hiding (with respect to opening) and the first nonmalleable commitments that satisfy a strict polynomial-time simulation requirement. Our approach differs from the approaches taken in previous works in that we view nonmalleable zero-knowledge as a building block rather than an end goal. This gives rise to a modular construction of nonmalleable commitments and results in a somewhat simpler analysis.