Provably secure identity-based identification schemes and transitive signatures

Ref: Gregory Neven. Ph.D thesis, Katholieke Universiteit Leuven, Belgium. May 2004.

Abstract: Cryptography is an ancient craft, but relatively young as a true science. Techniques that offered a reasonable level of protection many centuries ago, are clearly insufficient to meet the communication needs of today's digitalized society. Until the 1980s however, cryptographic design remained a craft, rather than a science: schemes were proposed with at most an intuition for their security, the sole criterion being resistance against attacks after years of exposure to experts.

A more modern approach is that of provable security. This approach requires the designer of a scheme to first clearly state what is understood under the security of the scheme. Next, a mathematical proof is needed showing that the only way to break the scheme is either by attacking an insecure underlying cryptographic building block, or by realizing a mathematical breakthrough. Provable security has evolved from a toy for theoreticians to an important scheme characteristic that is taken into account in the decision of industry standards.

In this thesis, we study the provable security of selected cryptographic primitives. We first distill useful yet feasible security notions, and subsequently prove the security of existing and new schemes under these notions.

The first part focuses on identity-based identification and signature schemes. These are cryptographic primitives providing entity and message authentication, respectively, that allow the public key of a user to be simply his identity (instead of a random string that has to be securely attributed to the user). As a first step, we present a general framework of security-preserving transformations between related primitives. We then use this framework as a tool to prove (and in a single instance, break) the security of schemes from 13 different "families" that were proposed in the literature over the last two decades, but that lacked a security proof prior to our work.

In the second part of this thesis, we discuss transitive signature schemes. These are signature schemes that allow to sign edges of a graph such that any user (and not just the signer) can, from two signatures on adjacent edges {i,j} and {j,k}, compute a third signature for the direct edge {i,k}. We answer an open question regarding the security of a particular scheme, and present a number of new, provably secure schemes offering efficiency advantages over existing schemes.

PS | PDF | Powerpoint presentation