Lower Bounds on Lattice Enumeration with Extreme Pruning
| Autor: | Yoshinori Aono, Junji Shikata, Phong Q. Nguyen, Takenobu Seito |
|---|---|
| Přispěvatelé: | National Institute of Information and Communications Technology [Tokyo, Japan] (NICT), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Japanese French Laboratory for Informatics (JFLI), National Institute of Informatics (NII)-Université Pierre et Marie Curie - Paris 6 (UPMC)-The University of Tokyo (UTokyo)-Centre National de la Recherche Scientifique (CNRS), Bank of Japan, Graduate School of Environment and Information Sciences [Yokohama], Yokohama National University, IACR, Hovav Shacham, Alexandra Boldyreva |
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
010102 general mathematics 0102 computer and information sciences 01 natural sciences Upper and lower bounds [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT] Exponential function Running time [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] 010201 computation theory & mathematics Bounded function Lattice (order) Enumeration Cryptosystem 0101 mathematics Lattice reduction Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783319968803 CRYPTO (2) Lecture Notes in Computer Science CRYPTO 2018, 38th Annual International Cryptology Conference CRYPTO 2018, 38th Annual International Cryptology Conference, IACR, Aug 2018, Santa-Barbara, United States. ⟨10.1007/978-3-319-96881-0_21⟩ |
| DOI: | 10.1007/978-3-319-96881-0_21 |
| Popis: | International audience; At Eurocrypt '10, Gama, Nguyen and Regev introduced lattice enumeration with extreme pruning: this algorithm is implemented in state-of-the-art lattice reduction software and used in challenge records. They showed that extreme pruning provided an exponential speed-up over full enumeration. However, no limit on its efficiency was known, which was problematic for long-term security estimates of lattice-based cryptosystems. We prove the first lower bounds on lattice enumeration with extreme pruning: if the success probability is lower bounded, we can lower bound the global running time taken by extreme pruning. Our results are based on geometric properties of cylinder intersections and some form of isoperimetry. We discuss their impact on lattice security estimates. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|