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

Category / Keywords: cryptographic protocols / non-malleable commitments, extractable commitments, Goldreich-Levin theorem

Original Publication (with minor differences): FOCS 2019

Date: received 13 Oct 2019

Contact author: vipul at cs cmu edu, silas at cs ucr edu

Available format(s): PDF | BibTeX Citation

Version: 20191015:074712 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]