Edition du vendredi 29 mars 2019 en salle Henri Lebesgue au rez de chaussée de  l’IRMAR de Rennes, bâtiments 22-23, campus de beaulieu. 

• 10h15 – Illaria Chilloti, KU Leuven  : Improved Bootstrapping for Approximate Homomorphic Encryption

Résumé : Since Cheon et al. introduced a homomorphic encryption scheme for approximate arithmetic (Asiacrypt ’17), it has been recognized as suitable for important real-life usecases of homomorphic encryption, including training of machine learning models over encrypted data. A follow up work by Cheon et al. (Eurocrypt ’18) described an approximate bootstrapping procedure for the scheme.
In this work, we improve upon the previous bootstrapping result. We improve the amortized bootstrapping time per plaintext slot by two orders of magnitude, from ∼ 1 second to ∼ 0.01 second. To achieve this result, we adopt a
smart level-collapsing technique for evaluating DFT-like linear transforms on a ciphertext. Also, we replace the Taylor approximation of the sine function with a more accurate and numerically stable Chebyshev approximation, and design a modified version of the Paterson-Stockmeyer algorithm for fast evaluation of Chebyshev polynomials over encrypted data.

(joint work with Hao Chen and Yongsoo Song)

• 11h30 : Ayoub Otmani, LITIS, Université de Rouen : Permutation Code Equivalence is Not Harder Than Graph Isomorphism When Hulls are Trivial

Résumé :  This talk deals with the problem of deciding if two finite-dimensional linear subspaces over an arbitrary field are identical up to a permutation of the coordinates. This problem is referred to as the permutation code equivalence.

I will explain that given access to a subroutine that decides if two weighted undirected graphs are isomorphic, one may deterministically decide the permutation code equivalence provided that the underlying vector spaces intersect trivially with their orthogonal complement with respect to an arbitrary inner product. Such class of vector spaces are usually called linear codes with trivial hulls. The reduction is efficient because it essentially boils down to computing the inverse of a square matrix of order the length of the involved codes. Experimental results obtained with randomly drawn binary codes with trivial hulls show that permutation code equivalence can be decided in a few minutes for lengths up to 50,000.

• 13h30 :Ida Tucker, ENS Lyon : Practical fully secure unrestricted inner product functional encryption modulo prime p.

Résumé :Functional encryption (FE) is an advanced cryptographic primitive which allows, for a single encrypted message, to finely control how much information on the encrypted data each receiver can recover. To this end many functional secret keys are derived from a master secret key. Each functional secret key allows, for a ciphertext encrypted under the associated public key, to recover a specific function of the underlying plaintext.

However constructions for general FE are far from practical, or rely on  non-standard and ill-understood cryptographic assumptions.

In this talk I will focus on the construction of efficient FE schemes for linear functions (i.e. the inner product functionality), and the framework in which our constructions hold. Such schemes yield many practical applications, and our constructions are the first FE schemes for inner products modulo a prime that are both efficient and recover the result whatever its size I will also describe an instantiation of the framework using class groups of imaginary quadratic fields.

• 14h45 Brice Minaud, INRIA : Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks

Résumé : Searchable encryption enables a client to encrypt data, and outsource its storage to an untrusted server, while retaining the ability to issue search queries over the outsourced data. For efficiency reasons, all practical constructions in this area allow for the host server to learn a limited amount of information on the encrypted data as it processes queries, expressed in the security model by a leakage function. In this talk, I will give a short introduction to searchable encryption, and focus on the implications of very general (and seemingly innocuous) leakage functions. We will see that the problem of reconstructing the contents of the database from leakage information is closely related to statistical learning theory. Using this new viewpoint, I will present attacks that approximately reconstruct the contents of an entire database using only the access pattern leakage of range queries, a minimal type of leakage present in all practical constructions today.

Joint work with Paul Grubbs, Marie-Sarah Lacharité, and Kenny Paterson, to appear at S&P 2019.

La prochaine édition du séminaire C2 se tiendra le vendredi 25 janvier  2019 dans la salle 105 couloir 25-26 du LIP6 de Sorbonne Université, métro Jussieu.

• 10h00 – Virginie Lallemand, LORIA : Multiplication Operated Encryption with Trojan Resilience

Résumé : In order to lower costs, the fabrication of Integrated Circuits is increasingly delegated to offshore contract foundries, making themexposed to malicious modifications, known as hardware Trojans. Recent works have demonstrated that a strong form of Trojan-resilience can be obtained from untrusted chips by exploiting secret sharing and Multi-Party Computation (MPC), yet with significant cost overheads. In this talk, we examine the possibility of building a symmetric cipher enabling similar guarantees in a more efficient manner. The solution proposed exploits a simple round structure mixing a modular multiplication and a multiplication with a binary matrix. Besides being motivated as a new block cipher design for Trojan resilience, our research also exposes the cryptographic properties of the modular multiplication, which is of independent interest.

Based on joint work with Olivier Bronchain, Sebastian Faust, Gregor Leander, Léo Perrin and François-Xavier Standaert

• 11h15 : Antoine Grospellier, INRIA : Constant overhead quantum fault-tolerance with quantum expander codes

Résumé :We prove that quantum expander codes can be combined with quantum fault-tolerance techniques to achieve constant overhead: the ratio between the total number of physical qubits required for a quantum computation with faulty hardware and the number of logical qubits involved in the ideal computation is asymptotically constant, and can even be taken arbitrarily close to 1 in the limit of small physical error rate. This improves on the polylogarithmic overhead promised by the standard threshold theorem. To achieve this, we exploit a framework introduced by Gottesman together with a family of constant rate quantum codes, quantum expander codes. Our main technical contribution is to analyze an efficient decoding algorithm for these codes and prove that it remains robust in the presence of noisy syndrome measurements, a property which is crucial for fault-tolerant circuits. We also establish two additional features of the decoding algorithm that make it attractive for quantum computation: it can be parallelized to run in logarithmic depth, and is single-shot, meaning that it only requires a single round of noisy syndrome measurement.

• 13h45 : Elise Barelli, Université de Versailles – Saint-Quentin, Équipe CRYPTO, Laboratoire LMV : Étude de clés compactes pour le schéma de McEliece utilisant des codes géométriques avec des automorphismes non triviaux.

Résumé : En 1978, McEliece introduit un système de chiffrement basé sur l’utilisation des codes linéaires et propose d’utiliser les codes de Goppa classiques, ie: des sous-codes sur un sous-corps de codes algébriques (AG codes) construit sur une courbe de genre 0. Cette proposition reste sécurisé et dans le but d’introduire une généralisation de ces codes, en 1996, H. Janwa et O. Moreno proposent d’utiliser des sous-codes sur un sous corps de codes construits à partir de courbes de genre > 0 , on les appelle les SSAG codes (Subfield Subcode of AG codes). Cette proposition donne un plus grand choix de code puisqu’on peut faire varier la courbe, le genre, et les points rationnels du diviseur qui génère le code. Le principal obstacle à l’utilisation de ces codes en cryptographie reste le taille de la clé publique comparé aux autres systèmes à clé publique. Pour contourner cette limitation, on réduit la taille des clés en utilisant des codes qui admettent une matrice génératrice compacte. Un moyen d’obtenir des matrices compactes est de choisir des codes avec un groupe d’automorphismes non-trivial, par exemple on utilise des SSAG codes quasi-cycliques.

• 15h00 : Julien Lavauzelle, IRMAR, Université de Rennes 1 : Constructions de protocoles de PIR

Résumé : Un protocole de récupération confidentielle d’information (private information retrieval, PIR) permet d’extraire l’entrée D_i d’une base de données D, sans révéler d’information sur i à l’entité qui détient D.

Dans cet exposé, nous donnerons un aperçu de techniques existantes pour la construction de tels protocoles. Nous préciserons notamment des paramètres qui quantifient leur efficacité, tels que la complexité algorithmique des serveurs, la complexité de communication ou la redondance de stockage.

Nous présenterons enfin deux constructions de protocoles de PIR. La première, fondée sur des objets combinatoires appelés designs transversaux, atteint une complexité calculatoire optimale pour les serveurs qui détiennent la base de données. La seconde se concentre sur la complexité de communication, et se place dans le contexte de fichiers encodés à l’aide de codes régénérants optimaux.

La prochaine édition du séminaire C2 se tiendra le vendredi 16 novembre 2018 dans la salle 105 couloir 25-26 du LIP6 de Sorbonne Université

• 10h00 : Alice Pellet-Mary, LIP ENS-Lyon : Quantum attack against some candidate obfuscators based on GGH13

Résumé : Since the first candidate indistinguishability obfuscator (iO) has been proposed in 2013 by Garg, Gentry, Halevi, Raykova, Sahai and Waters, a lot of other candidates have been proposed. All these constructions are only candidate constructions, in the sense that they come with no security proof. Alongside with all these constructions, some attacks have also been proposed, breaking many of the candidates.
In this talk, I will present a quantum attack against some iO that were not broken yet. This attack relies on recovering a short generator of a principal ideal in a cyclotomic field, which can be done in quantum polynomial time thanks to the works of Biasse and Song (SODA 2016) and Cramer, Ducas, Peikert and Regev (Eurocrypt 2016). Once this short generator is recovered, the rest of the attack is a mixed-input attack, which does not require any quantum computer.

• 11h15 : Baptiste Lambin, IRISA : On Recovering Affine Encodings in White-Box Implementations

• 13h45 : Jean-Marc Robert, Université de Toulon : Enhanced Digital Signature using Splitted Digit Exponent Representation

Résumé : Digital Signature Algorithm (DSA) involves modular exponentiation, of a public and known base by a random one-time exponent. In order to speed-up this operation, well-known methods take advantage of the memorization of base powers. However, due to the cost of the memory, to its small size and to the latency of access, previous research sought for minimization of the storage. In this paper, taking into account the modern processor features and the growing size of the cache memory, we improve the storage/efficiency trade-off, by using a RNS Digit exponent representation. We then propose algorithms for modular exponentiation. The storage is lower for equivalent complexities for modular exponentiation computation. The implementation performances show significant memory saving, up to 3 times for the largest NIST standardized key sizes compared to state of the art approaches. This work has been presented at WAIFI 2016 conference. We extend this approach to the Elliptic Curve Scalar Multiplication with another multiplicative digit approach we call R-splitting, providing side-channel resistance.

• 15h00: Anand Kumar Narayanan, LIP6 , Sorbonne université : Nearly linear time encodable codes beating the Gilbert-Varshamov bound.

Résumé : Error-correcting codes enable reliable transmission of information over an erroneous channel. One typically desires codes to transmit information at a high rate while still being able to correct a large fraction of errors. However, rate and relative distance (which quantifies the fraction of errors corrected) are competing quantities with a trade off. The Gilbert-Varshamov bound assures for every rate R, relative distance D and alphabet size Q, there exists an infinite family of codes with R + H_Q(D) > = 1-\epsilon.  Constructing codes meeting or beating theGilbert-Varshamov bound remained a long-standing open problem, until the advent of algebraic geometry codes by Goppa. In a seminal paper, for prime power squares Q ≥ 7^2, Tsfasman-Vladut-Zink constructed algebraic geometry codes beating the Gilbert-Varshamov bound. A rare occasion where an explicit construction yields better parameters than guaranteed by randomized arguments! For codes to find use in practice, one often requires fast encoding and decoding algorithms in addition to satisfying a good trade off between rate and minimum distance. A natural question, which remains unresolved, is if there exist linear time encodable and decodable codes meeting or beating the Gilbert-Varshamov bound. In this talk, I shall present the first nearly linear time encodable codes beating the Gilbert-Varshamov bound, along with a nearly quadratic decoding algorithm. Time permitting, applications to secret sharing, explicit construction of pseudorandom objects, Probabilistically Checkable Interactive Proofs and the like will also be discussed.

The talk will be based on joint work with Matthew Weidner
(Caltech/Cambridge). A preprint is available here
https://arxiv.org/abs/1712.10052

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

• 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
  

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

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.

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.

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

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 d≤4 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.

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.