抗泄漏可检测作弊的秘密共享技术解析

### 抗泄漏可检测作弊的秘密共享技术解析 #### 1. 核心工作概述 我们的主要成果可以用一个非正式定理来表述：存在这样一个编译器，当给定一个针对单调访问结构 A 的线性秘密共享方案时，它能生成一个针对 A 的秘密共享方案，该方案具备局部抗泄漏能力，抗泄漏率趋近于 1，信息率为 Ω(1)，并且能够检测出对共享份额进行任意篡改的作弊对手。这个编译器可以同时适用于 CDV 和 OKS 两种作弊模型。这里的抗泄漏率指的是可泄漏给对手的份额长度的渐近分数。 #### 2. 相关工作回顾 - **作弊检测模型**：此前已经提出了多种作弊检测模型，但这些模型都未考虑合格集份额泄漏的安全性问题，也无法在 SV 泄漏模型（包括局部泄漏和强泄漏）下提供安全保障。 - **抗泄漏秘密共享研究**：抗泄漏秘密共享的研究源于秘密共享在代码修复方面的应用。后续有多篇研究对其进行了深入探讨，如 Nielsen 和 Simkin 给出了抗泄漏阈值秘密共享的份额大小下限。 - **AMD 码研究**：AMD 码最早被提出后，在多个领域得到了应用。后来研究人员又考虑了其抗泄漏特性。 #### 3. 预备知识介绍 在深入了解核心工作之前，我们需要掌握一些基础概念。 - **随机变量与熵** - 用 X 表示随机变量，x 表示其具体实例。 - 对于随机变量 X，其最小熵定义为 \(H_{\infty}(X) = \min\{\log\frac{1}{Pr[X = s]} : s \in S\}\)。 - 统计距离 \(SD(X, Y) = \frac{1}{2}\sum_{s \in S}|Pr[X = s] - Pr[Y = s]|\)，当 \(SD(X, Y) \leq \epsilon\) 时，称 X 和 Y 是 ε - 接近的，记为 \(X \approx_{\epsilon} Y\)。 - **平均条件最小熵**：随机变量 X 给定 W 时的平均条件最小熵定义为 \(\tilde{H}_{\infty}(X|W) = \log\left(E_{w \leftarrow W}[\max_{x}Pr[X = x | W = w]]\right)\)。如果随机变量 W 最多能取 l 个值，那么 \(\tilde{H}_{\infty}(X|W) \geq H_{\infty}(X) - \log_2 l\)。 - **强种子提取器**：函数 \(Ext : \{0, 1\}^n \times \{0, 1\}^d \to \{0, 1\}^m\) 是一个针对最小熵为 k 且误差为 ε 的源的强种子提取器，需满足对于任何 (n, k) - 源 X 和独立且均匀选择的随机种子 \(U_d\)，有 \(Ext(X, U_d)||U_d \approx_{\epsilon} U_m||U_d\)，其中 \(U_m\) 和 \(U_d\) 相互独立。 - **猜测概率**：对于给定的随机变量 M，猜测概率定义为 \(GP(M) = \max_{m}Pr(M = m) = 2^{-H_{\infty}(M)}\)。给定随机变量 M 和泄漏变量 Z，平均猜测概率定义为 \(GP(M|Z) = \sum_{z}Pr(Z = z) \cdot \max_{m}Pr(M = m|Z = z) = 2^{-\tilde{H}_{\infty}(M|Z)}\)。 #### 4. 秘密共享与作弊检测 - **秘密共享方案**：一个针对访问结构 \((A_0, Z_M)\) 的秘密共享方案 S 由一对算法 (Share, Rec) 组成。Share 是一个概率算法，输入一个秘密 m 和参与方数量 n，生成 n 个份额；Rec 是一个确定性算法，输入部分参与方的份额，输出一个字符串。该方案需满足 ε - 正确性和 ε - 统计保密性。 - **可检测作弊的秘密共享**：以 (k, n) - 阈值秘密共享方案为例，在 OKS 模型下，若满足完美保密性、正确性和作弊检测性这三个条件，则称该方案是 (k, n, δ) - OKS 可检测作弊的。在 CDV 模型下，定义类似，但假设对手选择秘密分布。 #### 5. 局部泄漏与强局部泄漏模型 - **局部泄漏家族**：对于 2 - 单调访问结构，局部泄漏家族 \(H_{t,\mu}\) 由泄漏函数 \(Leak_{T,\bar{\tau}}\) 组成，其中 \(|T|\) 是对手选择的禁止集 T 的大小，\(\mu\) 是每个诚实份额的泄漏量。对于 (k, n) - 阈值访问结构，\(|T| = t = k - 1\) 是最优参数选择。 - **强局部泄漏家族**：强局部泄漏家族 \(H_{t,t',\mu}\) 由函数 \(h_{T,T',\bar{\tau}}\) 组成，其参数 t、t'、\(\mu\) 分别为适应性阈值、腐败阈值和泄漏量。对于 (k, n) - 阈值方案，\(t' = k - 1\) 和 \(t = k - 2\) 是强泄漏模型的最优参数选择。 #### 6. 抗泄漏秘密共享方案 一个针对秘密空间 S 实现 k - 单调访问结构的秘密共享方案 (Share, Rec)，若对于所有 \(Leak_{T,\bar{\tau}} \in H_{t,\mu}\)（或 \(h_{T,T',\bar{\tau}} \in H_{t,t',\mu}\)）以及任意两个秘密 \(m_0, m_1 \in S\)，统计距离 \(SD(Leak_{T,\bar{\tau}}(Share(m_0)), Leak_{T,\bar{\tau}}(Share(m_1)))\)（或 \(SD(h_{T,T',\bar{\tau}}(Share(m_0)), h_{T,T',\bar{\tau}}(Share(m_1)))\)）小于 ε，则称该方案是 ε - 抗局部泄漏（或强泄漏）的。抗泄漏率定义为 \(\lim_{\mu \to \infty}\frac{\mu}{\max_i |sh_i|}\)。 #### 7. AMD 码及其抗泄漏特性 - **AMD 码定义** - **强 AMD 码**：随机编码方案 \((AMD_{enc}, AMD_{dec})\) 是一个 (强) δ - AMD 码，需满足对于任何消息 \(m \in F^k\)，有 \(Pr[AMD_{dec}(AMD_{enc}(m, R) + A) \notin \{m, \perp\}] \leq \delta\)。 - **弱 AMD 码**：确定性编码方案 \((AMD_{enc}, AMD_{dec})\) 是一个 (弱) δ - AMD 码，对于均匀分布在 \(F^k\) 上的消息 M，有 \(Pr[AMD_{dec}(AMD_{enc}(M) + A) \notin \{M, \perp\}] \leq \delta\)。 - **抗泄漏 AMD 码** - **LR - 强 AMD 码**：强 AMD 编码方案 \((AMD_{enc}, AMD_{dec})\) 是一个抗泄漏强 (ρ, δ) - AMD 码，需满足对于任何消息 \(m \in F^k\)，有 \(Pr[AMD_{dec}(AMD_{enc}(m, R) + A(Z)) \notin \{m, \perp\}] \leq \delta\)，其中 Z 是泄漏变量，满足 \(H_{\infty}(AMD_{enc}(m, R)|Z) \geq H_{\infty}(AMD_{enc}(m, R)) - \rho n \log q\)。 - **LR - 弱 AMD 码**：弱 AMD 码 \((AMD_{enc}, AMD_{dec})\) 是一个抗泄漏弱 (ρ, δ) - AMD 码，对于均匀分布在 \(F^k\) 上的消息 M，有 \(Pr[AMD_{dec}(AMD_{enc}(M) + A(Z)) \notin \{M, \perp\}] \leq \delta\)，其中 Z 是泄漏变量，满足 \(H_{\infty}(AMD_{enc}(M)|Z) \geq H_{\infty}(AMD_{enc}(M)) - \rho n \log q\)。 #### 8. 抗泄漏秘密共享中的保密性概念 - **区分保密性**：通过对手在区分不同秘密时的优势 \(Adv_{ds}(LRShare, Leak)\) 来定义。若 \(Adv_{ds}(LRShare, Leak) \leq \epsilon\)，则称秘密共享方案是可区分安全的。 - **猜测概率定义的语义保密性**：通过对手在有泄漏信息和仅有消息长度信息两种情况下的猜测概率差异来定义，即 \(Adv_{ss}(LRShare, Leak)\)。可以证明，区分保密性意味着语义保密性。 下面用 mermaid 流程图展示秘密共享的基本流程： ```mermaid graph TD; A[输入秘密 m] --> B[Share 算法生成份额]; B --> C[份额分发]; C --> D[部分份额输入 Rec 算法]; D --> E[输出秘密]; ``` 同时，我们可以用表格总结不同概念的定义和特点： | 概念 | 定义 | 特点 | | ---- | ---- | ---- | | 最小熵 \(H_{\infty}(X)\) | \(\min\{\log\frac{1}{Pr[X = s]} : s \in S\}\) | 衡量随机变量的不确定性 | | 统计距离 \(SD(X, Y)\) | \(\frac{1}{2}\sum_{s \in S}|Pr[X = s] - Pr[Y = s]|\) | 衡量两个随机变量分布的差异 | | 平均条件最小熵 \(\tilde{H}_{\infty}(X|W)\) | \(\log\left(E_{w \leftarrow W}[\max_{x}Pr[X = x | W = w]]\right)\) | 考虑条件下的最小熵 | | 秘密共享方案 | 由 (Share, Rec) 算法组成，满足正确性和保密性 | 实现秘密的安全共享 | | 可检测作弊的秘密共享 | 满足完美保密性、正确性和作弊检测性 | 防止作弊行为 | | 抗泄漏秘密共享方案 | 统计距离小于 ε | 抗泄漏攻击 | | AMD 码 | 包括强、弱 AMD 码 | 检测编码消息的篡改 | | 抗泄漏 AMD 码 | 包括 LR - 强、LR - 弱 AMD 码 | 考虑泄漏情况下的安全性 | | 区分保密性 | \(Adv_{ds}(LRShare, Leak) \leq \epsilon\) | 基于区分不同秘密的能力 | | 语义保密性 | \(Adv_{ss}(LRShare, Leak)\) 有界 | 基于猜测概率 | #### 9. 研究方法概述 Srinivasan 和 Vasudevan 提出了 SV 编译器，它能将 2 - 单调通用访问结构的秘密共享转换为具有抗泄漏能力的秘密共享，还提出了另一个类似功能且能抵御强局部泄漏的编译器。我们的工作是为这些编译器添加作弊检测功能。 我们的编译器基本思路是在 SV 编译器前增加一个预处理步骤，使用代数操作检测（AMD）码对秘密进行编码，然后将编码后的码字作为 SV 编译器的输入。具体步骤如下： 1. **AMD 编码**：使用 AMD 码对消息 m 进行编码，得到码字 \(AMD_{enc}(m)\)。 2. **SV 编译**：将 \(AMD_{enc}(m)\) 输入 SV 编译器，生成新的份额。 SV 编译器将访问结构 A 的秘密共享方案的份额 \(Sh_i\) 转换为份额 \((w_i, Sh'_i \oplus r, S_i)\)，其中 \(Sh'_i = Sh_i \oplus Ext(w_i, s)\)， \(w_i\)、r、s 是随机字符串， \(Ext(w_i, s)\) 是强提取器， \(S_i\) 是 \((r, s)\) 使用 (2, n) 阈值 Shamir 秘密共享的份额。编译方案的 LRRec 算法先恢复 \((r, s)\)，计算 \(Ext(w_i, s)\) 并恢复 \(Sh_i\)，最后使用原始秘密共享方案的 Rec 算法恢复秘密。 #### 10. 实际应用中的问题及解决方案 虽然理论上使用 AMD 码可以检测编译后份额的篡改，但在实际中，由于编译方案存在泄漏，会违反 AMD 码的安全模型和检测保证，导致无法依赖该码的保护。 Ahmadi 和 Safavi - Naini 引入了抗泄漏 AMD 码，其泄漏模型要求在给定泄漏的情况下，强 AMD 码字的随机性（即 \((m, r, f(m, r))\) 中的 r）或弱 AMD 码消息空间的最小熵保持较高，并满足一个下界。后来，这个泄漏模型被进一步推广，允许码字的一部分 ρ 被泄漏。 为了证明定理 3，我们需要证明 SV 编译方案的泄漏不会违反 AMD 码字 \(AMD_{enc}(m)\) 的最小熵下界。我们使用平均猜测概率 \(GP(AMD_{enc}(M) | Z) = 2^{-H_{\infty}(AMD_{enc}(M)|Z)}\) 来表示 AMD 码字的泄漏率 ρ 与抗泄漏秘密共享方案保密性的关系。通过证明区分保密性意味着猜测保密性，我们完成了定理 3 的证明。 #### 11. 效率分析 我们的构造在第 4.2 节中是高效的，实现了信息率 Ω(1) 和抗泄漏率为 1，与 Srinivasan 等人的抗泄漏秘密共享方案相当，但能够检测主动篡改攻击。这是因为强和弱 AMD 码的编码率（消息长度与码字长度之比）接近 1，并且存在高效计算的最优构造。对于抗泄漏 AMD 码，也可以通过调整泄漏参数从 AMD 码构造得到。 #### 12. 扩展与未来工作方向 由于篇幅限制，我们目前只考虑了局部泄漏模型，扩展到 SV 强局部泄漏模型的内容将在完整版本中给出。在第 4.5 节中讨论了扩展到通用访问结构的情况。 抗泄漏可检测作弊的秘密共享可以用于构建抗泄漏鲁棒秘密共享，通过在所有最小合格子集上使用 LRRec 算法，直到找到正确的秘密。但这种重建算法效率较低，因为最小合格集的数量可能很大。未来的一个有趣研究方向是构建具有高效重建算法的抗泄漏鲁棒秘密共享。 下面用 mermaid 流程图展示我们编译器的工作流程： ```mermaid graph TD; A[输入秘密 m] --> B[AMD 编码: \(AMD_{enc}(m)\)]; B --> C[SV 编译]; C --> D[生成新份额]; D --> E[份额分发]; E --> F[部分份额输入 LRRec 算法]; F --> G[恢复 \((r, s)\) 和 \(Sh_i\)]; G --> H[Rec 算法恢复秘密]; ``` 再用表格总结不同编译器和编码方案的特点： | 方案 | 功能 | 特点 | | ---- | ---- | ---- | | SV 编译器 | 将 2 - 单调通用访问结构的秘密共享转换为抗泄漏秘密共享 | 未考虑作弊检测 | | 我们的编译器 | 为 SV 编译器添加作弊检测功能 | 结合 AMD 码 | | 强 AMD 码 | 检测编码消息的篡改 | 随机编码方案 | | 弱 AMD 码 | 检测编码消息的篡改 | 确定性编码方案 | | 抗泄漏强 AMD 码 | 在有泄漏情况下检测篡改 | 考虑泄漏模型 | | 抗泄漏弱 AMD 码 | 在有泄漏情况下检测篡改 | 考虑泄漏模型 | 综上所述，我们的研究在抗泄漏秘密共享的基础上增加了作弊检测功能，通过引入 AMD 码和改进编译器，提高了秘密共享方案的安全性和实用性。未来的研究可以进一步优化重建算法，提高方案的效率。