On the complexity of the BKW algorithm on LWE

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

zbMATH Keywords

learning with errors (LWE); Blum-Kalai-Wasserman (BKW) algorithm; fully homomorphic encryption scheme (FHE); learning parity with noise (LPN)

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

94A60: Cryptography

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Uses Software

• SageMath
• mpmath
• BKZ
• SWIFFT