[GR19] Non-Malleable Commitments using Goldreich-Levin List Decoding

Authors: Vipul Goyal, Silas Richelson | Venue: FOCS 2019 | Source

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.

BibTeX

@Inproceedings{FOCS:GoyRic19,
  author = {Vipul Goyal and Silas Richelson},
  title = {Non-Malleable Commitments using {Goldreich}-{Levin} List Decoding},
  pages = {686--699},
  editor = {David Zuckerman},
  booktitle = {60th Annual Symposium on Foundations of Computer Science},
  address = {Baltimore, MD, USA},
  month = {nov~9--12},
  publisher = {{IEEE} Computer Society Press},
  year = {2019},
  doi = {10.1109/FOCS.2019.00047},
}