Paper 2010/483

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

Huijia Lin, Rafael Pass

Abstract

We show \emph{unconditionally} that the existence of commitment schemes implies the existence of \emph{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.