Séminaires CRYPTO 2012-2013

webmaster Archives des séminaires CRYPTO (PRISM) Pas de commentaires
  • 19 juin 2013 – Cyril Hugounenq (UVSQ) : Étude de l’action du Frobenius sur les volcans de l-isogénies.
Résumé : On va d’abord introduire et voir les structures de volcan de ℓ-isogénie. Ensuite on va voir le lien entre la structure de ℓ-torsion d’une courbe et le volcan de l-isogénie. On va présenter notre objectif d’amélioration de l’algorithme de Couveignes. Enfin on va étudier l’action de l’endomorphisme de Frobenius sur les volcans de ℓ-isogénie et voir les pistes/opportunités qui s’ouvrent/se ferment à nous, le tout en regardant si cela a un apport pour l’algorithme de Couveignes.
  • 22 mai 2013 – Jacques Patarin (UVSQ) : Sécurité du XOR de deux bijections.
Résumé : On dispose de deux boîtes noires. L’une calcule une fonction aléatoire de n bits vers n bits. L’autre calcule f XOR g où f et g sont deux bijections aléatoires indépendantes de n bits vers n bits. On peut choisir les entrées de façon adaptative et observer les sorties (attaque CPA-2). On dispose d’une puissance de calcul infinie mais on est limité à q messages. Jusqu’à quelle valeur de q la probabilité de distinguer les 2 boîtes est-elle négligeable ?
Dans cet exposé nous verrons que la réponse est de ‘dre de q voisin de 2n. Mais plus que le résultat, c’est la méthode de preuve qui sera intéressante. En effet ce problème « simple et pur » est une bonne introduction à la « théorie des miroirs » (évaluation du nombre de solutions de systèmes d’égalité et de non égalité linéaires dans les corps finis), et à ses difficultés. Cette méthode peut ensuite s’appliquer à de très nombreux autres systèmes cryptographiques (comme les divers schémas de Feistel).
  • 24 avril 2013 – Malika Izabachene (LORIA) : Structural Lattice Reduction and Application to Average Hardness
Abstract : Lattice based cryptography is supported by worst-case to average-case reductions for the SIS and LWE problems, showing that if there exists any hard instance of a lattice reduction then almost all lattice instances are hard in average. In all such reductions, the average case problem instance refers to a special class of lattices related to the group structure G=Zqn. In this talk, we consider more general classes of random lattices where G can be any sufficiently large finite abelian group and show that worst-case to average-case reduction is still preserved in this case. To achieve this, we will introduce a novel group generalization of lattice reduction called structural lattice reduction.

This a a joint work with Nicolas Gama and Phong Nguyen.
  • 24 avril 2013 – Bastien Vayssière (UVSQ) : Design of Key Schedule and Related-key Slide Attacks
Abstract : In the recent years, the design of several lightweight block ciphers has reduced the key schedule to an affine function, or even no key schedule at all. It raises the question: how much can we reduce the key schedule in the design of a secure block cipher? Resistance to slide attacks is a minimal requirement, since for a wide class of block ciphers, these attacks cannot be thwarted only with a strong round function. We analyze the class RXP of affine key schedules based on xors, rotations, and a bit permuted choice. The linearity of those key schedules permits to prove the resistance against single-key and related-key slide attacks.
  • 19 avril 2013 – Dario Fiore (MPI-SWS) : Publicly Verifiable Delegation of Large Polynomials and Matrix Computations.
Abstract : Outsourced computations (where a client requests a server to perform some computation on its behalf) are becoming increasingly important due to the rise of Cloud Computing and the proliferation of mobile devices. Since cloud providers may not be trusted, a crucial problem is the verification of the integrity and correctness of such computation, possibly in a public way, i.e., the result of a computation can be verified by any third party, and requires no secret key – akin to a digital signature on a message.
In this talk I will present new protocols for publicly verifiable secure outsourcing of Evaluation of High Degree Polynomials and Matrix Multiplication. Compared to previously proposed solutions, ours improve in efficiency and offer security in a stronger model and under standard assumptions. Moreover, we propose the first solutions that can easily handle operations over finite fields of any prime characteristic, most notably small fields (such as F2). Towards solving this problem we formalized a new cryptographic primitive, called Algebraic One-Way Function, which turned out to be useful to solve open problems in other cryptographic areas, such as linearly-homomorphic signatures and identification protocols.
This is based on works joint with D. Catalano, R. Gennaro and K. Vamvourellis.
  • 1 mars 2013 – Gaëtan Leurent (UCL) : Differential Attacks against ARX Designs.
Abstract : In this talk, we study differential attacks against ARX schemes. We build upon the generalized characteristics of de Cannière and Rechberger; we introduce new multi-bit constraints to describe differential characteristics in ARX designs more accurately, and quartet constraints to analyze boomerang attacks. We also describe an efficient way to propagate those constraints.
We have developed a set of tools for the analysis of ARX primitives based on this set of constraints. We show that the new constraints are more precise than what was used in previous works, and can detect several cases of incompatibility. In particular, we show that several published attacks are in fact invalid because the differential characteristics cannot be satisfied. This highlights the importance of verifying differential attacks more thoroughly.
Moreover, we are able to build automatically complex non-linear differential characteristics for reduced versions of the hash function Skein. We describe several characteristics for use in various attack scenarios; this results in attacks with a relatively low complexity, in relatively strong settings. In particular, we show practical free-start and semi-free-start collision attacks for 20 rounds and 12 rounds of Skein-256, respectively.
  • 30 janvier 2013 – Daniel Augot (LIX et INRIA Saclay) : Les connexions entre le logarithme discret sur les corps finis non premiers et le décodage des codes de Reed-Solomon.
Résumé : Cheng et Wan étudient depuis 2004 comment le logarithme discret sur les corps non premiers se réduit à un certain problème de décodage des codes de Reed-Solomon. Leur objectif est de prouver la difficulté du décodage des codes de Reed-Solomon, en présence d’un grand nombre d’erreurs, sous l’hypothèse que le logarithme discret est difficile. Nous nous sommes proposés d’étudier la réduction dans un sens direct : comment utiliser des algorithmes de décodage connus pour construire un algorithme de calcul de logarithmes discrets sur les corps finis. La méthode se situe dans le contexte général de calcul de bases d’index, où la technique de découverte de relations repose sur le décodage. Dans un premier temps, nous avons utilisé des algorithmes de décodage unique, comme celui de Gao, par opposition au décodage en liste. Ces méthodes ont été implantées en Magma et NTL. Bien que cette méthode ne semble pas aussi performante que les méthodes classiques à la Adleman, il y a toutefois de nombreuses thématiques originales qui émergent.
Nous ferons aussi le point sur la difficulté du décodage des codes de Reed-Solomon.
En commun avec François Morain.
  • 23 janvier 2013 – Romain Basson (IRMAR) : Algèbre d’invariants des formes binaires en caractéristique positive.
Le développement d’une algorithmique pour les espaces de modules de courbes hyperelliptiques (en petit genre) peut s’envisager via la théorie classique des invariants des formes binaires ; une courbe hyperelliptique de genre g étant simplement reliée à une forme binaire de degré 2g+2. La description et la construction effective de ces algèbres d’invariants en caractéristique nulle ont débuté dans la seconde moitié du XIXème siècle, donnant d’ailleurs naissance aux prémices de l’algèbre commutative, et culminé en 1967 avec le résultat de Shioda concernant les octiques (qualifié de « tour de force » par Mumford !). En revanche, le cas des petites caractéristiques positives reste largement ouvert, notamment pour les octiques. Ainsi, après avoir donné un aperçu de la théorie classique, j’exposerai les résultats actuels concernant les algèbres de formes octiques en petites caractéristiques positives.
  • 9 janvier 2013 – Pierre-Jean Spaenlehauer (University of Western Ontario) : Bases de Gröbner de systèmes structurés et applications en Cryptologie.
Résumé : Pour de nombreuses applications en Cryptologie, en Géométrie Réelle ou en Optimisation, il est essentiel d’avoir des estimations précises de la complexité de résolution de systèmes polynomiaux multi-homogènes, déterminantiels et booléens.
Dans cet exposé, par des méthodes de type bases de Gröbner et sous des hypothèses de généricité sur les coefficients de ces systèmes, je présente de nouvelles bornes de complexité asymptotique :
– pour les systèmes déterminantiels et bilinéaires, ces bornes permettent d’identifier des sous-familles de systèmes pour lesquelles la complexité de résolution est polynomiale en le nombre de solutions ;
– pour les systèmes quadratiques booléens, un nouvel algorithme de résolution est proposé. Pour un système de n équations en n variables, l’espérance de la complexité d’une variante probabiliste est O(2^(0.792 n)), sous des hypothèses algébriques sur le système d’entrée. Ceci permet de résoudre ces systèmes exponentiellement plus rapidement que par recherche exhaustive (de complexité 4 log(n) 2^n).
L’obtention de ces bornes passe par une analyse de la structure algébrique de ces systèmes ; ceci conduit à des formules explicites pour la série de Hilbert générique des idéaux associés.
Enfin, je présenterai des applications de ces résultats à l’analyse de la sécurité des cryptosystèmes MinRank, HFE et QUAD.
Travaux commun avec Jean-Charles Faugère et Mohab Safey El Din (systèmes déterminantiels et multi-homogènes) et avec Magali Bardet, Jean-Charles Faugère et Bruno Salvy (systèmes booléens).
  • 28 novembre 2012 – Sorina Ionica (ENS) : Endomorphism rings of genus 2 jacobians.
Abstract : Algorithms for computing the endomorphism ring of a small dimension abelian variety rely on the exploration of the isogeny graph. Using Galois cohomology, we relate the endomorphism ring structure to certain properties of the ell-Tate pairing, such as non-degeneracy on subgroups of the ell-torsion giving kernels of isogenies of principally polarized abelian varieties in the ell-isogeny graph. In genus 2, we derive an efficient method to check whether the jacobian has locally maximal endomorphism ring at ell. We also present an algorithm to compute horizontal ell-isogenies starting from a jacobian with maximal endomorphism ring. No nice pictures of isogeny graphs this time, sorry!
  • 14 novembre 2012 – Rodolphe Lampe (PRiSM) : L’indistinguabilité du schéma d’Even-Mansour itéré.
Abstract : We analyze the security of the iterated Even-Mansour cipher (a.k.a. key-alternating cipher), a very simple and natural construction of a blockcipher in the random permutation model. This construction, first considered by Even and Mansour (J. Cryptology, 1997) with a single permutation, was recently generalized to use t permutations in the work of Bogdanov et al. (EUROCRYPT 2012). They proved that the construction is secure up to O(N^2/3) queries (where N is the domain size of the permutations), as soon as the number t of rounds is 2 or more. This is tight for t = 2, however in the general case the best known attack requires Ω(N^t/(t+1)) queries. In this paper, we give asymptotically tight security proofs for two types of adversaries :
– for non-adaptive chosen-plaintext adversaries, we prove that the construction achieves an optimal security bound of O(N^t/(t+1)) queries;
– for adaptive chosen-plaintext and ciphertext adversaries, we prove that the construction achieves security up to O(N^t/(t+2)) queries (for t even). This improves previous results for t ≥ 6.
Our proof crucially relies on the use of a coupling to upper-bound the statistical distance of the outputs of the iterated Even-Mansour cipher to the uniform distribution.
  • 7 novembre 2012 – Emmanuel Fouotsa (Université de Bamenda et IRMAR) : Sur un modèle d’Edwards de courbe elliptique défini en toutes caractéristiques.
Résumé : En 2007, Edwards a introduit un modèle de courbe elliptique défini sur les corps finis de caractéristique différente de 2, avec une loi de groupe non complète. Cette lacune sera comblée en 2008 par Bernstein et al. qui généralisent ce modèle. Toutefois, ce modèle reste défini en caractéristique différente de deux. Entre 2008 et 2009, des modèles binaires vont être proposés mais la relation avec le modèle original reste mystérieuse. Dans cet exposé, je présente un nouveau modèle d’Edwards défini en toutes caractéristiques, et qui est isomorphe au modèle original en caractéristique différente de 2. L’obtention de ce modèle et la loi de groupe se fait grâce aux fonctions théta. En particulier, ce nouveau modèle présente une arithmétique efficace et compétitive en caractéristique 2 et sur la ligne de Kummer, comparativement aux autres modèles de courbes elliptiques.
Séminaires CRYPTO 2012-2013