论文：Linearly Homomorphic Encryption from DDH

CL 同态加密特点：

  • 对群 $G$ 的要求

    • $G$ 上求解 DDH 问题是困难的，$G$ 的子群 $F$ 上求解 DL 问题是容易的
    • $G$ 的阶是未知的，否则 $G$ 上的 DDH 问题不再是困难的
  • 消息 $m$ 的取值空间为 $p$，$p$ 是子群 $F$ 的阶
  • 支持无限次模 $p$ 的同态加
  • 不同于 Paillier，该同态加密安全性不依赖质因数分解难问题，所以 $p$ 可独立选择而不依赖于安全参数，不过 $p$ 至少是 80 比特

CL 同态加密和 Elgamal 同态加密很像，不过 Elgamal 同态加密要求在群 $G$ 上求解 DDH 问题是困难的，求解 DL 问题是容易的，所以消息 $m$ 必须比较小，以便快速解密，因此 Elgamal 只支持对数次数的同态加。

性能上，在相同的安全级别时，CL 同态加密快于模数为 2048 比特的 Paillier 同态加密。

以下算法是一般版，见论文 第 2.3 节，改进版见论文 第 4.2 节。

Gen 和 Solve

定义 Gen 如下：

$(B, n, p, s, g, f, G, F) \leftarrow Gen(1^{\lambda}, 1^{\mu})$

  • 输入是 $\lambda, \mu$，

  • 输出 $(B, n, p, s, g, f, G, F)$

    • $s$ 是 $\lambda$ 比特的整数
    • $p$ 是 $\mu$ 比特的整数
    • $gcd(p,s)=1, n=p \cdot s$
    • $B$ 是 $s$ 的上界，可以是 $B=2^{2\lambda}$
    • $(G, \cdot)$ 是生成元为 $g$，阶为 $n$ 的循环群，$n$ 的上界是 $Bp$
    • $F ⊂ G$ 是 $G$ 的子群，阶为 $p$，生成元为 $f$
  • 具体过程见论文 第 3.1 节

在 $G$ 的子群 $F$ 求解 DL 问题如下：

$Solve(B, p, g, f, G, F, X) \rightarrow x$

  • 输入 $X=f^x$
  • 输出明文 $x$
  • 具体过程见论文 第 3.1 节

注意，$G$ 的阶 $n$ 并不会作为 $Solve$ 的输入，只有上界 $Bp$ 被隐式给出。因为如果给出 $n$ 或 $s$ 的话，$x \% p$ 是可以直接算出的，$G$ 上的 DDH 问题也不再是困难的，证明过程见论文 2.1 节。

密钥生成 KeyGen$(1^{\lambda})$

  1. $(B, n, p, s, g, f, G, F) \leftarrow Gen(1^{\lambda}, 1^{\mu})$
  2. 随机选择 $x \in [0, Bp-1]$，令 $h = g^x$
  3. 公钥为 $pk \leftarrow (B, p, g, h, f)$，私钥为 $sk \leftarrow x$
  4. 返回 $(pk, sk)$

加密 Encrypt$(1^{\lambda}, pk, m)$

  1. 随机选择 $r \in [0, Bp-1]$
  2. 计算 $c_1 \leftarrow g^r$
  3. 计算 $c_2 \leftarrow f^mh^r$
  4. 返回 $(c_1, c_2)$

解密 Decrypt$(1^{\lambda}, pk, sk, (c_1, c_2))$

  1. 计算 $M \leftarrow c_2/c_1^x$
  2. 求解 $m \leftarrow Solve(p, g, f, G, F, M)$
  3. 返回 $m$

推导：$M \leftarrow c_2/c_1^x = (f^mh^r)/g^{rx}=(f^mg^{xr})/g^{rx}=f^m$

因为在 $G$ 的子群 $F$ 上求解 DL 问题是容易的，所以可以通过 $Solve$ 解出 $m$

同态加 EvalSum$(1^{\lambda}, pk, (c_1, c_2), (c_1',c_2'))$

  1. 计算 $c_1'' \leftarrow c_1c_1'$ 和 $c_2'' \leftarrow c_2c_2'$
  2. 随机选择 $r \leftarrow [0, Bp-1]$
  3. 返回 $(c_1''g^r, c_2''h^r)$

推导：$(c_1, c_2)$ 和 $(c_1', c_2')$ 分别是 $m$ 和 $ m'$ 的密文，可以算出

$$ \begin{align} &M \leftarrow (c_2''h^r) / (c_1''g^r)^x\\ &=(c_2c_2'h^r)/(c_1c_1'g^r)^x\\ &=(c_2/c_1^x)(c_2'/c_1'^x)(h^r/g^{rx})\\ &=f^mf^{m'}\\ &=f^{(m+m') \% p} \end{align} $$

是 $m+m'$ 的解密

同态乘 EvalScal$(1^{\lambda}, pk, (c_1, c_2), \alpha)$

  1. 计算 $c_1' \leftarrow c_1^{\alpha}$ 和 $c_2' \leftarrow c_2^{\alpha}$
  2. 随机选择 $r \leftarrow [0, Bp-1]$
  3. 返回 $(c_1'g^r, c_2'h^r)$

推导：$(c_1,c_2)$ 是 $m$ 的密文，$\alpha$ 是数字，可以算出

$$ \begin{align} &M \leftarrow (c_2'h^r) / (c_1g^r)^x\\ &=(c_2^{\alpha}h^r)/(c_1^{\alpha}g^r)^x\\ &=(c_2/c_1^x)^{\alpha}(h^r/g^{rx})\\ &=f^{m\alpha \% p}\\ \end{align} $$

是 $m\alpha$ 的解密