Learning With Errors (LWE)

Every code listing from this chapter of Applied Post-Quantum Cryptography — 4 in total, 4 runnable here. Edit any cell and press Run.

The book's snippets build on each other down the chapter, but a Sage Cell kernel runs one cell and keeps no state afterwards, so each cell replays the earlier listings with apqc_book. That call is the only thing added to the book's own code.

← the playground

Listing 1 — Sage experiments

The quickest route to intuition is to build a small instance by hand and watch the error convert an easy system into a hard one. Fix a modulus and dimension.

Listing 2 — Sage experiments

Choose a secret vector and a batch of random rows.

Listing 3 — Sage experiments

Without noise, b=As is an exact system and s is recovered by solving it directly.

Listing 4 — Sage experiments

Now add a short error. In 𝔽₁₇ the value 16 represents -1, so this vector has entries in {-1,0,1}.