TODOs

• trait for Ring, PolynomialRing, Module
• implement cyclotomic polynomial and rings, and arithemetics
• trait for Sampler
• implement uniform sampler
• implement CBD Sampler
• (De)compression
• (De)serialization
• implement NTT
• CPA-PKE.KeyGen, Enc, Dec
• CCA-KEM.KeyGen, Encapsulate, Decapsulate (use RustCrypto's trait)
• End-to-end Testvectors
• Benchmarks & Profiling

System parameters

• Degree of ring (over
  $\mathbb{Z}$):
  $n=256$
• Rank of Mod-LWE:
  $k$
  • number of samples in RLWE
    $m=k$, thus ignored
• Modulus for quotient ring:
  $q=3329$
• Error distribution:
  ${\eta }_1,{\eta }_2$
  • central binomial distribution
    $B_{\eta }$ (see definition below)
  • only for Kyber512,
    ${\eta }_1>{\eta }_2$, for the rest,
    ${\eta }_1={\eta }_2$
  • secret
    $s$ also drawn from this distribution, see rationale in the slide
• Ciphertext round-off bits:
  $d_u,d_v$
  • $ct.u$ truncates to
    ${\mathbb{Z}}_{2^{d_u}}$,
    $ct.v$ truncates to
    ${\mathbb{Z}}_{2^{d_v}}$
  • "truncate" means dropping the LSB of each coeff (originally
    $\in {\mathbb{Z}}_q$)

Building blocks

Algebriac Objects

Ring

$R$, Quotient Ring

$R_q$, Module

$M=R_q^k$, Matrix (

$R_q^{k\times m}$) and matrix multiplication.
Polynomial ring with polynomial modulo operation.

NTT

See Kyber spec.

Uniform Sampler

Idea behind

$\mathsf{Parse}()$ is simple: since

$2^{11}<q<2^{12}$, let's use every 12 bits from a uniform random bytes string to generate a coeff in the NTT form of

$R_q$.
Furthermore, when the 12-bit value

$>q$, reject it.
Every 2 12-bit = 3 bytes, thus every 3 bytes can product at most 2

${\hat{R}}_q$ elements subject the sample rejection.

CBD Sampler

To sample a value from

$B_{\eta }$: Sample

$(a_1,\dots ,a_{\eta },b_1,\dots ,b_{\eta })\leftarrow \{0,1{\}}^{2\eta }$, outputs

$\sum _{i=[\eta ]}{a}_i-b_i$.
To sample a

$R_q$, just sample each coeff from

$B_{\eta }$.

(De)Compression

• Rounding/Discretization:
  $\lceil \cdot \rfloor :\mathbb{Q}\to \mathbb{Z}$
• Compress:
  ${\mathsf{Compress}}_q(x,d)=\lceil (2^d/q)\cdot x\rfloor \mathrm{mod}{2}^d$
  • for
    $x\in {\mathbb{Z}}_q$
  • for
    $x\in R_q$ (coeff-wise)
• Decompress:
  ${\mathsf{Decompress}}_q(x,d)=\lceil (q/2^d)\cdot x\rfloor$
  • for
    $x\in {\mathbb{Z}}_q$
  • for
    $x\in R_q$ (coeff-wise)

(De)Serialization

Namely Encoding/Decoding in Kyber Spec.

• serde for ring element:
  ${\mathsf{Decode}}_{12}(pk\in {\mathcal{B}}^{32\times 12})\to R_q$
• serde for message:
  ${\mathsf{Decode}}_1(msg\in \{0,1{\}}^{32})\to R_2\subseteq R_q$

Symmetric Primitives

All available in RustCryto

	FLPS-202	90s variant
PRF	SHAKE-256	AES-256-CTR
XOF	SHAKE-128	AES-256-CTR
KDF	SHAKE-256	SHA-256
Hash.H	SHA3-256	SHA-256
Hash.G	SHA3-512	SHA-512

CPA-PKE + FO-derived KEM

See Algorithm 4~9 in Kyber's spec.

References

• Kyber spec v3.02
• "A Gentle Intro to Kyber" (slide)