In this paper we propose a new technique that allows us to construct a non-malleable protocol with only a single ``slot", and to improve in at least one aspect over each of the previously proposed protocols. Two direct byproducts of our new ideas are a four round non-malleable commitment and a four round non-malleable zero-knowledge argument, the latter matching the round complexity of the best known zero-knowledge argument (without the non-malleability requirement). The protocols are based on the existence of one-way functions and admit very efficient instantiations via standard homomorphic commitments and sigma protocols.
Our analysis relies on algebraic reasoning, and makes use of error correcting codes in order to ensure that committers' tags differ in many coordinates. One way of viewing our construction is as a method for combining many atomic sub-protocols in a way that simultaneously amplifies soundness and non-malleability, thus requiring much weaker guarantees to begin with, and resulting in a protocol which is much trimmer in complexity compared to the existing ones.Category / Keywords: cryptographic protocols / Non-Malleability, Commitments, Zero-Knowledge Original Publication (with major differences): FOCS 2014 Date: received 28 Jul 2014, last revised 15 Sep 2016 Contact author: silas richelson at gmail com Available format(s): PDF | BibTeX Citation Note: Revised version. The earlier version of this paper had claimed that our 4-round non-malleable commitment construction (see Section 6) extends to provide 4-round concurrent non-malleable commitments as well. This claim was incorrect and has been withdrawn. Getting 4-round concurrent non-malleable commitments is left as an open problem. Version: 20160915:132957 (All versions of this report) Short URL: ia.cr/2014/586 Discussion forum: Show discussion | Start new discussion