Two-Message Non-Malleable Commitments
Dakshita Khurana

Abstract:

We construct two-message non-malleable commitments with respect to opening in the standard model, assuming only one-to-one one-way functions. Our protocol consists of two unidirectional 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 2 rounds of communication, cannot be proved secure via a black-box reduction to any "standard" intractability assumption. We extend this by showing a similar impossibility result for commitments with non-malleability with respect to opening, another standard notion of non-malleability for commitments, for any 2-message challenge-response protocol, as well.

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

This is joint work with Vipul Goyal and Amit Sahai.