On the Complexity of the BKW Algorithm on LWE

Martin R. Albrecht · Carlos Cid · Jean-Charles Faugère · Robert Fitzpatrick · Ludovic Perret

Designs, Codes and Cryptography 2015

Time bound

2^n+o(n)

Space bound

2^n+o(n)

Source / version date

11 Nov 2012

Comparison variant

BKW · Regev · unlimited samples

Cost scale

2^{c n + o(n)}

Input samples

2^{n+o(n)} fresh samples

Distribution model

Original Decision-LWE corollary; expectation and distribution assumptions as in the source

Reduction schedule

Exact block cancellation

Memory access

Classical tables

variant

Decision-LWE

formula

a≈2 log₂n, b=n/a; q^b=2^{n+o(n)}

success

Constant target distinguishing advantage; polynomial amplification permitted

Assumptions and source notes

Decision-LWE specialization of the original free-depth corollary: choose a≈2 log₂n and b=n/a. Then q^b=2^{n+o(n)} and m=exp(O(n/log₂⁴n))=2^{o(n)}. The simplified Search-LWE Theorem 1 fixes a≈log₂n and instead gives coefficient 2; do not conflate the two statements.

Source location

Corollary 1, pp. 2–3; Corollary 3, Equations (15)–(18); distinguish simplified Search-LWE Theorem 1
Version: ePrint 2012/636 PDF checked 2026-11-08; original version not separately diffed

Primary source ↗

@article{paper-87fab2296b57,
  author = {Martin R. Albrecht and Carlos Cid and Jean-Charles Faugère and Robert Fitzpatrick and Ludovic Perret},
  title = {{On the Complexity of the BKW Algorithm on LWE}},
  journal = {Designs, Codes and Cryptography},
  year = {2015},
  volume = {74},
  number = {2},
  pages = {325--354},
  url = {https://eprint.iacr.org/2012/636},
  cr_date = {2012-11-11},
  cr_status = {published},
  cr_venue = {Designs, Codes and Cryptography},
  cr_author_ids = {martin-r-albrecht; carlos-cid; jean-charles-faugere; robert-fitzpatrick; ludovic-perret}
}