Marc Fischlin's Ph.D. Thesis

Research Group of Prof.C.P.Schnorr, University of Frankfurt am Main

Trapdoor Commitment Schemes and Their Applications

Dissertation zur Erlangung des Doktorgrades der Naturwissenschaften
Fachbereich Mathematik der Johann Wolfgang Goethe-Universität
von Marc Fischlin



Informally, commitment schemes can be described by lockable steely boxes. In the commitment phase, the sender puts a message into the box, locks the box and hands it over to the receiver. On one hand, the receiver does not learn anything about the message. On the other hand, the sender cannot change the message in the box anymore. In the decommitment phase the sender gives the receiver the key, and the receiver then opens the box and retrieves the message. One application of such schemes are digital auctions where each participant places his secret bid into a box and submits it to the auctioneer.

In this thesis we investigate trapdoor commitment schemes. Following the abstract viewpoint of lockable boxes, a trapdoor commitment is a box with a tiny secret door. If someone knows the secret door, then this person is still able to change the committed message in the box, even after the commitment phase. Such trapdoors turn out to be very useful for the design of secure cryptographic protocols involving commitment schemes.

In the first part of the thesis, we formally introduce trapdoor commitments and extend the notion to identity-based trapdoors, where trapdoors can only be used in connection with certain identities. We then recall the most popular constructions of ordinary trapdoor protocols and present new solutions for identity-based trapdoors.

In the second part of the thesis, we show the usefulness of trapdoors in commitment schemes. Deploying trapdoors we construct efficient non-malleable commitment schemes which basically guarantee indepency of commitments. Furthermore, applying (identity-based) trapdoor commitments we secure well-known identification protocols against a new kind of attack. And finally, by means of trapdoors, we show how to construct composable commitment schemes that can be securely executed as subprotocols within complex protocols.

Download the thesis:
pdf pdfbw dvi ps psgz

Remark: The second pdf file is the black/white version of the first pdf file. In the b/w pdf file all colored pdf links are forced to be black. This prevents that, for instance, the red pdf links in the table of contents are printed grey instead of black.