内积加密：公钥 IPFE 与 CPA 安全性

“内积加密”系列文章的前半部分旨在总结和科普 Agrawal、Libert、Stehlé 在 2016 年提出 [ALS16]，Wee 在 2017 年改进 [Wee17]，Agrawal、Libert、Monosij、Titiu 在 2020 年完善 [ALMT20] 的内积加密算法。在这一篇里我们讨论公钥 IPFE 的语法、语义、安全性，为此我们需要引入计算意义下的不可区分性，并练习多项式时间归约和过渡证明法。题图来自 [PS10]。

前情提要

在 第一篇 里，我们定义了一次性私钥内积加密的语法、语义、安全性，在 前一篇 里，我们用一次一密构造了完美模拟安全的一次性私钥内积加密。

虽然完美，但一次性安全性令人不太满意，我们希望多次加密的情况下也有安全保障。此外，我们还希望任何人都能加密，但只有获得私钥的人才能解密——注意，这和普通的公钥加密还不太一样，因为即使获得了私钥，也不能完全解密出明文，而是只能知道明文向量和密钥向量的内积。这一篇定义公钥 IPFE，并通过不可区分性来刻画其安全性。

计算意义下的不可区分性

Shannon 证明了 [Sha49] 任何明文长度超过密钥长度的私钥加密都 不可能 具有完美安全性。考虑一个私钥内积加密，如果不允许使坏者查询任何密钥，则它的安全性定义就退化为私钥加密的安全性。如果允许使坏者查询多个明文的密文，而且要么总是加密第一个明文，要么总是加密第二个明文，则很容易发现私钥长度 固定 的内积加密不可能完美安全。

一个绕过这个不可能性的方式是允许密钥动态变化，但是有状态 (stateful)加密系统比普通的加密系统更难正确实现，通常大家希望加密、密钥生成都不需要改变密钥本身。另一个绕过这个不可能性的方式是不追求完美安全，而是要求任何实际 (practical)的攻击手段都无效 (ineffective)。如果你熟悉一点点计算机科学，马上就能意识到这里“实际”的意思就是“多项式时间”，而“无效”的意思则不是这么直截了当——它是指“效果比任何多项式的倒数都小”。

这个概念在密码学中是使用计算意义下的不可区分性 (computational indistinguishability)来刻画的。考虑两个实验¹ Exp0​,Exp1​，它们俩在计算意义下不可区分（简称“不可区分”）是说，对于任何高效²使坏者 A，其优势可忽略： $$\mathrm{Pr}[{\mathsf{E}\mathsf{x}\mathsf{p}}_0^{\mathcal{A}}=1]-\mathrm{Pr}[{\mathsf{E}\mathsf{x}\mathsf{p}}_1^{\mathcal{A}}=1]=\mathcal{O}({\lambda }^{-k})$$ 对任意 $k\in \mathbb{N}$ 成立，其中 $\lambda$ 是 安全参数。³这个性质记作 Exp0​≈Exp1​。提醒一下，第一篇里定义的完美不可区分性记作 ≡，那里优势必须对于任何使坏者严格为 0。还有一种不可区分性叫做统计意义下不可区分，是指优势对于任何使坏者都可忽略。

计算意义下的不可区分性相比完美不可区分性进行了两方面的弱化，一是限制了使坏者的计算资源（必须是多项式时间），二是允许使坏者具有微弱（但可忽略）的优势。套用之前对完美不可区分性的解读，计算意义下的不可区分性就是说：两个实验对任何实际上可行的算法来说都几乎没有区别。

这些概念可以“退化”到分布上，考虑一个分布⁴ D，则可如下定义实验 Exp：

1. 抽取 x←$​D。
2. 运行 $\mathcal{A}$ 并向它发送 x。
3. 从使坏者接收一位输出，把它作为实验结果。

如果两个分布⁴ $D_0,D_1$ 对应的实验具有某种不可区分性，则说这两个分布具有那种不可区分性，也用相同的记号表达。

最后，显然完美不可区分蕴含着统计意义下不可区分，后者又蕴含着计算意义下不可区分。

公钥 IPFE

先考虑语法，一个 公钥内积加密 (IPFE) 具有 4 个高效随机算法：

• 初始化算法 $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^n)$ 输入向量的维数 $n$（的一进制表示），输出主公私密钥对 (mpk,msk)。
• 密钥生成算法 $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},\mathbf{v})$ 用来产生任何一个向量 $\mathbf{v}$ 的密钥 skv​。
• 加密算法 $\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{p}\mathsf{k},\mathbf{u})$ 用来加密任何一个向量 $\mathbf{u}$ 得到密文 ctu​。
• 解密算法 $\mathsf{D}\mathsf{e}\mathsf{c}({\mathsf{s}\mathsf{k}}_{\mathbf{v}},{\mathsf{c}\mathsf{t}}_{\mathbf{u}})$ 应该能够计算 uTv。

语义也很容易定义，公钥 IPFE 方案正确，意思是说对任意维数 $n$ 以及任意 $\mathbf{u},\mathbf{v}\in {\mathbb{Z}}_p^n$ 都有 $$\mathrm{Pr}\left[\begin{array}{rl}(\mathsf{m}\mathsf{p}\mathsf{k},\mathsf{m}\mathsf{s}\mathsf{k})& \stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^n)\\ \mathsf{s}\mathsf{k}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},\mathbf{v})\\ \mathsf{c}\mathsf{t}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{p}\mathsf{k},\mathbf{u})\end{array}:\mathsf{D}\mathsf{e}\mathsf{c}(\mathsf{s}\mathsf{k},\mathsf{c}\mathsf{t})={\mathbf{u}}^{\text{T}}\mathbf{v}\right]=1.$$

注意 这个定义和第一篇里 私钥 IPFE 的定义有许多不同之处：

• 初始化算法不再输入质数 p。这个系列里要构造的方案中的 $p$ 是根据安全参数变化的，甚至可能是随机的；不过我们可以忽略该问题，可以认为 $p$ 是一个安全参数那么长的固定质数。
• 初始化算法输出一对密钥，包括主公钥 $\mathsf{m}\mathsf{p}\mathsf{k}$ 和主私钥 msk。通常来说，$\mathsf{m}\mathsf{p}\mathsf{k}$ 是全世界都可以知道的，而 $\mathsf{m}\mathsf{s}\mathsf{k}$ 则由权威机构（运行初始化算法的人）保管。
• 加密算法使用主公钥 mpk，这表示全世界的人都可以加密向量（之前只有权威机构才能加密）。不过仍然是只有持有 $\mathsf{m}\mathsf{s}\mathsf{k}$ 的人（权威机构）才能生成密钥，我们希望的安全性自然是：只有持有对应密钥的人才能计算对应的内积。

接下来定义安全性，这要用到计算意义下的不可区分性。

IND-CPA 安全性

IND-CPA 全称选择明文攻击下的不可区分性 (INDistinguishability under Chosen Plaintext Attack)。即将给出的定义是⁵ 完美保密性 的弱化版本——攻击者只能采用高效的策略，且允许攻击者具有微弱的优势。和完美保密性一样，这里也考虑两个实验 Expb​：

• 初始化：使坏者 $\mathcal{A}$ 发送 1n，挑战者 $\mathcal{C}$ 运行 (mpk,msk)←$​Setup(p,1n)，把 $\mathsf{m}\mathsf{p}\mathsf{k}$ 发送给 $\mathcal{A}$ 并自己记下 msk。
• 询问 I：这个阶段可以进行任意多轮，第 $q$ 轮使坏者 $\mathcal{A}$ 发送一个向量 vq​，挑战者 $\mathcal{C}$ 运行 ${\mathsf{s}\mathsf{k}}_q\stackrel{{}_{\$}}{\leftarrow }\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},{\mathbf{v}}_q)$ 并发送 ${\mathsf{s}\mathsf{k}}_q$ 给 A。
• 挑战：使坏者选择两个向量 u0​,u1​，挑战者运行 $\mathsf{c}\mathsf{t}\stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\boxed{\mathsf{m}\mathsf{p}\mathsf{k}},{\mathbf{u}}_b)$ 并把 $\mathsf{c}\mathsf{t}$ 发送给 A。
• 询问 II：同询问 I。
• 猜测：使坏者输出 b′∈{0,1}。

公钥 IPFE 具有 IND-CPA 安全性 就是说 Exp0​≈Exp1​。

注意这个定义有三点明显的不同之处：

• 使坏者会获得 mpk，这是在刻画公钥的公开性。
• 加密的时候用 mpk，这是因为 IPFE 的语法本身也变更了。
• 不要求完美不可区分，只要求计算意义下不可区分——高效使坏者只有微弱的优势。

现在证明对实验的不可区分性的弱化是 必要的：对于 完美正确 的公钥 IPFE 来说，它具有 完美不安全性⁶——如果允许使坏者具有无限的计算能力，则使坏者总是可以从密文中完美还原明文向量。这样操作：使坏者枚举 $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}$ 所有可能使用的随机数并运行之，直到找到了一个随机数使主公钥等于它看见的 mpk，此时它也知道了一个可能的主私钥 msk，此后它可以自己运行密钥生成算法生成标准基的密钥 skei​​，再运行解密算法即可知道密文里的向量的每个分量；由于算法的完美正确性，此时解密出来的结果必然是正确结果。

虽然完美正确的公钥 IPFE 总是完美不安全，但是上述暴力攻击的代价非常大，正确设置参数后，可能宇宙毁灭一万次也无法完成。计算意义下的安全性既使对安全性的讨论变得有意义又能够捕捉现实世界的安全要求。稍后我们会看到，在普遍相信的困难性假设下，存在着 IND-CPA 安全的公钥 IPFE。

此外，初学者经常提出的一个问题是：

既然使坏者自己有 mpk，为什么使坏者不能自己加密 ${\mathbf{u}}_0,{\mathbf{u}}_1$ 并根据收到的挑战密文是哪一个做出判断呢？

这个问题非常好，原因是 $\mathsf{E}\mathsf{n}\mathsf{c}$ 是随机算法，而使坏者不知道生成挑战密文时 $\mathsf{E}\mathsf{n}\mathsf{c}$ 使用的随机数。实际上，对任何 IND-CPA 的公钥 IPFE，每个明文的可能的密文都必须非常非常多——超过任何多项式——这样才能保证使坏者不能通过枚举可能密文的方式来攻破系统。

SIM-CPA 安全性

SIM-CPA 全称选择明文攻击下的模拟安全性 (SIMulation security under Chosen Plaintext Attack)，它是之前定义的 完美模拟安全性 的弱化版本。

为了不让这一篇过于冗长，我直接指出定义里需要修改的部分：

• 模拟器的初始化算法 ${\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}}^{\ast }$ 输入向量维数，输出内部状态和 模拟主公钥 mpk∗。其他部分的语法（接口）不变。
• 在真实、模拟实验中，$\mathcal{A}$ 在选择向量维数后会获得真实或模拟主公钥。
• 在真实、模拟实验中的询问、猜测环节都不变。挑战环节里使坏者要么收到真实密文（用 $\mathsf{m}\mathsf{p}\mathsf{k}$ 加密），要么收到模拟密文（由模拟器仅用可以计算的内积产生）。
• 我们只要求 Expreal​≈Expsim​。

利用过渡证明法 (hybrid argument) 容易知道 SIM-CPA 蕴含着 IND-CPA，因为 IND-CPA 里的两个实验分别与用 ${\mathbf{u}}_0,{\mathbf{u}}_1$ 和模拟器模拟回复的实验计算意义下不可区分，而两个模拟的实验完美不可区分。

单次安全蕴含着多次安全

现在来说 IND-CPA 脚注 5 里提到的问题。IND-CPA 的定义里如何体现了“选择明文攻击”呢？实际上，真正的 IND-CPA 的定义里，在询问 I/II 中使坏者每轮有两个选项：

• 一是和我们给出的定义一样，可以查询密钥。
• 二是它可以提供一个 u，然后挑战者运行 $\mathsf{c}\mathsf{t}\stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{p}\mathsf{k},\mathbf{u})$ 并把 $\mathsf{c}\mathsf{t}$ 发送给 A。

第二个选项刻画了使坏者可以看到很多明文的密文且每个明文都由使坏者自由选择的攻击模型（“选择明文攻击”），除了这些使坏者选择明文的密文，它还截获了一个密文（挑战密文），而且还知道它是某两个明文中的一个的密文，而 IND-CPA 就是刻画使坏者仍然无法知道截获的密文中的明文是哪个。不过，对于公钥 IPFE，第二个选项是多此一举，因为使坏者自己知道 mpk,u，完全可以自己完成这个加密——注意这个论证不会扩展到挑战密文，因为使坏者一开始 (a priori)不知道要加密的是挑战里的两个明文的哪一个。

以上单次挑战版本的 IND-CPA，还有多次挑战版本，那里就不区分询问和挑战环节了，询问 I、挑战、询问 II 合并成一个大的挑战环节，使坏者可以进行任意多轮挑战，每轮有两个选项：

• 一是提供 ${\mathbf{v}}_j$ 并获得 skj​←$​KeyGen(msk,vj​)。
• 二是提供 ${\mathbf{u}}_{i0},{\mathbf{u}}_{i1}$ 并获得 cti​←$​Enc(mpk,uib​)，其中 $b$ 表示处于哪一个实验。

猜测环节的要求变成：每组挑战过的向量都不能用任何查询过的密钥区分，即 $${\mathbf{u}}_{i0}^{\text{T}}{\mathbf{v}}_j={\mathbf{u}}_{i1}^{\text{T}}{\mathbf{v}}_j\forall i,j.$$ 很重要的一点是在 ${\mathsf{E}\mathsf{x}\mathsf{p}}_0$ 中，$\mathcal{A}$ 收到的密文总是两个向量中第一个的密文，在 ${\mathsf{E}\mathsf{x}\mathsf{p}}_1$ 中，$\mathcal{A}$ 收到的密文总是第二个的密文。很自然的想法是：有没有可能，使坏者只看到一组挑战密文的时候可能区分不出来，但是看到更多挑战密文的时候就可以区分了？

对也不对。对：可以证明单次挑战的 IND-CPA 蕴含着多次挑战的 IND-CPA，而我们之前定义的 IND-CPA 对于公钥 IPFE 等同于单次挑战的 IND-CPA，故我们定义的 IND-CPA、真正的单次挑战 IND-CPA、多次挑战 IND-CPA 三者是等价的。不对：这个证明会“大幅”（多项式倍，而不是常数倍）改变优势。证明方法是过渡证明法，下面演示一下下怎么用（一致）归约 [(uniform) reduction]的语言来做这个证明。

证明 假设高效的使坏者 $\mathcal{A}$ 最多进行 $Q$ 个明文挑战，$Q$ 是一个多项式。构造使坏者 B：

1. 抽取 q←$​{1,…,Q}。
2. 运行 $\mathcal{A}$ 并收到它选择的维数 1n，$\mathcal{B}$ 也选择 $1^n$ 作为维数，并从挑战者 $\mathcal{C}$ 获取 mpk，然后把 $\mathsf{m}\mathsf{p}\mathsf{k}$ 发给 A。
3. 自己和 $\mathcal{A}$ 都进入挑战环节，根据 $\mathcal{A}$ 的行动来行动：
   • 如果 $\mathcal{A}$ 请求一个密钥，则把请求转发给 $\mathcal{C}$ 并把回复转发回 A。
   • 如果 $\mathcal{A}$ 进行第 $q^{\prime }$ 次密文挑战：
     • 如果 q′<q，$\mathcal{B}$ 自己运行 $\mathsf{c}\mathsf{t}\stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{p}\mathsf{k},{\mathbf{u}}_1)$ 并用 $\mathsf{c}\mathsf{t}$ 回应 A。
     • 如果 q′>q，则类似上一种情况，但用 ${\mathbf{u}}_0$ 的密文回应 A。
     • 如果 q′=q，则把挑战转发给 $\mathcal{C}$ 并把回应转发回 A。
4. 当 $\mathcal{A}$ 结束挑战环节并做出猜测后，$\mathcal{B}$ 也结束挑战环节，并用 $\mathcal{A}$ 的猜测作为自己的猜测。

显然 $\mathcal{B}$ 也是高效的，简单的计算表明 $\mathcal{B}$ 的优势是 $\mathcal{A}$ 的优势的 Q1​。如果该 IPFE 满足我们定义的 IND-CPA，则 $\mathcal{B}$ 的优势可忽略，而 $\mathcal{A}$ 的优势只是 $\mathcal{B}$ 的 $Q$（多项式）倍，故也是³可忽略的，这就说明该 IPFE 也满足多次挑战的 IND-CPA 安全性。

解读 1 定义 ${\mathsf{H}}_q$ 为这样一个过渡实验，它是多次挑战 IND-CPA 类型的实验，但是它在回应挑战的时候，前 $q$ 次回应第二个明文的密文，之后回应第一个明文的密文。显然，$\mathcal{A}$ 在进行多次挑战 IND-CPA 的时候等同于在区分 H0​,HQ​。

为了考虑 $\mathcal{A}$ 区分 ${\mathsf{H}}_0,{\mathsf{H}}_Q$ 的优势，我们可以把它拆成区分 ${\mathsf{H}}_0,{\mathsf{H}}_1$ 的优势、${\mathsf{H}}_1,{\mathsf{H}}_2$ 的优势、…、${\mathsf{H}}_{Q-1},{\mathsf{H}}_Q$ 的优势之和。现在 $\mathcal{B}$ 的做法就是随机选择一组相邻的过渡实验，让 $\mathcal{A}$ 区分，为此它只需要借助一次挑战即可——毕竟相邻的实验里其他的挑战都是可以自己回应的——这就对应于 $\mathcal{B}$ 自己是在进行我们定义的 IND-CPA 的实验。假设 $\mathcal{B}$ 一开始抽取的数是 q：

• 如果 $\mathcal{B}$ 处于 ${\mathsf{E}\mathsf{x}\mathsf{p}}_0$ 里，则它运行的 $\mathcal{A}$ 处于 ${\mathsf{H}}_{q-1}$ 里。
• 如果 $\mathcal{B}$ 处于 ${\mathsf{E}\mathsf{x}\mathsf{p}}_1$ 里，则它运行的 $\mathcal{A}$ 处于 ${\mathsf{H}}_q$ 里。

这说明此时 $\mathcal{B}$ 的优势是 $\mathcal{A}$ 区分 ${\mathsf{H}}_{q-1},{\mathsf{H}}_q$ 的优势。又 $\mathcal{B}$ 随机选择 q，故总的来说它的优势是各种选择下优势的平均数，也就是这一大堆优势的和除以 $Q$——也就是 $\mathcal{A}$ 对多次挑战 IND-CPA 的优势除以 Q。

解读 2 同样考虑上述过渡实验，我们定义的 IND-CPA 保证了 ${\mathsf{H}}_q\approx {\mathsf{H}}_{q+1}$ 对所有⁷ $q$ 成立。而区分 ${\mathsf{H}}_0,{\mathsf{H}}_Q$ 的优势不过是多项式个“相邻优势”之和，故仍然⁸可忽略，即可以推出 H0​≈HQ​。即“多项式长度下不可区分性链的传递性”。

读者习题 上述定义的 SIM-CPA 可以换成多次挑战（多次模拟）吗？

本篇结语

在这一篇里我们引入了计算意义下的不可区分性，并定义了公钥 IPFE 的语法、语义、安全性。对应于私钥 IPFE，我们定义了完美安全性的对应版本（IND-CPA）和完美模拟安全性的对应版本（SIM-CPA）。不同于私钥 IPFE，公钥 IPFE 的 IND-CPA 安全性蕴含着多次安全性，这一点可以通过多项式时间归约和过渡证明法证明。

下一次 讲循环群、和 MDDH 假设。

参考文献