-
Jeudi 17 novembre 2016 11:00–12:00 – Ilaria Chilotti – UVSQ
Faster Fully Homomorphic Encryption : Bootstrapping in less than 0.1 Seconds
Résumé : In this paper, we revisit fully homomorphic encryption (FHE) based on GSW and its ring variants. We notice that the internal product of GSW can be replaced by a simpler external product between a GSW and an LWE ciphertext. We show that the bootstrapping scheme FHEW of Ducas and Micciancio (Eurocrypt 2015) can be expressed only in terms of this external product. As a result, we obtain a speed up from less than 1 second to less than 0.1 seconds. We also reduce the 1GB bootstrapping key size to 24MB, preserving the same security levels, and we improve the noise propagation overhead by replacing exact decomposition algorithms with approximate ones. Moreover, our external product allows to explain the unique asymmetry in the noise propagation of GSW samples and makes it possible to evaluate deterministic automata homomorphically as in (ePrint 2014/283) in an efficient way with a noise overhead only linear in the length of the tested word. Finally, we provide an alternative practical analysis of LWE based scheme, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key. (Full paper : http://eprint.iacr.org/2016/870.pdf)
Lieu : Bât. Descartes, Salle 301
-
Jeudi 1er décembre 2016 11:00–12:00 – Valentin Suder – UVSQ
Orthomorphismes réguliers sur GF(2^n)
Résumé : Dans ce travail, nous nous intéressons à l’étude des orthomorphismes —aussi appelés permutations complètes— du corps fini GF(2^n). Un orthomorphisme est une fonction bijective x ↦ f(x) de GF(2^n) telle que la fonction x ↦ f(x)+x est aussi bijective. Depuis que le concept d’orthomorphisme a été introduit par Mann dans les années 40, pour aider la construction de carrés latins orthogonaux, d’autres applications de ces objets combinatoires ont été trouvées. Malgré la multitude d’articles se concentrant sur l’étude des orthomorphismes, il apparait que peu de propriétés ou de classes sont connues. Parmi ces classes, la plupart sont des fonctions monômiales, binômiales voire trinômiales.
Dans cet exposé, nous commencerons par introduire la notion d’orthomorphisme, les propriétés de bases, et montrerons les applications les plus courantes. Nous parlerons notamment de deux attentes pour utiliser les orthomorphismes en cryptographie. Il sera ensuite présenté quelques classes classiques et connues d’orthomorphismes. Dans une seconde partie, nous démontrerons quelques nouvelles propriétés des orthomorphismes. Nous introduirons aussi une nouvelle idée qui permet de construire un très grand nombre de permutations complètes sur GF(2^n) lorsqu’il existe un entier d divisant 2^n-1. Plus spécifiquement, nous nous intéressons aux partitions d-régulières de GF(2^n), c’est-à-dire aux partitions des éléments non-nuls en ensembles de d éléments qui se somment à zéro. Nous regarderons tout d’abord le cas où les partitions sont les cosets d’un sous-groupe de GF(2^n)*.
Nous conclurons en proposant un certains nombre de conjectures et d’observations sur ces nouvelles classes d’orthomorphismes.Lieu : Bât. Descartes, Salle 301
-
Jeudi 9 février 2017 11:00–12:00 – Francisco Vial Prado – UVSQ
The Betrayal Problem (Excalibur Blending of FHE-NTRU keys)
Résumé : In this talk we examine hierarchic structures equipped with a public-key encryption scheme, with decryption rights inherited according to the hierarchic tree. We deal with authorities wanting to sell secrets of their children to third parties. We propose the first construction that avoids such betrayals, relying on secure two-party computations in cyclotomic polynomial rings (called Excalibur protocols), and we base the security of our protocols on standard assumptions, in addition to two new polynomial factorization problems in cyclotomic rings. This talk will be given in french.
Keywords : secure multi-party computation, cyclotomic rings, fully homomorphic encryption.Lieu : Bât. Descartes, Salle Archimède
-
Jeudi 23 février 2017 11:00–12:00 – Colin Chagneau – UVSQ
Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks ?
Résumé : AEZ is a authentication encryption oriented block cipher submitted to the CAESAR competition and well suited for software implementation. It was selected for the second round when we analyse the resilience of the last version, namely AEZ v4.1, against key-recovery. We showed that, while it was partly updated in order to thwart key-recovery attack based on birthday paradox published at Asiacrypt 2015 by Fuhr, Leurent and Suder, such attacks remain and lead to a full recovery of the secret. Basically our attack proceeds in two steps, the first one leverages the use of a tweakable block cipher to prompt a collision and retrieve one of the three sub-keys ; the second attack a 4-round AES weakened by the knowledge of this sub-key and retrieve the full secret materials. Despite our attack does not violate the security claims of AEZ since no one was made for beyond-birthday security, it emphasizes an unwanted property of AEZ and its weakness against key-recovery attack.
Lieu : Bât. Descartes, Salle 301
-
Jeudi 20 avril 2017 11:00–12:00 – Gaëtan Leurent (Inria Paris)
Breaking Symmetric Cryptosystems Using Quantum Algorithms
Résumé : Due to Shor’s algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. The main known applicable result is Grover’s algorithm that gives a quadratic speed-up for exhaustive search. In this talk, we examine more closely the security of symmetric ciphers against quantum attacks, both against primitives, and against modes of operation.
First we show that a quantum procedure called Simon’s algorithm can dramatically speed up several attacks. We consider a model where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it. We show that the most widely used modes of operation for authentication and authenticated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model.
Next, we investigate quantum cryptanalysis techniques, because our trust in symmetric ciphers relies mostly on their ability to resist cryptanalysis techniques. More specifically, we consider quantum versions of differential and linear cryptanalysis. We show that it is usually possible to use quantum computations to obtain a quadratic speed-up for these attack techniques, but the situation must be nuanced : we don’t get a quadratic speed-up for all variants of the attacks.Lieu : Bât. Descartes, Salle Ératosthène