École normale supérieure LIENS École Doctorale de Sciences Mathématiques de Paris Centre

Michel Ferreira

Description

Niveau: Supérieur, Doctorat, Bac+8
École normale supérieure LIENS – École Doctorale de Sciences Mathématiques de Paris Centre Reducing The Need For Trusted Parties In Cryptography THÈSE D'HABILITATION présentée pour l'obtention du Diplôme d'Habilitation à Diriger des Recherches de l'École normale supérieure (Spécialité Informatique) par Michel Ferreira Abdalla Soutenue publiquement le 24 novembre 2011 devant le jury composé de Jean-Sébastien Coron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Rapporteur Antoine Joux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Rapporteur Kenny Paterson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rapporteur Ronald Cramer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Examinateur Marc Fischlin . . . . . . . . . . . .

• language she


• has she been


• diriger des recherches de l'école normale


• école doctorale de sciences mathématiques


• key infrastructure


• ecole normale


• based cryptography


• based cryptosystems

Sujets

• Fischel
• Luis Ernesto Derbez Bautista
• Fouqué
• Paterson
• Bresson

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 novembre 2011
• Nombre de lectures: 27
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

École normale supérieure
LIENS – École Doctorale de Sciences Mathématiques de Paris Centre
Reducing The Need For
Trusted Parties In Cryptography
THÈSE D’HABILITATION
présentée pour l’obtention du
Diplôme d’Habilitation à Diriger des Recherches
de l’École normale supérieure
(Spécialité Informatique)
par
Michel Ferreira Abdalla
Soutenue publiquement le 24 novembre 2011 devant le jury composé de
Jean-Sébastien Coron .....................................Rapporteur
Antoine Joux .............................................Rapporteur
Kenny Paterson .......................................... Rapporteur
Ronald Cramer .........................................Examinateur
Marc Fischlin ...........................................Examinateur
Nigel Smart .............................................Examinateur
Jacques Stern ...........................................Examinateur
David Pointcheval ..........................................Directeur
Travaux effectués au sein de l’Équipe de Cryptographie
du Laboratoire d’Informatique de l’École normale supérieureAcknowledgements
First and foremost, I would like to thank David Pointcheval. I can honestly say that I would
not be where I am today without his support and guidance, including the supervision of this
thesis, and especially for his friendship. Had it not been for his enthusiasm for cryptography
and persistence, I would probably still be in the U.S. or back in Brazil.
Inaddition toDavid, Iwould alsolike tothank Jean-Sébastien Coron, Ronald Cramer,Marc
Fischlin, Antoine Joux, Kenny Paterson, Nigel Smart, and Jacques Stern for accepting to be
part of this jury. Special thanks to Antoine, Jean-Sébastien, and Kenny, for also accepting to
be Rapporteurs for this thesis.
Next, I would like to thank the following, both current and former, colleagues from the ENS
Crypto team: Charles Bouillaguet, Bruno Blanchet, Olivier Blazy, David Cadé, Dario Cata-
lano, Yuanmi Chen, Céline Chevalier, Patrick Derbez, Léo Ducas, Dario Fiore, Pierre-Alain
Fouque, Georg Fuchsbauer, Malika Izabachène, Jérémy Jean, Roch Lescuyer, Vadim Lyuba-
shevsky, David Naccache, Gregory Neven, Phong Nguyen, Miriam Paiola, Duong Hieu Phan,
David Pointcheval, Oded Regev, Jacques Stern, Mario Strefler, Mehdi Tibouchi, and Damien
Vergnaud. Their friendship and shared passion for numbers has led to numerous discussions,
papers, and most importantly has created an enjoyable work environment. I would also like to
thank the administrative and technical staff of the Computer Science department of ENS for
their everyday support: Michelle Angely, Jacques Beigbeder, Lise-Marie Bivard, Isabelle Delais,
Joëlle Isnard, Jean Claude Lovato, Valérie Mongiat, and Ludovic Ricardou.
The work on which this thesis is based was made possible by numerous collaborations, and I
would like to thank all of those with whom I have had the opportunity to work. In particular, I
would like to give a special acknowledgement to my most frequent collaborators: Mihir Bellare,
Emmanuel Bresson, Dario Catalano, Céline Chevalier, Olivier Chevassut, Alex Dent, Pierre-
Alain Fouque, Eike Kiltz, John Malone-Lee, Chanathip Namprempre, Gregory Neven, David
Pointcheval, and Nigel Smart.
I hold a special place in my acknowledgements for Mihir Bellare and Phil Rogaway, who got
me started in Cryptography. Thanks to them, I published my firstpaper in the field, and I have
since been hooked.
Upon my arrival in France, I was fortunate enough to have Marcelo “Baiano” as a dear
friend. Not only did he help me get settled in Paris, but he also showed me the “French” ropes.
I am also extremely lucky to have met Dario Catalano, who is the one person most responsible
for jump-starting my social life in Paris. Without his cherished friendship and sense of humor,
my wife and I would have driven each other up the wall.
Finally, I would like to thank my wife Stacie for her love and support. Not only has she
been able to put up with the crazy hours and deadlines throughout the years, but she has even
learned to speak the crypto lingo. I also thank her for having the courage to move with me
into a foreign country whose language she could barely speak and for accepting to “survive” in
2a 20 m apartment with me and our cat Tigger.
— i —— ii —Abstract
Trustedpartiesarefundamentalfortheestablishmentofsecurecommunication amongusers.
Suchis thecase, for example, whenestablishingatrusted relationship between usersandcertain
publicinformationinapublic-keyinfrastructureforpublic-keyencryptionandsignatureschemes
or when storing high-entropy secret keys in a cryptographic device. Clearly, if the trusted party
misbehaves in either of these situations, then the overall security of the scheme or protocol in
which we are interested can be adversely affected.
There are several ways in which one can try to reduce the amount of trust in third parties,
such as making the task of recovering the secret key harder for the adversary, as in distributed
cryptosystems or minimizing the damage caused by secret-key exposures, as in forward-secure
and intrusion-resilient cryptosystems. In this thesis, we consider two additional methods.
The first one, which goes by the name of password-based key exchange, is to assume that
the secret keys used in authenticated key exchange protocols have low entropy and do not need
to be stored in a cryptographic device. In spite of the low entropy of secret keys, such protocols
can still provide a level of assurance which may be sufficient for most applications.
The second method for reducing the amount of trust in third parties is to use an identity-
based cryptosystem, in which the public key of a user can be an arbitrary string such as an
email address. As identity-based cryptosystems provide collusion resistance, they can also be
used to lessen the damage caused by secret-key exposures by generating independentsecret keys
for different time periods or devices. Moreover, identity-based cryptosystems can allow users to
haveamorefine-grainedcontrolover thedecryptioncapabilities ofthirdparties,furtherlimiting
the harmful consequences due to their misbehavior.
Keywords: Provable security, password-based cryptography, identity-based cryptography.
— iii —— iv —Résumé
Les tiers de confiance sont essentiels aux communications sécurisées. Par exemple, dans une
infrastructuredegestiondeclés,l’autoritédecertification estlaclédevoutedel’authentification
en garantissant le lien entre une identité et une clé publique. Une carte à puce se doit, pour sa
part, d’assurer la confidentialité et l’intégrité des données secrètes lorsqu’elle sert de stockage
de données cryptographiques. En effet, si ces garanties sont mises en défaut dans l’une de ces
situations, alors la sécurité globale du système peut en être affectée.
Plusieurs approches permettent de réduire l’importance des tiers de confiance, telles qu’ac-
croîtreladifficultéderecouvrerlaclésecrète,enladistribuantparmiplusieursentités,oulimiter
l’impact d’unefuited’information secrète, comme dans les cryptosystèmes «intrusion-resilient»
ou «forward-secure». Dans cette thèse, nous considérons deux méthodes complémentaires.
La première méthode consiste à utiliser des mots de passe, ou des clés secrètes de faible
entropie, qui n’ont pas besoin d’être stockés dans un dispositif cryptographique sécurisé. Malgré
la faible entropie du secret, de tels protocoles peuvent fournir un niveau d’assurance satisfaisant
pour la plupart des applications. On considère en particulier la mise en accord de clés.
Ladeuxièmeméthodelimitelebesoindegarantiedelapartdestiersdeconfianceenutilisant
un cryptosystème basé sur l’identité, dans lequel la clé publique d’un utilisateur peut être une
chaîne de caractères arbitraire, telle qu’une adresse email. Comme ces systèmes fournissent une
résistance aux collusions, ils peuvent aussi être utilisés pour réduire les dommages causés par
l’exposition de clés secrètes en générant des secrets indépendants pour chaque période de temps
oupourchaquepériphérique/entité.Parailleurs,cessystèmesbaséssurl’identitépermettentaux
utilisateurs d’avoir un contrôle plus fin sur les capacités de déchiffrement des tiers, en limitant
les conséquences liées à un mauvais usage.
Mots-clés : Sécurité prouvée, cryptographie basée sur des mots de passe, cryptographie basée
sur l’identité.
— v —Contents
I Reducing The Need For Trusted Parties In Cryptography 1
Introduction 3
1 Provable security 7
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Basic tools. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Standard complexity assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Example: Public-key encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Password-based cryptography 15