FHE学习笔记 #4 概率论中的前置知识

文章使用 wolai 编写并导出，在 wolai 中观看效果更好，有颜色高亮和实时更新

可忽略函数 Negligible Function

由浅入深的英文讲解 🧑🏻‍🍳：https://mathwiki.cs.ut.ee/asymptotics/06_the_negligible_the_noticeable_and_the_overwhelming

Negligible function - Wikipedia

LaTeX 英文教程：lec02.pdf (berkeley.edu)

一个函数 \(\mu: \mathbb{N} \rightarrow \mathbb{R}\)，以下几种描述等价，当且：

• 函数 \(\mu(x)\) 是可忽略函数

• \(\forall c\in \mathbb N^+,\exists N_c\in \mathbb Z,\;\text{s.t.}\;\forall x>N_c,|\mu(x)|<x^{-c}\)

• 对于所有正值多项式 \(\text{poly}(\cdot)\)，存在正整数 \(N_{\text{poly}}\)，使得：

  \[ \forall x>N_\text{poly},\;|\mu(x)|<\frac{1}{\operatorname{poly}(x)} \]

• 对于所有正值多项式 \(\text{poly}(\cdot)\)，\(\mu(n) \in \mathcal O\left(\frac1{\operatorname{poly}(n)}\right)\) 成立

通常将可忽略函数记为 \(\operatorname{negl}\)。可忽略函数的衰减速度大于任意多项式，其意义在于：

• 以可忽略的概率发生的事件，因为几乎不可能发生，所以对所有实践用途，它们可被忽略

• 若一个攻破密码事件发生的概率是可忽略的，则是不重要的，即担心发生概率足够小的事件是没有意义的

• 当应用于概率函数时，则称为 Negligible Probability

常见的可忽略函数有指数函数，如 \(2^{-n}\)。

一些引理：

• 如果 \(f_1,f_2\) 是可忽略的，那么 \(f_1+f_2\) 也是可忽略的

• 如果 \(f\) 是可忽略的，对于任意正常数 \(c\)，\(c\cdot f\) 也是可忽略的

• 如果 \(f\) 是可忽略的，对于任意实多项式 \(p\)，\(p\cdot f\) 也是可忽略的

• 如果 \(f\) 是可忽略的，对于任意正常数 \(c\)，\(f^c\) 也是可忽略的

根据可忽略函数的定义，可以继续定义所谓的 Overwhelming Function：

一个函数 \(f\) 是 Overwhelming Function，当且仅当 \(1-f\) 是可忽略函数。

Noticeable Function

由浅入深的英文讲解 🧑🏻‍🍳：https://mathwiki.cs.ut.ee/asymptotics/06_the_negligible_the_noticeable_and_the_overwhelming

LaTeX 英文教程：lec02.pdf (berkeley.edu)

Noticeable Function 定义方式和可忽略函数类似

一个函数 \(\mu: \mathbb{N} \rightarrow \mathbb{R}\)，以下几种描述等价，当且：

• 函数 \(\mu(x)\) 是 Noticeable Function

• \(\exists c\in \mathbb N,\exists N_c\in \mathbb Z,\;\text{s.t.}\;\forall x>N_c,|\mu(x)|\ge x^{-c}\)

• 存在正值多项式 \(\text{poly}(\cdot)\)，存在正整数 \(N_{\text{poly}}\)，使得：

  \[ \forall x>N_\text{poly},\;|\mu(x)|\ge\frac{1}{\operatorname{poly}(x)} \]

• 存在正值多项式 \(\text{poly}(\cdot)\)，\(\mu(n) \in \Omega\left(\frac1{\operatorname{poly}(n)}\right)\) 成立

常见的 Noticeable Function 其实大多是正值多项式，如 \(n^{-3}\)。

不是可忽略函数被称为 Non-negligible，但是并不等价于 Noticeable Function，一个经典的反例如下：

\[ \mu(n)=\left\{\begin{array}{cc}2^{-n}&, n \text { is even } \\n^{-3} &, n \text { is odd }\end{array}\right. \]

这个函数既不是可忽略的，也不是 Noticeable 的。

高斯分布 Gaussian Distribution

Normal distribution - Wikipedia

Marcolla C, Sucasas V, Manzano M, et al. Survey on Fully Homomorphic Encryption, Theory and Applications[J]. 2022.https://www.techrxiv.org/articles/preprint/Survey_on_Fully_Homomorphic_Encryption_Theory_and_Applications/19315202/2/files/34375853.pdf

高斯分布就是我们熟知的正态分布 Normal distribution，记为 \(\chi\)，一般的形式为：

\[ \forall x\in\mathbb R,\;f(x)=\frac{1}{\sigma \sqrt{2 \pi}} e^{-\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^{2}} \]

\(\mu\) 是分布的均值，$ $ 是标准差。

而在全同态加密中，该分布通常定义为 \(\mathbb Z\) 上的离散高斯分布 Discrete Gaussian Distribution，同时均值为 0，并有个宽度参数 (width parameter) \(\alpha q\)，该分布记为 \(\mathcal{D}_{\mathbb{Z}, \alpha q}\)。

\(\mathbb Z\) 上的分布 \(\mathcal{D}_{\mathbb{Z}, \alpha q}\) 为每个 \(x\in\mathbb Z\) 分配一个正比于 \(\begin{aligned}\exp \left(\frac{-\pi x^{2} }{(\alpha q)^{2}}\right)\end{aligned}\) 的权重，最终形式为：

\[ \mathcal{D}_{\mathbb{Z}, \alpha q}(x)=\frac{f(x)}{f(\mathbb{Z})} \;\text{where}\; f(\mathbb{Z})=\sum_{z \in \mathbb{Z}} \frac{1}{\alpha q} \begin{aligned}\exp \left(\frac{-\pi z^{2} }{(\alpha q)^{2}}\right)\end{aligned} \]

\(\mathcal{D}_{\mathbb{Z}, \alpha q}\) 的标准差为 \(\sigma \approx \alpha q / \sqrt{2 \pi}\)（是有条件的，但是没看懂，原文是「如果 \(\sigma\) 大于 \(\mathbb Z\) 的平滑参数 \(\eta_{\epsilon}(\mathbb{Z})\)」）

\(B\)-bounded Distribution

采样 Sample 的概念：

• 给定概率分布 \(\mathcal{D}\)，我们使用 \(x \leftarrow \mathcal{D}\) 表示按照概率分布 \(\mathcal{D}\) 取出 \(x\)

• 给定一个集合 \(\mathcal{S}\)，我们使用 \(x \leftarrow \mathcal{S}\) 表示从集合 \(\mathcal{S}\) 中均匀取出 \(x\)

因为资料比较杂，笔者还看不懂，列举了几篇论文中的定义如下：

• 一个分布 \(\chi\) 是 \(B\)-bounded 的如果它 is supported on \([−B, B]\)

• 给定一个多项式环 \(R=\mathbb{Z}[x] /\langle f(x)\rangle\)，在 \(R\) 上定义 \(B\)-bounded Distribution \(\chi\)，使得从 \(\chi\) 中取样的多项式的系数范数以 overwhelming 的概率小于 \(B\)

一般而言，\(B\) 需要设置得尽可能小以保证安全性，通常用 small element 来表示。

安全参数 Security Parameter

Security parameter - Wikipedia

安全多方计算 —— 定义、原语 - 安全计算 - 密码学 | symlpigeon's little gensokyo = 神隐陌路的个人小站

密码学中常提到的安全参数是什么？ - 知乎 (zhihu.com)

在密码学中，安全参数可以衡量攻击者破解一个加密方案的难度，分为：

• 计算 computational 安全参数，用 \(\kappa\) 来表示：

  • 通常决定了计算复杂度，是对加密方案所基于的计算问题的输入大小的度量，意味着破解一个算法需要的计算空间的大小

  • 适用于底层的密码学协议是依赖数学困难问题（NP 问题），即安全性建立在攻击者计算能力有限 bounded computational power 的情况下

  • 例子：使用 \(\kappa\;\text{bit}\) 大小的模数的 RSA 加密方案，破解这个方案的计算空间大小为 \(\mathcal{O}\left(2^{\kappa}\right)\)

• 统计 statistical 安全参数， 用 \(\lambda\) 来表示：

  • 衡量攻击者破解加密方案的概率，无论攻击者的算力有多强大

  • 通常用于衡量攻击者对交互式协议攻击的困难程度

  • 依赖于不同变量分布之间的**统计距离 **statistical distance，如果这个距离非常小（\(<2^{-\sigma}\)），即可以忽略，那么通过猜测来区分这两个变量基本上是无法实现的

  统计距离的标准定义：

  \[ \operatorname{SD}(X, Y) \stackrel{\text { def }}{=} \frac{1}{2} \sum_{x}|\operatorname{Pr}(X=x)-\operatorname{Pr}(Y=x)| \]

  \(X,Y\) 是两个不同分布的随机变量，另一种常见的等价定义是：

  对于任意判别算法 Distinguisher Algorithm：\(D: \mathcal{S} \rightarrow\{0,1\}\)，$ $ 为随机变量的集合，可以得到：

  \[ \operatorname{S D}(X, Y) \stackrel{\text { def }}{=} \max _{D}|\operatorname{Pr}(D(X)=1)-\operatorname{Pr}(D(Y)=1)| \]

  等价表示为：

  \[ |\operatorname{Pr}(D(X)=1)-\operatorname{Pr}(D(Y)=1)| \leq \operatorname{S D}(X, Y) \]

  证明比较有趣：

  1. 首先记 \(p_{s} \stackrel{\text { def }}{=} \operatorname{Pr}(X=s),\;q_{s} \stackrel{\text { def }}{=} \operatorname{Pr}(Y=s),\;s\in \mathcal{S}\)

  2. 由统计距离的标准定义，去掉绝对值：

     \[ \operatorname{S D}(X, Y)=\frac{1}{2}\left(\sum_{s \in \mathcal{S}, p_{s} \geq q_{s}}\left(p_{s}-q_{s}\right)+\sum_{s \in \mathcal{S}, p_{s}>q_{s}}\left(q_{s}-p_{s}\right)\right)= \sum_{s \in S, p_{s} \geq q_{s}}\left(p_{s}-q_{s}\right) \]

     这是因为：

     \[ \sum_{s \in \mathcal{S}, p_{s} \geq q_{s}}\left(p_{s}-q_{s}\right)-\sum_{s \in \mathcal{S}, p_{s}>q_{s}}\left(q_{s}-p_{s}\right)=\sum_{s \in \mathcal{S}} p_{s}-\sum_{s \in \mathcal{S}} q_{s}=1-1=0 \]

     通过展开 \(\sum_{s \in \mathcal{S}, p_{s}>q_{s}}\left(q_{s}-p_{s}\right)\) 的括号，可以推出它和 \(\sum_{s \in \mathcal{S}, p_{s} \geq q_{s}}\left(p_{s}-q_{s}\right)\) 是相等的。

  3. 假设 \(\operatorname{Pr}(D(X)=1) \geq \operatorname{Pr}(D(Y)=1)\)，可以知道

     \[ \operatorname{Pr}(D(X)=1) - \operatorname{Pr}(D(Y)=1)\le \sum_{s \in \mathcal{S}, p_{s} \geq q_{s}}\left(p_{s}-q_{s}\right) \]

     这里可以想象一下，只有当 \(D\) 正好将所有 \(s \in \mathcal{S}, p_{s} \geq q_{s}\) 的 \(s\) 映射为 1 时，\(\operatorname{Pr}(D(X)=1) - \operatorname{Pr}(D(Y)=1)\) 的结果最大，此时也就是等于 \(\sum_{s \in \mathcal{S}, p_{s} \geq q_{s}}\left(p_{s}-q_{s}\right)\) 。所以对于任意 \(D\)，上式都成立。

     由此得到最终结论：

     \[ \begin{aligned}|\operatorname{Pr}(D(X)=1)-\operatorname{Pr}(D(Y)=1)|&=\operatorname{Pr}(D(X)=1)-\operatorname{Pr}(D(Y)=1)\\ &\leq\sum_{s \in \mathcal{S}, p_{s} \geq q_{s}}\left(p_{s}-q_{s}\right)=\operatorname{S D}(X, Y)\end{aligned} \]

安全参数的概念是为了引出不可区分的概念。

不可区分性 Indistinguishability

Computational indistinguishability - Wikipedia

安全多方计算 —— 定义、原语 - 安全计算 - 密码学 | symlpigeon's little gensokyo = 神隐陌路的个人小站

Distribution ensemble - Wikipedia

分布集合 Distribution Ensemble 是一系列分布构成的集合，形式为 \(X=\left\{X_{i}\right\}_{i \in I}\)，其中 \(I\) 是一个可数索引集，每个 \(X_i\) 都是一个概率分布。

常见形式为 \(\left\{D_{n}\right\}_{n \in \mathbb{N}}\)，可以认为每个 \(D_n\) 分布在长度为 \(n\) 的字符串

\(\left\{D_{n}\right\}_{n \in \mathbb{N}}\) 和 \(\left\{E_{n}\right\}_{n \in \mathbb{N}}\) 是两个分布集合，由安全参数 \(n\) 索引（通常指输入的长度），如果对于任意的非均匀概率多项式时间算法 \(A\)，以下值 \(\delta(n)\) 是一个 \(n\) 上的可忽略函数，则称它们为计算不可区分的 Computational Indistinguishablility：

\[ \delta(n)=\left|\underset{x \leftarrow D_n}{\operatorname{Pr}}[A(x)=1]-\underset{x \leftarrow E_n}{\operatorname{Pr}}[A(x)=1]\right| \]

记为 \(D_{n} \approx E_{n}\)。当 \(n\to \infty\) 时，任意高效的算法 \(A\) 的行为在 \(D_n\) 和 \(E_n\) 上不会有明显变化。

如果对于任意的算法 \(A\) 都满足上述性质，则称为统计不可区分 Statistical Indistinguishablility。

根据文献^[1] 描述：

对于足够大的 \(B\)，\(\mathcal{D}_{\mathbb{Z}, \alpha q}\) 和 \(B\)-bounded Distribution 是计算不可区分的，在实践中常取 \(B=10 \cdot \sigma\)

1. Fan J, Vercauteren F. Somewhat practical fully homomorphic encryption[J]. Cryptology ePrint Archive, 2012. ↩︎