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.
