Sunoo Park: New Constructions of Non-Malleable Commitments and Applications

Abstract: Non-malleable commitments (NMC) are fundamental cryptographic
primitives.  Since their conception by Dolev, Dwork and Naor (STOC 91),
numerous applications of NMC have been discovered including
round-efficient MPC.  Recently Goyal, Pandey and Richelson (STOC 16)
constructed round optimal non-malleable commitments using a connection
to split-state non-malleable codes.  However, this connection was not
general; it relied on specific properties of the inner-product code of
Aggarwal et al. (STOC 14).  As such, the resulting non-malleable
commitments suffer from high communication complexity and are not secure
against an adversary who launches a concurrent attack.  Both drawbacks
significantly limit the utility of the construction of Goyal et al.

Recently there has been exciting new constructions of two-source
non-malleable extractors; objects which are known to imply split-state
non-malleable codes.  Chattopadhyay, Goyal and Li (STOC 16) and Li (ECCC
16) construct two-source non-malleable extractors which provide
significant improvements to the concurrent security and rate of the
codes of Aggarwal et al.

In this work we revisit the construction of Goyal et al. and make three
contributions:

* We identify a natural property of a strong two-source non-malleable
extractor called efficient conditional preimage sampling which makes it
sufficient for round optimal non-malleable commitments.  Thus we make
the compiler of Goyal et al. more modular, so new advances in
non-malleable extractors will lead to advances in non-malleable commitments.
* We prove that the recent non-malleable extractor of Li supports
efficient conditional preimage sampling and so get a new construction of
non-malleable commitments.  The basic version of this construction,
which is non-malleable against a synchronizing adversary, has only three
rounds of interaction and has quasi-optimal communication complexity.
This improves drastically upon all previous schemes for non-malleable
commitment.
* We prove also that the non-malleable extractor of Chattopadhyay et al.
supports efficient conditional preimage sampling, and so get another new
construction of round-optimal non-malleable commitment.  This time our
scheme satisfies a weaker notion of non-malleability (known as
non-malleability wrt replacement) in the much more demanding bounded
concurrency setting.  We then show that this weaker notion suffices for
the main application of NMC to round-efficient MPC by giving a (four
round) round-optimal multi-party coin flipping protocol.  Using the
compiler of Garg, Mukherjee, Pandey and Polychroniadou (EUROCRYPT 16) we
obtain several round efficient protocols for general MPC based on
various assumptions.  Previous round optimal coin flipping protocols
relied on the non-standard assumption that adaptive one-way functions exist.

Joint work with Vipul Goyal, Ashutosh Kumar, Silas Richelson, and
Akshayaram Srinivasan.