Non-malleable commitments are a fundamental cryptographic tool for preventing (concurrent) man-in-the-middle attacks. Since their invention by Dolev, Dwork, and Naor in 1991, their round-complexity has been extensively studied, leading up to constant-round protocols based on one-way functions (OWFs), and three-round protocols based on sub-exponential OWFs, and standard polynomial-time hardness assumptions such as decisional Diffie--Hellman (DDH) and ZAPs (i.e., two-round witness-indistinguishable proofs). But constructions of two-round, or non-interactive, non-malleable commitments have so far remained elusive; the only known construction relied on a strong and non-falsifiable assumption with a non-malleability flavor. Additionally, a recent result by Pass shows the impossibility of basing two-round non-malleable commitments on falsifiable assumptions using a polynomial-time black-box security reduction. In this work, we show how to overcome this impossibility using super-polynomial-time hardness assumptions. Our main result demonstrates the existence of two-round concurrent non-malleable commitments based on the following four primitives (all with sub-exponential security): (1) non-interactive commitments, (2) ZAPs (i.e., 2-round witness indistinguishable proofs), (3) collision-resistant hash functions, and (4) a “weak” time-lock puzzle. Primitives (1), (2), and (3) can be based on, e.g., the discrete log and the RSA assumption. Time-lock puzzles---puzzles that can be solved by “brute-force” in time $2^t$ , but cannot be solved significantly faster even using parallel computers---were proposed by Rivest, Shamir, and Wagner in 1996 and have been extensively studied since. We additionally obtain a non-interactive (i.e., one-message) version of our protocol satisfying concurrent non-malleability w.r.t. uniform attackers and show that our non-malleable commitments satisfy an even stronger notion of chosen commitment attack security.Non-malleable commitments are a fundamental cryptographic tool for preventing (concurrent) man-in-the-middle attacks. Since their invention by Dolev, Dwork, and Naor in 1991, their round-complexity has been extensively studied, leading up to constant-round protocols based on one-way functions (OWFs), and three-round protocols based on sub-exponential OWFs, and standard polynomial-time hardness assumptions such as decisional Diffie--Hellman (DDH) and ZAPs (i.e., two-round witness-indistinguishable proofs). But constructions of two-round, or non-interactive, non-malleable commitments have so far remained elusive; the only known construction relied on a strong and non-falsifiable assumption with a non-malleability flavor. Additionally, a recent result by Pass shows the impossibility of basing two-round non-malleable commitments on falsifiable assumptions using a polynomial-time black-box security reduction. In this work, we show how to overcome this impossibility using super-polynomial-time hardness assumptions. Our main result demonstrates the existence of two-round concurrent non-malleable commitments based on the following four primitives (all with sub-exponential security): (1) non-interactive commitments, (2) ZAPs (i.e., 2-round witness indistinguishable proofs), (3) collision-resistant hash functions, and (4) a “weak” time-lock puzzle. Primitives (1), (2), and (3) can be based on, e.g., the discrete log and the RSA assumption. Time-lock puzzles---puzzles that can be solved by “brute-force” in time $2^t$, but cannot be solved significantly faster even using parallel computers---were proposed by Rivest, Shamir, and Wagner in 1996 and have been extensively studied since. We additionally obtain a non-interactive (i.e., one-message) version of our protocol satisfying concurrent non-malleability w.r.t. uniform attackers and show that our non-malleable commitments satisfy an even stronger notion of chosen commitment attack security.

SIAM Journal on ComputingJan 1, 20203 citations

A Perfectly Binding Commitment Scheme Against Quantum Attacks.

Bing Zeng, Liang Chen, Xueming Tang

Jan 1, 20110 citations

Quantum Non-malleability and Authentication

Gorjan Alagic, Christian Majenz

arXiv:1610.04214Lecture notes in computer scienceJan 1, 201719 citations

Non-interactive and Non-malleable Commitment Scheme Based on Lattice

Xia Feng

NTRU is a well-known public-key cryptosystem based on the difficulty of lattice reduction problems,and is mainly applied in public-key encryption and digital signature.This paper constructed a non-interactive and non-malleable commitment scheme,which relies the security on the intractable CVP on lattice,and the binding property of committer is satisfied.The validity of commitment is verified by hash function's collision resistance.Perturbing the plaintext with randomized mapping,plaintext will be in random distribution,and this scheme satisfies the hiding property of verifier and is non-malleable with respect to decommitment.This scheme has high efficiency as well as NTRU,and can resist channel eavesdropping attack,message replay attack and copying commitment attack.NTRU is a well-known public-key cryptosystem based on the difficulty of lattice reduction problems,and is mainly applied in public-key encryption and digital signature.This paper constructed a non-interactive and non-malleable commitment scheme,which relies the security on the intractable CVP on lattice,and the binding property of committer is satisfied.The validity of commitment is verified by hash function's collision resistance.Perturbing the plaintext with randomized mapping,plaintext will be in random distribution,and this scheme satisfies the hiding property of verifier and is non-malleable with respect to decommitment.This scheme has high efficiency as well as NTRU,and can resist channel eavesdropping attack,message replay attack and copying commitment attack.

Jan 1, 20120 citations

Attacking post-quantum cryptography

Leon Groot Bruinderink

Dec 17, 20190 citations

Based on RSA and Factoring

Chunhui Wu, Qin Li, Dongyang Long

Abstract—Non-malleability is an important property in commitment schemes. It can resist to the person-in-the-middle (PIM) attacks within the interaction. In this paper, we focus on the non-malleability in ID-based trapdoor commitments. We first give two constructions of (full) ID-based trapdoor commitment schemes based on RSA and Factoring assumptions respectively and then extend them to non-malleable schemes. The formal proofs show that our proposed schemes satisfy all the desired security properties.Abstract—Non-malleability is an important property in commitment schemes. It can resist to the person-in-the-middle (PIM) attacks within the interaction. In this paper, we focus on the non-malleability in ID-based trapdoor commitments. We first give two constructions of (full) ID-based trapdoor commitment schemes based on RSA and Factoring assumptions respectively and then extend them to non-malleable schemes. The formal proofs show that our proposed schemes satisfy all the desired security properties.

Jan 1, 20150 citations

2^t

, but cannot be solved significantly faster even using parallel computers---were proposed by Rivest, Shamir, and Wagner in 1996 and have been extensively studied since. We additionally obtain a non-interactive (i.e., one-message) version of our protocol satisfying concurrent non-malleability w.r.t. uniform attackers and show that our non-malleable commitments satisfy an even stronger notion of chosen commitment attack security.