## 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](https://github.com/RustCrypto/traits/tree/master/kem))
- [ ] 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](#CBD-Sampler))
- 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,\ldots,a_\eta, b_1,\ldots,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}\rightarrow \mathbb{Z}$
- Compress: $\mathsf{Compress}_q(x,d)= \lceil (2^d/q)\cdot x\rfloor\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})\rightarrow R_q$
- serde for message: $\mathsf{Decode}_{1}(msg\in \{0,1\}^{32})\rightarrow 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](https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf)
- "A Gentle Intro to Kyber" ([slide](https://drive.google.com/file/d/1FyX4kJ9WWuSOOmJDoApvwa87GO4wY0kA/view?usp=sharing))