Séminaire CCA du vendredi 9 juin

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

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

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

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

Slides de l’exposé

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

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

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

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