| Home > Publications > PhD theses > Informatics (CW) |
CW 2004_04
Gregory Neven
Provably secure identity-based identification schemes and transitive signatures
Advisors: Frank Piessens and Bart De Decker
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.
