隐私计算与数据安全汇总版#

第一章 安全多方计算 (MPC)#

1.1 核心概念#

• ​定义：多方协作计算函数\(f\)时满足：
• ✅ 正确性：计算结果准确
• 🔒 隐私性：仅输出结果可见
• ​核心矛盾：隐私输入保护与协同计算的平衡

# 输入：竞拍价 x_i，输出：(最高价, 中标者)
def auction(x):
    winner = argmax(x)
    return x[winner], winner

1.2 基础协议架构#

1.2.1 秘密分享机制#

• 份额生成：随机选择 \(r_1, r_2 \in \mathbb{Z}_p\)，计算 \(r_3 = (x - r_1 - r_2) \mod p\)
• 分配：
  • \(P_2\): \((r_1, r_3)\)
  • \(P_3\): \((r_1, r_2)\)
  • \(P_1\) 自留：\((r_2, r_3)\)
• 秘密恢复 任何两方合作可恢复秘密： $$ x ≡ r_1 + r_2 + r_3 \mod p $$

1.2.2 安全加法协议 (Secure Addition Protocol)#

1. 输入预处理：

   • 每个 \(P_i\) 将 \(x_i\) 按复制秘密分享方案分配： $$ x_i \equiv r_{i,1} + r_{i,2} + r_{i,3} \mod p $$
   • \(P_1\) 持有：\(\{r_{i,2}, r_{i,3}\}\)
   • \(P_2\) 持有：\(\{r_{i,1}, r_{i,3}\}\)
   • \(P_3\) 持有：\(\{r_{i,1}, r_{i,2}\}\)

2. 本地份额聚合：

   • 每个参与方 \(P_j\) 计算本地持有的所有份额和： $$ s_1 = \sum_{i=1}^3 r_{i,1} \mod p \quad (P_2, P_3 \text{计算}) $$ $$ s_2 = \sum_{i=1}^3 r_{i,2} \mod p \quad (P_1, P_3 \text{计算}) $$ $$ s_3 = \sum_{i=1}^3 r_{i,3} \mod p \quad (P_1, P_2 \text{计算}) $$

3. 结果重构：

   • 所有参与方交换并检验 \(s_1, s_2, s_3\) 的值
   • 共同计算： $$ y = s_1 + s_2 + s_3 \mod p $$

正确性证明：

隐私性分析：

• 中间值 \(s_1, s_2, s_3\) 均为随机数之和，满足： $$ \forall \ell \in {1,2,3}, \quad s_\ell \sim \text{Uniform}(\mathbb{Z}_p) $$
• 模拟器可生成假 \(s'_1, s'_2\) 满足： $$ s’_3 = y - s’_1 - s’_2 \mod p $$ 与真实协议计算不可区分

1.2.3 安全乘法协议 (Secure Multiplication Protocol)#

1. 本地交叉项计算：
   • 各参与方利用本地持有的份额计算：

*注：$a_i, b_j$ 表示 $a, b$ 的第 $i, j$ 个份额*

2. 安全求和：
   • 调用安全加法协议计算： $$ y = (u_1 + u_2 + u_3) \mod p. $$

正确性证明：

1.3 安全威胁模型#

1.3.1 输入替换攻击防御#

缓解策略： 1. ​输入承诺机制： - 预提交阶段使用Pedersen承诺： $$ C_i = g^{x_i}h \mod p $$ - \(g,h\)：公开群元素 - \(r_i\)：随机数 - 结果验证阶段强制打开承诺

2. ​经济惩罚机制： - 引入保证金制度，异常输入导致结果偏差时罚没抵押 - 使用零知识证明验证输入合规性

1.3.2 协议偏离攻击防御#

防御机制1：份额分发验证#

执行阶段：秘密分享阶段 (Sec 1.2.1)
验证流程： 1. 当 \(P_i\) 发送份额给 \(P_j\) 时，同步发送承诺值： - \(P_1\) 发送给 \(P_2\)：\(Commit(r_{1,1}), Commit(r_{1,3})\) - \(P_1\) 发送给 \(P_3\)：\(Commit(r_{1,1}), Commit(r_{1,2})\) 2. 接收方 \(P_j\) 请求打开承诺： - 若 \(Open(Commit(r_{i,k})) \neq r_{i,k}\)，判定 \(P_i\) 违规

数学保证： $$ \forall i,j,k,\quad r_{i,k}^{(P_j)} = r_{i,k}^{(P_i)} \mod p $$

防御机制2：中间结果交叉验证#

执行阶段：安全加法协议结果重构 (Sec 1.2.2步骤3)
验证流程： 1. 每个参与方公布两份s_ℓ计算证据： - \(P_1\) 公布：\(s_2^{P_1}, s_3^{P_1}\)
- \(P_2\) 公布：\(s_1^{P_2}, s_3^{P_2}\)
- \(P_3\) 公布：\(s_1^{P_3}, s_2^{P_3}\) 2. 结果一致性检查： $$ \begin{cases} s_1^{P_2} \stackrel{?}{=} s_1^{P_3} \ s_2^{P_1} \stackrel{?}{=} s_2^{P_3} \ s_3^{P_1} \stackrel{?}{=} s_3^{P_2} \end{cases} $$ 3. 若任意等式不成立，启动错误定位协议

防御机制3：乘法协议交叉项审计#

执行阶段：安全乘法协议步骤1 (Sec 1.2.3)
验证流程： 1. 预生成Beaver三元组 \((α,β,γ=αβ)\) 并秘密分享 2. 执行乘法协议时额外计算： $$ \delta = (a-α)(b-β) = ab - αb - βa + γ $$ 3. 验证： $$ \delta + αb + βa \stackrel{?}{=} γ + ab \mod p $$ 4. 偏差值超过阈值时判定恶意行为

1.4 协议安全性增强#

1.4.1 正确性保障#

定理：在一致性验证协议下，最终结果 \(y\) 满足： $$ y = f(x_1,…,x_n) \mod p $$ 证明： 1. 若所有验证通过，则保证： $$ \forall r_{i,k}, s_ℓ \text{ 满足 } \sum r_{i,k} = x_i $$ 2. 乘法协议中交叉项验证确保： $$ ab \equiv \sum u_i \mod p $$

1.4.2 隐私性保持#

定理：防御机制不泄露额外信息
证明： 1. 承诺值 \(C_i\) 在DL假设下完美隐藏 2. 交叉验证过程仅公开线性组合值： $$ s_ℓ = \sum r_{i,ℓ} \sim \text{Uniform}(\mathbb{Z}_p) $$ 3. Beaver三元组审计使用预先生成的随机数，与真实输入无关

1.5 协议执行流程图#

graph TD

A[秘密分享] --> B[输入承诺]

B --> C{恶意检查}

C --通过--> D[安全加法]

C --拒绝--> E[终止协议]

D --> F[安全乘法]

F --> G[结果验证]

G --有效--> H[输出y]

G --无效--> I[错误追溯]

第二章 隐私计算与密码学基础#

2.1 可证明安全框架#

2.1.1 安全框架介绍#

🔐 保密性基础#

🛡️ 威胁模型演进#

graph LR
    A[COA] -->|仅观察密文| B[KPA]
    B -->|已知部分明文| C[CPA]
    C -->|选择明文攻击| D[CCA2]
    style A fill:#f9f,stroke:#333
    style D fill:#f99,stroke:#300

🧩 核心安全模型#

graph TD
    A[敌手] -->|获取公钥| B[Challenger]
    B -->|生成挑战密文| A
    A -->|猜测明文| B
    style B fill:#f0f3ff,stroke:#4a7

graph LR
    A[敌手] -->|解密查询| B[Oracle]
    B -->|返回解密结果| A
    A -->|构造关联密文| B
    style B fill:#ffe,stroke:#d90

🔬 密码学基础假设#

离散对数家族

其他重要假设

🏗️ 假设层次结构#

graph BT
    A[理想模型] --> B[ROM]
    B --> C[强假设]
    C --> D[DDH]
    C --> E[LWE]
    D --> F[CDH]
    E --> F
    F --> G[DL]
    style A fill:#f0f,stroke:#300
    style G fill:#9f9,stroke:#090

• 可靠性排序: ROM > LWE > DDH > CDH > DL
• 工程实践: 优先选择高层假设，权衡效率与安全

2.1.2 IND-CPA 安全模型#

sequenceDiagram
    participant C as Challenger
    participant A as Adversary
    C->>C: (pk,sk) ← Gen(1^λ)
    C->>A: Send pk
    loop 加密查询（可选）
        A->>C: m
        C->>A: Enc_pk(m)
    end
    A->>C: m0, m1
    C->>C: b ← {0,1}, c* ← Enc_pk(m_b)
    C->>A: Send c*
    A->>C: b'
    alt b' = b
        C->>A: 1
    else
        C->>A: 0
    end

安全定义： $$ \forall \mathsf{PPT} \mathcal{A}, \exists \mathsf{negl}(\cdot) s.t. $$ $$ \Pr[\mathsf{PubK}_{\mathcal{A},\Pi}^{\mathsf{CPA}}(\lambda)=1] \leq \frac{1}{2} + \mathsf{negl}(\lambda) $$ 也即达成在选择明文攻击下的不可区分性

2.1.3 IND-CCA 安全模型#

sequenceDiagram
    participant C as Challenger
    participant A as Adversary
    C->>C: (pk,sk) ← Gen(1^λ)
    C->>A: Send pk
    loop 解密查询阶段 1
        A->>C: c ≠ c*
        C->>A: Dec_sk(c)
    end
    A->>C: m0, m1
    C->>C: b ← {0,1}, c* ← Enc_pk(m_b)
    C->>A: Send c*
    loop 解密查询阶段 2
        A->>C: c ≠ c*
        C->>A: Dec_sk(c)
    end
    A->>C: b'
    alt b' = b
        C->>A: 1
    else
        C->>A: 0
    end

安全定义：

2.2 核心密码原语详解#

2.2.1 门限秘密分享#

2.2.2 密码学哈希函数#

graph BT
    RO[随机谕示机] --> CR[抗碰撞]
    CR --> PRE[抗原像]
    PRE --> SPA[抗第二原像]
    style RO fill:#f9f,stroke:#333

# 抗碰撞性失效示例
def find_collision():
    return (m, m') s.t. H(m) == H(m')  # 实际可能找到！

2.2.3 茫然传输协议#

sequenceDiagram
    participant S as 发送方
    participant R as 接收方
    R->>S: 选择比特b，生成公钥pk_b
    S->>R: 加密消息: c₀=Enc(pk₀,m₀), c₁=Enc(pk₁,m₁)
    R->>R: 用sk_b解密c_b

安全条件：

2.2.4 形式化验证框架#

通用可组合性 (UC) 框架#

graph TB
    RealWorld[现实协议] -->|模拟器| IdealWorld[理想功能]
    Adversary -->|攻击| RealWorld
    Environment -->|输入/输出| RealWorld
    style IdealWorld fill:#ffe,stroke:#eb5

验证工具对比：

# 不可提取承诺缺陷示例
class BadCommitment:
    def commit(self, m):
        return hash(m + "static_salt")  # 盐值固定导致可提取！

第三章 ？？？#

3.1 Shamir秘密分享方案#

3.1.1 数学基础#

$$

\begin{aligned} &\text{秘密多项式: } q_s(x) = s + \sum_{i=1}^t a_ix^i \mod p \ &\text{份额分发: } s_j = q_s(\alpha_j) \quad (\alpha_j \neq 0, \forall j) \end{aligned} $$

3.1.2 安全属性#

graph LR
    S[秘密s] --> P((多项式构造))
    P -->|分发| S1(份额1)
    P -->|分发| S2(份额2)
    P -->|分发| Sn(份额n)

    classDef red fill:#fdd,stroke:#f00;
    classDef green fill:#dfd,stroke:#0f0;

    class S1,S2 red
    class S3,Sn green

完美隐私性证明： 1. 任意\(t\)个份额构成\(\mathbb{F}^t\)的满射 2. 存在双射映射\(\phi: \mathbb{F}^t \to \mathbb{F}^t\) 3. 均匀采样\(\mathbb{F}^t\)不泄露\(s\)信息

3.2 半诚实安全协议#

3.2.1 协议框架#

三阶段流程： 1. 输入分享阶段

def share_secret(s, t, n):
    poly = random_polynomial(s, t)
    return [poly.eval(alpha_i) for alpha_i in alpha_list]

2. 计算阶段
   $$ \begin{aligned} &\boxed{加法：[a]+[b] = [a+b]} \ &\boxed{标量乘法：c[a] = [ca]} \ &\boxed{乘法协议：} \ &\quad 1. 本地计算[h_i] = [a_i] \cdot [b_i] \ &\quad 2. 重分享[h_i] \rightarrow [h]_t \ &\quad 3. 线性组合\sum r_i[h]_t = [ab]_t \end{aligned} $$

3. 输出重构阶段
   使用拉格朗日插值： $$ y = \sum_{i=1}^{t+1} r_i \cdot s_i \mod p $$

3.2.2 安全性证明#

for 每个输入门:
    生成随机多项式 f_j(x) 满足 f_j(0)=x_j
    伪造份额 s_i = f_j(alpha_i) 

对每个乘法门:
    本地生成随机中间值
    使用重组向量构造一致性份额

根据已知输出y_j，逆向构造诚实方份额

完美隐私性证明： 1. 输入分享阶段：\(t\)个随机点不泄露多项式信息 2. 乘法协议：双重掩膜保证中间值随机性 3. 输出阶段：已知结果可逆向插值构造

3.3 计算示例#

3.3.1 加法示例#

3.3.2 乘法协议分解#

graph TD
    A[输入a=2] -->|多项式2+x| A1((3,4,5))
    B[输入b=4] -->|多项式4-x| B1((3,2,1))
    A1 --> C[本地乘积]
    B1 --> C
    C --> D[9,8,5]
    D --> E[重分享]
    E --> F[新多项式8+2x-x²]
    F --> G[输出8]

步骤解析： 1. 本地计算乘积项：\(h_i = a_i \cdot b_i\) 2. 分发新份额：\(P_i\)用\(h_i\)生成新的\(t\)次多项式 3. 线性组合重组：\(\sum r_i h_i = ab\)

3.4 协议优化#

3.4.1 批量处理优化#

3.4.2 预处理技术#

graph LR
    P[预处理阶段] -->|生成随机三元组| T((a,b,c=ab))
    T -->|存储| S[离线存储]
    S -->|在线阶段| U[快速计算]

优势： - 在线阶段减少80%通信量 - 支持异步并行计算 - 增强抗合谋攻击能力

3.5 扩展应用#

3.5.1 隐私集合求交#

3.5.2 联邦学习#

graph TB
    C[协调节点] -->|分发模型参数| W1((工作者1))
    C -->|分发模型参数| W2((工作者2))
    W1 -->|加密梯度| C
    W2 -->|加密梯度| C
    C -->|聚合梯度| U[更新模型]

安全保证： - 差分隐私注入 - 梯度值门限解密 - 模型参数零知识验证