0%

基于LWE的公钥加密机制构造

发表于 更新于 分类于

格密码学中有两种主要的基于 LWE 假设的公钥加密构造方法，分别为 [Reg05] 中提出的原始版本和 [GPV08] 中提出的对偶（Dual）版本。

[Reg05] Primal-version

  • 构造（Construction）：

    regev05

  • 正确性（Correctness）：

  • 安全性（Security）：这里简单地给出证明要点。在上述加密过程中，攻击者看到的是：

    而 $\mathbf{b}^t = \mathbf{s}^t \mathbf{A} + \mathbf{e}^t$，因此根据 LWE 假设，这个四元组与下面的四元组不可区分，其中 $\widetilde{}$ 表示均匀随机的变量：

    又由于 $\mathbf{u} = \mathbf{Ax}$，因此根据 SIS 假设可知 $\mbox{Tuple2}$ 与下面的 $\mbox{Tuple3}$ 也是不可区分的：

    此时注意到 $u’ = \mathbf{b}^t \mathbf{x} + bit \cdot \frac{q}{2}$，当 $\mathbf{b}^t$ 已经均匀随机化成了 $\widetilde{\mathbf{b}^t}$，且加密比特信息未知，$u’$ 就相当于是一个 one-time pad，$\mbox{Tuple3}$ 与下面的 $\mbox{Tuple4}$ 是不可区分的 ：

    而 $\mbox{Tuple4}$ 是完全随机的，攻击者无法从中得到任何与加密比特消息有关的信息，因此这个构造是安全的。

[GPV08] Dual-version

  • 构造（Construction）

    gpv08

  • 正确性（Correctness）：

  • 安全性（Security）：同样简单地给出证明要点。在上述加密过程中，攻击者看到的是：

    而 $\mathbf{b}^t = \mathbf{s}^t \mathbf{A} + \mathbf{e}^t$，因此根据 LWE 假设，$\mbox{Tuple1}$ 与下面的 $\mbox{Tuple2}$ 不可区分：

    又由于 $\mathbf{u} = \mathbf{Ax}$，因此根据 SIS 假设可知 $\mbox{Tuple2}$ 与下面的 $\mbox{Tuple3}$ 也是不可区分的：

    此时注意到 $b’$ 同样是 one-time pad，因此 $\mbox{Tuple3}$ 与 $\mbox{Tuple4}$ 不可区分：

    而 $\mbox{Tuple4}$ 是完全随机的，因此这个构造是安全的。

两种构造的对比

从上面的两种构造来看，不难发现它们之间存在着对偶关系（对偶没有具体定义，它广泛地指那些具有相似性和对称性但又无法完全对称的关系）。

pk ciphertext
[Reg05] $\mathbf{b}^t$（长为：$n \cdot \log q$） $(\mathbf{u}, u’)$ （长为：$(n+1)$）
[GPV08] $\mathbf{u}$ （长为：$n$） $(\mathbf{b}^t, b’)$（长为：$(n \cdot \log q + 1)$）

【注】：$m \approx \log q$。

同时，对于 [Reg05] 来说，当攻击者拿到（或者说给定）一个 $\mbox{Tuple} = (\mathbf{A}, \mathbf{b}^t, \mathbf{u}, u’)$ 时，根据这个 $Tuple$ 其实是可以唯一确定私钥 $\mathbf{s}$ 的（当然根据安全性，攻击者求不出这个值），但是用来生成密文的随机值 $\mathbf{x}$ 是无法确定的。而与之对应的是，在 [GPV08] 中，当给定一个 $\mbox{Tuple} = (\mathbf{A}, \mathbf{u}, \mathbf{b}^t, b’)$ 时，根据这个 $Tuple$ 可以唯一确定那个用来生成密文的随机值 $\mathbf{s}$，但是满足这个 $Tuple$ 关系的私钥 $\mathbf{x}$ 却可以有很多可能的取值。

参考资料