Paper 2017/291

How to Achieve Non-Malleability in One or Two Rounds

Dakshita Khurana and Amit Sahai

Abstract

Despite over 25 years of research on non-malleable commitments in the plain model, their round complexity has remained open. The goal of achieving non-malleable commitment protocols with only one or two rounds has been especially elusive. Pass (TCC 2013, CC 2016) 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 sub-exponential assumptions. We show that this belief was false. Indeed, we obtain the following positive results: - We construct the first two-message non-malleable commitments satisfying the strong definition of non-malleability with respect to commitment, assuming standard sub-exponential assumptions, namely: sub-exponentially hard one-way permutations, sub-exponential ZAPs, and sub-exponential DDH. Furthermore, our protocol is public-coin. - We also obtain two-message private-coin non-malleable commitments with respect to commitment, assuming only sub-exponentially hard DDH or QR or N^{th}-residuosity. - We bootstrap the above protocols (under the same assumptions) to obtain constant bounded-concurrent non-malleability while preserving round complexity. - We compile the above protocols to obtain, in the simultaneous messages model, the first {\em one-round} non-malleable commitments, with full concurrent security respect to opening, under standard sub-exponential assumptions. 1. 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. 2. As an application of this result, in the simultaneous exchange model, we obtain the first two-round multi-party pseudorandom coin-flipping. We believe that our protocols are likely to find several additional applications. - In order to obtain our results, we develop several tools and techniques that may be of independent interest. 1. We give the first two-round black-box rewinding strategy based on standard sub-exponential assumptions, in the plain model. 2. We also develop the first two-message zero-knowledge arguments with strong super-polynomial simulation. 3. Finally, we give a two-round tag amplification technique for non-malleable commitments, that amplifies a 4-tag scheme to a scheme for all tags, while only relying on sub-exponential DDH. This includes a more efficient alternative to the DDN encoding.