How to achieve non-malleability in one or two rounds

Non-malleable commitments, introduced by Dolev, Dwork and Naor (STOC 1991), are a fundamental cryptographic primitive, and their round complexity has been a subject of great interest. And yet, the goal of achieving non-malleable commitments with only one or two rounds} has been elusive. Pass (TCC 2013) captured this difficulty by proving important impossibility results regarding two-round non-malleable commitments. This led to the widespread belief that achieving two-round non-malleable commitments was impossible from standard assumptions. We show that this belief was false. Indeed, we obtain the following positive results: We construct two-message non-malleable commitments satisfying non-malleability with respect to commitment, based on standard sub-exponential assumptions, namely: Sub-exponential one-way permutations, sub-exponential ZAPs, and sub-exponential DDH. Furthermore, our protocol is public-coin}. We obtain two-message private-coin} non-malleable commitments with respect to commitment, assuming only sub-exponential DDH or QR or N^{th}-residuosity. We bootstrap the above protocols (under the same assumptions) to obtain two round constant bounded-concurrent non-malleable commitments. In the simultaneous message model, we obtain unbounded concurrent non-malleability in two rounds. In the simultaneous messages model, we obtain one-round} non-malleable commitments, with unbounded concurrent security with respect to opening, under standard sub-exponential assumptions.- This implies non-interactive non-malleable commitments with respect to opening, in a restricted model with a broadcast channel, and a-priori bounded polynomially many parties such that every party is aware of every other party in the system. To the best of our knowledge, this is the first protocol to achieve completely non-interactive non-malleability in any plain model setting from standard assumptions.- As an application of this result, in the simultaneous exchange model, we obtain two-round multi-party pseudorandom coin-flipping. We construct two-message zero-knowledge arguments with super-polynomial strong} simulation (SPSS-ZK), which also serve as an important tool for our constructions of non-malleable commitments. In order to obtain our results, we develop several techniques that may be of independent interest.- We give the first two-round black-box rewinding strategy based on standard sub-exponential assumptions, in the plain model.- We also give a two-round tag amplification technique for non-malleable commitments, that amplifies a 4-tag scheme to a scheme for all tags, while relying on sub-exponential DDH. This includes a more efficient alternative to the DDN encoding.The full version of this paper is available online at: Https://eprint.iacr.org/2017/291.pdf.