Kyber

As explained in Real-World Cryptography

Kyber is a lattice-based public-key cryptographic scheme based on the learning with errors problem that supports key encapsulation and key exchange.

Kyber is a lattice-based public-key cryptographic scheme designed for post-quantum encryption and key exchange. It belongs to the CRYSTALS family and is based on the learning with errors problem. section 14.3 section 14.3.2

The practical goal is to establish a shared secret without sending that secret directly, even when an attacker can observe the public exchange. section 14.3.3 section 14.5

Kyber builds the exchange from noisy modular linear algebra:

• Generate a private vector s with small coefficients and publish random vectors together with noisy products t = As + e, all computed modulo q. section 14.3.3
• Create an ephemeral private vector r and corresponding noisy public values using the other participant’s public matrix. section 14.3.3
• Encapsulate a symmetric key; the simplified explanation encrypts a single bit and uses small errors so both sides recover approximately the same value. section 14.3.3

The noisy equation

A public key can be represented as t = As + e: A is random, s is secret, and e is deliberately small noise. Recovering the secret from these noisy products is tied to LWE and lattice problems. section 14.3.2 section 14.3.3

Figure 14.9 The learning with errors problem (LWE) is said to be a lattice-based construction due to the existence of a reduction to a lattice problem: the CVP. In other words, if we can find a solution to the CVP, then we can find a solution to the LWE problem.

Use the LWE reduction diagram to connect Kyber’s noisy equations with the closest vector problem and lattice-based security. section 14.3.2

Figure 14.10 The Kyber public key encryption scheme. Note that the shared secret is approximately the same during encryption and decryption as re and e₁s are both small values because r, s, and the errors are much smaller than q/2). Thus, the last step of the decryption (dividing by q/2, which can be seen as a bitwise shift to the right) gets rid of any discrepancy between the two shared secrets. Note that all operations are done modulo q.

Use the scheme diagram to follow encapsulation, approximate shared-secret agreement, and modular decryption. section 14.3.3

How Real-World Cryptography covers it

How deep it goes

Explains LWE-based key generation and approximate decryption, while stopping short of a complete implementation or formal proof.

Examples

Uses noisy matrix equations, one-bit encapsulation, and modular shared-secret reconciliation as teaching examples.

What it assumes

Assumes basic public-key cryptography and introduces lattice and LWE intuition before describing Kyber’s mechanism.

What you can do after

Evaluate Kyber’s role in post-quantum key exchange and understand how LWE noise supports shared-secret recovery.

How it connects

Connects lattice-based cryptography, learning with errors, CRYSTALS-Dilithium, and hybrid key exchange.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Related concepts

• ciphertextproduces · Ciphertext is data produced by encryption whose original content is intended to be unreadable without the required decryption capability.
• cryptographic primitivekind of · A cryptographic primitive is a fundamental algorithmic building block that provides a basic security function such as encryption, hashing, or digital signing.
• key exchangeimplements · Key exchange is a cryptographic protocol by which communicating parties establish a shared secret over a communication channel without directly transmitting that secret.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.