Dakshita Khurana: On Removing Interaction in Non-Malleable Commitments

Abstract: Non-malleable commitments guarantee that a man-in-the-middle adversary cannot modify a commitment to a secret plaintext to obtain a different commitment to a related plaintext. These prevent an adversary from using information in a subprotocol or in one protocol session to mount an attack on another. They are an important component of various multi-party protocols including coin-flipping, auctions and general-purpose MPC. Because of their wide applicability, there has been a long line of research aiming to understand the amount of interaction and the hardness assumptions required to obtain non-malleable commitments. 

 

Can non-malleable commitments exist that need no interaction beyond a one-shot message from the committer to the receiver? Strong impossibility results in the literature suggested that these objects would be difficult to construct based on falsifiable assumptions. However, recently developed techniques have enabled constructions of non-interactive non-malleable commitments from different sets of well-studied cryptographic assumptions. These include new black-box constructions as well as constructions from indistinguishability obfuscation. 

 

All existing works that build non-interactive non-malleable commitments proceed in two steps. First, they construct "base" schemes that only support a small number of tags or identities, and next they amplify these schemes to obtain commitments supporting a small space of tags into commitments that support a much larger tag space. The amplification step, which will be the focus of this talk, has intrinsic connections with non-interactive privacy-preserving proofs of consistency. We will discuss two new methods to enable such proofs. 

 

The first relies on hinting PRGs that were introduced in a recent work of Koppula and Waters in the context of CCA secure encryption, and makes black-box use of the base scheme.

 

The second develops and makes use of a new type of proof: a non-interactive distributionally indistinguishable proof system (NIDI), which overcomes a significant drawback of NIWIs, namely, the lack of a meaningful secrecy guarantee when proving statements about languages with a unique witness. 

 

This talk is based in part on joint work with Rachit Garg, George Lu and Brent Waters.