Paper 2019/1195

Non-Malleable Commitments Using Goldreich-Levin List Decoding

Vipul Goyal and Silas Richelson

Abstract

We give the first construction of three-round non-malleable commitments from the almost minimal assumption of injective one-way functions. Combined with the lower bound of Pass (TCC 2013), our result is almost the best possible w.r.t. standard polynomial-time hardness assumptions (at least w.r.t. black-box reductions). Our results rely on a novel technique which we call bidirectional Goldreich-Levin extraction. Along the way, we also obtain the first rewind secure delayed-input witness indistinguishable (WI) proofs from only injective one-way functions. We also obtain the first construction of a distributionally extractable commitment scheme from injective one-way functions. We believe both of these to be of independent interest. In particular, as a direct corollary of our rewind secure WI construction, we are able to obtain a construction of 3-round promise zero-knowledge from only injective one-way functions.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.FOCS 2019
Keywords
non-malleable commitmentsextractable commitmentsGoldreich-Levin theorem
Contact author(s)
vipul @ cs cmu edu
silas @ cs ucr edu
History
2019-10-15: received
Short URL
https://ia.cr/2019/1195
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1195,
      author = {Vipul Goyal and Silas Richelson},
      title = {Non-Malleable Commitments Using Goldreich-Levin List Decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1195},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1195}},
      url = {https://eprint.iacr.org/2019/1195}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.