Settling the Round-Complexity of Non-Malleable Commitments

Abstract

We show \emph{unconditionally} that the existence of commitment schemes implies the existence of \emph{constant-round} non-malleable commitments; earlier protocol required additional assumptions such as collision resistant hashfunctions 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 secure multi-party computation can be based on only enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.