后量子 KEM 方案：Kyber

参考文献：

1. Bos J, Ducas L, Kiltz E, et al. CRYSTALS-Kyber: a CCA-secure module-lattice-based KEM[C]//2018 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE, 2018: 353-367.
2. Avanzi R, Bos J, Ducas L, et al. Crystals-kyber[J]. NIST, Tech. Rep, 2017.
3. Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory (TOCT), 2014, 6(3): 1-36.
4. NIST PQC 标准化的第三轮结果

Kyber

Module-LWE

Kyber 基于 MLWE 问题，成为了唯一进入 NIST PQC 第 3 轮的 KEM 方案（一共 4 个方案，另外 3 个都是签名，其中 2 个也基于 MLWE，另外 1 个基于 Hash）。

MLWE 最早作为标准 LWE 与 Ring-LWE 的扩展 General LWE 出现在 BGV 方案中：分圆多项式环记做 $R_q=Z_q[X]/(X^n+1)$，随机采样秘密向量 $s\in R_q^k$，均匀随机采样 $a_i\in U(R_q^k)$，计算 $b_i=a_i^{T}s+e_i\in R_q$，输出 $m$ 对样本 $(a_i,b_i)\in R_q^k\times R_q$

基于 MLWE 问题的密码方案，需要使得 $m=k$ 以保证私钥的安全性。因此，按行排列，$m$ 个 MLWE 样本可以写作 $(A,b)\in R_q^{k\times k}\times R_q^k$，其中 $b=As+e$

使用 MLWE 的一个优势是：改变安全级别时，只需调整矩阵规模 $k$ 以及噪声规模 $\eta$，而环 $R_q$ 不需要改变，因此可以代码复用，有利于软硬件优化。

IND-CPA PKE

Kyber 使用 Newhope-Simple 的思路，通过压缩密钥和密文来减小规模。对于 $x\in {\mathbb{Z}}_q$，进行 $d$ 比特离散化：
$$\begin{array}{rl}\text{Compress}(x,d)& :=\lfloor \frac{2^d}{q}\cdot x\rceil (\mathrm{mod}{2}^d)\\ \text{Decompress}(x,d)& :=\lfloor \frac{q}{2^d}\cdot x\rceil (\mathrm{mod}q)\end{array}$$

这可以被视为FHE中的“模切换”技术，引入了少量的（均匀）舍入噪声。

Kyber 的 PKE 方案与 Newhope 和 LAC 的几乎完全一样：

IND-CCA KEM

同样的，Kyber 也是用 Fujisaki–Okamoto transform 得到 CCA 安全的 KEM：

当解密错误时，并不输出 ⊥ ∉ { 0 , 1 } 256 \perp \not \in \{0,1\}^{256} ⊥∈{0,1}256，而是输出伪随机的 $H(z,c)$，“隐式拒绝”。

KEY EXCHANGE

无身份认证的 KE 协议：

单方面身份认证的 KE 协议：

双向身份认证的 KE 协议：

正确性分析

在 CPA PKE 中，公钥的第二分量包含中心二项分布噪声和舍入噪声，
$$\begin{array}{rl}b& =\text{Decompress}(\text{Compress}(A\cdot s+e,d_0),d_0)\\ & =As+e+r_0\end{array}$$

其中 $s{\leftarrow }_R{\Psi }_{{\eta }_1}^{kn}$，$e{\leftarrow }_R{\Psi }_{{\eta }_2}^{kn}$。在压缩时简单丢弃了低位比特，因此可以近似地认为舍入噪声是均匀的。令 $l=\lceil \log q\rceil$，那么 $r_0{\leftarrow }_{R}U(R_{2^{l-d_0}}^k)$

类似地，密文的第一分量中的噪声为：
$$\begin{array}{rl}{c}_1& =\text{Decompress}(\text{Compress}(A^T\cdot s^{\prime }+e^{\prime },d_1),d_1)\\ & =A^T\cdot s^{\prime }+e^{\prime }+r_1\end{array}$$

其中 $s^{\prime }{\leftarrow }_R{\Psi }_{{\eta }_1}^{kn}$，$e^{\prime }{\leftarrow }_R{\Psi }_{{\eta }_2}^{kn}$，$r_1{\leftarrow }_{R}U(R_{2^{l-d_1}}^k)$

对于密文的第二分量，可以计算出它携带的噪声项：
$$\begin{array}{rl}{c}_2& =\text{Decompress}(\text{Compress}(b^T\cdot s^{\prime }+e^{\prime \prime }+\text{Encode}(m),d_2),d_2)\\ & =b^T\cdot s^{\prime }+e^{\prime \prime }+\text{Encode}(m)+r_2\\ & =(As{)}^T{s}^{\prime }+e^T{s}^{\prime }+r_0^T{s}^{\prime }+e^{\prime \prime }+r_2+\text{Encode}(m)\end{array}$$

其中 $e^{\prime \prime }{\leftarrow }_R{\Psi }_{{\eta }_2}^{kn}$，$r_2{\leftarrow }_{R}U(R_{2^{l-d_2}}^k)$。

解密步骤是 $m\leftarrow \text{Decode}(c_2-c_1^T\cdot s)$，我们可以计算出
$$\begin{array}{rl}{c}_2-c_1^T\cdot s=& \text{Encode}(m)+(As{)}^T{s}^{\prime }+e^T{s}^{\prime }+r_0^T{s}^{\prime }\\ & +e^{\prime \prime }+r_2-s^T{A}^T{s}^{\prime }-s^T{e}^{\prime }-s^T{r}_1\\ =& \text{Encode}(m)+(e+r_0{)}^T{s}^{\prime }-s^T(e^{\prime }+r_1)+(e^{\prime \prime }+r_2)\end{array}$$

简记 $E=\Vert (e+r_0{)}^T{s}^{\prime }-s^T(e^{\prime }+r_1)+(e^{\prime \prime }+r_2){\Vert }_{\infty }$ 为解密时的累积噪声规模。由于对消息采用了MSB编码方式，所以等式 $m=\text{Decode}(\text{Encode}(m)+e)$ 成立的充要条件是 $\Vert e{\Vert }_{\infty }<\lfloor q/4\rceil$。

因此，我们需要选取合适的参数集，使得解密错误率足够小：
$$\Delta :=\mathrm{Pr}\left[E\ge \lfloor \frac{q}{4}\rceil :(n,k,{\eta }_1,{\eta }_2,d_0,d_1,d_2)\right]$$

实例化

在第三轮 NIST PQC 文档中，Kyber 的参数选取如下：

由于 $q=3329=13\times 256+1$，因此在 $GF(q)$ 中存在 $256$ 次本原单位根，从而可以支持 $\log 128=7$ 轮的“不完全的反循环NTT变换”，将环元素 $f\in R_q$ 同构于 $128$ 个长度为 $2$ 的小多项式。注意 NTT 实现时采用 Montgomery 算法、 Barrett 算法，进行加速。

用到的对称原语（PRF, XOF, KDF, Hash）采用 FIPS-202 标准（SHA3）：