内积加密：MDDH 假设

“内积加密”系列文章的前半部分旨在总结和科普 Agrawal、Libert、Stehlé 在 2016 年提出 [ALS16]，Wee 在 2017 年改进 [Wee17]，Agrawal、Libert、Monosij、Titiu 在 2020 年完善 [ALMT20] 的内积加密算法。在这一篇里我们讨论一些针对 ALS 方案的准备知识：循环群、MDDH 假设。

插播新闻 加州 出现了首例 无已知与出国旅行有联系的新冠患者，目前许多密码学、量子计算学者正在访问 Simons Institute，希望大家平安！

前情提要

在 第一篇 和 第二篇 里，我们定义了一次性私钥内积加密的语法、语义、安全性并用一次一密构造了完美模拟安全的一次性私钥内积加密。从 第三篇 开始，话题转向公钥 IPFE，我们定义了语法、语义、安全性。

公钥 IPFE 的安全性基于计算意义下的不可区分性 (computational indistinguishability)，上回也提到从完美不可区分弱化为计算意义下不可区分是 必要的，运用相同的论证可以知道：若存在着 IND-CPA 的公钥 IPFE，则 P​=NP。这是因为在非确定性多项式时间 (non-deterministic polynomial time) 内可以轻松算（猜）出主私钥，若 P=NP，则主私钥也可以在多项式时间内算出，从而可以轻松区分 IND-CPA 里面的两个实验。

既然目前没有人解决 $\mathsf{P}\stackrel{?}{=}\mathsf{N}\mathsf{P}$ 问题，那怎么可能证明一个公钥 IPFE 具有 IND-CPA 安全性呢？答案是我们需要假设一些问题难解 (intractable)，这也叫做计算性假设 (computational assumption)，然后证明“如果某某假设成立，则某某 IPFE 具有 IND-CPA 安全性”这种命题。

这里要用到的是大名鼎鼎的判定性 Diffie–Hellman 假设 (decisional Diffie–Hellman assumption)，简称 DDH 假设。实际上有时它的一个变体——判定性矩阵 Diffie–Hellman 假设 (decisional matrix Diffie–Hellman assumption)，即 MDDH 假设——更好用。无论是考虑哪个假设，都需要先介绍循环群 (cyclic group) 的概念。

循环群

如果读者知道什么是循环群 (cyclic group)，则可以跳过这段麻瓜版¹循环群说明。一个质数阶循环群 $(G,[[\cdot ]],-)$ 包括三个部分：

• 集合 $G$ 包含恰好质数 $p$ 个元素，这里 $p=|G|$ 叫做该群的阶 (order)。
• 一个双射 [[⋅]]:Zp​→G,x↦[[x]]，我们管 $[[x]]$ 叫做 $x$ 的编码，或者指数里的 $x$ ($x$ in the exponent)，而 $x$ 叫做 $[[x]]$ 的离散对数 (discrete logarithm)。
• 一个运算 −:G×G→G,([[x]],[[y]])↦[[x]]−[[y]]，满足 $[[x-y]]=[[x]]-[[y]]$ 对任意 $x,y\in {\mathbb{Z}}_p$ 成立。

用人话来说，$p$ 阶循环群允许我们对 ${\mathbb{Z}}_p$ 里的元素编码，并且可以用编码运算，并且先（作为数）运算再编码等价于先编码再（作为群元素）运算。通常来说，双中括号和减号本身并不是很重要，或者在一个具体的上下文中有明确指代，这时也直接说 $G$ 是循环群。

习题 从 $[[1]]$ 出发，如何对任意 $z\in {\mathbb{Z}}_p$ 用多项式次 $-$ 算出 [[z]]？注意 $z$ 的长度是 Θ(logz)，使用 $-$ 的次数应该是 $\log z$ 的多项式。

此外，还可以把 $[[\cdot ]]$ 扩展到矩阵记法，考虑 A∈Zpm×n​，则 $[[\mathbf{A}]]\in G^{m\times n}$ 且 [[A]][i,j]=[[A[i,j]]]。矩阵的运算也可以自然定义，即 $[[\mathbf{A}]]-[[\mathbf{B}]]=[[\mathbf{A}-\mathbf{B}]]$ 和 B[[A]]C=[[BAC]]。容易验证这些运算也都可只用多项式次 $-$ 完成。

最后，实际上人类还是更喜欢使用 +，令 $$[[x]]+[[y]]\stackrel{\text{def}}{==}[[x+y]].$$ 利用上面习题解答中的技巧，可以用 $-$ 高效实现 +。

MDDH 假设

说了这么多，搞一个循环群出来有什么用呢？考虑有 x,y∈Zp​，若 y​=0，则 很容易算出 x/y。然而这个运算过程是需要知道 $x,y$ 作为数的写法的。如果现在只知道 [[x]],[[y]]，则看起来没有什么好方法可以计算 $[[x/y]]$——当然，由于 $[[\cdot ]]$ 是双射，总是可以还原 $x,y$ 这两个数，但这看起来无法用多项式次 $-$ 完成。

循环群的定义中刻意忽略了一些数上面容易进行的运算，从语法上 (syntactically)看起来我们只能用 $-$ 和“字符串相等”来操作编码，于是导致一些整数表示下简单的问题变得困难起来。这种困难性正是密码学所需要的——当然，什么都困难也不行，毕竟密码学算法也是要有人正常使用的。我们需要一些操作是简单的，另一些问题是困难的：一个正常用户可以通过“简单”部分正常使用系统，而一个攻击者则会面对“困难”的部分。

我们要求 $[[1]]$ 和映射 $-$ 可以高效计算。这样通过刚才的习题，我们可以高效进行如下两件事：

• 输入一个数，计算它的编码。
• 输入一些（不需要知道离散对数的）编码和一些系数（以数的形式给出），计算这些编码在这些系数下的线性组合。

然而，“计算一个编码的离散对数”并不是必然容易的——实际上人们相信对于一些群来说这个问题是困难的，这叫做离散对数假设 (discrete logarithm assumption)，简称 DLOG 假设。这个假设可以用来构造一些密码学工具，然而这里我们要用到一些更强的假设。

最直观的刻画循环群里问题困难性的方法是说“任何对编码的操作都只能是对编码的字符串相等和 $-$ 调用”。这种刻画方式叫做一般群模型 (generic group model)。它和现实世界脱节比较大——比如，凭什么我不可以调用 $-$ 运算到一半去看运算的中间过程？这是一个过强，甚至无法在现实世界实现 [Den02] 的模型。

一个常见的标准模型下的假设是 DDH 假设，它说的是两个分布的不可区分性： $$[[a,b,ab]]\approx [[a,b,c]],$$ 其中 a,b,c←$​Zp​。对于一个从未考虑过计算复杂性的人来说这个假设简直不可思议，因为这两个分布统计上非常不同：

• 第一个分布里第三个群元素完全决定于前两个，第二个分布里第三个群元素和前两个独立且是均匀随机的。
• 大多数来自于第二个分布的样本是不可能出现于第一个分布的。
• 第一个分布的熵是 2log2​p，第二个分布的熵是 3log2​p。

的确，一个运行指数时间的使坏者可以轻松区分两个分布，然而对于一些循环群，人们相信² DDH 假设是成立的——目前没有发现任何技巧可以在多项式时间内以不可忽略的优势区分两个分布。

DDH 假设的推广是 MDDH 假设。令 $k$ 是一个常数，$\ell ,q$ 是多项式，${\text{MDDH}}_{k,\ell }^q$ 假设是说如下两个分布不可区分： $$([[\mathbf{A}]],[[{\mathbf{S}}^{\text{T}}\mathbf{A}]])\approx ([[\mathbf{A}]],[[{\mathbf{C}}^{\text{T}}]]),$$ 其中 A←$​Zpk×ℓ​,S←$​Zpq×ℓ​,C←$​Zpq×k​。

注意，当 $\ell \le k$ 且 $p$ 超过任何多项式时，这个假设无条件成立——那两个分布统计意义下不可区分。但如果 ℓ>k，则 $p$ 必须超过任何多项式才有意义（否则可以计算离散对数，从而容易区分）。如果不提 ℓ,q，则 ℓ=k+1,q=1，这种情况下：

• 第一个分布中 ${\mathbf{s}}^{\text{T}}\mathbf{A}$ 在 $\mathbf{A}$ 的行空间里，第二个分布中 ${\mathbf{c}}^{\text{T}}$ 几乎一定不在 $\mathbf{A}$ 的行空间里。
• 如果把第二部分和 $\mathbf{A}$ 拼成一个大矩阵，则第一个分布里这个矩阵的秩 (rank) 几乎一定是 $k$（从而不可逆），而第二个分布里这个矩阵的秩几乎一定是 $k+1$（从而可逆）。
• 第一个分布的熵远远低于第二个。

我们将会看到，这些魔法般的假设可以帮助我们实现安全的公钥密码系统。

小试牛刀

现在举一个使用计算性假设和多项式时间归约 (polynomial-time reduction) 来证明安全性的例子。考虑经典的 ElGamal 加密 [EG84]：

• 一个用户的私钥是 a←$​Zp​，公钥是 [[a]]。
• 加密 $[[m]]$ 时生成 $b\stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p$ 并输出 $[[b]]$ 和 [[d]]=[[m]]+b[[a]]。
• 解密时输出 [[d]]−a[[b]]。

我们证明它的 SIM-CPA 安全性——定义类似 IPFE 的 SIM-CPA，但不存在询问 I/II 环节，模拟器只需要生成模拟公钥和一个模拟密文（不知道明文的情况下）。这个模拟器十分简单：抽取 $a,b,d\stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p$ 并输出 $[[a]]$ 作为模拟公钥，以及 $[[b]],[[d]]$ 作为模拟密文。

显然，这个模拟器“完全玩坏了”，因为它的输出和真实密文分布相去甚远（例如明文是 $[[0]]$ 的情况，一个随机的 $d$ 几乎不可能恰好等于 ab）。然而不要紧，SIM-CPA 只要求真实世界和模拟世界在计算意义下不可区分，若 DDH 假设成立，则可以证明这个模拟器🉑。

读者习题 1 证明 DDH 假设蕴含着 ${\text{MDDH}}_1$ 假设。（若 DDH 假设里的两个分布不可区分，则 ${\text{MDDH}}_1$ 假设里的两个分布也不可区分。）

读者习题 2 证明 ${\text{MDDH}}_k$ 假设蕴含着 ${\text{MDDH}}_{k,\ell }^q$ 假设，其中 $\ell ,q$ 是任意取值为正整数的多项式。

本篇结语

这一篇里我们介绍了循环群和 MDDH 假设，并练习了如何在计算性假设的前提下证明不可区分性。至此，理解 [ALS16] IPFE 方案的准备工作终于搞定了，下一篇 将会是上半部分的末篇，我们叙述 ALS 的构造并证明它的 SIM-CPA 安全性。

参考文献