后量子 KEM 方案：Newhope

Peikert’ KEM

基于 RLWE 的公钥密码基本上都遵从 LPR10 的类 ElGamal 框架。不同之处在于参数的选取以及各种纠错算法、压缩算法等等。

Peikert 使用 reconciliation和解 来实现密钥封装key encapsulation mechanism, KEM。

• 和解机制两方对一个带噪环元素上达成近似的共识它可以降低载荷大小
• 密钥封装发送方直接把对称密钥加密后发送给接收方这与 Diffie-Hellman 密钥交换协议不同KEM 只用到了发送者的随机性

密文空间是 $C$密钥空间是 $K$ 的密钥封装方案是一组算法

• $Setup()$输出公开参数 $pp$
• $Gen(pp)$输出公钥 $pk$ 和私钥 $sk$
• $Encaps(pp,pk)$输出密文 $c\in C$ 和密钥 $k\in K$
• $Decaps(sk,c)$输出一个 k ∈ K ∪ { ⊥ } k \in K \cup \{\perp\} k∈K∪{⊥}

Reconciliation

最开始和解机制由 Ding 提出但是这个方案是有偏斜的。Peikert 通过 “随机加倍” 的方式解决了偏斜问题。

限制 $p|q$定义 $\lfloor \cdot {\rceil }_p:Z_q\to Z_p$ 为
$$\lfloor x{\rceil }_p=\lfloor p/q\cdot x\rceil (\mathrm{mod}p)$$
将 $Z_q$ 上的元素圆整到 $Z_p$ 上。每个 $Z_p$ 上的点对应以它为中心的 $q/p$ 长小区间的 $Z_q$ 上的点。

类似地定义 $\lfloor \cdot {\rfloor }_p:Z_q\to Z_p$ 为
$$\lfloor x{\rfloor }_p=\lfloor p/q\cdot x\rfloor (\mathrm{mod}p)$$
将 $Z_q$ 上的元素下取整整到 $Z_p$ 上。每个 $Z_p$ 上的点对应以它为左边界的 $q/p$ 长小区间的 $Z_q$ 上的点。

Even Modulus

设置 $p=2$并且 $q$ 是偶数。定义不交的区间
I 0 : = { 0 , 1 , ⋯   , ⌊ q / 4 ⌉ − 1 } I 1 : = { − ⌊ q / 4 ⌋ , ⋯   , − 2 , − 1 } \begin{aligned} I_0 &:= \{0,1,\cdots,\lfloor q/4 \rceil -1\}\\ I_1 &:= \{-\lfloor q/4 \rfloor,\cdots,-2,-1\}\\ \end{aligned} I0​I1​​:={0,1,⋯,⌊q/4⌉−1}:={−⌊q/4⌋,⋯,−2,−1}​
各自包含 $Z_q$ 上的 $\lfloor q/4\rceil$ 和 $\lfloor q/4\rfloor$ 个元素。

交叉圆整cross-rounding$⟨\cdot {⟩}_2:Z_q\to Z_2$
$$⟨v{⟩}_2:=\lfloor 4/q\cdot v\rfloor (\mathrm{mod}2)$$
可以看出 ⟨ v ⟩ 2 = b ∈ { 0 , 1 } \langle v \rangle_2 = b \in \{0,1\} ⟨v⟩2​=b∈{0,1}其中 $v\in I_b\cup (\frac{q}{2}+I_b)$

可以这么理解将 $Z_q$ 组织成一个一维环面最右端是 $0$最左端是 $q/2$那么 $I_0$ 就是右上弧$I_1$ 就是右下弧而 $\frac{q}{2}+I_0$ 是左下弧$\frac{q}{2}+I_1$ 是左上弧。于是有

• 对于 $\lfloor v{\rceil }_2$ 运算$I_0$ 与 $I_1$ 上的元素被映射到 $0$而 $\frac{q}{2}+I_0$ 与 $\frac{q}{2}+I_1$ 上的元素被映射到 $1$
• 对于 $⟨v{⟩}_2$ 运算$I_0$ 与 $\frac{q}{2}+I_0$ 上的元素被映射到 $0$而 $I_1$ 与 $\frac{q}{2}+I_1$ 上的元素被映射到 $1$
• 虽然由于圆整和下取整可能存在偏斜bias但是 $⟨v{⟩}_2$ 完美隐藏了 $\lfloor v{\rceil }_2$ 的信息

如果 $v,w\in Z_q$ 是足够接近的元素那么给定 $w=v+e$ 与reconciliation information $⟨v{⟩}_2$可以恢复出 $\lfloor v{\rceil }_2$

定义集合 $E:=\left[-\frac{q}{8},\frac{q}{8}\right)\cap \mathbb{Z}$定义 reconciliation function $rec:Z_q\times Z_2\to Z_2$
$$rec(w,b):=\{\begin{array}{rlr}0,& & w\in I_b+E(\mathrm{mod}q)\\ 1,& & otherwise\end{array}$$
那么 $rec(w,⟨v{⟩}_2)=\lfloor v{\rceil }_2$如图所示

一维环面 $Z_q$ 上$I_0+E$ 是右上的二分之一弧$I_1+E$ 是右下的二分之一弧。假设 $v$ 的交叉圆整是 $b$由于 $w=v+e$ 十分靠近 $v$如果 $w\in I_b+E$那么说明 $v$ 位于右边$b=0$在右上弧$b=1$在右下弧因此输出 $\lfloor v{\rceil }_2=0$否则 $v$ 位于环面的左边输出 $\lfloor v{\rceil }_2=1$。

Odd Modulus

设置 $p=2$并且 $q$ 是奇数。此时由于不能平分 $Z_q$因此 $\lfloor v{\rceil }_2=0/1$ 的比特将会出现偏斜。Peikert 使用随机加倍的方法消除了这个倾斜。

随机化函数 $dbl:Z_q\to Z_{2q}$ 定义为
$$\bar{v}:=2v-\bar{e}(\mathrm{mod}2q)$$

其中 e ˉ ∈ { − 1 , 0 , 1 } \bar e \in \{-1,0,1\} eˉ∈{−1,0,1} 是模二均匀取 $0$ 的概率为 $0.5$取 $\pm 1$ 的概率各为 $0.25$中心化的亚高斯分布的随机数。

由于解决了偏斜问题因此 $⟨\bar{v}{⟩}_2$ 完美隐藏了 $\lfloor \bar{v}{\rceil }_2$ 的信息。

如果 $w,v\in Z_q$ 十分接近那么 $2w,dbl(v)\in Z_{2q}$ 也十分接近从而使用 $Z_{2q}$偶数模上的 $rec(\cdot )$ 可以达成 $\lfloor \bar{v}{\rceil }_2=0/1$ 共识。注意 $I_0,I_1,E$ 的取值范围。

Peikert’s KEM

IND-CPA

在 LPR13 中将 LPR10二的幂次分圆多项式环上 的 RLWE 扩展到了任意的环并提出了一套快速计算的工具包括 powerful basis用于张量分解, CRT basis用于类 FFT 乘法, decoding basis用于 BDD 解码。看不懂分数理想、对偶空间。

给定环 $R_q:=Z_q[x]/(m(x))$ 的一组 decoding basis D = { d j } D = \{d_j\} D={dj​}那么环元素可以坐标表示为
$$v=\sum _j{v}_j\cdot d_j\in R_q$$

从整数环 $\mathbb{Z}$ 扩展到分圆环 $R:=\mathbb{Z}[{\zeta }_m]\subset K:=\mathbb{Q}[{\zeta }_m]$定义 $\lfloor v{\rceil }_2:R_q\to R_2$
$$\lfloor v{\rceil }_2:=\sum _j\lfloor v_j{\rceil }_2\cdot d_j$$

类似的定义 $⟨v{⟩}_2:R_q\to R_2$
$$⟨v{⟩}_2:=\sum _j⟨v_j{⟩}_2\cdot d_j$$

对于偶数模定义 $rec:R_q\times R_2\to R_2$
$$rec(w,b):=\sum _{j}rec(w_j,b_j)\cdot d_j$$

对于奇数模定义 $dbl:R_q\to R_{2q}$
$$dbl(v):=\sum _{j}dbl(v_j)\cdot d_j$$

Peikert’s KEM 使用的还是 LPR10 定义的简化版 RLWE 问题。算法如下

在两样本的 $R-DLW{E}_{q,\chi }$ 假设下上述的 KEM 算法是 IND-CPA 安全的。

IND-CCA

可以使用 Fujisaki-Okamoto transformation 来获得 IND-CCA 安全的 KEM。

Peikert 也尝试了其他的转换方案但都有各种各样的问题。后续的密钥封装方案Newhope, LAC也都是先构造 IND-CPA 的 KEM然后再用 FO 转换获得 IND-CCA 的 KEM。

密钥封装方案 KEM 和公钥加密方案 PKE 是等价的

• 使用 One-padding 方式可以从 KEM 自然的转化为 PKE 方案。
• 随机生成 key 然后使用 PKE 加密发送这就是一个 KEM 方案。

Newhope - reconciliation

Newhope 进入了 NIST 后量子征集的第二轮但没有进入第三轮。它使用了十分类似 Peikert’s KEM 的方案。

参数选取

Newhope 使用了二的幂次分圆环 $R_q={\mathbb{Z}}_q[X]/(X^n+1)$其中 $n=1024$$q=12289$ 是满足 $2n\mid q-1$ 的最小素数为了使用 NTT 加速。

另外由于高精度的离散高斯分布会消耗大量的熵实际实现时效率不高。因此Newhope 采用了中心化二项分布centered binomial distribution${\Psi }_k$计算方法是
$$\sum _{i=1}^k{b}_i-b_i^{\prime }$$

其中 b i , b i ′ ∈ { 0 , 1 } b_i,b_i' \in \{0,1\} bi​,bi′​∈{0,1} 是独立的均匀随机比特。Newhope 选取了 $k=16$标准差为 $\sqrt{k/2}=2\sqrt{2}$

四维格上的和解

为了降低解密错误率Newhope 选择了密钥空间 { 0 , 1 } 256 \{0,1\}^{256} {0,1}256将每 $1$ 比特编码到 $4$ 个系数上。

方便理解我们首先考虑二维格 ${\tilde{D}}_2$它的基底为 $\{(0,1),(0.5,0.5)\}$如图所示

将每个比特对应的 $2$ 个整系数 $Z_q^2$ 平凡地映射到 $[0,1{)}^2={\mathbb{R}}^2/{\mathbb{Z}}^2$ 上向量 $x$在虚线围成的正方形中灰色的部分Voronoi cell被解码为 $0$白色的部分被解码为 $1$面积各占 $\frac{1}{2}$两个区域的边界是到点 $(0.5,0.5)$ 的 L1 范数的 $0.5$ 等高线。 因此这个 BDD 解码过程是特别简单高效的

但是如果发送者向量 $x_s$ 和接收者向量 $x_c$ 恰好在边界附近即使 $x_c,x_s$ 很接近依然可能会出现和解失败的情况。Newhope 使用 $x_s$ 与它所在的 Voronoi cell 中心点的向量差 $r$ 作为 reconciliation vector辅助 $rec(x,r)$ 的计算接收者获取 $r$ 后计算 $x_s+r$ 向对应的中心倾斜以跨越边界。

另外为了压缩载荷Newhope 对 Voronoi cell 进行了离散化也就是把每个坐标分量从 $Z_q$ 圆整到 $Z_{2^r}$ 上r-bit discretization保留了 MSB 信息。为了消除奇数模 $q$ 导致的 small bias以 $\frac{1}{2}$的概率添加 $(\frac{1}{2q},\frac{1}{2q})$ 到 $x$ 上这叫做 Blurring the edges。

Newhope 使用的是 $d=4$ 维格 ${\tilde{D}}_4$基底 { u 1 , u 2 , u 3 , g = ( 0 , 5 , 0.5 , 0.5 , 0.5 ) } \{u_1,u_2,u_3,g=(0,5,0.5,0.5,0.5)\} {u1​,u2​,u3​,g=(0,5,0.5,0.5,0.5)}其中 $u_i$ 是 ${\mathbb{Z}}^4$ 的单位正交基。此时根据上述 ${\tilde{D}}_2$ 的和解思路
H e l p R e c ( x ; b ) : = C V P D ~ 4 ( 2 r q ( x + b g ) ) ( m o d 2 r ) ∈ { 0 , 1 , 2 , 3 } 4 R e c ( x ; r ) : = D e c o d e ( 1 q x − 1 2 r B r ) ∈ { 0 , 1 } \begin{aligned} HelpRec(x;b) &:= CVP_{\tilde D_4}\left( \dfrac{2^r}{q}(x+bg) \right) \pmod{2^r} \in \{0,1,2,3\}^4\\ Rec(x;r) &:= Decode\left(\dfrac{1}{q}x - \dfrac{1}{2^r}Br\right) \in \{0,1\} \end{aligned} HelpRec(x;b)Rec(x;r)​:=CVPD~4​​(q2r​(x+bg))(mod2r)∈{0,1,2,3}4:=Decode(q1​x−2r1​Br)∈{0,1}​

其中的 $CVP$ 和 $Decode$ 算法如下

Newhope 使用了 $2$ 比特位离散化因此 key 的每个比特需要 $r\cdot d=2\times 4=8$ 比特的 reconciliation information。

KEM 方案

Newhope 使用了 NTT 算法、Montgomery reduction 算法、Short Barrett reduction 算法加速环上的运算。另外使用 SHA-3 标准里的 SHAKE128、SHAKE256 来实例化 PRG、Hash、XOF 等功能。

IND-CPA 安全的 KEM 方案如下

类似 Peikert’s KEMNewhope 也使用 FO 转换来获得 IND-CCA 安全的 KEM。

Newhope - Simple

基于和解机制的 KEM 的优点是载荷很小。不过上边描述的 Newhope 较为复杂不容易理解和实现。后续Newhope 给出了另一种方案不再使用和解机制而是通过 “舍入”或者说 “模切换” 直接丢弃低位比特。

方案描述

编码函数就是 Regev 的 MSB 编码方式为
k = E n c o d e ( v ∈ { 0 , 1 } n ) : = ∑ i = 0 n − 1 k i ⋅ ⌊ q 2 ⌋ ⋅ X i k = Encode(v \in \{0,1\}^n) := \sum_{i=0}^{n-1} k_i \cdot \left\lfloor \dfrac{q}{2} \right\rfloor \cdot X^i k=Encode(v∈{0,1}n):=i=0∑n−1​ki​⋅⌊2q​⌋⋅Xi

降低载荷规模的思路为由于噪声集中在低位比特把它们简单丢弃视作“模切换”。在通信时直接丢弃 $k$ 的各项系数的低位比特得到 $k^{\prime }$ 发送给对方。

解码函数提取 MSB为
$$\mu =Extract(k^{\prime }):=\left\{\begin{array}{rlr}{\mu }_i=1,& & v_i\in \left[-\lfloor \frac{q}{2}\rfloor ,\lfloor \frac{q}{2}\rfloor \right)\\ {\mu }_i=0,& & otherwise\end{array}\right\},\forall i=0,\cdots ,n-1$$

Encryption-based KEM 与 Reconciliation-based KEM 的对比如下

Newhope - Simple 比前述的基于和解的 Newhope仅仅只有很小的载荷损失上涨了 $6.25\%$并拥有相同的安全性。

代码描述

为了降低解密错误率Newhope-Simple 使用了 D2/D4 重复码

密文压缩算法就是丢弃低位比特

使用 NTT 等加速算法最终的 Newhope - Simple 算法如下