course | privacy-preserving-models-and-algorithms

# Privacy-Preserving Models and Algorithms

>   隐私保护模型与算法，课程学习内容及思考

## midterm exam

### essay quiz

>   论述大数据生命周期每个阶段面临的安全威胁和采取的安全技术

大数据生命周期通常有以下几个阶段：

>   单同态、部分同态以及全同态的含义；并以 RSA 算法为例给出同态算法及其所具备的同态性，验证之

**单同态** 指

**部分同态** 指

**全同态** 指

### design quiz

>   设计一个基于多服务器的隐私信息检索 PIR 方案：
>
>   1.   数据 $X = (x_{1}, x_{2}, ..., x_{16})$
>   2.   待查数据为 $x_{10}$
>   3.   总共有 4 个服务器
>
>   给出详细步骤并分析其安全性

假设 $\sigma\oplus i$ 表示将 $\sigma$ 的第 $i$ 位取反；例如 $\sigma = 111$，则 $\sigma \oplus 2 = 110$

1.    将数据 $X = (x_{1}, x_{2}, ..., x_{16})$ 转换成矩阵表示的方式如下：
     $$
     \left[
     \begin{array}{1}
     x_{1} & x_{2} & x_{3} & x_{4} \\ 
     x_{5} & x_{6} & x_{7} & x_{8} \\ 
     x_{9} & x_{10} & x_{11} & x_{12} \\ 
     x_{13} & x_{14} & x_{15} & x_{16}
     \end{array}
     \right]
     $$
     将其转换为矩阵位置的表示方式如下：
     $$
     \left[
     \begin{array}{1}
     x_{00} & x_{01} & x_{02} & x_{03} \\ 
     x_{10} & x_{11} & x_{12} & x_{13} \\ 
     x_{20} & x_{21} & x_{22} & x_{23} \\ 
     x_{30} & x_{31} & x_{32} & x_{33}
     \end{array}
     \right]
     $$
     则待查数据 $x_{10}$ 在位置矩阵中表示为 $x_{21}$

2.   由服务器个数为 4，数据总数量为 16，则生成 $\sqrt{4} = 2$ 个，每个位长为 $\sqrt{16} = 4$ 随机参数：
     $$
     \begin{align}
     \sigma_{0} &= 0001 \\ 
     \tau_{0} &= 1000 \\ 
     \sigma_{1} &= \sigma_{0} \oplus 2 = 0011 \\ 
     \tau_{1} &= \tau_{0} \oplus 1 = 1100
     \end{align}
     $$
     其中的 2 和 1，是由 $x_{21}$ 对应位置得到的，则转成随机数矩阵为：
     $$
     \left[
     \begin{array}{1}
     \sigma_{0} = 0001 & \tau_{0} = 1000 \\
     \sigma_{1} = 0011 & \tau_{1} = 1100
     \end{array}
     \right]\left[
     \begin{array}{1}
     \sigma_{0} = 0001 & \tau_{0} = 1000 \\
     \sigma_{1} = 0011 & \tau_{1} = 1100
     \end{array}
     \right]
     $$

3.   由 4 个服务器，同样也用位置矩阵来表示可得：
     $$
     \left[
     \begin{array}{1}
     DB_{00} = \sigma_{0} \times \tau_{0} & DB_{01} = \sigma_{0} \times \tau_{1} \\
     DB_{10} = \sigma_{1} \times \tau_{0} & DB_{11} = \sigma_{1} \times \tau_{1}
     \end{array}
     \right]
     $$
     则计算结果如下：
     $$
     \begin{align}
     DB_{00} &= \{x_{30}\} \\
     DB_{01} &= \{x_{30}, x_{31}\} \\
     DB_{10} &= \{x_{20}, x_{30}\} \\
     DB_{11} &= \{x_{20}, x_{21}, x_{30}, x_{31}\}
     \end{align}
     $$
     将所有计算结果进行异或（下面的公式中 $\oplus$ 是异或，不再是上边自定义的取反符号）：
     $$
     x_{30} \oplus x_{30} \oplus x_{31} \oplus x_{20} \oplus x_{30} \oplus x_{20} \oplus x_{21} \oplus x_{30} \oplus x_{31} = x_{21}
     $$
     由上面的式子可以看出，经过将返回结果异或后，只剩下了 $x_{21}$，这与一开始要查询的标号相等，也就表示最后从这么多服务器返回的这么多结果中取得了想要的值，至此，基于多服务器的 PIR 方案结束

接下来验证该方案的 **正确性** 以及 **安全性**：

1.   正确性

用一种比较直观的方式来表示为什么能够得出想要的值

关注于第 2 步中，第二个 $\sigma$ 和 $\tau$ 矩阵可以得知，当 $\sigma_{i}$ 与 $\tau_{j}$ 分别组合时（其中 $i, j \in \{0, 1\}$），$\sigma_{i}$ 中的第 3 个 bit 值为 1，以及 $\tau_{j}$ 的第 0 个 bit 值为 1，组合出的 $x_{i, j}$ 都是成对出现的；

只有因为选定的 $x_{21}$ 而导致的 $\sigma_{i}$ 的第 2 bit 和 $\tau_{j}$ 的第 1 bit，在整个过程中只出现一次；

在最后的全部结果异或过程中，由于异或操作的特性，偶数个出现的会被消除，奇数个的会保留，也就因此返回了正确的值

2.   安全性

根据正确性可以得知，在 4 个服务器所存储的数据相同，且互相之间不能通信的情况下，服务器只根据生成的随机数来返回所需的数据，本地所选择的 $x_{i}$ 对于服务器来说是未知的。服务器总共返回了 9 个数据，而检索者最后只需要取得其中一个，其他数据是不被需要的，但是服务器无法确定检索者具体想要哪个数据，也就达到了隐私保护的目的。

>   设计一个基于 **对称算法** 的比特承诺方案，给出详细步骤并分析其安全性

假设一个场景，A 与 B 进行猜数游戏，A 所猜的值是 B 所想的值（预测与揭示模型），要求如下：

1.   A 先猜数，且不能反悔
2.   B 随后得出自己所想的值
3.   B 在 A 主动揭示自己猜的内容之前，无法得知 A 所猜的值
4.   整个流程必须保证 A 和 B 之间不能互相受到干扰

具体设计流程如下：

1.   承诺阶段：

1.   B 生成一个比特序列 $r$，将其发给 A；过程表示为：$B \to A: r$

2.   A 确定所猜想的数 $x$，并且生成另一个随机数 $k$ 作为对称密钥，并且用 $k$ 计算加密 $s = E(k, r \mathbin\Vert x)$

这里的 $ r \mathbin\Vert x$ 表示将 $r$ 与 $x$ 链接起来，例如：当假设 $x = 63 = 00111111$，比特序列 $r = 1111$，则 $ r \mathbin\Vert x = 111100111111$；

然后将 S 发给 B；$ A \to B: s$

3.   B 确定自己所想的值为 $y$

2.   揭示阶段：

1.   A 将对称密钥 $k$ 发送给 B；$A \to B: k$
     2.   B 使用所得的对称密钥计算 $r^{'} \mathbin\Vert x = D(s, k)$，得出结果后，验证 $ r^{'} = r$，则往后的值就是 A 所承诺的 $x$
     3.   随后 B 就可以对比 $x$ 和 $y$，并证明猜测的正确性

算法的 **安全性**：

## homework

1.   请简述大数据如何服务于信息安全。
2.   请简述自主访问控制模型和强制访问控制模型的基本思想及两者的区别和联系。
3.   请简述 BLP 模型与 Biba 模型的基本思想及两者的区别和联系。
4.   请简述基于单发送者广播加密的访问控制方案，给出方案具体流程并分析其安全性。
5.   请简述基于公钥广播加密的访问控制方案，给出方案具体流程并分析其安全性。
6.   请简述典型的对称密文检索方案，给出方案具体流程并分析其安全性。
7.   请简述基于 **文档-关键词索引** 的密文关键词检索方案，给出方案具体流程并分析其安全性。
8.   请给出属性加密访问控制技术的基本思想，并简述 CP-ABE 算法。
9.   构造基于单向函数的比特承诺方案，给出方案具体流程并分析其安全性。
10.   给出基于交互式 Schnorr 协议的零知识证明系统，使得 A 让 B 相信其拥有私钥 s。
11.   假设 A 的财富值为 a=0，B 的财富值为 b=1，设计基于混淆电路的安全协议比较 A 和 B 的财富值，给出协议具体流程并分析其安全性。

如果觉得我的文章对你有用，请随意赞赏

发表评论 取消回复 请友善发言喔

发表评论取消回复
请友善发言喔