Design and Analysis of Opaque Signatures [Elektronische Ressource] / Laila El Aimani

Laila El Aimani

Sujets

• Informatik

Informations

• Publié par: rheinische_friedrich-wilhelms-universitat_bonn
• Publié le: 01 janvier 2011
• Nombre de lectures: 48
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Design and Analysis of Opaque Signatures
Dissertation
zur
Erlangung des Doktorgrades (Dr. rer. nat.)
der
Mathematisch-Naturwissenschaftlichen Fakulta¨t
der
Rheinischen Friedrich-Wilhelms-Universita¨t Bonn
vorgelegt von
Laila El Aimani
aus
Marrakech, Marokko
Bonn 2011Tag der Disputation: 29 April 2011
Promotionskommission:
Prof. Dr. Joachim von zur Gathen, Erstgutachter - Betreuer (b-it, Universita¨t Bonn)
Prof. Dr. Marek Karpinski, Fachnahes Mitglied (Universita¨t Bonn)
Prof. Dr. Alexander Markowetz, Fachangrenzendes Mitglied (Universita¨t Bonn)
Prof. Dr. Kenny Paterson, Zweitgutachter (Royal Holloway, University of London)
Prof. Dr. Jean-Jacques Quisquater, Fachangrenzendes Mitglied (Universite´ Catholique de Lou-
vain)
Erscheinungsjahr: 2011Abstract (Zusammenfassung)
Digital signatures were introduced to guarantee the authenticity and integrity of the underlying
messages. A digital signature scheme comprises the key generation, the signature, and the verifi-
cation algorithms. The key generation algorithm creates the signing and the verifying keys, called
also the signer’s private and public keys respectively. The signature algorithm, which is run by the
signer, produces a signature on the input message. Finally, the verification algorithm, run by any-
one who knows the signer’s public key, checks whether a purported signature on some message is
valid or not. The last property, namely the universal verification of digital signatures is undesirable
in situations where the signed data is commercially or personally sensitive. Therefore, mechanisms
which share most properties with digital signatures except for the universal verification were in-
vented to respond to the aforementioned need; we call such mechanisms “opaque signatures”. In
this thesis, we study the signatures where the verification cannot be achieved without the cooper-
ation of a specific entity, namely the signer in case of undeniable signatures, or the confirmer in
case of confirmer signatures; we make three main contributions.
We first study the relationship between two security properties important for public key en-
cryption, namely data privacy and key privacy. Our study is motivated by the fact that opaque
signatures involve always an encryption layer that ensures their opacity. The properties required
for this encryption vary according to whether we want to protect the identity (i.e. the key) of the
signer or hide the validity of the signature. Therefore, it would be convenient to use existing work
about the encryption scheme in order to derive one notion from the other.
Next, we delve into the generic constructions of confirmer signatures from basic cryptographic
primitives, e.g. digital signatures, encryption, or commitment schemes. In fact, generic con-
structions give easy-to-understand and easy-to-prove schemes, however, this convenience is of-
ten achieved at the expense of efficiency. In this contribution, which constitutes the core of this
thesis, we first analyze the already existing constructions; our study concludes that the popular
generic constructions of confirmer signatures necessitate strong security assumptions on the build-
ing blocks, which impacts negatively the efficiency of the resulting signatures. Next, we show that
a small change in these constructions makes these assumptions drop drastically, allowing as a result
constructions with instantiations that compete with the dedicated realizations of these signatures.
Finally, we revisit two early undeniable signatures which were proposed with a conjectural
security. We disprove the claimed security of the first scheme, and we provide a fix to it in order
to achieve strong security properties. Next, we upgrade the second scheme so that it supports a
iiidesirable feature, and we provide a formal security treatment of the new scheme: we prove that it
is secure assuming new reasonable assumptions on the underlying constituents.
ivAcknowledgments
In the course of my PhD studies, I have had the support of many people and I am pleased to
acknowledge here their different contributions.
My largest debt goes undoubtedly to my supervisor Joachim von zur Gathen for giving me
the opportunity to pursue this PhD in a splendid environment. I thank him also for his insights,
guidance, and support at all stages of my PhD studies.
Next, I am profoundly grateful to Damien Vergnaud for making me discover cryptographic
protocols in general and undeniable signatures in particular. His advices and suggestions have
contributed inestimably to my understanding of this fascinating area.
I have also benefited from conversations and correspondence with many researchers that I met
at different events. I wish to thank particularly Marc Joye, Pascal Paillier, and Kenny Paterson for
precious discussions which sharpened my knowledge in reductionist security.
I would like to thank also Prof. Marek Karpinski, Prof. Alexander Markowetz, Prof. Kenny
Paterson, and Prof. Jean-Jacques Quisquater for accepting to devote a good part of their time in
order to evaluate this work. I actually appreciate greatly the extremely careful assessment of my
thesis and the many interesting remarks I got from my reviewers. It is also an honor for me to have
such brilliant people in my PhD committee.
Accomplishing this PhD would not have been possible without the assistance of my colleagues
at cosec and b-it. I cherish so much our seminars, discussions, and social activities which made
my PhD experience both interesting and enjoyable.
My sincere thanks go also to my current colleagues at Technicolor, more specifically the Se-
curity and Content Protection Labs team at Rennes. The head of this group, Eric Diehl, deserves
special thanks for his interest in my work, and for maintaining a rich and stimulating working en-
vironment in a friendly atmosphere. I wish to present again my profound gratitude to my colleague
Marc Joye; I value very much his technical insight, his availability to discuss my results, and his
encouragement to further improve them.
Finally, and at every stage of my studies, I have had endless support from my family. In
particular, my mother as well as my sister Salma and my brother Jabrane were an unfailing source
of encouragement at times when I was most discouraged. I am heartily thankful for their love and
support, and it is to them that I dedicate this work.
vviPreface
This thesis presents the ensemble of my PhD results obtained in the area of “opaque” signatures,
1namely [El Aimani & Vergnaud, 2007; El Aimani, 2008, 2009a,b, 2010] .
A digital signature is a mechanism that captures most properties satisfied by a “traditional”
signature in the paper world. In fact, digital signatures guarantee that the signed message has not
been altered in transit, and that it comes from the source that claims to be its provenance, namely
the signer. More formally, a digital signature consists of three algorithms: (1) the key generation
algorithm which creates the signing and the verifying keys, (2) the signing algorithm which takes
on input the signing key and a message, and outputs a signature on the input message, (3) and
the verification algorithm which checks the validity of an alleged signature on a given message
using the verifying key. An important feature in digital signatures is the universal verification,
i.e. anyone who knows the verifying key, called also the signer’s public key, can verify signatures
issued by this signer. However, such a property can be undesirable in some applications and needs
to be controlled or limited; we talk then about obscure or opaque signatures. In this document, we
will focus on confirmer and undeniable signatures. Let us then specify the context.
Consider for example the case of inter-organizational electronic messages; signatures on these
messages are indispensable to resolve disputes as they ensure integrity and authenticity of the
underlying messages, however, self-authentication of these signatures will make the messages vul-
nerable to industrial spy or extortionist. Undeniable signatures come to rescue in this situation
as they: (1) cannot be verified without cooperation with the signer via the confirmation/denial
protocols, (2) are non-transferable since a verifier cannot transfer his conviction, to a third party,
about the validity/invalidity of a signature he has just verified, (3) are binding in the sense that a
signer cannot deny a signature he has actually issued. Unfortunately, the very virtue of undeni-
able signatures (verification with only the signer’s help) became their major shortcoming for many
practical applications since absence of the signer obstructs the entire verification process. There-
fore, the concept of undeniable signatures was upgraded to designated confirmer signatures where
the verification is delegated to a designated confirmer.
Building complicated systems upon simple and basic primitives is customary in cryptography
as it allows to re-use existing work about the primitives, and it achieves easy-to-understand and
1The works [El Aimani & von zur Gathen, 2007; El Aimani & Raekow, 2009, 2010] are not reported in this
document as they do not accord with the general theme of the thesis.
viieasy-to-prove systems. However, monolithic or dedicated schemes better often, in terms of effi-
ciency, those obtained from instantiating generic constructions with concrete prim