Description
Le problème (SVP) de trouver un vecteur non nul le plus court d'un réseau de $\R^n$ de dimension $d$ est un problème très classique ; au cours des dix dernières années, de nombreux travaux ont montré des bornes inférieures sur la complexité de ce problème. Ces résultats sont à la base des arguments de sécurité d'un certain nombre de cryptosystèmes (Ajtai-Dwork, NTRU). Le meilleur algorithme pratique pour ce problème, dû à Kannan, consiste à énumérer des points dans un ellipsoïde. Son analyse consiste classiquement à borner le nombre de points par le volume, qui est à son tour estimé par le volume du pavé circonscrit, donnant une complexité de $\tilde{O}(d^{d/2(1+o(1))})$. Nous montrons qu'une analyse plus fine conduit \`a une complexit\'e de $\tilde{O}(d^{d/(2e)(1+o(1))})$; ce résultat permet également d'améliorer la complexité des algorithmes de recherche du vecteur le plus proche (CVP), ou de calcul de bases "blocs-réduites" à la Schnorr.
Next sessions
-
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
-