Prochain séminaire CCA le vendredi 16 novembre

La prochaine édition du séminaire CCA se tiendra le vendredi 16 novembre 2018 dans la grande salle du LIP6 de Sorbonnes Université

Séminaire CCA du vendredi 15 juin 2018

Salle Jacques-Louis Lions 2, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)

  • 10h00, Yann Rotella, INRIA Paris : Attaques algébriques revisitées

La complexité de la résolution d’équations algébriques décrivant une primitive cryptographique est généralement difficile à évaluer mais reste cependant un problème fondamental pour les cryptographes. Depuis 2003, l’immunité algébrique est considérée comme le critère pertinent pour évaluer la sécurité des chiffrements symétriques au regard des attaques algébriques.

Au travers de quelques exemples de primitives cryptographiques telles que le PRG de Goldreich, le chiffrement à flot FLIP et les registres filtrés, nous investiguons de manière générale les possibilités que nous offrent des équations particulières. Plus précisément, nous montrons qu’il est possible d’exploiter le caractère creux des certaines équations algébriques, que la représentation soit multivariée ou univariée. Ceci nous permet de déterminer, selon le contexte, le critère à prendre en compte pour évaluer correctement la résistance de certains types de systèmes aux attaques algébriques.


  • 11h30, Victor Cauchois, DGA et IRMAR : Constructions de matrices MDS pour la cryptographie.

Les matrices MDS ont été plébiscitées en cryptographie symétrique pour concevoir les couches de diffusion linéaires car elles assurent une diffusion minimale maximale sur les symboles. En vue d’implémentations matérielles légères, les matrices récursives et les matrices circulantes qui n’utilisent qu’un nombre linéaire de coefficients ont été largement explorées. Un résultat classique sur les corps de caractéristique 2 assure de plus qu’il n’existe pas de matrices circulantes involutives ni de matrices récursives involutives. Il est possible pourtant de « tordre » les définitions classiques de la récursivité, de la cyclicité et de l’involutivité pour construire des matrices MDS qui peuvent être implémentées au niveau matériel avec un nombre linéaire de multiplications dans un corps de Galois et avec une architecture presque identique pour réaliser la multiplication par la matrice ou par son inverse.


  • 14h30, Alexandre  Wallet, LIP, ENS Lyon : On the Ring-LWE and Polynomial-LWE problems.

The Ring Learning With Errors problem (RLWE) comes in various forms. Vanilla RLWE is the decision dual-RLWE variant, consisting in distinguishing from uniform a distribution depending on a secret belonging to the dual OK^vee of the ring of integers OK of a specified number field K. In primal-RLWE, the secret instead belongs to OK. Both decision dual-RLWE and primal-RLWE enjoy search counterparts. Also widely used is (search/decision) Polynomial Learning With Errors (PLWE), which is not defined using a ring of integers OK of a number field K but a polynomial ring Z[x]/f for a monic irreducible f in Z[x]. We show that there exist reductions between all of these six problems that incur limited parameter losses. More precisely: we prove that the (decision/search) dual to primal reduction from Lyubashevsky et al. [EUROCRYPT 2010] and Peikert [SCN 2016] can be implemented with a small error rate growth for all rings (the resulting reduction is nonuniform polynomial time); we extend it to polynomial-time reductions between (decision/search) primal RLWE and PLWE that work for a family of polynomials f that is exponentially large as a function of deg f (the resulting reduction is also non-uniform polynomial time); and we exploit the recent technique from Peikert et al. [STOC 2017] to obtain a search to decision reduction for RLWE. The reductions incur error rate increases that depend on intrinsic quantities related to K and f.

Based on joint work with Miruna Roșca and Damien Stehlé.


  • 16h00, Cécile Pierrot, LORIA : Discrete Logarithm Lattices
In this talk we consider the Bounded Distance Decoding (BDD) problem: Given a lattice L and a vector t such that: t = v + e, with v in L and e an error vector of bounded norm, find v the lattice vector from which t comes. We propose a concrete family of dense lattices of arbitrary dimension n where BDD can be solved in deterministic polynomial time. The lattice construction needs discrete logarithm computations that can be made in deterministic polynomial time for well-chosen parameters. This construction is directly adapted from the Chor-Rivest cryptosystem.Each lattice comes with a deterministic polynomial time decoding algorithm able to decode up to large radius. Namely, we reach decoding radius within O(log n) Minkowski’s bound, for both l1 and l2 norms.
This is a joint work with Léo Ducas.

Séminaire CCA du vendredi 16 mars 2018

Salle Jacques-Louis Lions 2, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)

  • 10h00, Sonia Belaïd, CryptoExperts : On the Security of Composed Masked Implementations with Least Refreshing.  Transparents de l’exposé
    Abstract : Masking is a sound and widely deployed countermeasure to counteract side-channel attacks. It consists in randomly splitting each sensitive variable manipulated in the implementation into t+1 shares, where the masking order t represents the security level. While this countermeasure is very useful to improve the security level, it can be complex to design while t grows. Therefore, until recently, security proofs on masking schemes were limited to small gadgets (additions, multiplications, etc). Namely, no concrete result was given on their composition (e.g., larger implementations) for a tight number of shares (t+1).
    In this talk, I’ll present two recent progresses in this area. The first one, published at CCS in 2016, introduces new security notions to finally achieve secure composition in the widely deployed t-probing model: the t-non interference (t-NI) and the t-strong non interference (t-SNI). Actually satisfied by most existing schemes, these notions are carefully manipulated to prove the probing security of compositions. However, this method can be quite conservative on some schemes and a security proof sometimes requires much more refreshing (i.e., random values) than necessary. Therefore, I’ll also discuss, as a second progress on this topic, a very new method which allows to prove the exact t-probing security of well-chosen schemes and the t-probing security of their composition with less randomness requirements.
  • 11h30, Duong Hieu Phan, Université de Limoges : Identity-based Encryption from Codes with Rank Metric

Abstract : The concept of identity-based encryption (IBE), introduced by Shamir in 1984, allows the use of users’ identifier information such as email as public key for encryption. There are two problems that makes the design of IBE extremely hard: the requirement that the public key can be an arbitrary string and the possibility to extract decryption keys from the public keys. In fact, it took nearly twenty years for the problem of designing an efficient method to implement an IBE to be solved. The known methods of designing IBE are based on different tools: from elliptic curve pairings by Sakai, Ohgishi and Kasahara and by Boneh and Franklin in 2000 and 2001 respectively; from the quadratic residue problem by Cocks in 2001; and from the Learning-with-Error problem by Gentry, Peikert, and Vaikuntanathan in 2008.

In this talk, we propose a new method, based on the hardness of learning problems with rank metric, to design the first code-based IBE scheme. In order to overcome the two above problems in designing an IBE scheme, we first construct a rank-based PKE, called RankPKE, where the public key space is dense and thus can be obtained from a hash of any identity. We then extract a decryption key from any public key by constructing an trapdoor function which relies on RankSign – a signature scheme from PQCrypto 2014.

Joint work with Philippe Gaborit, Adrien Hauteville and Jean-Pierre Tillich.


  • 14h30, Maria Naya Plasencia , INRIA : New Results on Symmetric Quantum Cryptanalysis

 Abstract: The security of symmetric cryptography is completely based on cryptanalysis: we only gain confidence in the security of a symmetric primitive through extensive and continuous scrutiny. It is therefore not possible to determine whether a symmetric primitive might be secure or not in a post-quantum world without first understanding how a quantum adversary could attack it. In this talk I will provide an overview of the subject and present some recent results on symmetric quantum cryptanalysis: a new efficient quantum collision search algorithm (joint work with A. Chailloux and A. Schrottenloher) and an extensive analysis of the use of modular additions on symmetric primitives (joint work with X. Bonnetain). We will discuss some implications of these results in quantum-safe symmetric cryptography.


  • 16h00, Elena Kirshanova, ENS de Lyon : Learning with Errors and Extrapolated Dihedral Cosets

Abstract: In this talk, I introduce the Extrapolated Dihedral Problem (eDCP) – a relaxed version of the dihedral coset problem (DCP). I show that under quantum polynomial time reductions, LWE is equivalent to eDCP. The extent of extrapolation varies with the LWE noise rate. The result implies that LWE does not require the full power of solving DCP, but rather only a solution to eDCP, which could be easier to find. I will also discuss a connection between eDCP and Childs and Van Dam’s algorithm for generalized hidden shift problems (SODA 07).

Joint work with Zvika Brakerski, Damien Stehlé, Weiqiang Wen


Séminaire CCA du vendredi 17 novembre 2017

Salle Jacques-Louis Lions 2, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)

  • 10h00, Valentin Suder, Université de Versailles : Equivalences différentielles des boîtes-S

Dans ce travail, nous parlerons de deux notions d’équivalences sur les boîtes-S, ces fonctions non-linéaires qui composent les algorithmes de cryptographie symétrique. Premièrement, nous introduisons la DDT-équivalence, qui relie les fonctions booléennes vectorielles qui ont la même table de distribution des différences (DDT). Ensuite, nous comparons cette notion à l’équivalence entre deux fonctions dont les DDT ont le même support, et que nous appelons la $\gamma$-équivalence. Nous discutons le lien entre ces deux équivalences et donnons un algorithme qui permet de calculer les classes d’équivalences. Nous en profitons pour étudier la taille de ces classes pour des familles de boîtes-S connues. Enfin, nous démontrons que les permutations APN ne peuvent avoir deux lignes de leur DDT qui soient similaires.

  • 11h30, Guilhem Castagnos, Université de Bordeaux : Encryption Switching Protocols Revisited: Switching modulo p

Last year, Couteau, Peters and Pointcheval introduced a new primitive called encryption switching protocols, allowing to switch ciphertexts between two encryption schemes. If such an ESP is built with two schemes that are respectively additively and multiplicatively homomorphic, it naturally gives rise to a secure 2-party computation protocol. It is thus perfectly suited for evaluating functions, such as multivariate polynomials, given as arithmetic circuits. Couteau et al. built an ESP to switch between Elgamal and Paillier encryptions which do not naturally fit well together. Consequently, they had to design a clever variant of Elgamal over Z/nZ with a costly shared decryption. In this talk, we first present a conceptually simple generic construction for encryption switching protocols. We then give an efficient instantiation of our generic approach that uses two well-suited protocols, namely a variant of Elgamal in Z/pZ and the Castagnos-Laguillaumie encryption defined over class groups of quadratic fields which is additively homomorphic over Z/pZ.
Among other advantages, this allows to perform all computations modulo a prime p instead of an RSA modulus. Overall, our solution leads to significant reductions in the number of rounds as well as the number of bits exchanged by the parties during the interactive protocols. We also show how to extend its security to the malicious setting.

Joint work with Laurent Imbert and Fabien Laguillaumie.

  • 14h30, Cyril Hugounenq, Université Grenoble Alpes : Calcul d’isogénies à l’aide du Frobenius

Cet exposé présente des résultats issu d’un travail commun avec Luca De Feo Jérôme Plût et Eric Schost.

Le problème du calcul d’isogénies est étant donné deux courbes elliptiques, un entier r tel que les deux courbes soient reliées par une isogénie de degré r, calculer cette isogénie. Ce problème est apparu dans l’algorithme SEA de comptage de points de courbes elliptiques définies sur des corps finis. L’apparition de nouvelles applications du calcul d’isogénies (cryptosystème à trappe, fonction de hachage, accélération de la multiplication scalaire, cryptosystème post quantique) ont motivé par ailleurs la recherche d’algorithmes
plus rapides en dehors du contexte SEA. L’algorithme de Couveignes (1996), malgré ses améliorations par De Feo (2011), présente la meilleure complexité en le degré de l’isogénie mais ne peut s’appliquer dans le cas de grande caractéristique.

L’objectif de cet exposé est donc de présenter une modification de l’algorithme de Couveignes utilisable en toute caractéristique avec une complexité en le degré de l’isogénie similaire à celui de Couveignes.

L’amélioration de l’algorithme de Couveignes se fait en suivant deux axes: la construction de tours d’extensions de corps finis de degré $\ell$ efficaces pour rendre les opérations plus rapides, à l’image
des travaux de De Feo (2011), De Feo Doliskani Schost (2013), Doliskani Schost (2015), et la détermination d’ensembles de points d’ordre $\ell^k$ stables sous l’évaluation d’isogénies.

L’exposé se concentrera sur le second axe pour lequel nous étudions les graphes d’isogénies. Nous utilisons pour notre travail les résultats précédents de Kohel (1996), Fouquet et Morain (2001), Miret et al. (2005,2006,2008), Ionica et Joux (2001). Nous présentons donc dans cet exposé, à l’aide d’une étude de l’action du Frobenius sur les points d’ordre $\ell^k$, un nouveau moyen de déterminer les directions dans le graphe (volcan) d’isogénies. Ces directions vont nous servir à déterminer des points stables sous l’évaluation d’isogénies et ainsi nous permettre d’atteindre notre objectif d’amélioration de l’algorithme de Couveignes.

  • 16h00 : Marine Minier, Université de Lorraine : Utilisation de la programmation par contraintes pour la recherche d’attaques différentielles à clés liées contre l’AES.

l’AES (Advanced Encryption Standard) est comme son nom l’indique le standard actuel de chiffrements par blocs. C’est donc tout naturellement un des algorithmes les plus étudiés. Au cours de ces dernières années, plusieurs cryptanalyses ont été découvertes dans différents modèles d’attaques. Dans cet exposé, nous nous intéresserons aux attaques différentielles à clés liées où l’adversaire peut introduire des différences dans les textes clairs mais également dans la clé. Nous montrons alors comment la programmation par contraintes (CP) peut être utilisée pour modéliser ces attaques et permet de trouver efficacement toutes les chemins différentiels à clés liées optimaux sur AES-128, AES-192 et AES-256. En particulier, nous améliorons la meilleure différentielle contre la version complète d’AES-256 et nous donnons la meilleure différentielle contre 10 tours d’AES-192. Ces résultats nous ont permis d’améliorer, sur AES-256, la complexité du meilleur distingueur à clés liées, de la meilleure attaque de base à clés liées et de la meilleure q-multicollision.

Séminaire CCA du vendredi 9 juin

Salle Jacques-Louis Lions 2, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)

  • 10h00, Luca de Feo, UVSQ : Open problems in isogeny-based cryptography
    Résumé : Isogeny-based cryptography (IBC) is a very young field, only 10 years old. Protocols in this family include key-exchange, encryption, « provably secure » hash functions and trapdoor systems. Hardness assumptions in IBC come from the difficulty of finding paths in isogeny graphs, that is graphs of elliptic curves linked by isogenies of some prescribed degree. Recently some IBC protocols have raised a wave of interest thanks to their resistance to quantum attacks and their compact key size. This talk will review the essential topics in IBC and list some open problems, in a way accessible to the non-specialist.
  • 11h30, Damien Stehlé, ENS Lyon : Middle-Product Learning With Errors

Résumé : We introduce a new variant MP-LWE of the Learning With Errors problem (LWE) making use of the Middle Product between polynomials modulo an integer q. We exhibit a reduction from the Polynomial-LWE problem (PLWE) parametrized by a polynomial f, to MP-LWE which is defined independently of any such f. The reduction only requires f to be monic with constant coefficient coprime with q. It incurs a noise growth proportional to the so-called expansion factor of f. We also describe a public-key encryption scheme with quasi-optimal asymptotic efficiency (the bit-sizes of the keys and the run-times of all involved algorithms are quasi-linear in the security parameter), which is secure against chosen plaintext attacks under the MP-LWE hardness assumption. The scheme is hence secure under the assumption that PLWE is hard for at least one polynomial f of degree n among a family of f’s which is exponential in n.

This is joint work with Miruna Roșca, Amin Sakzad and Ron Steinfeld.

Slides de l’exposé

  • 14h30, Matthieu Rambaud, Télécom-ParisTech : Dense families of explicit coding-friendly curves

Résumé : A folklore conjecture states that, for all p a prime number and 2t an even integer, there exists a family of curves defined over the prime field  F_p  such that
(i) the genera tend to infinity
(ii) the ratio of two successive genera tends to 1 (Density condition)
(iii) after a base field extension of degree 2t, the asymptotic number of points reaches the Ihara bound (Optimality condition)
The only cases known so far are for t=1, with the classical modular curves X_0(N).  Cascudo–Cramer–Xing–Yang showed that certain cases of this conjecture, if true, would divide by two the complexity of the bilinear multiplication in extensions of small finite fields F_p.
We first present a false –but talkative– proof of the conjecture from the previous authors. We then propose an explicit family of Shimura curves solving the case p=3 and 2t=6.

  • 16h00, Kaushik Chakraborty, INRIA : Cryptography with Space-Time Constraint

Résumé : In the presentation, I will discuss about designing cryptographic primitives using the concept of no-superluminal signalling (NSS) principle. According to NSS principle, information can’t travel faster than the speed of light. Using this principle together with the principles of Quantum information, one can design certain cryptographic primitives which are impossible to do so in classical domain without any computational assumption. I shall also discuss about a couple of cryptographic primitives, namely Position Based Quantum Cryptography and Bit Commitment. For position based cryptography, I will talk about a generic attack strategy to break any position verification scheme. For bit commitment, I will explain how to design bit commitment scheme without any computational assumption. I would like to conclude by discussing about the security of such schemes in post-quantum era.

Séminaire CCA du 20 janvier 2017

Salle Jacques-Louis Lions 2, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)

  • 10h00, Jean-Pierre Flori, ANSSI : Quelle courbe elliptique pour la cryptographie ?
    Résumé : Choisir une courbe elliptique pour un usage cryptographique n’est pas une tâche aussi simple qu’il n’y paraît. C’est d’autant plus vrai quand il s’agit de standardiser une courbe destinée à être utilisée par un grand nombre de systèmes et pour une longue durée. En effet,  alors que les critères de résistance aux attaques classiques sont bien compris, le processus de sélection une courbe correcte est source de  « malléabilité » et des doutes ont été émis sur la possibilité de manipuler ce processus afin de générer une courbe qui tomberait dans une classe faible (mais dont la faiblesse ne serait connue que d’un nombre restreint de personnes). Dans cet exposé nous nous intéresserons aux différents critères à prendre compte lors de la génération d’une courbe, que ce soit pour satisfaire les plus paranoïaques ou les plus avides de performances, et à l’assurance qu’apporte le processus sur la « non-malléabilité » de la courbe produite, mais aussi à la construction de certificats permettant de vérifier rapidement qu’une courbe a bien été générée par un processus donné.
  • 11h15,  : Christophe Petit, University of Oxford, Mathematical Institute : Post-quantum cryptography based on supersingular isogeny problems?

Abstract: Motivated by Shor’s quantum factorization and discrete logarithm algorithms and by recent progress on quantum computer hardware, the biggest national security agencies around the world are encouraging a transition towards cryptography protocols that will resist to quantum computers. Isogeny-based cryptography is a recent trend in this area, with papers on the topic published at top crypto conferences and efficient implementations developed by Microsoft Research.

In this talk, I will review the isogeny problems that have been proposed in the literature, the existing cryptographic constructions based on these problems, and some preliminary cryptanalysis results.

The talk will include joint works with Lauter-Kohel-Tignol (ANTS2014), Galbraith-Shani-Ti (ASIACRYPT2016), and Galbraith-Silva Velon.

  • 14h15, Nabil Merkiche, DGA IP  et Sorbonnes universités, UPMC Univ Paris 06, CNRS, LIP6 : Mise en oeuvre d’accélérateurs matériels pour la cryptographie basé sur l’arithmétique RNS

Résumé : L’arithmétique RNS appliquée à la cryptographie est un sujet de recherche dans le domaine académique. Par son caractère intrinsèquement parallèle, cette arithmétique est un excellent candidat pour des accélérateurs matériels sur silicium. Dans un premier temps, nous verrons comment cette arithmétique est utilisée dans différentes applications cryptographiques : réduction modulaire pour calcul sur courbes elliptiques et son utilisation pour le calcul sur les réseaux euclidien (arrondi de Babaï). Dans une second temps, nous verrons que l’intérêt de l’arithmétique RNS ne s’arrête pas à son efficacité dans les calculs, mais aussi à détecter des attaques en fautes « à la volée » lors de calculs cryptographiques.

  • 15h30, Pierrick Méaux, Inria, ENS, CNRS, PSL : Symmetric Encryption Scheme adapted to Fully Homomorphic Encryption Scheme

Abstract : Fully Homomorphic Encryption is a recent powerful cryptographic construction, which enables one to securely compute all functions on encrypted data, and decrypt the result of the function applied to the real data. This construction gives the possibility to securely delegate computation, which is a very important property with the increasing development of Cloud computing. Nevertheless, in current client-server frameworks, the client devices are too restricted to support pure FHE. In order to solve this problem, FHE has to be combined with primitives which incur small computation and communication cost: Symmetric Encryption schemes.

In this talk, we will present symmetric encryption schemes adapted to FHE, focusing on the FLIP family of stream ciphers.
The presentation will be based on the following works:
1. Méaux, Journault, Standaert, Carlet. Towards stream ciphers for efficient FHE with low-noise ciphertexts. Eurocrypt 2016
2. Duval, Lallemand, Rotella. Cryptanalysis of the FLIP Family of Stream Ciphers. Crypto 2016

Séminaire CCA du 14 octobre

Salle Jacques-Louis Lions 2, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)

  • 10h00, Alain Passelègue, Equipe-Projet CASCADE, ENS : Randomness Complexity of Private Circuits for Multiplication.

Résumé : Many cryptographic algorithms are vulnerable to side channel analysis and several leakage models have been introduced to better understand these flaws. In 2003, Ishai, Sahai and Wagner introduced the d-probing security model, in which an attacker can observe at most d intermediate values during a processing. They also proposed an algorithm that securely performs the multiplication of 2 bits in this model, using only d(d+1)/2
random bits to protect the computation. We study the randomness complexity of multiplication algorithms secure in the d-probing model. We propose several contributions: we provide new theoretical characterizations and constructions, new practical constructions and a new efficient algorithmic tool to analyze the security of such schemes.

We start with a theoretical treatment of the subject: we propose an algebraic model for multiplication algorithms and exhibit an algebraic characterization of the security in the d-probing model. Using this characterization, we prove a linear (in d) lower bound and a quasi-linear (non-constructive) upper bound for this randomness cost. Then, we construct a new generic algorithm to perform secure multiplication in the d-probing model that only uses d+d2/4 random bits.

From a practical point of view, we consider the important cases d4 that are actually used in current real-life implementations and we build algorithms with a randomness complexity matching our theoretical lower bound for these small-order cases. Finally, still using our algebraic characterization, we provide a new dedicated verification tool, based on information set decoding, which aims at finding attacks on algorithms for fixed order d at a very low computational cost.

  • 11h15, David Kohel, IMM, Université Aix-Marseille : La géométrie de l’arithmétique efficace des courbes elliptiques
    Résumé : L’introduction des courbes d’Edwards en 2007 a relancé l’étude plus profond de l’arithmétique des courbes elliptiques au vu des applications cryptographiques. En particulier, la recherche s’est focalisée sur le rôle du modèle d’une courbe elliptique — un triple de courbe, point de base, et un plongement projectif
    ou affine. Au côté computationnel, un modèle projectif (par rapport à un modèle affine) permet d’éviter des inversions dans le corps de base, tandis qu’au côté mathématique, il permet de réduire plusieurs questions de l’arithmétique à l’algèbre linéaire (en passant par le langage des faisceaux). Nous exposons le rôle du modèle, particulièrement sa classification linéaire et son rôle dans la linéarisation des opérations d’addition, de doublement, et de multiplication scalaire sur une courbe elliptique.
  • 14h15, Pierre-Alain Fouque, IRISA, Université de Rennes 1 : Comparison between Subfield and Straightforward Attacks on NTRU

Recently in two independent papers, Albrecht, Bai and Ducas and Cheon, Jeong and Lee presented two very similar attacks, that allow to break NTRU with larger parameters and GGH Multinear Map without zero encodings. They proposed an algorithm for recovering the NTRU secret key given the public key which apply for large NTRU modulus, in particular to Fully Homomorphic Encryption schemes based on NTRU. Hopefully, these attacks do not endanger the security of the NTRUE NCRYPT scheme, but shed new light on the hardness of this problem. The basic idea of both attacks relies on decreasing the dimension of the NTRU lattice using the multiplication matrix by the norm (resp. trace) of the public key in some subfield instead of the public key itself. Since the dimension of the subfield is smaller, the dimension of the lattice decreases, and lattice reduction algorithm will perform better. Here, we revisit the attacks on NTRU and propose another variant that is simpler and outperforms both of these attacks in practice. It allows to break several concrete instances of YASHE, a NTRU-based FHE scheme, but it is not as efficient as the hybrid method of Howgrave-Graham on concrete parameters of NTRU. Instead of using the norm and trace, we propose to use the multiplication by the public key in some subring and show that this choice leads to better attacks. We √ can then show that for power of two cyclotomic fields, the time complexity is polynomialFinally, we show that, under heuristics, straightforward lattice reduction is even more efficient, allowing to extend this result to fields without non-trivial subfields, such as NTRU Prime. We insist that the improvement on the analysis applies even for relatively small modulus ; though if the secret is sparse, it may not be the fastest attack. We also derive a tight estimation of security for (Ring-)LWE and NTRU assumptions. when q=2Ω(nloglogn).

  • 15h30, Jean-Christophe Deneuville, XLIM, Université de Limoges – Chiffrement efficace basé sur les codes, sans masquage de structure

Résumé : La plupart des schémas de chiffrement basés sur les codes (McEliece [1], MDPC [2] notamment) reposent sur le fait de masquer la structure du code utilisé. Pour McEliece, cela a souvent conduit à des attaques efficaces. D’autre part, introduire du bruit dans les chiffrés peut conduire à des erreurs de déchiffrement, et le fait de ne pas pouvoir diminuer arbitrairement la probabilité de mal déchiffrer peut également conduire à des attaques [3]. Dans cet exposé, je présenterai une nouvelle approche (inspirée de [4]) pour la construction de schémas de chiffrement basés sur les codes, dont la sécurité ne dépend pas de la qualité du masquage de la structure. Cette approche est instanciée en métrique de Hamming et en métrique Rang, et conduit à des cryptosystèmes relativement efficaces (respectivement HQC et RQC*). Je présenterai la réduction de sécurité de IND-CPA au problème du « syndrom decoding » de codes quasi-cycliques ainsi qu’une analyse de la probabilité d’erreur de déchiffrement pour HQC. Asymptotiquement notre approche permet d’obtenir des tailles de clés publiques en O(λ^2) pour HQC et O(λ^{4/3}) pour RQC pour λ le paramètre de sécurité. Enfin je donnerai des jeux de paramètres concrets pour différents paramètres de sécurité pour HQC et RQC.

*HQC : Hamming Quasi-Cyclic, RQC : Rank Quasi-Cyclic

[1] : Robert J McEliece. A public-key cryptosystem based on algebraic. Coding Thv, 4244:114–116, 197

[2] : Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier, and Paulo SLM Barreto. Mdpc-mceliece: New mceliece variants from moderate density parity-check codes. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 2069–2073. IEEE, 2013.

[3] : Guo, Qian and Johansson, Thomas and Stankovski, Paul. A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors. 22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2016

[4] : Michael Alekhnovich. More on average case vs approximation complexity. In 44th FOCS, pages 298–307. IEEE Computer Society Press, October 2003.


Séminaire CCA du 1er Juillet

Salle Jacques-Louis Lions, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)

  • 10h00, Léo Perrin, Université du Luxembourg : Rétro-ingénierie de boîtes S
    Résumé : Les boîtes-S sont des composants cruciaux de bien des systèmes de chiffrements symmétriques modernes, notamment l’AES. Leur conception doit obéir à des contraintes aussi bien d’ordre cryptographique, comme la non-linéarité, que d’ordre technique, comme la possibilité d’une implémentation efficace.
    Les critères voire la structure utilisés ne sont parfois pas décrits dans la spécification d’un nouvel algorithme. Par exemple, ni la NSA ni le FSB (son homologue russe) ne justifient leurs choix de boîte-S.
    Cette présentation traite des différentes méthodes de rétro-ingénierie que nous avons développées pour retrouver la structure ou les critères utilisés pour construire une boîte-S dont on ne connaît que la table des valeurs. En particulier, ces méthodes nous ont permis de retrouver des informations non-publiées sur la boite-S utilisée par le chiffrement par blocs Skipjack (conçu par la NSA) et celle utilisée à la fois par la fonction de hachage Stribog et le chiffrement par blocs Kuznechik (conçus par le FSB).D’une façon plus surprenante, nous avons pu appliquer les mêmes méthodes à la décomposition de la seule permutation APN connue opérant sur un nombre pair de bits, à savoir celle trouvée par Dillon et al.
  • 11h15, Benoît Gérard, DGA MI et IRISA Université de Rennes 1 :  Canaux auxiliaires et cryptographie symétrique : deux attaques de l’espace
    Résumé : Trop souvent on entend qu’une attaque par canaux auxiliaires sur une primitive symétrique est impossible dès lors que l’on n’a que peu de mesures à disposition. On entend aussi que si toute variable intermédiaire fuitée dépend d’une grosse partie du secret l’attaque demande une puissance de calcul trop grande. Le but de cette présentation est de montrer que bien que les attaques soient alors plus compliquées, on est parfois en mesure d’attaquer dans ces conditions et qu’il est donc important d’avoir une analyse de sécurité plus poussée.
    Dans un premier temps on présentera le principe des attaques par canaux auxiliaires classiques sur les primitives symétriques. Celles-ci sont basées sur une stratégie de type diviser pour mieux régner ainsi que sur l’utilisation d’outils statistiques appliqués à un grand nombre de mesures.
    On montrera ensuite que dans le cas d’implantations très sérialisées il est possible d’utiliser un petit nombre de courbes (voire une seule). On détaillera l’exemple des SASCA où l’attaque s’apparente à un décodage de code LDPC.
    Enfin, on montrera que des attaques peuvent toujours être menées même quand la stratégie diviser pour mieux régner n’est pas applicable (en tout cas pas directement). On présentera alors les attaques sur la multiplication dans GF(2^n) qui se réduisent à la résolution d’un problème LPN.
  • 14h15, André Chailloux, INRIA Paris : Cryptographie Relativiste
    Résumé : La cryptographie relativiste est un nouvel axe de recherche, dont l’objectif est d’utiliser un principe de physique relativiste qui implique que l’information ne peut pas être transmise à une vitesse plus grande que celle de la lumière. En utilisant des contraintes de temps et de lieu, on peut utiliser ce principe pour prouver la sécurité de certaines tâches cryptographiques.
    L’avantage de la cryptographie relativiste est la garantie d’une sécurité à long terme, indépendante des avancées des logiciels ou du matériel informatique (y compris l’arrivée des ordinateurs quantiques) et s’inscrit donc dans le contexte de la cryptographie post-quantique, et plus généralement dans celui de la sécurité à très long terme.
    Je me focaliserons sur certaines primitives utilisées dans calcul multipartite sécurisé, avec des applications comme les systèmes de vote en ligne ou les enchères secrètes. Je présenterai quelques constructions de ces primitives et discuterai des possibilités ainsi que des difficultés de leur implémentation.
  • 15h30, Xavier Caruso, IRMAR, Université de Rennes 1 : Multiplication rapide des polynômes tordus sur les corps finis
    Résumé : Les polynômes tordus, appelés également parfois polynômes de Ore, sont une version non commutative des polynômes usuels. Ils interviennent dans plusieurs domaines des mathématiques et de l’informatique et, en particulier, en théorie des codes où ils servent de support aux codes
    de Gabidulin. Dans cet exposé, je présenterai des algorithmes rapides pour la multiplication des polynômes tordus, basés sur une stratégie de type évaluation-interpolation. Les applications à la théorie des codes
    seront également discutées.

Séminaire CCA du 1er avril 2016

Salle Jacques-Louis Lions, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)

  • 10h00, François Morain, LIX, INRIA Saclay-Ile de France : Factorisation d’entiers — hier, aujourd’hui, demain
    Résumé : de tous temps, il y a eu des passionnés des nombres pour factoriser des entiers. De nos jours, c’est devenu un enjeu de sécurité. Les techniques ont évolué avec le temps, le matériel également. Après un bref survol du passé et du présent, nous présenterons l’algorithme de factorisation de Shor, qui fonctionne dans le modèle quantique, et qui sert de motivation à une grande partie des recherches sur les ordinateurs quantiques. Nous montrerons que l’arithmétique classique peut apporter son aide à certaines parties des implantations physiques de cet algorithme.
    Travail conjoint avec F. Grosshans, T. Lawson, B. Smith.
  • 11h15, Pierre Karpman,  LIX, INRIA Saclay-Ile de France et NTU :  Collisions explicites pour la fonction de compression de SHA-1
    Résumé : Il y a dix ans, Wang et al. publièrent la première attaque théorique sur la fonction de hachage SHA-1 en montrant comment obtenir des collisions pour un coût d’environ 2^69 appels à  la fonction au lieu des 2^80 requis par une attaque générique (W2005). Ces travaux ont eu un impact considérable sur la recherche sur SHA-1 en particulier et sur les fonctions de hachage en général. Cependant, malgré plusieurs améliorations qui ont fait baisser le coût estimé de la meilleure attaque à  2^61 (Stevens, 2013), aucune collision n’a encore été publiquement calculée et beaucoup de travaux se sont concentrés sur l’attaque de versions réduites.Dans cet exposé nous présenterons des améliorations récentes de l’état de l’art sur trois points : 1) nous montrons comment monter des attaques sur la fonction de compression de SHA-1 plutôt que sur la fonction de hachage complète ; 2) nous avons explicitement calculé une collision pour la fonction de compression complète de SHA-1, pour un coût moyen estimé de 2^57 (ainsi que pour une version réduite à  76/80 tours pour un coût moyen de 2^50) ; 3) la recherche de collision a été implémentée sur cartes graphiques et a permis de démontrer l’intérêt de ce type de plateforme pour le calcul d’attaques de cryptographie symétrique (Karpman et al., 2015), (Stevens et al., 2016).

Travaux communs avec Marc Stevens et Thomas Peyrin.

  • 14h15, Gwezheneg Robert, IRMAR, Université de Rennes 1 : Décodage des codes de Gabidulin généralisés
    Résumé : Les codes de Gabidulin sont l’analogue en métrique rang des codes de Reed-Solomon. Parmi leurs propriétés notables, ils sont optimaux et disposent d’algorithmes de décodage efficaces. Cela explique leur utilisation dans diverses applications, comme par exemple le codage espace-temps. Concevoir un tel code consiste à décrire une famille finie de matrices complexes, éloignées les unes des autres en métrique rang. C’est dans ce but que nous avons généralisé les codes de Gabidulin à des corps de nombres. Dans cet exposé, nous allons nous intéresser à leur décodage, et plus précisément à deux aspects de ce décodage.Nous commencerons par définir les codes de Gabidulin généralisés. Pour cela, nous présenterons les $\theta$-polynômes et la métrique rang. Nous établirons que ce sont des codes MRD (ils atteignent la borne de Singleton pour la métrique rang).La première partie est consacrée au décodage d’erreurs et d’effacements. Cela concerne aussi bien les codes originaux sur les corps finis que leur généralisation. Dans le modèle d’erreur seule, décoder un code de Gabidulin revient à résoudre un problème appelé reconstruction linéaire. Nous verrons un algorithme quadratique résolvant ce problème. Nous présenterons ensuite deux modèles d’effacements, et expliquerons que corriger des effacements revient à décoder un autre code de Gabidulin, avec des paramètres différents.Dans la seconde partie, nous allons considérer des codes dont les coefficients sont dans un anneau d’entiers. Nous serons alors confrontés à un problème spécifique aux corps infinis : la croissance des coefficients. Bien que le nombre d’opérations soit quadratique, la taille des nombres sur lesquels elles portent augmente exponentiellement, rendant l’algorithme inutilisable en pratique. Nous allons donc nous intéresser à la réduction des codes de Gabidulin généralisés, modulo certains idéaux de l’anneau des entiers. Nous montrerons que notre algorithme de décodage calcule le mot du code modulo cet idéal.
  • 15h30, Marc Kaplan, TelecomParisTech : attaquer les cryptosystèmes symétriques en utilisant l’algorithme quantique de recherche de période
    Résumé : au milieu des années 90, la découverte par Peter Shor de l’algorithme qui porte son nom a révélé au monde que les ordinateurs quantiques, quand ils seront disponibles, seront une grande menace pour la cryptographie à clé publique telle qu’on la pratique aujourd’hui. Au coeur de cet algorithme se trouve une procédure de recherche de période dans un groupe. Dans notre exposé, nous montrerons que le plus simple algorithme quantique de recherche de période, connu sous le nom d’algorithme de Simon, peut également être utilisé pour attaquer la cryptographie symétrique.Pour certains groupes assez simples, l’algorithme de Simon permet de trouver la période d’un fonction avec O(n) requêtes quantiques à la fonction alors qu’il faut O(2^n) requêtes classiques. Cela permet de construire des attaques simples en faisant des requêtes en superposition à l’oracle cryptographique. Nous appliquons cette idée à plusieurs cryptosystèmes, incluant certains modes d’operation utilisés pour l’authentification ou le chiffrement authentifié, ainsi que des candidats à la compétition CEASAR. Enfin, nous montrons que les slide attacks reposent sur une structure similaire et peuvent être exponentiellement plus efficaces pour un adversaire quantique que pour un adversaire classique.

Séminaire CCA du 11 décembre

Amphi émeraude, Télecom Paris Tech, 46 rue Barrault

  • 10:00. Pierre Loidreau « Codes cellulaires et applications cryptographiques »

Dans le domaine de la cryptographie à clé publique reposant sur les codes correcteurs d’erreurs, un problème essentiel pour les concepteurs de systèmes est de parvenir à gérer la très grande taille de clé publique nécessaire pour assurer une sécurité convenable. Un moyen consiste à utiliser des codes structurés tels les codes quasi-cycliques qui permettent des représentations compactes de la clé publique. Cependant, même si en théorie la sécurité des systèmes n’en est pas affectée, dans la pratique la structure algébrique sous-jacente est assez peu considérée dans la mise au point d’attaques par décodage. Dans cet exposé on étudiera une famille de codes généralisant la notion de codes quasi-cycliques. La matrice génératrice est formée de « cellules » qui sont des matrices carrées prises dans une algèbre de matrices engendrée par un polynôme. On montrera qu’un diviseur de ce polynôme permet d’engendrer des codes de paramètres plus petits. On décrira les effets de cette projection sur le décodage et la recherche de mots de petit poids dans des codes quasi-cycliques tant en métrique de Hamming qu’en métrique rang. On montrera comment cette approche peut réduire la complexité des attaques déjà connues, en fonction du poids du polynôme considéré ou bien de l’espace de ses coefficients. Les résultats soulèvent des questions sur l’existence  de polynômes particuliers qui divisent des polyômes de type $X^n-1$ dans des corps finis.
Bien que le sujet ne soit pas lié à la cryptographie à base de réseaux, on  montrera, si le temps le permet comment ces idées ont été appliquées ou pourraient être appliqués à des problèmes de décodage de type Ring-LWE.

  • 11:15. Léo Ducas,  « Fast Fourier Orthogonalization »

The classical Fast Fourier Transform (FFT) allows to compute in quasi-linear time the product of two polynomials, in the circular convolution ring $\mathbb R[x]/(x^d -1)$ — a task that naively requires quadratic time. Equivalently, it allows to accelerate matrix-vector products when the matrix is circulant. In this work, we discover that the ideas of the FFT can be applied to speed up the orthogonalization process of a circulant matrix. We show that, when $n$ is composite, it is possible to proceed to the orthogonalization in an inductive way, leading to a structured Gram-Schmidt decomposition. In turn, this structured Gram-Schmidt decomposition accelerates a cornerstone lattice algorithm: the Nearest Plane algorithm. The results easily extend to cyclotomic rings, and can be adapted to Gaussian Samplers. This finds applications in lattice-based cryptography, improving the performances of trapdoor functions.

  • 14:15. Philippe Langevin, Institut mathématique de Toulon, « propriété d’extension de la métrique de Lee »

Le théorème d’extension de MacWilliams affirme qu’une isométrie définie sur un code linéaire se prolonge  en une transformation monomiale, c’est-à-dire,  une isométrie de l’espace de Hamming tout entier. La question du  prolongement d’une isométrie à l’espace ambiant se pose pour toutes les métriques dans mon exposé je ferai le point sur des travaux récents concernant la propriété d’extension de la métrique de
Lee dans le cas des codes linéaires définis sur un corps premier.

  • 15:30. Renaud Sirdey, CEA List, « Mise en œuvre pratique du chiffrement homomorphe »

Nous présentons des travaux d’implémentation du chiffrement (fully) homomorphe et de développement d’outils logiciels supports (compilateurs) permettant de faire le lien entre des algorithmes applicatifs et ce formalisme bas-niveau, de manière aussi performante que possible. L’exposé portera également sur les problématiques d’intégration du chiffrement homomorphe dans des cas d’applications concrets, en particulier pour ce qui est de son interfaçage avec du chiffrement symétrique. Enfin, nous essaierons de faire un point sur les performances actuelles et présenterons quelques scénarios applicatifs qui semblent aujourd’hui être à la portée du FHE.