Fiat-Shamir签名与BLISS类签名：基于Module-NTRU的密码学方案解析

### Fiat - Shamir签名与BLISS类签名：基于Module - NTRU的密码学方案解析 #### 1. 引言 在密码学领域，寻找安全且高效的签名方案一直是研究的重点。本文将介绍基于Module - NTRU假设的两种签名方案：基于iMNTRU的Fiat - Shamir签名和基于MNTRU的BLISS类签名，并对其安全性进行分析，同时给出具体的参数实例。 #### 2. 基于iMNTRU的有损识别方案 ##### 2.1 密钥生成 - 选择参数：选择秩$d \in N$、环维度$n$和素数模$q$。 - 采样：从$iMNTRU_{q,n,d,D_1,D_2,U}(R_q)$分布中采样$(h', F, g, t)$，其中$D_1$和$D_2$是用于采样秘密密钥的分布，这里从均匀分布$U_n^{\beta}$中独立采样$F$中的每个$f$和$g$中的每个$g$。 - 计算$h'$：在$F \cdot h' + g = t \pmod{q}$中计算$h' = \{h_i\}_{i = 1}^{d - 1}$。 - 确定密钥：取$F$的一行$(f_1, \cdots, f_{d - 1})$，令$f_d := g$，则$f = (f_1, \cdots, f_{d - 1}, f_d)$为秘密密钥；$h = (h_1, \cdots, h_{d - 1}, 1)$，$(h, t)$为公共密钥，满足$\langle h, f\rangle = t$。 ##### 2.2 识别过程 1. **承诺阶段**：证明者从分布$U_n^{\gamma}$中采样多项式向量$y := (y_1, \cdots, y_d)$，计算承诺$u := \left[\sum_{i = 1}^{d - 1} h_iy_i \pmod{q}\right]_r$，并将$u$发送给验证者。 2. **挑战阶段**：验证者从分布$B_{\kappa}$（长度为$n$、权重为$\kappa$的三元向量集合）中生成随机挑战$c$，并将$c$发送给证明者。 3. **响应阶段**：证明者计算$z_i := y_i + c \cdot f_i$，若对于所有$1 \leq i \leq d - 1$，满足$\|z_i\|_{\infty} \leq \gamma - \beta \cdot \kappa$，且$\left|\left[\sum_{i = 1}^{d - 1} h_iy_i - c \cdot f_d \pmod{q}\right]_r\right| < 2^{r - 1} - \beta \cdot \kappa$以及$\|w\|_{\infty} < \lfloor q/2\rfloor - \beta \cdot \kappa$，则返回$z$；否则返回$\perp$。 4. **验证阶段**：验证者若对于所有$i$，有$\|z_i\|_{\infty} \leq \gamma - \beta \cdot \kappa$且$\left[\sum_{i = 1}^{d - 1} h_iz_i - t \cdot c \pmod{q}\right]_r$等于$u$，则接受$(z, u)$；否则拒绝。 ##### 2.3 方案性质 - **完美na - HVZK**：存在两个算法$Sim(.)$和$Trans(.)$，其输出分布相同。 - **正确性**：在变体决定性iMNTRU假设下，识别方案的正确性误差为$\delta \approx 1 - \exp\left(-\beta\kappa n\left(\frac{d - 1}{\gamma} + \frac{1}{2^{r - 1} + 1}q\right)\right)$。 - **有损性**：定义有损密钥生成算法$LossyIGen(q, n, d, \beta)$，该方案具有$\epsilon_{ls}$ - 有损稳健性，其中$\epsilon_{ls} \leq \frac{1}{|B_{\kappa}|} + 2 \cdot |B_{\kappa}|^2 \cdot (4(\gamma - B) + 1)^{n(d - 1)} \cdot (2^{r + 1} + 1)^n / q^n$。 - **最小熵**：识别方案具有$\alpha := n \cdot \log E$比特的最小熵，其中$E = \min\left\{(2\gamma + 1)^{d - 1}, \frac{q}{(4\gamma + 1)^{(d - 1)}(2^{r + 1} + 1)}\right\}$。 - **计算唯一响应（CUR）**：对于识别方案的任何对手，产生两个有效转录$(u, c, z)$和$(u, c, z')$（$z \neq z'$）的成功概率被限制为$(4(\gamma - B) + 1)^{n(d - 1)} \cdot (2^{r + 1} + 1)^n \cdot q^{-n}$。 #### 3. 基于MNTRU的BLISS类签名方案 ##### 3.1 签名方案 - **密钥生成**：选择秩$d \in N$、素数