On the complexity of the BKW algorithm on LWE
From MaRDI portal
Publication:2256097
DOI10.1007/s10623-013-9864-xzbMath1331.94051MaRDI QIDQ2256097
Carlos Cid, Jean-Charles Faugère, Ludovic Perret, Martin R. Albrecht, Robert Fitzpatrick
Publication date: 19 February 2015
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10623-013-9864-x
learning with errors (LWE); Blum-Kalai-Wasserman (BKW) algorithm; fully homomorphic encryption scheme (FHE); learning parity with noise (LPN)
68Q25: Analysis of algorithms and problem complexity
94A60: Cryptography
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Uses Software