[LP11a] Constant-round non-malleable commitments from any one-way function

Authors: Huijia Lin, Rafael Pass | Venue: STOC 2011 | Source

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 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.

BibTeX

@Inproceedings{STOC:LinPas11,
  author = {Huijia Lin and Rafael Pass},
  title = {Constant-round non-malleable commitments from any one-way function},
  pages = {705--714},
  editor = {Lance Fortnow and Salil P. Vadhan},
  booktitle = {43rd Annual {ACM} Symposium on Theory of Computing},
  address = {San Jose, CA, USA},
  month = {jun~6--8},
  publisher = {{ACM} Press},
  year = {2011},
  doi = {10.1145/1993636.1993730},
}