Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Non-Malleability, Constant-round,

Date: received 13 Sep 2010

Contact author: huijia at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20100914:011750 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]