Séminaire CCA du vendredi 16 mars 2018

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

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

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

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

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


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

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


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

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

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