Description
Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a _quantum_ algorithm for SVP and SIVP. A main open question is whether this reduction can be made classical. Using the main result, we obtain a public-key cryptosystem whose hardness is based on the worst-case quantum hardness of SVP and SIVP. Previous lattice-based public-key cryptosystems such as the one by Ajtai and Dwork were only based on unique-SVP, a special case of SVP. The new cryptosystem is much more efficient than previous cryptosystems: the public key is of size \tilde{O}(n) and encrypting a message increases its size by \tilde{O}(n) (in previous cryptosystems these values are \tilde{O}(n^4) and \tilde{O}(n^2), respectively).
Next sessions
-
Comprendre le générateur sac-à-dos (et améliorer les attaques contre lui) / Understanding the Knapsack generator (and improving the attacks against it)
Speaker : Florette Martinez - Université Picardie Jules Verne
Résumé : Le générateur sac-à-dos, présenté en 1985 est un générateur pseudo aléatoire annoncé sécurisé qui combine un générateur pseudo aléatoire non sécurisé et un problème dur. Une erreur de design repérée en 2011 permet à W. Meier et S. Knellwolf de retrouver une partie du secret mais les explications théoriques et heuristiques sont partielles. Dans cet exposé, je vais présenter une nouvelle[…] -
Soutenance de thèse : Cryptanalyse de schémas de cryptographie à clé publique (Cryptanalysis of public-key cryptosystems)
Speaker : Paul Kirchner - IRISA
Résumé : La cryptanalyse de schémas de cryptographie à clé publique repose sur un ensemble de techniques algorithmiques et algébriques en théorie des nombres. Dans une première partie de cette thèse, nous présentons des améliorations de l’algorithme LLL, dû à Lenstra, Lenstra et Lovasz pour réduire un réseau euclidien, c’est-à-dire réduire la norme et orthogonaliser le plus possible les vecteurs[…]-
Cryptography
-
-
Oblivious Transfer from Zero-Knowledge Proofs (or how to achieve round-optimal quantum Oblivious Transfer without structure)
Speaker : Léo Colisson - Université Grenoble Alpes
We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable oblivious transfer (OT) protocol (the protocol itself involving quantum interactions), mostly lifting the round-complexity properties and security guarantees (plain-model/statistical security/unstructured functions…) of the ZK protocol to the resulting OT protocol. Such a construction is unlikely[…]-
Cryptography
-