参考文献：

1. 基于编码的密码方案：McEliece、Niederreiter-CSDN博客
2. 低密度奇偶校验码（LDPC）-CSDN博客
3. [BJMM12] Becker A, Joux A, May A, et al. Decoding random binary linear codes in 2 n/20: How 1+ 1= 0 improves information set decoding[C]//Advances in Cryptology–EUROCRYPT 2012: 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings 31. Springer Berlin Heidelberg, 2012: 520-536.
4. [MO15] May A, Ozerov I. On computing nearest neighbors with applications to decoding of binary linear codes[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015: 203-228.
5. [DGK20] Drucker N, Gueron S, Kostic D. QC-MDPC decoders with several shades of gray[C]//International Conference on Post-Quantum Cryptography. Cham: Springer International Publishing, 2020: 35-50.
6. [ABB+22] Aragon N, Barreto P, Bettaieb S, et al. BIKE: bit flipping key encapsulation. NIST PQC Round 4, 2022.

Quasi-Cyclic Codes

我们只考虑 ${\mathbb{F}}_2$ 上的线性码。对于 $[n,k]$-线性码 $\mathcal{C}$，

其生成矩阵 $G\in {\mathbb{F}}_2^{k\times n}$（行矢，子空间的基）满足
C = { m G ∣ m ∈ F 2 k } \mathcal C = \{mG \mid m \in \mathbb F_2^k\} C={mG∣m∈F2k​}
校验矩阵 $H\in {\mathbb{F}}_2^{(n-k)\times n}$（行矢，校验位置的指示向量）满足
C = { c ∈ F 2 n ∣ c H T = 0 } \mathcal C = \{c \in \mathbb F_2^n \mid c H^T=0\} C={c∈F2n​∣cHT=0}
为了安全性，code-based PKE/KEM 需要数万的维度。如果使用一般的线性码，将会导致巨大的公钥。类似于 LWE 和 RLWE，这里也可以引入代数结构，从而降低存储和计算开销。

• 二元循环矩阵（binary circulant matrix）：矩阵的第一行定义了整个矩阵，其余的各行都是上一行的循环右移。
• 分块循环矩阵（block-circulant matrix）：是一个分块矩阵，其每个分块都是相同大小的二元循环矩阵。子方阵的阶被称为阶（order），每一行包含的分块矩阵数量被称为指数（index）。

拟循环码（Quasi-Cyclic, QC）的定义如下：

也就是说，QC-code 的生成矩阵是：以 ${\mathbb{F}}_2^{r\times r}$ 中的循环矩阵作为构建单位，排列出 $k_0\times n_0$ 的大矩阵。子空间的基，是其 $k_{0}r$ 个长度为 $n_{0}r$ 的行矢。

Polynomial Ring

容易看出，${\mathbb{F}}_2^{r\times r}$ 中的循环矩阵（交换环），和卷积环 $\mathcal{R}:={\mathbb{F}}_2[X]/(X^r-1)$ 是同构的。确切地说，定义映射 $\varphi :{\mathbb{F}}_2^{r\times r}\to \mathcal{R}$，
$$\varphi :A=\left[\begin{array}{cccc}{a}_0& a_1& \cdots & a_{r-1}\\ a_{r-1}& a_0& \cdots & a_{r-2}\\ ⋮& & \ddots & ⋮\\ a_1& a_2& \cdots & a_0\end{array}\right]\mapsto \varphi (A)=a_0+a_{1}X+\cdots +a_{r-1}{X}^{r-1}$$
对于矩阵转置，对应地定义 $\varphi (A{)}^T=a_0+a_{r-1}X+\cdots +a_1{X}^{r-1}$

将映射 $\varphi$ 扩展到向量空间 ${\mathbb{F}}_2^r$，即
$$\varphi :(v_0,v_1,\cdots ,v_{r-1})\mapsto v_0+v_{1}X+\cdots v_{r-1}{X}^{r-1}$$
那么也有：$\varphi (vA)=\varphi (v)\varphi (A)$，也就是 “矩阵-向量乘” 被转换为了 “环 $\mathcal{R}$ 上的多项式乘法”。两个循环矩阵的乘积也同理，但在 code-based PKE/KEM 中用不到。

现在，QC-code 的生成矩阵 $G$ 可以被视为 ${\mathcal{R}}^{k_0\times n_0}$ 中的元素，QC-code 本身被视为 $\mathcal{R}$ 上的 $[n_0,k_0]$-线性码。写作如下形式：

其中 $g_{ij}$ 和 $h_{ij}$ 都是 $\mathcal{R}$ 中的元素。

BIKE 仅使用 $(2,1)$-QC codes，私钥是 $(h_0,h_1)\in {\mathcal{R}}^2$，其定义的线性码是
$$\mathcal{C}=\{(f{h}_1,f{h}_0)\mid f\in R\}=\{(f_0,f_1)\in {\mathcal{R}}^2\mid f_0{h}_0+f_1{h}_1=0\}$$
生成矩阵：$G=(h_1,h_0)$，校验矩阵：$H=(h_0^T,h_1^T)$，容易验证 $G{H}^T=h_1{h}_0+h_0{h}_1=0$

QC-MDPC

中密度校验码（Moderate-Density Parity-Check, MDPC）具有相对稀疏的校验矩阵，通常的密度 $O(\sqrt{n})$，这使其具有类似于 LDPC 的迭代解码器。

伪循环的 MDPC 码，其定义为：

BIKE 从集合 ${\mathcal{H}}_w=\{(h_0,h_1)\in {\mathcal{R}}^2\mid HW(h_0)=HW(h_1)=w/2\}$ 中，均匀采样一对稀疏多项式，生成随机的 QC-MDPC 码 $\mathcal{C}$。

Decoding

LDPC 中的 Bit Flipping decoding 可以高效解码至多 $O(\sqrt{n})$ 个错误 ，也可以用于 MDPC 的解码。[DGK20] 提出了一种 QC-MDPC 的常数时间解码器，叫做 Black-Gray-Flip（BGF），可以在更少的迭代步骤中，获得更低的解码失败率（Decoding Failure Rate, DFR）。

其中的 $threshold(S,i)$ 是阈值函数，依赖于校验子的重量 $s+e{H}^T$ 和迭代轮数 $i$。迭代次数 NbIter、参数 $\tau$，以及阈值函数的选取，会影响解码的效率和 DFR。

BIKE

首先，定义如下符号：

构造

[ABB+22] 采用了 McEliece scheme 的等价变体，Niederreiter scheme。

其密钥恢复的安全性，建立在类似于 NTRU 的一种译码问题的困难性假设上；其 IND-CPA 安全性，建立在 QC-MDPC 的随机码译码问题上。

对于一般校验子译码问题（general syndrome decoding problem），存在从 search 到 decision 的归约（因此两者等价）。但是对于 QC 变体，还没有归约（decision 不比 search 难）。不过，目前已知的最优求解器都是从信息集译码（Information Set Decoding, ISD）诱导出的，其对于 decision 的求解效率并不比 search 的更好。因此，可以认为 decision-QCSD 是困难的，其安全强度使用 search-QCSD 的最优求解器来估计。

BIKE 需要如下的一些参数集，在后文给出它们的具体选取。

BIKE 的具体构造如下：

[ABB+22] 没有构造 IND-CPA PKE 方案，而是直接给出了 IND-CPA KEM 的构造。注意这里只是 IND-CPA 安全的，他们并没有给出 IND-CCA 安全的证明：没有证明 QC-MDPC 解码失败率的上界，只是用模拟实验和外推法估计了其 DFR 的值。

此外，QC-MDPC-based Niederreiter-like PKE 的明文范围是 ${\mathcal{E}}_t⊊{\mathcal{R}}^2$，并非消息空间 M = { 0 , 1 } l \mathscr M = \{0,1\}^l M={0,1}l。在原始的 Niederreiter 中，使用可逆映射 $\psi :\mathcal{M}\to {\mathcal{E}}_t$ 将消息编码为噪声。而 BIKE 直接设计 KEM，使用散列函数 $H$ 根据随机数 $m$ 生成对应的错误 $e$，然后再用散列函数 $L$ 根据 $e$ 生成掩码，对 $m$ 做对称加密。

参数

BIKE 的参数集是 $r,w,t,l$ 和 $H,K,L$ 以及 $decoder$

BIKE 的设计目标是 KEM，因此固定 $l=256$。函数 $H$ 是生成恰当错误的 XOF，它使用 $m$ 作为种子，用 CTR-mode AES 或者 SHAKE256 作为 PRG，基于 Rejection Sampling 方法产生重量为 $t$ 的伪随机错误。散列函数 $K,L$ 都是压缩到 { 0 , 1 } 256 \{0,1\}^{256} {0,1}256 的 RO，使用 SHA384 实例化，截取前 256 比特。

目前已知：

1. 如果 $r$ 是偶数，那么将会受到 squaring attack；
2. 如果 $2^l\mid r$，那么 squaring attack 可以被重复 $l$ 次，进一步降低安全等级；
3. 因此，$r$ 必须是奇数，甚至是素数。

进一步地，使得 $2\mathrm{mod}r$ 是本原的，此时 $X^r-1\in {\mathbb{F}}_2[X]$ 仅有 $(X-1)$ 和 $(X^{r-1}+\cdots X+1)$ 两个不可约因子，尽可能地消除 $\mathcal{R}$ 的结构。

根据 PIKE 算法描述，其解密时的校验子 $c_0{h}_0=e_0{h}_0+e_1{h}_1$，其中 $(h_0,h_1)\leftarrow {\mathcal{H}}_w⊊{\mathcal{R}}^2$ 以及 $(e_0,e_1)\leftarrow {\mathcal{E}}_t⊊{\mathcal{R}}^2$，它们和参数 $r,w,t$ 有关。为了达到 NIST PQC 要求的 Level 1,3,5 安全级别，需要：

• 在现有最优攻击下，QC-MDPC 译码问题实例的难度达标；
• 为了 IND-CCA 安全性，需要 decoder 的解码失败率足够低。

[ABB+22] 的参数如下，

目前渐进最优的 ISD 问题的解码器是 [MO15]，指数为 $0.0473n$，但是其多项式因子难以估计。BIKE 使用 [BJMM12] 的结果，其指数为 $0.0494n$。由于 QC-code 中任意码字的 $r$ 个循环也都是码字，因此相较于 random code 译码可以加速 $r$ 因子。

安全强度的估计公式为：

代码实现

NIST PQC Round 4 只提供了 C ref 实现，BIKE 的优化实现在 https://github.com/awslabs/bike-kem。使用 google-perftools 分析该实现，可以发现在整个密钥传输过程中，KEM.Dec 占据了 72% 的总时间，而其中的 Decode 就占据了 67% 的总时间（函数 find_err1, find_err2 和 recompute_syndrome）。对比 gf2x 乘法，采用了 Karatzuba，仅占据了 24% 的总时间；KeyGen 中的 mod_inv、Deccode 中的 recompute_syndrome，各自占据大约一半的 Karatzuba 开销。

因此，找到 MDPC 更高效的解码器（还要保证 DFR 充分小），才是提升 BIKE 效率的关键。