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.
