MENU

一些隐私计算的基础知识

• August 18, 2022 • Read: 1475 • 隐私计算

数学基础

欧拉函数

任意给定一个正整数 $ n $，在小于等于 $ n $ 的正整数中有多少个数与 $ n $ 构成互质关系？计算这些值的方法就叫做欧拉函数，记作 $ \varphi $，如在 $ 1 $ 到 $ 8 $ 中与 $ 8 $ 形成互质关系的是 $ 1，3，5，7 $，所以 $ \varphi(8) = 4 $

欧拉定理

如果有两个正整数 $ a $ 和 $ n $ 互质，则有 $ a^{\varphi(n)} \equiv 1(\operatorname{mod} n) $，即 $ a^{\varphi(n)} + 1 = kn (k \in R) $

费马小定理

费马小定理是一个欧拉定理的特殊情况

假设正整数 $ a $ 与 质数 $ n $ 互质，因为 $ \varphi(n) = n - 1 $，所以有 $ a^{(n - 1)} \equiv 1(\operatorname{mod} n) $

欧拉函数之积

如果 $ n $ 可以分解为两个互质的整数之积，即 $ n = p_{1} \times p_{2} $，则有 $ \varphi(n) = \varphi(p_{1}) \times \varphi(p_{2}) $，如 $ \varphi(35) = \varphi(5) \times \varphi(7) = 4 \times 6 = 24 $

模反元素

如果有两个正整数 $ a $ 和 $ n $ 互质，那么一定可以找到整数 $ b $，使得 $ ab-1 $ 被 $ n $ 整除，即 $ ab \equiv 1 (\operatorname{mod} n) $，此时 $ b $ 就称为 $ a $ 的模反元素

RSA算法

密钥生成

  1. 随机选两个不相等的质数 $ p $ 和 $ q $，在实际应用中，这两个质数越大则越难破解
  2. 计算 $ n = p \times q $
  3. 计算 $ \varphi(n) = \varphi(p) \times \varphi(q) = (p - 1) \times (q - 1) $
  4. 随机取一整数 $ e $，其中 $ 1 < e < \varphi(n) $
  5. 计算 $ e $ 的模反元素（也称模逆元） $ d $，即解方程 $ ed - 1 = k\varphi(n) $
  6. 公钥为 $ (n, e) $，私钥为 $ (n, d) $

加密过程

  1. 发送方将明文转换为一串数字 $ m $，其中$ (m < n) $
  2. 使用加密公式 $ m^{e} \equiv c(\operatorname{mod} n) $ 计算出密文 $ c $，即求解 $ m^{e} - c = kn (k \in Z) $
  3. 将密文 $ c $ 发送给接受方

解密过程

  1. 接收方接收到密文 $ c $
  2. 使用解密公式 $ c^{d} \equiv m (\operatorname{mod} n) $ 计算出明文 $ m $，即求解 $ c^{d} - m = kn (k \in Z) $

算法推导

$$
\begin{array}{lll}
m^{e} & - & c = kn \\
c & = & m^{e} + k_{1}n(k_{1} = -k) \\
c^{d} & = & (m^e + k_{1}n)^d \\
& = & m^{ed} + k_{2}n (k_{2} = \sum\limits_{1 \le i \le d}\binom{d}{i}m^{e(d-i)}k_{1}^in^{i-1}) \\
& = & m^{k_{3}\varphi(n) + 1} + k_{2}n (ed = k_{3}\varphi(n) + 1) \\
& = & m(m^{k_3\varphi(n)}) + k_{2}n \\
& = & m(1 + k_{4}\varphi(n)) + k_{2}n (m^{k_{3}\varphi(n)} = 1 + k_{4}n) \\
& = & m + k_{5}n (k_{5} = k_{2} + mk_{4})
\end{array}
$$

不经意传输

不经意传输（Oblivious Transfer, OT）是一个密码学协议。在这个协议中发送方将一批消息发送给接收方，接收方只能从中选取一条，但是发送方不知道接收方选择了哪一条，接收方也不知道发送方发送的其他几条数据是什么。不经意传输协议可以保护接受方的隐私（选择哪一条）不被发送方知道，是密码学的一个基本协议，也称茫然传输协议。

基于 RSA 算法的不经意传输协议

我们假设 Alice 要发送消息给 Bob

基于 RSA 算法的不经意传输协议步骤如下：

  1. Alice 生成公私钥，并将公钥 $ (n, e) $ 发送给 Bob
  2. Alice 生成 $ N $ 个随机数 $ X_{i} $，并发送给 Bob
  3. Bob 生成随机数 $ k $ 和 编号 $ b $ （代表选择 $ X_{b} $）
  4. Bob 使用公钥加密 $ k $，并使用 $ b $ 盲化密文（$ (v = X_{b} + k^{e}) \operatorname{mod} n $）后发送给 Alice
  5. Alice 对所有 $ X $ 解密，得到 $k_{0} ~ k_{N-1}$ （$ k_{i} = (v-X_{i})^d \operatorname{mod} n $）
  6. Alice 对 $ N $ 个解密结果分别加入真实信息后发送给 Bob （$ m_{i}' = m_{i} + k_{i} $）
  7. Bob 对第 $b$ 个消息进行解密即可得到明文，对其它消息解密只能得到无意义的随机值

布隆过滤器

布隆过滤器（Bloom Filter）是一个由固定大小的二进制向量或者位图（Bitmap）和一系列映射函数组成的。在初始状态时，对于长度为 $ m $ 的位数组，他的所有位都被置为 $ 0 $

当有变量被加入集合时，通过 $ k $ 个映射函数将这个变量映射成位图中的 $ k $ 个点，把他们置为 $ 1 $。

查询数据时只需要看这些点是不是都是 $ 1 $ 就可以大概率知道集合中是否包含该数据，若有任一位为 $ 0 $ 则一定不存在，若都为 $ 1 $ 则可能存在，可能存在是因为映射函数本身都是散列函数，而散列函数会有碰撞。

隐私计算安全模型

半诚实模型

参与者严格按照协议规定执行协议，但是可能受到被恶意攻击者所影响，泄露自己获得的所有信息，包括自身的输入、输出以及参与协议计算所收集到的信息等。

恶意模型

在协议执行时，攻击者可以通过在其控制下的参与方进行通过不合法的输入，或者恶意篡改输入等等方法来分析诚实的参与者的隐私信息。还可以通过提前终止和拒绝参与等方式导致协议的终止。

隐蔽模型

在协议执行时，攻击者可以通过在其控制下的参与方进行通过不合法的输入，或者恶意篡改输入等等方法来分析诚实的参与者的隐私信息，也可以严格按照协议规定执行协议，并在过程中推测其他参与方的隐私。不诚实的参与方发起这样的作弊行为会有 $ \lambda $ 的概率被其他参与方检测出来。

与恶意模型不同的是如果没有检测到攻击者则攻击者可能会成功地实现作弊。这类系统被称为满足威慑因子为 $ \lambda $ 的隐蔽安全模型。

不诚实门限

根据敌手方占参与方总数的比例，安全性假设还可细分为诚实多数制（Honest Majority）安全和非诚实多数制（Dishonest Majority）安全。如果一个有 $ n $ 个参与方的系统能在最多有 $ t $ 个参与者做出包括合谋在内的不诚实行为的情况下，仍保证隐私数据不被泄露，则称该系统为可容忍 $ (t, n) $ 不诚实门限的系统。一般而言，在 $ n $ 相同的情况下，$ t $ 越大则隐私协议安全性越高。当 $ t < \frac{n}{2} $ 时，协议被称为诚实多数制协议，当 $ \frac{n}{2} \le t \le n - 1$ 时，协议被称为非诚实多数制协议。

参考文献

深入浅出隐私计算：技术解析与应用实践/李伟荣著.北京：机械工业出版社，2022.1

Leave a Comment