Non-Malleable Commitments using Goldreich-Levin List Decoding

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

Authors

• Vipul Goyal
• Silas Richelson

Keywords

• Protocols
• Prediction algorithms
• Cryptography
• Receivers
• Standards
• Decoding
• List Decoding
• One-way Function
• Interactive
• Running Time
• Unit Vector
• Parametrized
• Inverter
• Head And Tail
• Probability 1
• Multi-party Computation
• Security Parameter
• Security Proof
• Random Bits
• Number Of Strings
• Random String
• Properties Hold
• Zero-knowledge Proof
• cryptographic protocols, non-malleable commitments, Goldreich-Levin Decoding