加密数据库中的选择性文档检索方案解析

### 加密数据库中的选择性文档检索方案解析 #### 1. 加密方案基础参数与算法 在加密数据库的选择性文档检索（SDR）方案中，采用了对称的Brakerski - Vaikuntanathan（BV）方案。该方案的参数选择至关重要，需保证方案的正确性和安全性。相关参数如下： - 分圆多项式 \(f(x) = x^{\alpha} + 1\) - 环 \(R_q = \mathbb{Z}_q[x]/\langle f(x) \rangle\) 上的误差分布 \(\chi\) - 密文度数 \(D\)（支持 \(D - 1\) 次乘法） - 支持的加法次数 \(A\) - 消息空间 \(t < q\)，且 \(t\) 为素数 - 误差参数 \(\sigma\)（离散高斯误差分布的标准差） 为保证方案的正确性，BV方案要求 \(q \geq 4 \cdot (2t\sigma^2\sqrt{\alpha})^D \cdot (2\alpha)^{(D - 1)/2} \cdot \sqrt{A}\)。 加密方案包含以下算法： - **密钥生成（SH.Keygen(1κ)）**：从误差分布 \(\chi\) 中采样一个环元素 \(s\)，设置秘密密钥 \(sk := s\)。若仅关注同态性，从 \(R_q\) 中采样 \(s\) 即可。 - **加密（SH.Enc(sk, m)）**：消息空间为 \(R_t\)，将消息编码为系数在 \(\mathbb{Z}_t\) 中的 \(\alpha\) 次多项式。采样 \(a \stackrel{R}{\leftarrow} R_q\) 和 \(e \stackrel{R}{\leftarrow} \chi\)，输出密文 \(c = (c_0, c_1) \in R_q^2\)，其中 \(c_1 = -a\)，\(c_0 = as + te + m\)。 - **乘法（SH.Mul(c, c')）**：给定两个密文 \(c = (c_0, c_1)\) 和 \(c' = (c_0', c_1')\)，使用多项式乘法输出密文向量 \(c_{mul} = c \cdot c' = (c_0c_0', c_0c_1' + c_0'c_1, c_1c_1')\)。 - **加法（SH.Add(c, c')）**：给定两个密文 \(c = (c_0, c_1, c_2)\) 和 \(c' = (c_0', c_1', c_2')\)，通过密文向量的逐坐标加法输出密文向量 \(c_{add} = c + c' = (c_0 + c_0', c_1 + c_1', c_2 + c_2') \in R_q^3\)。 - **解密（SH.Dec(sk, c)）**：首先定义秘密密钥向量 \(s = (1, s, s^2, \ldots, s^D) \in R_q^{D + 1}\)，计算 \(\langle c, s \rangle = \sum_{i = 0}^{D} c_is^i \in R_q\)，并输出消息 \(m = \langle c, s \rangle \pmod{t}\)。 #### 2. BV参数选择与实现 基于实际需求，并参考Lauter等人的研究，选择了以下固定参数：\(D = 2\)，\(A = 100\)，\(t = 2\)，\(\sigma = 8\)。根据这些固定参数计算出的灵活参数如下表所示： | \(\alpha\) | \(\lceil \lg(q) \rceil\) | \(\lg(T)\) | WC \(|c|\) | MUL | ADD | | ---- | ---- | ---- | ---- | ---- | ---- | | 256 | 14 | 64 | 896 B | \(410 \times 10^{-6}\) | \(11 \times 10^{-6}\) | | 512 | 20 | 107 | 2.5 kB | \(454 \times 10^{-6}\) | \(21 \times 10^{-6}\) | | 1024 | 33 | 134 | 8.25 kB | \(2.8 \times 10^{-3}\) | \(72 \times 10^{-6}\) | 该方案使用C/C++结合FLINT（快速数论库）实现，并在Intel Xeon CPU [email protected] GHz、运行Linux 2.6.37 - sabayon x86 64的机器上进行测试。对于512次多项式，一次加法（乘法后）耗时 \(21 \times 10^{-6}\) 秒，一次乘法耗时 \(454 \times 10^{-6}\) 秒。 目前方案为单线程实现，可通过并行计算优化。同态乘法需计算四个独立的多项式乘法，加法需计算三个独立