Multi-trapdoor Commitments and their Applications to Non-Malleable Protocols*

Abstract We introduce the notion of multi-trapdoor commitments which is a stronger form of trapdoorcommitment schemes. We then construct two very efficient instantiations of multi-trapdoor commitment schemes, based on the Strong RSA Assumption and the recently introduced StrongDiffie-Hellman Assumption. The main applications of our result are non-malleable trapdoor commtiments and a compilerthat takes any proof of knowledge and transforms it into one which is secure against a concurrent man-in-the-middle attack. Such a proof of knowledge immediately yields concurrently secureidentification protocols. When using our number-theoretic istantiations, the non-malleable commitment and the com-piler are very efficient (require no more than four exponentiations). The latter also maintains the round complexity of the original proof of knowledge; it works in the common reference stringmodel, which in any case is necessary to prove security of proofs of knowledge under this kind of attacks. Compared to previously known efficient solutions, ours is a factor of two faster. 1 Introduction A commitment scheme is the cryptographic equivalent of an envelope. Consider the classic example of sealed bid auctions. Parties who want to bid on an item, place their bids in an envelope, in order to maintain secrecy until the end of the bidding period. At that time all bids are revealed by opening the envelopes, which in particular means that parties cannot alter bids at this point. A commitment scheme plays the role of the envelope: it's a cryptographic protocol composed of two phases: the committing phase and the opening phase. At the end of the first phase, a sender has committed to a message which however remains secret; in the opening phase the sender can only reveal that fixed message