Rosario Gennaro, IBM T. J. Watson Research Center

We introduce the notion of multi-trapdoor commitments which is a stronger form of trapdoor commitment schemes. We then construct a very efficient instantiation of a multi-trapdoor commitment scheme, based on the Strong RSA Assumption.

The main application of our result is the construction of a compiler that takes any proof of knowledge and transforms it into one which is secure against a concurrent man-in-the-middle attack.

When using our Strong RSA construction of multi-trapdoor commitments, this compiler is very efficient (requires no more than four exponentiations) and 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.

Efficient solutions were known only for proofs of knowledge for some specific language, while our transformation works over any proof. Moreover, compared to previously known efficient proofs, our solution is a factor of eight more efficient in computation.

The main practical applications of our results are concurrently secure identification and deniable authentication protocols. For these applications our results are the first simple and efficient solutions based on the Strong RSA Assumption.

Co-sponsored by Laboratory for Secure Systems, New Jersey Institute for Trustworthy Enterprise Software, and the PORTIA project.