Breaking the Three Round Barrier for Non-malleable Commitments

We construct two-message non-malleable commitments with respect to opening in the standard model, assuming one-to-one one-way functions. Our protocol consists of two uni-directional messages by the committer (with no message from the receiver), and is secure against all polynomial-time adversaries in the standard synchronous setting.

Pass (TCC 2013) proved that any commitment scheme with non-malleability with respect to commitment, using only two messages of communication, cannot be proved secure via a black-box reduction to any "standard" intractability assumption. We extend this by showing a similar implausibility for two-message bi-directional commitments with non-malleability with respect to opening, another standard notion of non-malleability for commitments.

However, somewhat surprisingly, we show that this barrier breaks down in the synchronous setting, with two unidirectional messages by the committer (and no receiver message), for non-malleability with respect to opening. 

 

Our techniques are combinatorial, and depart significantly from the commit-challenge-response structure followed by nearly all prior works on non-malleable protocols in the standard model. Our protocol, together with our implausibility result, also resolves the round complexity of block-wise non-malleable codes (Chandran et. al., ICALP 2016) w.r.t. most natural black-box reductions.