内积加密（线性泛函加密）：引子

本篇博文是一系列关于内积加密的科普文章的首篇。该系列文章的前半部分旨在总结和科普 Agrawal、Libert、Stehlé 在 2016 年提出 [ALS16]，Wee 在 2017 年改进 [Wee17]，Agrawal、Libert、Monosij、Titiu 在 2020 年完善 [ALMT20] 的内积加密算法。在这一篇里我们讨论内积加密、完美保密性和完美模拟安全性的定义，并初步讨论这两种安全性之间的关系。

本来我打算在我最近一篇论文发布之后再发这篇博文的，不过今天我发现本篇的内容完全载于已有文献中，所以不用憋着了。另外这篇也顺便充当生日庆祝文🎂

2019 年 12 月 23 日更新 我发现之前我认为 Abdalla、Catalano、Fiore、Gay、Ursu 在 2018 年 [ACF⁺18] 完善了该内积加密算法（我以为他们证明了适应性完美模拟安全性）是误解，因此暂时重新把功劳归为我导师和我（即将发布的论文）。这篇博文已经抢发了，所以就这样搁着吧。

2020 年 2 月 19 日更新 今天 ePrint 上出来了 [ALMT20]，他们已经证明了内积加密的模拟安全性，所以把功劳归于他们。

内积加密

密码学 (cryptography) 在信息化的世界中不可或缺，它是保障数据安全的重要手段之一。自从 Shannon 对一次一密 (one-time pad) 与完美保密性 (perfect secrecy) 的研究 [Sha49] 以来，现代密码学已经有了长足的发展，公钥加密 (public-key encryption) 对很多人已经是耳熟能详的概念。

在云与大数据的时代，人们希望利用服务提供商的计算能力，同时也要保障自己数据的隐私。现代密码学有（或者至少定义了）一系列工具用于各种有意思的场景，例如零知识证明 (zero-knowledge proof)、多方安全计算 (multi-party computation)、全同态加密 (fully homomorphic encryption)、基于属性的加密 (attribute-based encryption)、泛函加密 (functional encryption)、程序混淆 (program obfuscation)……这里我们讨论比较简单而又不那么简单的线性泛函加密 (inner-product functional encryption)，也叫内积加密 (IPFE)。（“线性泛函”是“行向量”的“大学生说法”，只是名字唬烂，概念很简单。）

内积加密是一种特殊的泛函加密，在这样一个加密体制里，密文和密钥都和向量相关联，而用密钥解密密文会得到两个向量的内积，而无其他。要研究一个密码学对象，第一步是要给出它的语法、语义的定义，第二步是给出安全性的定义，接下来便是研究各种安全性之间的关系（如果有多个安全性的定义），满足特定安全性的方案可以如何实现，以及这样一个方案有什么用等等。

在本文里，我们考虑最简单的“一次性”私钥 IPFE。我们主要感兴趣的是 ${\mathbb{Z}}_p$ 上向量的内积加密，其中 $p$ 是一个质数。两个 $n$ 维向量 $\mathbf{u},\mathbf{v}\in {\mathbb{Z}}_p^n$ 的内积定义为 $$⟨\mathbf{u},\mathbf{v}⟩={\mathbf{u}}^{{}_{\text{T}}}\mathbf{v}=\sum _{i=1}^n\mathbf{u}[i]\mathbf{v}[i].$$ 严格来说，这不是（欧几里得意义下的）内积，而是线性空间与对偶空间（通过对偶基同构于自身）之间自然的双线性形式——这也是为什么我管这个加密叫做线性泛函加密的原因。

先来定义内积加密的语法，一个内积加密包括四个高效随机¹算法：

• 初始化算法 $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(p,1^n)$ 输入²质数 $p$（的二进制表示）和向量的维数 $n$（的一进制表示），输出主密钥 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{s}\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}})$ 应该能够计算 uT​v。

接下来是语义，也就是所谓的正确性。内积加密方案正确，意思是说对（任意安全参数 $\lambda$ 和）任意质数 p、维数 $n$ 以及任意 $\mathbf{u},\mathbf{v}\in {\mathbb{Z}}_p^n$ 都有 $$\mathrm{Pr}\left[\begin{array}{rl}\mathsf{m}\mathsf{s}\mathsf{k}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(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{s}\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.$$

完美保密性

朴素来说，加密算法应该保证没有密钥的人看到密文后不知道明文是什么。这里有几个问题：

• 如何刻画不知道的含义？尤其是，如果攻击者已经知道一部分关于明文的信息时如何刻画？
• 若攻击者已知 ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_Q$ 的密钥，那它当然可以计算明文向量和这些向量的内积，因此不可能保护这部分关于明文向量的信息。如何刻画“其他信息都被保护”？

常见的安全性定义对攻击者 (attacker) 的能力估计都非常保守，通常最大化攻击者可以知道的关于明文的信息，但仍有 1 bit 的关于明文的信息未知，然后刻画“攻击者无法知道这额外 1 bit 的知识”。这里最简单的刻画是完美保密性。

现在换用密码学里更常见的术语³：使坏者 (adversary) $\mathcal{A}$ 和挑战者 (challenger) C。考虑两个实验 Expb​，示意图如下：

挑战者 $\mathcal{C}$

${}_{\mathsf{m}\mathsf{s}\mathsf{k}\stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(p,1^n)}$

$\begin{array}{r}\stackrel{p,1^n}{\leftarrow }\end{array}$

${}^{{\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)}$

$\begin{array}{r}\stackrel{{\mathbf{v}}_q}{\leftarrow }\\ \stackrel{{\mathsf{s}\mathsf{k}}_q}{\to }\end{array}\circlearrowleft$

${}^{\mathsf{c}\mathsf{t}\stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},{\mathbf{u}}_b)}$

$\begin{array}{r}\stackrel{{\mathbf{u}}_0,{\mathbf{u}}_1}{\leftarrow }\\ \stackrel{\mathsf{c}\mathsf{t}}{\to }\end{array}$

${}^{{\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)}$

$\begin{array}{r}\stackrel{{\mathbf{v}}_q}{\leftarrow }\\ \stackrel{{\mathsf{s}\mathsf{k}}_q}{\to }\end{array}\circlearrowleft$

使坏者 $\mathcal{A}$

$\downarrow {}^{\text{（对 }b\text{ 的猜测）}}{b}^{\prime }$

严格来说，实验分成 5 个阶段：

• 初始化：使坏者 $\mathcal{A}$ 发送 p,1n，挑战者 $\mathcal{C}$ 运行 $\mathsf{m}\mathsf{s}\mathsf{k}\stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(p,1^n)$ 并自己记下 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}(\mathsf{m}\mathsf{s}\mathsf{k},{\mathbf{u}}_b)$ 并把 $\mathsf{c}\mathsf{t}$ 发送给 A。
• 询问 II：同询问 I。
• 猜测：使坏者输出 b′∈{0,1}。

我们要求使坏者查询过密钥的所有向量 ${\mathbf{v}}_q$ 都满足 u0T​​vq​=u1T​​vq​。用 ${\mathsf{E}\mathsf{x}\mathsf{p}}_b^{\mathcal{A}}$ 表示让 $\mathcal{A}$ 参与实验 ${\mathsf{E}\mathsf{x}\mathsf{p}}_b$ 的输出结果，这是一个随机变量（随机性来源于 IPFE 算法的随机性和使坏者本身的随机性）。称这个 IPFE 方案完美保密，若对任意 $\mathcal{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]=0.$$ 这也记作 Exp0​≡Exp1​。此外，上述等式左边的量叫做 $\mathcal{A}$ 区分 ${\mathsf{E}\mathsf{x}\mathsf{p}}_0,{\mathsf{E}\mathsf{x}\mathsf{p}}_1$ 的优势 (advantage)。

如何理解这个定义？可以把 $\mathcal{A}$ 输出 1 的概率当成 $\mathcal{A}$ 这个算法行为的度量，那么这个定义就是在说任何算法在这两个实验里的行为都一样（即这两个实验从外部观察具有同一性 [are identical]）。另一种理解是，$\mathcal{A}$ 的输出是对 $b$ 的猜测，考虑如下博弈：

• 初始化、询问 I 和上述实验相同。
• 在 挑战 之时，挑战者随机选择 b←$​{0,1}，生成 ${\mathbf{u}}_b$ 的密文并发送给使坏者。
• 询问 II、猜测和上述实验相同。使坏者获胜当且仅当 b=b′，即使坏者猜对了。

在这样的观点下显然必须要求任何请求的密钥都不能（通过内积）区分两个明文向量，否则使坏者可以以 1 的概率获胜。注意到挑战者抽取到 $b$ 时，使坏者参与实验 Expb​，故使坏者的获胜概率和它的区分优势之间的关系是 $$\begin{array}{rl}\mathrm{Pr}[b^{\prime }=b]& =\mathrm{Pr}[b=0]\mathrm{Pr}[b^{\prime }=0|b=0]+\mathrm{Pr}[b=1]\mathrm{Pr}[b^{\prime }=1|b=1]\\ & =\frac{1}{2}(1-\mathrm{Pr}[{\mathsf{E}\mathsf{x}\mathsf{p}}_0^{\mathcal{A}}=1])+\frac{1}{2}\mathrm{Pr}[{\mathsf{E}\mathsf{x}\mathsf{p}}_1^{\mathcal{A}}=1]\\ & =\frac{1}{2}-\frac{1}{2}(\mathrm{Pr}[{\mathsf{E}\mathsf{x}\mathsf{p}}_0^{\mathcal{A}}=1]-\mathrm{Pr}[{\mathsf{E}\mathsf{x}\mathsf{p}}_1^{\mathcal{A}}=1]).\end{array}$$ 这说明对于完美保密的 IPFE，使坏者即使已经知道密文一定来自某两个明文，且这两个明文各有先验一半的概率出现，甚至它还获得了一些密钥，只要这些密钥不能通过内积区分明文，那么使坏者的任何猜测都是瞎猜（瞎猜猜对的概率永远是 21​）。

${\mathsf{E}\mathsf{x}\mathsf{p}}_0,{\mathsf{E}\mathsf{x}\mathsf{p}}_1$ 惟一的不同之处在于挑战密文里加密的明文向量不同，使坏者在这两组实验里几乎掌握了密文里蕴含的明文的所有信息，除了 1 bit 不知道——明文是它选择的两个向量中的哪一个。这个定义就是刻画：使坏者在这样“予坏人方便”的条件下仍然使不出坏。

那么再次总结：假设使坏者已经有一些关于明文的信息（通过它可以选择 ${\mathbf{u}}_0,{\mathbf{u}}_1$ 刻画），即使再获得一些其他信息（通过它可以查询密钥刻画），只要新的信息不能通过该方案设计的功能（也就是计算内积）推断出关于明文的新信息，就确实无法推断任何关于明文的新信息。

我们这里没有尝试保护密钥里的向量，保护密钥里的向量的定义（和方法）留到以后的博文再分解，感兴趣的读者可以阅读 [LV16, Lin17]。

完美模拟安全性

另一种常见的安全性定义方法是利用模拟范式 (simulation paradigm)⁴。在这个范式里，我们想象一个使坏者偷窥正常用户产生的密文和密钥，并尝试从中计算一些信息。显然，根据 IPFE 的功能，获取了 ${\mathbf{v}}_q,{\mathbf{u}}^{\ast }$ 的密钥和密文后，使坏者可以计算 vq​,(u∗)T​vq​，这是无法避免的信息泄露。现在希望用一个定义刻画“只有这些信息泄露了”，这句话的形式化版本就是：任何可以通过观察密钥和密文计算出信息，都可以通过只观察内积计算出。

然而，一个观察密文和密钥的使坏者，如果对其输入内积，它很明显就会察觉到异样——输入格式都变了。为了消除密钥密文和内积结果之间的鸿沟，模拟范式引入了模拟器 (simulator) 的概念。简单来说，模拟器的目的是完成使坏者进行的计算，但是它的输入是内积而不是密钥和密文。

一个无聊的结论是：完美保密的 IPFE 永远有模拟器，只是它不一定高效。

为了让事情有意思一点，可以加强要求，令模拟器必须高效，但这个定义对于本身就不高效的使坏者来说没有道理。一种解决方案是：要求模拟器只能以预言机使用 (have oracle access to) 使坏者来完成计算（它不知道使坏者的代码），并且它是多项式时间带预言的图灵机 (oracle Turing machine)，但是这个定义太复杂了，不太适合大众。

这里采用一个更强的定义，用一种特别的黑盒模拟：模拟器和真实算法具有类似的接口！模拟器可以生成模拟密钥和模拟密文，而且只需要用能够计算的内积就可以完成模拟。一旦有这样一个模拟器（再加上合适的定义使得这个模拟器能够代表真实算法），那么对于任何观察密钥和密文的使坏者，可以给它看模拟密钥和模拟密文（而不是真实密钥和真实密文），它也会产生一个输出，可以证明这个输出将会和真实输出是一致的。

一个模拟器是指四个高效随机算法 Setup∗,KeyGen1∗​,Enc∗,KeyGen2∗​：

• ${\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}}^{\ast }(p,1^n)$ 输入参数，输出模拟器的初始状态 σ。
• ${\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}}_1^{\ast }(\sigma ,{\mathbf{v}}_q)$ 输入模拟器当前状态和一个向量，输出一个模拟密钥 ${\mathsf{s}\mathsf{k}}_q$ 和一个新状态 σ′。
• ${\mathsf{E}\mathsf{n}\mathsf{c}}^{\ast }(\sigma ,z_1,\dots ,z_{Q_1})$ 输入模拟器当前状态以及若干个内积，输出一个模拟密文 $\mathsf{c}\mathsf{t}$ 和一个新状态 σ′。注意：模拟密文的时候，模拟器的输入不包括明文向量 u。
• ${\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}}_2^{\ast }(\sigma ,{\mathbf{v}}_q,z_q)$ 输入模拟器当前状态、一个向量、一个内积，输出一个模拟密钥 ${\mathsf{s}\mathsf{k}}_q$ 和一个新状态 σ′。

模拟器当然最好是完美的，考虑一个使坏者 A，它可能参与两个实验——“真实实验 Expreal​”和“模拟实验 Expsim​”——之一，表示为下图（“世界”和“实验”在这里是同义词）：

真实
世界

${}_{\mathsf{m}\mathsf{s}\mathsf{k}\stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(p,1^n)}$

$\begin{array}{r}\stackrel{p,1^n}{\leftarrow }\end{array}$

${}^{{\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)}$

$\begin{array}{r}\stackrel{{\mathbf{v}}_q}{\leftarrow }\\ \stackrel{{\mathsf{s}\mathsf{k}}_q}{\to }\end{array}\circlearrowleft$

${}_{\mathsf{c}\mathsf{t}\stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},{\mathbf{u}}^{\ast })}$

$\begin{array}{r}\stackrel{{\mathbf{u}}^{\ast }}{\leftarrow }\\ \stackrel{\mathsf{c}\mathsf{t}}{\to }\end{array}$

${}^{{\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)}$

$\begin{array}{r}\stackrel{{\mathbf{v}}_q}{\leftarrow }\\ \stackrel{{\mathsf{s}\mathsf{k}}_q}{\to }\end{array}\circlearrowleft$

$\mathcal{A}$

$\begin{array}{l}\stackrel{p,1^n}{\to }\end{array}$

${}_{\sigma \stackrel{{}_{\$}}{\leftarrow }{\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}}^{\ast }(p,1^n)}$

$\circlearrowleft \begin{array}{l}\stackrel{{\mathbf{v}}_q}{\to }\\ \stackrel{{\mathsf{s}\mathsf{k}}_q}{\leftarrow }\end{array}$

${}^{({\mathsf{s}\mathsf{k}}_q,\sigma )\stackrel{{}_{\$}}{\leftarrow }{\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}}_1^{\ast }(\sigma ,{\mathbf{v}}_q)}$

$\begin{array}{l}\stackrel{{\mathbf{u}}^{\ast }}{\to }\\ \stackrel{\mathsf{c}\mathsf{t}}{\leftarrow }\end{array}$

${}^{\begin{array}{l}\\ \\ (\mathsf{c}\mathsf{t},\sigma )\stackrel{{}_{\$}}{\leftarrow }{\mathsf{E}\mathsf{n}\mathsf{c}}^{\ast }(\sigma ,\\ \{({\mathbf{u}}^{\ast }{)}^{{}_{\text{T}}}{\mathbf{v}}_q{\}}_{q\le Q_1})\end{array}}$

$\circlearrowleft \begin{array}{l}\stackrel{{\mathbf{v}}_q}{\to }\\ \stackrel{{\mathsf{s}\mathsf{k}}_q}{\leftarrow }\end{array}$

${}^{({\mathsf{s}\mathsf{k}}_q,\sigma )\stackrel{{}_{\$}}{\leftarrow }{\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}}_2^{\ast }(\sigma ,{\mathbf{v}}_q,({\mathbf{u}}^{\ast }{)}^{{}_{\text{T}}}{\mathbf{v}}_q)}$

模拟
世界

$\downarrow b^{\prime \text{（在哪个世界？）}}$

上图应该清楚说明了为什么刚才的定义里 $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}$ 的模拟算法拆成了两个。实验过程是这样的：

• 初始化：使坏者选择参数，我们用这些参数初始化真实算法或者模拟算法。
• 询问 I：使坏者查询若干个 ${\mathbf{v}}_q$ 的密钥，我们要么生成真实密钥，要么生成模拟密钥。无论是真实算法还是模拟器，都会得到 ${\mathbf{v}}_q$ 作为输入。假设这一阶段查询了 $Q_1$ 个密钥。
• 挑战：使坏者选择一个向量 u∗，我们要么用真实算法加密 u∗，要么用模拟器以及 $({\mathbf{u}}^{\ast }{)}^{{}_{\text{T}}}{\mathbf{v}}_q$（其中 q=1,…,Q1​）生成模拟密文。注意，这里模拟器的输入不包括 u∗。
• 询问 II：类似询问 I，但在模拟世界中，模拟器额外得到 $({\mathbf{u}}^{\ast }{)}^{{}_{\text{T}}}{\mathbf{v}}_q$ 作为输入。这里给模拟器输入这个值的原因是，它是真实世界里在查询发生后可以计算的内积；另一方面，如果模拟器不知道这个信息，它是不可能模拟出正确的结果的。
• 猜测：使坏者输出 b′∈{0,1}。可以理解为它猜测自己在哪个世界里，或者对使坏者（观察者）在不同世界里行为的度量。

再次强调：任何时刻提供给模拟器的信息都是内积加密在设计上 (by design) 应该能计算的信息，而模拟器的工作就是仅使用这些信息产生密钥和密文。这个模拟器完美，如果对任意 $\mathcal{A}$（可以有无限计算能力）都有 $$\mathrm{Pr}[{\mathsf{E}\mathsf{x}\mathsf{p}}_{\text{real}}^{\mathcal{A}}=1]-\mathrm{Pr}[{\mathsf{E}\mathsf{x}\mathsf{p}}_{\text{sim}}^{\mathcal{A}}=1]=0,$$ 换言之，Expreal​≡Expsim​。这个定义就是在说真实实验和模拟实验（从外部观察）没有差别。

另一种理解模拟范式的方法是 缸中之脑 的比喻：可以给使坏者（脑）营造一个它无法发现和真实世界区别的环境（缸）；使坏者（脑）本来观察（“接”）的是真实世界（真实算法的输出），在模拟世界（缸）里面它“接”的管子通到模拟算法上。

用模拟范式定义安全性可以直观地刻画最终达到的效果，它基于两步论证：

• 真实世界和模拟世界没有差别，所以真实世界里密文和密钥泄露的信息就是模拟世界里泄露的信息；
• 模拟世界里能够泄露的信息最多就是模拟器用到的信息。

这里模拟器用到的就是 IPFE 所有允许计算的信息，这就刻画了密文和密钥不包含密文里的向量、明文向量与密文里的向量的内积之外的任何信息这一命题。此外，该模拟器是适应性 (adaptive) 的，它可以回答使坏者适应性提出的任何问题，并保持模拟的完美性，这说明信息的泄露也是适应性的——在任何阶段泄露的信息就是到那个阶段为止所有被允许算出的信息。

过渡证明法

之前已经说过，任何完美保密的 IPFE 都具有一个（不一定高效的）模拟器。现在自然要问：如果一个 IPFE 具有上述定义里完美的模拟器，它是否也是完美保密的？

答案是肯定，用密码学中的常见套路过渡证明法 (hybrid argument) 即可：要证明两种回答使坏者问题的方式是等价的，只要每次修改一点回答方式，保证每次修改都和前一次等价，直到从第一种修改到第二种即可。这其实就是概率等式的传递性；更一般的情况是三角不等式，不过那是后话了。

现在想证明 Exp0​≡Exp1​，考虑下面两个过渡实验 (hybrid experiments)：

• 在 ${\mathsf{H}}_b$ 中，使用模拟器和 ${\mathbf{v}}_q,{\mathbf{u}}_b^{{}_{\text{T}}}{\mathbf{v}}_q$ 生成模拟密钥和密文来回应使坏者的查询和挑战。

在 ${\mathsf{E}\mathsf{x}\mathsf{p}}_0$ 中，使坏者收到的是 ${\mathbf{v}}_q,{\mathbf{u}}_0$ 的真实密钥、密文，根据模拟安全性 (simulation security)，用 ${\mathbf{v}}_q,{\mathbf{u}}_0^{{}_{\text{T}}}{\mathbf{v}}_q$ 生成模拟密钥、密文是等价的，这恰好是 ${\mathsf{H}}_0$ 里的做法，因此 Exp0​≡H0​；同理，H1​≡Exp1​。

最后，因为使坏者的挑战和查询满足 u0T​​vq​=u1T​​vq​，所以 ${\mathsf{H}}_0\equiv {\mathsf{H}}_1$——它们是用同一个模拟器和同一组密钥里的向量和内积生成的应答。于是得到 Exp0​≡Exp1​。

本篇结语

这一篇定义了内积加密的语法、语义，并定义了两种安全性——完美保密性和模拟安全性。前者刻画了“密钥和密文无法用于推断明文中除了内积之外的任何新信息”，后者刻画了“密钥和密文中关于明文的信息只有内积”。此外，模拟安全性蕴含着完美保密性。

下一篇 会讲如何构造一个模拟安全的内积加密。

参考文献