基于格的数字签名算法：BLISS（Bimodal Lattice Signature Scheme）
字数 2049 2025-11-02 10:11:13

基于格的数字签名算法：BLISS（Bimodal Lattice Signature Scheme）

BLISS（Bimodal Lattice Signature Scheme）是一种基于格困难问题的后量子数字签名算法，其安全性依赖于最坏情况下的格问题（如LWE或SIS）。BLISS通过高斯采样和拒绝采样技术实现高效签名，同时保持紧凑的签名尺寸。下面将逐步讲解BLISS的签名生成与验证过程。

1. 关键参数与基础概念

BLISS依赖以下参数：

  • 模数 \(q\)：一个整数模数（如 \(q = 12289\)）。
  • 维度 \(n\)：格向量的维度（如 \(n = 512\)）。
  • 噪声分布：离散高斯分布，用于生成随机向量。
  • 公钥与私钥：
    • 私钥：短向量 \(\mathbf{s}_1, \mathbf{s}_2\)（满足 \(\mathbf{a} \cdot \mathbf{s}_1 + \mathbf{s}_2 = q \mod 2q\)）。
    • 公钥：向量 \(\mathbf{a}\) 和 \(\mathbf{t} = \mathbf{a} \cdot \mathbf{s}_1 + \mathbf{s}_2\)。

2. 签名生成过程

假设签名者对消息 \(m\) 进行签名，私钥为 \((\mathbf{s}_1, \mathbf{s}_2)\)，公钥为 \((\mathbf{a}, \mathbf{t})\)。步骤如下：

步骤 1：生成临时随机向量

  • 随机采样两个短向量 \(\mathbf{y}_1, \mathbf{y}_2\)，
    从离散高斯分布中抽取（均值为 0，方差为 \(\sigma\)）。
  • 计算承诺向量：
    \(\mathbf{u} = \mathbf{a} \cdot \mathbf{y}_1 + \mathbf{y}_2 \mod q\)。

步骤 2：计算挑战值

  • 使用哈希函数 \(H\)（如 SHA-3）将 \(\mathbf{u}\) 和消息 \(m\) 映射为一个挑战向量 \(\mathbf{c}\)：
    \(\mathbf{c} = H(\mathbf{u} \| m)\)。
    \(\mathbf{c}\) 是一个稀疏的二进制向量（大多数元素为 0，少数为 ±1）。

步骤 3：生成候选签名

  • 计算签名向量：
    \(\mathbf{z}_1 = \mathbf{y}_1 + \mathbf{s}_1 \cdot \mathbf{c}\),
    \(\mathbf{z}_2 = \mathbf{y}_2 + \mathbf{s}_2 \cdot \mathbf{c}\)。
    若 \(\mathbf{z}_1, \mathbf{z}_2\) 的范数过大，则返回步骤 1 重新采样（拒绝采样）。

步骤 4：拒绝采样优化

  • 为避免泄露私钥信息，BLISS引入拒绝采样：以一定概率丢弃 \((\mathbf{z}_1, \mathbf{z}_2)\)，
    确保签名分布与高斯分布独立于私钥。具体概率由参数 \(M\) 控制。

步骤 5：输出签名

  • 最终签名为 \((\mathbf{z}_1, \mathbf{z}_2, \mathbf{c})\)。

3. 签名验证过程

验证者使用公钥 \((\mathbf{a}, \mathbf{t})\) 验证签名 \((\mathbf{z}_1, \mathbf{z}_2, \mathbf{c})\) 对消息 \(m\) 的有效性：

步骤 1：重计算承诺

  • 计算：
    \(\mathbf{u}' = \mathbf{a} \cdot \mathbf{z}_1 + \mathbf{z}_2 - \mathbf{t} \cdot \mathbf{c} \mod q\)。

步骤 2：验证挑战一致性

  • 计算 \(\mathbf{c}' = H(\mathbf{u}' \| m)\)。
  • 检查是否 \(\mathbf{c}' = \mathbf{c}\)。

步骤 3：验证范数边界

  • 检查 \(\|\mathbf{z}_1\|\) 和 \(\|\mathbf{z}_2\|\) 是否小于预设阈值（防止攻击者伪造过大向量）。

4. 安全性关键点

  • 格困难问题：伪造签名需解决SIS（Short Integer Solution）问题。
  • 拒绝采样：确保签名不泄露私钥分布。
  • 参数选择：维度 \(n\) 和模数 \(q\) 需平衡安全性与效率。

5. 总结

BLISS通过高斯采样和巧妙的拒绝采样机制，实现了基于格问题的数字签名，其签名尺寸远小于传统RSA或ECC方案，适用于后量子安全场景。整个过程依赖哈希函数和模运算，确保高效性与安全性。

基于格的数字签名算法：BLISS（Bimodal Lattice Signature Scheme） BLISS（Bimodal Lattice Signature Scheme）是一种基于格困难问题的后量子数字签名算法，其安全性依赖于最坏情况下的格问题（如LWE或SIS）。BLISS通过高斯采样和拒绝采样技术实现高效签名，同时保持紧凑的签名尺寸。下面将逐步讲解BLISS的签名生成与验证过程。 1. 关键参数与基础概念 BLISS依赖以下参数： 模数 \( q \) ：一个整数模数（如 \( q = 12289 \)）。 维度 \( n \) ：格向量的维度（如 \( n = 512 \)）。 噪声分布 ：离散高斯分布，用于生成随机向量。 公钥与私钥 ： 私钥：短向量 \( \mathbf{s}_ 1, \mathbf{s}_ 2 \)（满足 \( \mathbf{a} \cdot \mathbf{s}_ 1 + \mathbf{s}_ 2 = q \mod 2q \)）。 公钥：向量 \( \mathbf{a} \) 和 \( \mathbf{t} = \mathbf{a} \cdot \mathbf{s}_ 1 + \mathbf{s}_ 2 \)。 2. 签名生成过程 假设签名者对消息 \( m \) 进行签名，私钥为 \( (\mathbf{s}_ 1, \mathbf{s}_ 2) \)，公钥为 \( (\mathbf{a}, \mathbf{t}) \)。步骤如下： 步骤 1：生成临时随机向量 随机采样两个短向量 \( \mathbf{y}_ 1, \mathbf{y}_ 2 \)， 从离散高斯分布中抽取（均值为 0，方差为 \( \sigma \)）。 计算承诺向量： \( \mathbf{u} = \mathbf{a} \cdot \mathbf{y}_ 1 + \mathbf{y}_ 2 \mod q \)。 步骤 2：计算挑战值 使用哈希函数 \( H \)（如 SHA-3）将 \( \mathbf{u} \) 和消息 \( m \) 映射为一个挑战向量 \( \mathbf{c} \)： \( \mathbf{c} = H(\mathbf{u} \| m) \)。 \( \mathbf{c} \) 是一个稀疏的二进制向量（大多数元素为 0，少数为 ±1）。 步骤 3：生成候选签名 计算签名向量： \( \mathbf{z}_ 1 = \mathbf{y}_ 1 + \mathbf{s}_ 1 \cdot \mathbf{c} \), \( \mathbf{z}_ 2 = \mathbf{y}_ 2 + \mathbf{s}_ 2 \cdot \mathbf{c} \)。 若 \( \mathbf{z}_ 1, \mathbf{z}_ 2 \) 的范数过大，则返回步骤 1 重新采样（拒绝采样）。 步骤 4：拒绝采样优化 为避免泄露私钥信息，BLISS引入拒绝采样：以一定概率丢弃 \( (\mathbf{z}_ 1, \mathbf{z}_ 2) \)， 确保签名分布与高斯分布独立于私钥。具体概率由参数 \( M \) 控制。 步骤 5：输出签名 最终签名为 \( (\mathbf{z}_ 1, \mathbf{z}_ 2, \mathbf{c}) \)。 3. 签名验证过程 验证者使用公钥 \( (\mathbf{a}, \mathbf{t}) \) 验证签名 \( (\mathbf{z}_ 1, \mathbf{z}_ 2, \mathbf{c}) \) 对消息 \( m \) 的有效性： 步骤 1：重计算承诺 计算： \( \mathbf{u}' = \mathbf{a} \cdot \mathbf{z}_ 1 + \mathbf{z}_ 2 - \mathbf{t} \cdot \mathbf{c} \mod q \)。 步骤 2：验证挑战一致性 计算 \( \mathbf{c}' = H(\mathbf{u}' \| m) \)。 检查是否 \( \mathbf{c}' = \mathbf{c} \)。 步骤 3：验证范数边界 检查 \( \|\mathbf{z}_ 1\| \) 和 \( \|\mathbf{z}_ 2\| \) 是否小于预设阈值（防止攻击者伪造过大向量）。 4. 安全性关键点 格困难问题 ：伪造签名需解决SIS（Short Integer Solution）问题。 拒绝采样 ：确保签名不泄露私钥分布。 参数选择 ：维度 \( n \) 和模数 \( q \) 需平衡安全性与效率。 5. 总结 BLISS通过高斯采样和巧妙的拒绝采样机制，实现了基于格问题的数字签名，其签名尺寸远小于传统RSA或ECC方案，适用于后量子安全场景。整个过程依赖哈希函数和模运算，确保高效性与安全性。