Séminaire Cryptographie 2010/2011
Pour recevoir par e-mail les annonces de ce séminaire, vous pouvez vous inscrire sur la mailing list crypto.Pour aller directement au prochain séminaire
- Programme du premier trimestre 2010/2011
- Mercredi 29 Septembre 2010 : Soutenance de thèse de Jonathan Etrog
- Jeudi 30 Septembre 2010 : Soutenance de thèse de Gaëtan Leurent
- Mercredi 13 Octobre 2010 : Soutenance de thèse de Georg Fuchsbauer
- Jeudi 4 Novembre 2010: Angelo De Caro
- Jeudi 4 Novembre 2010: Jiqiang Lu
- Jeudi 9 Décembre 2010 : Soutenance de thèse de Santiago Zanella Béguelin
- Jeudi 9 Décembre 2010: Ben Smyth
- Vendredi 10 Décembre 2010 : Soutenance d'habilitation de Pierre-Alain Fouque
- Jeudi 16 Décembre 2010: David Xiao
- Programme du second trimestre 2010/2011
- Programme du troisième trimestre 2010/2011
- Programme du dernier trimestre 2010/2011
Programme du premier trimestre 2010/2011
TOP
Mercredi 29 Septembre 2010 : Soutenance de thèse de Jonathan Etrog
Orange Labs, UVSQ14h dans la salle des Actes
Cryptanalyse linéaire et conception de protocoles d’authentification à sécurité prouvée
Jury :- Gildas Avoine (Rapporteur)
- Anne Canteaut (Rapporteur)
- Carlos Cid
- Jacques Patarin (Directeur)
- Vincent Rijmen
- Matt Robshaw
- Henri Gilbert
Résumé : Cette thèse, restreinte au cadre de la cryptologie symétrique, s’intéresse à deux aspects séparés de la cryptologie : la protection des messages à l’aide d’algorithmes de chiffrement et la protection de la vie privée à travers des protocoles d’authentification. La première partie concerne l’étude de la cryptanalyse linéaire et la seconde la conception de protocoles d’authentification à sécurité prouvée garantissant une forme forte d’intraçabilité. Dans la première partie, nous nous intéressons à la cryptanalyse linéaire qui bien qu’introduite au début des années 90 a connu récemment un nouvel essor dû au développement de nouvelles variantes. Nous nous sommes à la fois intéressés à son aspect pratique et théorique. Dans un premier temps, nous présentons une cryptanalyse d’une version réduite de SMS4, algorithme utilisé dans le chiffrement du WiFi chinois puis nous introduisons la cryptanalyse multilinéaire et décrivons une nouvelle forme de cryptanalyse multilinéaire. La deuxième partie concerne l’étude de protocoles d’authentification RFID respectant la vie privée. Nous définissons un modèle d’attaquant permettant de formaliser les notions de sécurité relatives à ces protocoles. Nous proposons ensuite deux protocoles réalisant chacun un compromis entre l’intraçabilité forte et la résistance aux attaques par déni de service et admettant des implantations à bas coût et établissons des preuves de sécurité dans le modèle standard pour ces deux protocoles.
Abstract: This Ph.D, devoted to symmetric cryptography, addresses two separate aspects of cryptology. First, the protection of messages using encryption algorithms and, second, the protection of privacy through authentication protocols. The first part concerns the study of linear cryptanalysis while the second is devoted to the design of authentication protocols with proven security. Although introduced in the early 90s, linear cryptanalysis has recently experienced a revival due to the development of new variants. We are both interested in its practical and theoretical aspects. First, we present a cryptanalysis of a reduced version of SMS4, the encryption algorithm used in WiFi in China then, second, we introduce multilinear cryptanalysis and describe a new form of multilinear cryptanalysis. The second part of the thesis concerns the study of RFID authentication protocols respecting privacy. We define a model to formalize the notions of security for these protocols. Then we propose two protocols, each one performing a compromise between strong unlinkability and resistance to denial of service attacks, which allow low-cost implementations. We establish security proofs in the standard model for these two protocols.
TOP
Jeudi 30 Septembre 2010 : Soutenance de thèse de Gaëtan Leurent
ENS14h dans l'Amphi Evariste Galois - NIR
Construction et analyse de fonctions de hachage
Jury :- Alex Biryukov
- Anne Canteaut (Rapporteur)
- Orr Dunkelman
- Arnaud Durand
- Pierre-Alain Fouque (Responsable scientifique)
- Antoine Joux
- David Pointcheval (Directeur)
- Bart Preneel (Rapporteur)
Résumé : Les fonctions de hachage sont des fonctions cryptographiques qui se comportent comme une fonction aléatoire. Ce sont des primitives essentielles en cryptographie, qui sont utilisées dans de nombreux standards et protocoles : pour des schémas de signatures, des codes d’authentification, où pour la dérivation de clef. Les fonctions de hachage sont un sujet particulièrement actif actuellement, à cause de la compétition SHA-3 organisée par le NIST. Cette compétition a été organisée après des attaques dévastatrices sur les fonctions les plus utilisées actuellement (MD4, MD5, SHA-1), et vise à standardiser une nouvelle fonction de hachage. Mon travail de doctorat s’est articulé autour de cette compétition. Dans une première partie, j’ai travaillé sur les nouvelles attaques de Wang et. al. contre MD4 et MD5. J’ai proposé des améliorations de ces attaques et des nouvelles applications contre certains MACs. Dans une deuxième partie, j’ai construit un candidat pour la compétition SHA-3. J’ai utilisé ma connaissance de la famille de MD4 pour construire une fonction qui résiste aux principaux types d’attaques. Mon candidat, SIMD, a été accepté pour le deuxième tour de la compétition SHA-3. Enfin, dans une troisième partie, j’ai développé de nouvelles attaques contre certains candidats dans la compétition SHA-3. Ces attaques utilisent de nouvelles techniques qui s'appliquent à plusieurs fonctions de hachage ou schéma de chiffrement par bloc. J’ai donc abordé les deux principaux aspects de la cryptographie symétrique : la construction et l’analyse.
Abstract: Hash functions are cryptographic functions with no structural properties. It is an essential primitive in modern cryptography, used in many protocols and standards, including signature schemes, authentication codes, and key derivation. Hash function study is a very active topic currently because of the SHA-3 competition. This competition is organised by NIST to select a new hash function standard, after devastating attacks against the most widely used hash function : MD4, MD5, and SHA-1. My work has been organized around this competition. In the first part, I studied the new attacks of Wang et. al. against MD4 and MD5. I describe some improvements of these attacks, and new applications to higher-level constructions. In the second part, I describe a new hash function, SIMD, which has been submitted to NIST for the SHA-3 competition. The design of SIMD follows ideas from the MD4 family, but I used my knowledge of this family to make it resistant to most attacks. Finally, in the third part, I describe new attacks against SHA-3 candidates. I describe new attacks techniques which are general enough to apply to several hash functions or block ciphers. Thus, this thesis covers the two main realms of symmetric cryptography: design and analysis.
TOP
Mercredi 13 Octobre 2010 : Soutenance de thèse de Georg Fuchsbauer
ENS14h dans la salle Henri Cartan (niveau -2 du DI)
Signatures Automorphes et Applications
Jury :- Xavier Boyen
- Jean-Sébastien Coron (rapporteur)
- Arnaud Durand
- Louis Granboulan
- Jens Groth
- David Pointcheval (directeur de thèse)
- Nigel Smart (rapporteur)
- Jacques Stern
Résumé : Nous mettons en avant la conception modulaire de protocoles cryptographiques et proposons des briques conduisant à des résultats efficaces. Cette thèse introduit ainsi deux primitives nommées signatures automorphes et signatures commutantes et exemplifie leur utilité en donnant de nombreuses applications. Les signatures automorphes sont des signatures numériques dont les clés de vérification appartiennent à l'espace des messages, les messages et les signatures se composent d'éléments d'un groupe bilinéaire, et la vérification se fait en évaluant des équations de produit de couplages. Ces signatures, dont nous donnons des réalisations pratiques sous des hypothèses appropriées, présentent un partenaire parfait au système de preuves efficace de Groth et Sahai. Ensemble, ils nous permettent d'instancier les signatures de groupe, et pour la première fois de manière efficace les signatures en blanc à interaction minimale et les signatures par délégation anonymes. Les signatures commutantes étendent le chiffrement vérifiable comme suit: en plus de produire et chiffrer une signature de façon que la validité soit vérifiable, un signataire peut le faire même quand le message est déjà chiffré (et inconnu); donc, signature et chiffrement commutent. Notre réalisation combine les signatures automorphes avec les preuves Groth-Sahai, dont nous démontrons de nouvelles propriétés. Comme application, nous présentons la première implémentation d'accréditations anonymes délégables aux émissions et délégations non-interactives. En outre, notre schéma est plus efficace que les précédents. Toutes nos constructions sont prouvées sûres dans le modèle standard et sous des hypothèses non-interactives.
Abstract: We advocate modular design of cryptographic primitives and give building blocks to achieve this efficiently. This thesis introduces two new primitives called automorphic signatures and commuting signatures, and illustrates their usefulness by giving numerous applications. Automorphic signatures are digital signatures whose verification keys lie in the message space, messages and signatures consist of elements of a bilinear group, and verification is done by evaluating a set of pairing-product equations. These signatures, of which we provide practical instantiations under appropriate assumptions, make a perfect counterpart to the efficient proof system by Groth and Sahai. Together, they enables us to give the first efficient instantiations of round-optimal blind signatures and anonymous proxy signatures, as well as a new fully secure group signature scheme. Commuting signatures extend verifiably encrypted signatures as follows: in addition to encrypting a signature and the signed message so that the validity of the plaintexts can be verified, the signer can do so even if the message is already encrypted (and unknown); thus signing and encrypting commute. Our instantiation combines automorphic signatures with Groth-Sahai proofs, of which we identify a series of useful properties. As an application, we give the first instantiation of delegatable anonymous credentials with non-interactive (and thus concurrently secure) issuing and delegation. Our scheme is also significantly more efficient than previous ones. All our constructions are proved secure in the standard model under non-interactive assumptions.
TOP
Jeudi 4 Novembre 2010: Angelo De Caro
Università di Salerno10h dans l'Amphi Evariste Galois - NIR
Efficient Fully Secure (Hierarchical) Predicate Encryption for Conjunctions, Disjunctions and k-CNF/DNF formulae
- Abstract
- Predicate encryption is an important cryptographic primitive that has found wide applications as it allows for fine-grained key management. In a predicate encryption scheme for a class PP of predicates, the owner of the master secret key can derive a secret key SK_P for any predicate P in PP. Similarly, when encrypting plaintext M, the sender can specify an attribute vector x for the ciphertext CT. Then, key SK_P can decrypt all ciphertexts CT with attribute vector x such that P(x)=1.
In this paper, we give fully secure implementations for Conjunctions (also called Hidden Vector Encryption in the literature), Disjunctions and k-CNF/DNF predicates that guarantee the security of the plaintext and of the attribute. Our construction for Disjunctions and Conjunctions are linear in the number of variables.
Previous fully secure constructions for Disjunction required time exponential in the number of variables while for Conjunctions the best previous construction was quadratic in the number of variables. We also give reduction of k-CNF and k-DNF formulae to Conjunctions for any constant k. In proving the full security of our constructions, we elaborate on the recent paradigm of {\em dual encryption system} introduced in [Waters -- Crypto 2009] resulting in a simplified proof strategy that could be of independent interest. We also give a hierarchical version of our scheme that has as special case Anonymous HIBE.
TOP
Jeudi 4 Novembre 2010: Jiqiang Lu
ENS11h dans l'Amphi Evariste Galois - NIR
Meet-in-the-Middle Attack on 8 Rounds of the AES Block Cipher under 192 Key Bits.
- Abstract
- The AES block cipher has a 128-bit block length and a user key of 128, 192 or 256 bits, released by NIST for data encryption in the USA; it became an ISO international standard in 2005. In 2008, Demirci an Selccuk gave a meet-in-the-middle attack on 7-round AES under 192 key bits. In 2009, Demirci et al. (incorrectly) described a new meet-in-the-middle attack on 7-round AES under 192 key bits. Subsequently, Dunkelman et al. described an attack on 8-round AES under 192 key bits by taking advantage of several advanced techniques, including one about the key schedule.
In this paper, we show that by exploiting a simple observation on the key schedule, a meet-in-the-middle attack on 8-round AES under 192 key bits can be obtained from Demirci and Selccuk's and Demirci et al.'s work; and a more efficient attack can be obtained when taking into account Dunkelman et al.'s observation on the key schedule. In the single-key attack scenario, attacking 8 rounds is the best currently known cryptanalytic result for AES in terms of the numbers of attacked rounds, and our attack has a dramatically smaller data complexity than the currently known attacks on 8-round AES under 192 key bits.
TOP
Jeudi 9 Décembre 2010 : Soutenance de thèse de Santiago Zanella Béguelin
IMDEA Software - Mines ParisTech10h dans l'Amphi Evariste Galois - NIR
Certification Formelle de Preuves Cryptographiques Basées sur le Langage
Jury :- Michael Backes (rapporteur)
- Gilles Barthe (directeur)
- Nick Benton
- Cédric Fournet
- Yassine Lakhnech (rapporteur)
- Jean-Jacques Lévy
- Christine Paulin-Mohring (rapporteur)
- David Pointcheval (rapporteur)
Résumé : Les séquences de jeux sont une méthodologie établie pour structurer les preuves cryptographiques. De telles preuves peuvent être formalisées rigoureusement en regardant les jeux comme des programmes probabilistes et en utilisant des méthodes de vérification de programmes. Cette thèse décrit CertiCrypt, un outil permettant la construction et vérification automatique de preuves basées sur les jeux. CertiCrypt est implementé dans l'assistant à la preuve Coq, et repose sur de nombreux domaines, en particulier les probabilités, la complexité, l'algèbre, et la sémantique des langages de programmation. CertiCrypt fournit des outils certifiés pour raisonner sur l'équivalence de programmes probabilistes, en particulier une logique de Hoare relationnelle, une théorie équationnelle pour l'équivalence observationnelle, une bibliothèque de transformations de programme, et des techniques propres aux preuves cryptographiques, permettant de raisonner sur les événements. Nous validons l'outil en formalisant les preuves de sécurité de plusieurs exemples emblématiques, notamment le schéma de chiffrement OAEP et le schéma de signature FDH.
Abstract: The game-based approach is a popular methodology for structuring cryptographic proofs as sequences of games. Game-based proofs can be rigorously formalized by taking a code-centric view of games as probabilistic programs and relying on programming language techniques to justify proof steps. In this dissertation we present CertiCrypt, a framework that enables the machine-checked construction and verification of game-based cryptographic proofs. CertiCrypt is built upon the general-purpose proof assistant Coq, from which it inherits the ability to provide independently verifiable evidence that proofs are correct, and draws on many areas, including probability and complexity theory, algebra, and semantics of programming languages. The framework provides certified tools to reason about the equivalence of probabilistic programs, including a relational Hoare logic, a theory of observational equivalence, verified program transformations, and ad-hoc programming language techniques of particular interest in cryptographic proofs, such as reasoning about failure events. We validate our framework through the formalization of several significant case studies, including proofs of security of the Optimal Asymmetric Encryption Padding scheme against adaptive chosen-ciphertext attacks, and of existential unforgeability of Full-Domain Hash signatures.
Jeudi 9 Décembre 2010: Ben Smyth
LORIA13h30 dans l'Amphi Evariste Galois - NIR
Attacking ballot secrecy in Helios
- Abstract
- Helios 2.0 is an open-source web-based end-to-end verifiable electronic voting system, suitable for use in low-coercion environments. The scheme is particularly significant due to its implementation and deployment for use in real-world elections: the Catholic University of Louvain adopted the system to elect the university president, and Princeton University used Helios to elect the student vice president; in addition, the International Association of Cryptologtic Research trialled the scheme in a non-binding poll. In this talk, we will analyse ballot secrecy and discover a vulnerability which allows an adversary to compromise voters' privacy. This vulnerability has been successfully exploited to break privacy in a small election using the current Helios implementation. Moreover, the feasibility of an attack is considered in the context of French legislative elections and, based upon our findings, we believe it constitutes a threat to ballot secrecy in real-world elections. Finally, a fix is proposed.
TOP
Vendredi 10 Décembre 2010 : Soutenance d'habilitation de Pierre-Alain Fouque
ENS10h30 en salle Celan (Bâtiment principal)
Sur Quelques Méthodes Algébriques et Statistiques en Cryptanalyse
Jury :- Jean-Charles Faugère
- Henri Gilbert (rapporteur)
- Louis Goubin (rapporteur)
- Antoine Joux
- David Pointcheval
- Bart Preneel (rapporteur)
- Adi Shamir
- Jacques Stern (directeur)
Résumé : La cryptanalyse, anciennement l’art de déchiffrer les messages secrets, s’est rapidement développée depuis la Seconde Guerre mondiale. Durant cette guerre, le nombre total de messages chiffrés interceptés est estimé entre deux et trois millions. Pour accélérer les décryptements, les cryptanalystes britanniques ont mis au point le premier ordinateur, appelé Colossus. C’est ainsi que la cryptanalyse est devenue une science à l’intersection des mathématiques et de l’informatique. Cette thèse décrit plusieurs classes d’attaques cryptographiques qui diffèrent par les techniques employées. Les premiers outils mathématiques utilisés en cryptanalyse sont les statistiques : elles ont permis d’exploiter les distributions de probabilité non-uniformes de répartition des lettres dans les langues naturelles et, plus tard, les distributions biaisées des sorties des mécanismes cryptographiques. Puis, après l’invention de la cryptographie à clé publique, les cryptanalystes ont fait appel à l’algèbre pour étudier les schémas reliés à des problèmes difficiles en théorie de la complexité : le problème RSA, du Logarithme Discret, du sac-à-dos, ceux issus de la théorie des codes correcteurs d’erreurs, ou ceux concernant la résolution de systèmes polynomiaux en plusieurs variables dans un corps fini. Il est également possible en cryptanalyse de schémas symétriques d’utiliser des outils algébriques pour l’étudier des primitives, mais la mise en forme des équations à résoudre est souvent plus complexe qu’en cryptographie asymétrique. Enfin, les attaques par canaux auxiliaires constituent un nouvel outil pour les cryptanalystes, qui tirent ainsi profit des implémentations logicielles ou matérielles des systèmes cryptographiques. Ces implémentations laissent fuir des informations sur les variables internes manipulées au cours des calculs. La connaissance de ces informations, jusqu’alors non prises en compte, autorise un grand nombre d’attaques nouvelles très efficaces.
TOP
Jeudi 16 Décembre 2010: David Xiao
LRI, Univ. Paris Sud - LIAFA, Univ. Paris 710h30 dans l'Amphi Evariste Galois - NIR
Privacy, incentives, and truthfulness.
- Abstract
- Imagine the government is taking a census, and you as an individual are worried that by participating, private information about you (such as your address, age, ethnicity, etc.) may eventually be revealed when the government publishes the census data. How can the government assure you that by using an appropriate release mechanism that "sanitizes" census data, no individual's privacy will be compromised?
This question has been studied for a long time in the statistics community, and more recently the computer science community has contributed the formal notion of differential privacy, which captures the idea that "no individual's data can have a large effect on the output of the release mechanism". This has been interpreted to mean that individuals should be comfortable revealing their information, since little private information is leaked.
In this talk, we first give an introduction to this fast-developing area of research. We then investigate the above interpretation about the guarantees of differential privacy. We argue that the interpretation is incomplete because unless participation in the database somehow explicitly benefits the individuals, they will always refuse to participate regardless of whether the release mechanism is differentially private or not. We then show that by combining differential privacy with the notion of incentives and truthfulness from game theory, one can take (almost) any release mechanism that motivates individuals to participate and modify it so that in addition it satisfies differential privacy.
Programme du second trimestre 2010/2011
TOP
Jeudi 3 Février 2011: Christian Cachin
IBM Research - Zurich10h30 dans l'Amphi Evariste Galois - NIR
Cryptographic Interfaces: From Hardware-Security Modules to Open Key-Management Systems
- Abstract
- Cryptographic keys must be stored and managed. In real-world applications, they are often guarded by hardware-security modules (HSMs) with sophisticated physical protection. Several logical attacks through the key-management operations in cryptographic interfaces of HSMs have been reported in the past, which allowed to expose keys merely by exploiting the interface in unexpected ways. We are currently building a key-lifecycle management system accessible through an open protocol. We describe how to secure the system against attacks through its cryptographic interface. Its key-management operations integrate traditional access control with the semantics of cryptographic operations so that they respect the dependencies introduced through the cryptographic operations on keys.
TOP
Mardi 8 Février 2011 - Séminaire du Département : Nigel Smart
Univ. Bristol14h Salle Henri Cartan - Passage Rouge - Niveau -2
Attestation: Trying to decipher what it is
- Abstract
- This talk will summarize some of the ongoing work we have been doing in Bristol in looking at security models for DAA type protocols. The first part of the talk will from a high level view look at what DAA provides and how it differs from standard group signatures. We will look at how the industrial requirements of the TCG standards body conflict with what one would want as a theoretical basis. The second part of the talk will go into more detail of a new security model which tries to address the high level problems raised in the first part.
TOP
Jeudi 10 Février 2011: Nigel Smart
Univ. Bristol10h30 dans l'Amphi Evariste Galois - NIR
"Ideal" Fully Homomorphic Encryption
TOP
Jeudi 3 Mars 2011: Nigel Smart
Univ. Bristol10h30 dans l'Amphi Evariste Galois - NIR
Extensions to Fully Homomorphic Encryption
TOP
Vendredi 4 Mars 2011: David Mandell Freeman
Stanford Univ.14h00 en Salle W (4è étage)
Homomorphic Signatures for Polynomial Functions
- Abstract
- We construct the first homomorphic signature scheme that is capable of evaluating multivariate polynomials on signed data. Given the public key and a signed data set, there is an efficient algorithm to produce a short signature that authenticates the mean, standard deviation, least-squares fit, and other functions of the signed data. Previous systems for computing on signed data could only handle linear operations. Our system uses ideal lattices in a way that is a "signature analogue" of Gentry's construction of fully homomorphic encryption. Security is based on hard problems on ideal lattices similar to those in Gentry's system.
Programme du troisième trimestre 2010/2011
TOP
Jeudi 7 avril 2011: Christian Rechberger
ENS, Chaire France Telecom pour la sécurité des réseaux de télécommunications10h30 dans l'Amphi Evariste Galois - NIR
The SHA-3 competition through the rebound lens
- Abstract
- After the MD5 disaster and related breakthroughs in hash cryptanalysis, the cryptologic community as well as practitioners are searching for a trustworthy next generation hash function standard. This culminated in a large international multi-year effort, the SHA-3 competition, planned to end in 2012.
In this talk we survey the remaining candidates in this competition and discuss how this competition led to a new way of doing hash cryptanalysis: the rebound attack. AES-like proposals were first targets because of their simplicity. Recently we started to apply this method also to very different constructions, and consistently get results that beat the best known attacks. We survey those results, and comment on their impact on the outcome of the SHA-3 competition.
TOP
Jeudi 28 avril 2011: Damien Stehlé
ENS Lyon10h30 dans l'Amphi Evariste Galois - NIR
Making NTRU as Secure as Worst-Case Problems over Ideal Lattices
- Abstract
- NTRUEncrypt, proposed in 1996 by Hoffstein, Pipher and Silverman, is the fastest known lattice-based encryption scheme. However, since its introduction, doubts have regularly arisen on its security. We show how to modify NTRUEncrypt to make it semantically secure, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. The proof relies on the recent results from [Lyubashevsky et al., Eurocrypt'10], on the hardness of the Ring-LWE problem. Our main contribution is to show that if the secret key polynomials are selected by rejection from discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its domain. During this talk, I will also discuss extensions of this result for NTRUSign.
TOP
Jeudi 5 mai 2011: Adi Shamir
Weizmann Institute10h30 dans la salle U ou V (niveau -2 du DI)
New Attacks on Minimal Cryptographic Schemes
- Abstract
- Cryptographic schemes are called minimal if they are stripped down to their simplest possible form, and any further elimination of one of their elements is known to lead to successful cryptanalytic attacks. Determining the minimal forms and assumptions of various cryptographic constructions had always been popular among the theoreticians, and more recently it had also been attempted by practitioners in order to speed up the submissions to various competitions.
In this talk I will show how dangerous it is to walk along this bleeding edge by describing some new attacks on various minimal constructions.
TOP
Jeudi 26 mai 2011: Chris Peikert
Georgia Institute of Technology10h30 dans l'Amphi Evariste Galois - NIR
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
- Abstract
- We give new methods for generating and using 'trapdoors' in cryptographic lattices, which are simultaneously simple, efficient, easy to implement (even in parallel), and asymptotically optimal with very small hidden constants. Our methods involve a new kind of trapdoor, and include specialized algorithms for inverting $\lwe$, randomly sampling $\sis$ preimages, and securely delegating trapdoors. These tasks were previously the main bottleneck for a wide range of cryptographic schemes, and our techniques substantially improve upon the previous ones, both in terms of practical performance and quality of the produced outputs. Moreover, the simple structure of the new trapdoor and associated algorithms can often be exposed within applications, leading to further simplifications and efficiency improvements. We exemplify the applicability of our methods with new signature schemes and CCA-secure encryption schemes, which have better performance and security than the best previously known lattice-based solutions to these problems.
Programme du dernier trimestre 2010/2011
TOP
Vendredi 1er juillet 2011: Christian Rechberger
ENS, Chaire France Telecom pour la sécurité des réseaux de télécommunications10h30 en Salle INFO 5 - Niveau -1 - NIR
Bicliques in Block Cipher Cryptanalysis: New Results on AES
- Abstract
- Since Rijndael was chosen as the Advanced Encryption Standard (AES), improving upon 7-round attacks on the 128-bit key variant or upon 8-round attacks on the 256-bit key variant is considered to be one of the most difficult challenges in the cryptanalysis of block ciphers for more than a decade.
We present a novel technique of block cipher cryptanalysis using so-called bicliques. This allows us to obtain for the first time results on a higher number of rounds, yet the advantage over brute-force search may become small.
In contrast to most shortcut attacks settings on AES versions, we do not need any related-keys. Our approach is practically verified to a large extent, yet its full implementation needs prohibitively large computational resources and hence does not threaten the practical use of AES in any way.
TOP
Lundi 4 juillet 2011: Orr Dunkelman
Weizmann Institute10h30 en Salle INFO 5 - Niveau -1 - NIR
Rethinking IDEA
- Abstract
- IDEA is a 64-bit block cipher with 128-bit keys introduced by Lai and Massey in 1991. IDEA is one of the most widely used block ciphers, due to its inclusion in several cryptographic packages, such as PGP. Since its introduction in 1991, IDEA has withstood extensive cryptanalytic efforts, but no attack was found on the full (8.5-round) variant of the cipher.
In this talk, we will discuss the various attacks on IDEA: The early differential and linear attempts, impossible differential attacks, the Demirci-Selcuk-Ture attack, and some of the newer attacks which are based on the Biryukov-Demirci relation.
Finally, we shall introduce a new and simple attack on 6-round IDEA which uses 20 known plaintexts and has a time complexity of 2112. This attack is currently the best known attack on IDEA (in the single-key model).
Webmaster: webdi![[@]](pub/ressources/commercial_at.png)
di![[.]](pub/ressources/full_stop.png)
ensfr.
diensfr.