Paper 2003/214

Multi-Trapdoor Commitments and their Applications to Non-Malleable Protocols

Rosario Gennaro


We introduce the notion of multi-trapdoor commitments which is a stronger form of trapdoor commitment schemes. We then construct two very efficient instantiations of multi-trapdoor commitment schemes, based on the Strong RSA Assumption and the recently introduced Strong Diffie-Hellman Assumption. The main applications of our result are non-malleable trapdoor commtiments and a compiler} that 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 secure identification protocols. When using our number-theoretic istantiations, the non-malleable commitment and the compiler 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 string model, 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Preliminary version in Crypto 2004
Contact author(s)
rosario @ watson ibm com
2004-11-26: last of 9 revisions
2003-10-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rosario Gennaro},
      title = {Multi-Trapdoor Commitments and their Applications to Non-Malleable Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2003/214},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.