DGK密码体制

这是一个由Damgård,Geisler和Krøigaard (DGK)提出的密码体制,它是一种加法同态的密码体制,专用于小明文,非常适合于安全比较协议。

生成密钥

为了生成密钥,将 $k,t$ 和 $\ell$ 作为输入参数,其中 $k > t > \ell$。首先为素数 $p,q$ 生成 $k$ 位RSA模数 $n=pq$。选择 $u$ 作为大于 $\ell + 2$ 的最小素数,它整除 $p−1$ 和 $q−1$,然后生成两个 $t$ 位素数 $v_p$ 和 $v_q$ 使得 $v_p | (p-1)$ 以及 $v_q | (q-1)$。公钥为 $pk = (n, g, h, u)$,私钥为 $sk = (p, q, v_p, v_q)$。

最后,我们选择随机元素 $g,h \in \mathbb{Z}^*_n$ 使得 $h$ 的乘法阶为 $v$ 模 $p$ 和 $q$,$g$ 的阶为 $uv$。公钥现在是 $pk = (n,g,h,u)$,而私钥是 $sk = (p,q,v)$。明文空间为 $\mathbb{Z}_u$,密文空间为 $\mathbb{Z}^*_n$。

加密

为了加密 $m \in \mathbb{Z}_u$,我们选择一个随机的略长于 $2t$ 位的整数 $r$,并设密文为

我们注意到,通过选择 $r$ 作为比 $v$ 大得多的数,我们确保 $h^r$ 与由 $h$ 生成的群中的均匀随机元素在统计上是不可区分的。私钥的所有者(知道 $v$)可以通过使用随机的 $r \in \mathbb{Z}_v$ 来更有效地做到这一点。

解密

对于密文 $c$ 的解密,可以通过注意以下内容来进行“真正的”解密

显然,$g^{v_pv_q}$ 的阶为 $u$,因此在 $m$ 的值和 $(g^{v_pv_q})^m \bmod n$ 的值之间存在一一对应的关系。由于 $u$ 非常小,所以可以简单地建立包含 $(g^{v_pv_q})^m \bmod n$ 的值和 $m$ 的对应值的表。

比较

对于密文下的比较,只需要决定 $c$ 是否加密 $0$。这很简单,因为 $c^v \bmod n = 1$ 当且仅当 $c$ 加密 $0$ 时。这从以下事实得出:$v_p v_q$ 是 $h$ 的阶,$uv_pv_q$ 是 $g$ 的阶,并且 $m<u$。如果进行解密的一方也存储了 $n$ 的因子,则可以通过代替检查 $c^v \bmod p=1$ 来优化这一点,这在实践中将节省3-4倍。

当逐位比较两个整数 $x$ 和 $y$ 时,最明显的方法是从左(最高有效部分)到右扫描两个位行,搜索第一个不同的位。这些不同位的比较结果将确定两个整数的比较结果。DGK协议遵循类似的方法。假设两个整数都包含分别由 $x$ 和 $y$ 表示的 $\ell$ 位,因此 $x = x_{\ell -1}…x_1x_0$,$x_{\ell - 1}$ 是 $x$ 的最高有效位。然后计算数字 $c_i$,$0 \leq i < \ell$,对于每个 $j$,$i<j<\ell$,当 $x_j=y_j$,$i<j<\ell$ 并且同时 $x_i \neq y_i$ 时,该数字才为零。

更具体地,

显然,当 $x_j=y_j$ 对于每个 $j$,$i < j < \ell$ 时,异或之和正好为零。变量 $s$ 可以设置为 $−1$ 或 $1$,具体取决于执行的比较。例如,当 $s=−1$ 时,当 $x_i=1$ 且 $y_i=0$ 时,$c_i$ 仅为零(对于每个 $j$,$i<j$,$x_j=y_j$),从而 $y < x$。为了避免一方获知比较结果,一方将设置参数 $s$,而另一方将获知 $c_i$ 是否 $=0$。