On the complexity of the BKW algorithm on LWE
| Autor: | Ludovic Perret, Martin R. Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, Carlos Cid |
|---|---|
| Přispěvatelé: | Royal Holloway [University of London] (RHUL), Polynomial Systems (PolSys), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Danmarks Tekniske Universitet = Technical University of Denmark (DTU), European Project: 216676,EC:FP7:ICT,FP7-ICT-2007-1,ECRYPT II(2008), Technical University of Denmark [Lyngby] (DTU), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
BKW
business.industry Applied Mathematics Faculty of Science\Mathematics LPN Dimension (graph theory) Research Groups and Centres\Information Security\ Information Security Group Cryptography Approx Computer Science Applications [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Learning with errors Lattice reduction business Algorithm 94A60 FHE Mathematics |
| Zdroj: | Designs, Codes and Cryptography Designs, Codes and Cryptography, Springer Verlag, 2015, 74 (2), pp.26. ⟨10.1007/s10623-013-9864-x⟩ Designs, Codes and Cryptography, 2015, 74 (2), pp.26. ⟨10.1007/s10623-013-9864-x⟩ SCC 2012--Third international conference on Symbolic Computation and Cryptography SCC 2012--Third international conference on Symbolic Computation and Cryptography, Jul 2012, Castro Urdiales, Spain. pp.100-107 |
| ISSN: | 0925-1022 1573-7586 |
| Popis: | This work presents a study of the complexity of the Blum---Kalai---Wasserman (BKW) algorithm when applied to the Learning with Errors (LWE) problem, by providing refined estimates for the data and computational effort requirements for solving concrete instances of the LWE problem. We apply this refined analysis to suggested parameters for various LWE-based cryptographic schemes from the literature and compare with alternative approaches based on lattice reduction. As a result, we provide new upper bounds for the concrete hardness of these LWE-based schemes. Rather surprisingly, it appears that BKW algorithm outperforms known estimates for lattice reduction algorithms starting in dimension $$n \approx 250$$ n ? 250 when LWE is reduced to SIS. However, this assumes access to an unbounded number of LWE samples. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink