La prochaine édition du séminaire C2 se tiendra le vendredi 15 novembre  2019 en salle Jaques-Louis Lions 2 de l’INRIA Paris, 2 ,rue Simone Iff,  Métro Ligne 6, arrêt Dugommier.

Exceptionnellement, le séminaire ne se déroulera que le matin, la thèse de Xavier Bonnetain se déroulant l’après-midi également à 14h00 :  Xavier Bonnetain, Inria Paris, Soutenance de thèse : Hidden Structures and Quantum Cryptanalysis

• 10h00 -Geoffroy Couteau, IRIF, Université Paris-Diderot : Efficient Pseudorandom Correlation Generators: Silent OT Extension and More

Abstract : I will present recent developments in secure computation in the preprocessing model. In this model, a protocol is divided in two phases: a preprocessing phase, independent of the inputs, during which long correlated strings are generated and distributed among the parties; and a lightweight online phase, were the actual computation takes place. The generation of the preprocessing material forms the main efficiency bottleneck of all modern secure computation protocols, due to the very large communication, computation, and storage involved.

In this talk, I will discuss how a new cryptographic primitive, a pseudorandom correlation generator (PCG), can be used to considerably improve this state of affair. Informally, a PCG allows to stretch short, correlated keys into long correlated pseudorandom string of near-arbitrary length. This allows the preprocessing phase of all secure computation protocols to be executed with a tiny amound of communication (to generate the short correlated keys) followed only by local operations (to stretch correlated strings from these keys). I will discuss how to formalize this primitive, and describe a way to construct PCGs for an important class of correlations from the hardness of syndrome decoding. In turns, this results in considerable improvements for state-of-the-art secure computation, both from an asymptotic point of view and in practice.

• 11h15 – Pierre Karpman, Université Grenoble Alpes : High-order private multiplication in characteristic two revisited

Abstract : We revisit the high-order masking schemes for private multiplication introduced by Belaïd et al. at EUROCRYPT 2016, and the matrix model for non-interference (NI) security that they develop in their follow-up work of CRYPTO 2017. This leads to two main results.
1) We generalise the theorems of CRYPTO 2017 so as to be able to apply them to masking schemes over any finite field — in particular GF(2) — and to be able to analyse the strong non-interference (SNI) security notion. This leads to an efficient algorithm that allows us to computationally check the (S)NI security of concrete multiplication gadgets over GF(2) up to order 11.
2) We propose new SNI and NI multiplication gadgets over GF(2) (and any extension thereof) up to order 9 and 11 that moderately improve the randomness complexity of the schemes of Barthe et al. (EUROCRYPT 2017).

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

• 10h00 – Thomas Debris, INRIA Paris : Wave: a New Family of Trapdoor One-Way PSF Based on Codes.

(joint work with Nicolas Sendrier and Jean-Pierre Tillich)

We present here a new family of trapdoor one-way Preimage Sampleable Functions (PSF) based on codes, the Wave-PSF family. The trapdoor function is one-way under two computational assumptions: the hardness of generic decoding for high weights and the indistinguishability of generalized $\UV$-codes.

Our proof follows the GPV strategy \cite{GPV08}.  By including rejection sampling, we ensure the proper distribution for the trapdoor inverse output. The domain sampling property of our family is ensured by using and proving a variant of the left-over hash  lemma.  We instantiate the new Wave-PSF family with ternary generalized $\UV$-codes to design a « hash-and-sign » signature scheme which achieves {\em existential unforgeability under adaptive chosen message attacks} (EUF-CMA) in the random oracle model. For 128 bits of classical security, signature sizes are in the order of 13 thousand bits, the public key size in the order of 3 megabytes, and the rejection rate is limited to one rejection every 10 to 12 signatures.

• 11h15 – Adrien Hauteville, INRIA Saclay : Durandal: a rank metric based signature scheme.

Joint work with Nicolas Aragon, Olivier Blazy, Philippe Gaborit and Gilles Zémor

Abstract : These last years, the interest for post-quantum cryptography has strongly increased, especially since the NIST call for post-quantum cryptosystems standardization. Code-based cryptography is a good candidate in this domain.

The Hamming metric is well-known for several years, however rank metric is a newer topic but possesses many advantages in term of keysize or security hypothesis.

This presentation introduces the Rank-based cryptography and the new signature scheme Durandal, which is a variation of the Lyubashevsky approach in Euclidean lattices.

• 13h45 – Aurore Guillevic, LORIA :  A first step toward an implementation of the Tower Number Field Sieve: selecting polynomials

Joint work with Shashank Singh, IISER Bhopal, India

Abstract : In this work, we provide a first step toward a practical implementation of the Tower Number Field Sieve. This algorithm is expected to compute more efficiently discrete logarithms in finite fields GF(p^n), where p is large prime number (hundreds of bits) and n is a small composite integer (n=6,8,12 for example).

The NFS-like algorithms for discrete logarithm computation are made of four main steps: polynomial selection (two polynomials define two number fields), relation collection (collecting a large set of multiplicative relations of elements from these two number fields), linear algebra (computing the right kernel of a large sparse matrix) and finally, computing the discrete logarithm of a given target in GF(p^n) w.r.t. a generator.

We generalize to the new Tower setting the ranking formula used in the first step of NFS that selects the best parameters (polynomials) among a large set. For this we re-define the $\alpha$ function and write an exact implementation (Magma and SageMath). This function measures the bias in the smoothness probability of norms in number fields compared to random integers of the same size.

We use it to estimate the yield of polynomials, that is the expected number of relations, as a generalization of Murphy’s $E$ function, and finally the total amount of operations needed to compute a discrete logarithm with the Tower-NFS in the targeted fields.

As another application, this can be used to refine the earlier work of Barbulescu and Duquesne on estimating the running-time of the algorithm. We apply our estimates to some pairing-friendly curves, whose related pairing target field is GF(p^n), for some small composite n. For each curve, we generate curve parameters for p of increasing size every 32 bits, and p^n from 3000 bits to 12000 bits, in order to have more intuition on how does the Tower-NFS algorithm scale for increasing size of p.

• 15h00 : Leonardo Colo, Université d’Aix-Marseille : Orienting supersingular isogeny graphs

Abstract : Supersingular isogeny graphs have been used in the Charles–Goren–Lauter cryptographic hash function~\cite{CGL2006} and the supersingular isogeny Diffie–Hellman (SIDH) protocole of De\,Feo and Jao~\cite{JDF2011}. A recently proposed alternative to SIDH is the commutative supersingular isogeny Diffie–Hellman (CSIDH) protocole, in which the isogeny graph is first restricted to $\FF_p$-rational curves $E$ and $\FF_p$-rational isogenies then oriented by the quadratic subring $\ZZ[\pi] \subset \End(E)$ generated by the Frobenius endomorphism $\pi: E \rightarrow E$.

We introduce a general notion of orienting supersingular elliptic curves and their isogenies, and use this as the basis to construct a general oriented supersingular isogeny Diffie-Hellman (OSIDH) protocole.

By imposing the data of an orientation by an imaginary quadratic ring $\OO$, we obtain an augmented category of supersingular curves on which the class group $\Cl(\OO)$ acts faithfully and transitively. This idea is already implicit in the CSIDH protocol, in which supersingular curves over $\FF_p$ are oriented by the Frobenius subring $\ZZ[\pi] \simeq \ZZ[\sqrt{-p}]$. In contrast we consider an elliptic curve $E_0$ oriented by a CM order $\OO_K$ of class number one. To obtain a nontrivial group action, we consider $\ell$-isogeny chains, on which the class group of an order $\OO$ of large index $\ell^n$ in $\OO_K$ acts, a structure we call a whirlpool. The map from $\ell$-isogeny chains to its terminus forgets the structure of the orientation, and the original base curve $E_0$, giving rise to a generic supersingular elliptic curve. Within this general framework we define a new oriented supersingular isogeny Diffie-Hellman (OSIDH) protocol, which has fewer restrictions on the proportion of supersingular curves covered and on the torsion group structure of the underlying curves. Moreover, the group action can be carried out effectively solely on the sequences of moduli points (such as $j$-invariants) on a modular curve, thereby avoiding expensive isogeny computations, and is further amenable to speedup by precomputations of endomorphisms on the base curve $E_0$.

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