Centered Binomial Distribution (CBD) – Why Kyber does not use Gaussian

Every code listing from this chapter of Applied Post-Quantum Cryptography — 5 in total, 5 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 — A simple Sage implementation

Here is a very small version in Python.

Listing 2 — A simple Sage implementation

A quick test is:

Listing 3 — Histogram view

To understand CBD properly, one should look at the histogram.

Listing 4 — Histogram view

The distribution tends to concentrate around zero and becomes increasingly bell-shaped. This is exactly why the distribution is often described as a discrete approximation to a Gaussian.

A very simple visualization can be done with matplotlib:

Listing 5 — A small upgrade to the toy Kyber code

If we had earlier written a toy sampler that generated small values from a simple routine, then we can now replace it with CBD-style sampling.

For example, we might write something like: