Dakshita Khurana: Two-Message Non-Malleable Commitments

Speaker: Dakshita Khurana

Date: Friday, June 24, 2016

Time: 10:30 AM to 12:00 PM

Public: Yes

Location: Hewlett, G882

Event Type:

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Goodwin, 617 324 7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Dakshita Khurana: Two-Message Non-Malleable Commitments

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, in the synchronous setting.

Our protocol makes only black-box use of any non-interactive statistically binding commitment scheme. Such a scheme can be based on any one-to-one one-way function.
Our techniques depart significantly from the commit-challenge-response structure followed by nearly all prior works on non-malleable protocols in the standard model. Our methods are combinatorial in nature.
Our protocol resolves the round complexity of commitments with non-malleability with respect to opening via natural (non-embedding) black-box security reductions. We show that completely non-interactive non-malleable commitments w.r.t. opening cannot be proved secure via most natural black-box reductions. This result extends to also rule out bi-directional two-message non-malleable commitments w.r.t. opening in the synchronous or asynchronous setting.
We also demonstrate the utility of two round non-malleable commitments in obtaining round optimal multi-party protocols in the simultaneous message exchange model.
Our protocol, together with our impossibility result, also resolves the round complexity of block-wise non-malleable codes (Chandran et. al.) w.r.t. natural black-box reductions.

This is joint work with Vipul Goyal and Amit Sahai.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security (CIS) Seminar Series 2016.

Created by Deborah Goodwin Email at Tuesday, June 21, 2016 at 8:15 AM.