Ring-LWE (RLWE)

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 experiment

We can define a simple quotient ring in Sage.

Listing 2 — Sage experiment: polynomial multiplication

We can see the basic idea without writing a full NTT implementation.

Listing 3 — Sage experiment: a toy RLWE-style setup

We can create a small ring and form the analog of an LWE sample.

Listing 4 — A sibling assumption: NTRU

RLWE is not the only way to build a hard problem inside the ring R_q. An older construction, NTRU (from 1996, predating LWE), lives in the same ring but hides its secret differently. Instead of the additive-noise equation b = a s + e, NTRU picks two short secret polynomials f, g ∈ R_q (with f invertible) and publishes a single quotient:

The NTRU assumption is that h looks like a uniformly random ring element, and that recovering the short pair (f,g) from h is hard.