Non-malleability is an important security property of commitment schemes. The property means security against the man-in-the-middle attack, and it is defined and proved in the simulation paradigm using the corresponding simulator. Many known non-malleable commitment schemes have the common drawback that their corresponding simulators do not work in a straight-line manner, requires rewinding of the adversary. Due to this fact, such schemes are proved non-malleable only in the stand-alone cases. In the multiple-instances setting, i.e., when the scheme is performed concurrently with many instances of itself, such schemes cannot be proved non-malleable. The paper shows an efficient commitment scheme proven to be non-malleable even in the multiple-instances setting, based on the KEA1 and DDH assumptions. Our scheme has a simulator that works in a straight-line manner by using the KEA1-extractor instead of the rewinding strategy.
Non-malleability is an important security property of commitment schemes. The property means security against the man-in-the-middle attack, and it is defined and proved in the simulation paradigm using the corresponding simulator. Many known non-malleable commitment schemes have the common drawback that their corresponding simulators do not work in a straight-line manner, requires rewinding of the adversary. Due to this fact, such schemes are proved non-malleable only in the stand-alone cases. In the multiple-instances setting, i.e., when the scheme is performed concurrently with many instances of itself, such schemes cannot be proved non-malleable. The paper shows an efficient commitment scheme proven to be non-malleable even in the multiple-instances setting, based on the KEA1 and DDH assumptions. Our scheme has a simulator that works in a straight-line manner by using the KEA1-extractor instead of the rewinding strategy.
We present a non-malleable commitment scheme that retains its security properties even when concurrently executed a polynomial number of times. That is, a man-in-the-middle adversary who is simultaneously participating in multiple concurrent commitment phases of our scheme, both as a sender and as a receiver cannot make the values he commits to depend on the values he receives commitments to. Our result is achieved without assuming an a-priori bound on the number of executions and without relying on any set-up assumptions. Our construction relies on the existence of standard collision resistant hash functions and only requires a constant number of communication rounds.
Commitment schemes are fundamental building blocks in cryptography, and have wide applications in constructing various protocols. Non-malleable commitment considers concurrent executions of a commitment scheme against a man-in-the-middle adversary. In this paper, we investigate non-malleability of statistically hiding commitment schemes, and present the first concurrent non-malleable statistically hiding commitment scheme. Our protocol admits black-box simulation, and relies on the robust (stand-alone) non-malleable commitment and specially designed witness indistinguishable proofs to achieve concurrent non-malleability. Based on the one-way function assumption, the commit phase of our protocol needs polynomial rounds, and the decommit phase needs super-logarithmic 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 nonmalleable 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 Nth-residuosity.; We bootstrap the above protocols (under the same assumptions) to obtain two round constant boundedconcurrent non-malleable commitments. In the simultaneous message model, we obtain unbounded concurrent non-malleability in two rounds.; In the simultaneous messages model, we obtain oneround 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.
Abstract—Non-malleability is an important property in commitment schemes. It can resist to the person-in-the-middle (PIM) attacks within the interaction. In this paper, we focus on the non-malleability in ID-based trapdoor commitments. We first give two constructions of (full) ID-based trapdoor commitment schemes based on RSA and Factoring assumptions respectively and then extend them to non-malleable schemes. The formal proofs show that our proposed schemes satisfy all the desired security properties.
We propose the first black-box construction of non-malleable commitments according to the standard notion of non-malleability with respect to commitment. Our construction additionally only requires a constant number of rounds and is based only on (black-box use of) one-way functions. Prior to our work, no black-box construction of non-malleable commitments was known (except for relaxed notions of security) in any (polynomial) number of rounds based on any cryptographic assumption. This closes the wide gap existent between black-box and non-black-box constructions for the problem of non-malleable commitments. Our construction relies on (and can be seen as a generalization of) the recent non-malleable commitment scheme of Goyal (STOC 2011). We also show how to get black-box constructions for a host of other cryptographic primitives. We extend our construction to get constant-round concurrent non-malleable commitments, constant-round multi-party coin tossing, and non-malleable statistically hiding commitments (satisfying the notion of non-malleability with respect to opening). All of the mentioned results make only a black-box use of one-way functions. Our primary technical contribution is a novel way of implementing the proof of consistency typically required in the constructions of non-malleable commitments (and other related primitives). We do this by relying on ideas from the ``zero-knowledge from secure multi-party computation" paradigm of Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). We extend in a novel way this ``computation in the head" paradigm (which can be though of as bringing powerful error-correcting codes into purely computational setting). To construct a non-malleable commitment scheme, we apply our computation in the head techniques to the recent (constant-round) construction of Goyal. Along the way, we also present a simplification of the construction of Goyal where a part of the protocol is implemented in an information theoretic manner. Such a simplification is crucial for getting a black-box construction. This is done by making use of pair wise-independent hash functions and strong randomness extractors. We show that our techniques have multiple applications, as elaborated in the paper. Hence, we believe our techniques might be useful in other settings in future.
Non-malleable commitment is one of the most fundamental cryptographic primitives in that it is often used as a basic building block in modern cryptography. Briefly, a commitment scheme allows a sender to commit to a value while keeping the value secret from the receiver. In addition, when the commitment is opened in a later stage, the scheme guarantees that the sender can reveal only the unique value being committed to in the previous stage. A commitment scheme is said to be non-malleable if no adversary can succeed in committing to a related massage m', after seeing a commitment of a message m. In this dissertation, we study the construction of non-malleable commitments and some of their applications.A black-box construction of non-malleable commitment is presented in the first part of this dissertation. Our protocol requires only a constant number of rounds and satisfies the standard notion of non-malleability w.r.t. commitment. Our technique is based on ideas from the ``zero-knowledge from secure multi-party computation'' paradigm by Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). Furthermore, our construction only uses one-way functions as a black-box and thus does not depend on the actual implementation details of the functions. Prior to our result, under the standard notion of security, no black-box construction of constant-round non-malleable commitment was known. Hence, our main result closes the gap between black-box and non-black-box constructions for the problem of non-malleable commitment.In the second part of this dissertation, we show that our technique can be applied to multiple applications. Specifically, we extend our work to obtain a constant-round concurrent non-malleable commitment, a constant-round multi-party parallel coin tossing, and a non-malleable statistically hiding commitment (according to the notion of non-malleability w.r.t. opening.) Additionally, all results mentioned above are based only on a black-box use of one-way functions.