隐私集合求交 PSI

课程地址：https://www.secretflow.org.cn/community/bootcamp/2narwgw4ub8rabq/course/8hi4z2o3knhn1ey?isMooc=true

课程概述

• 主讲人：张磊（隐语技术部密码团队）
• 核心内容：SPU 中 PSI 的实现方案、调度架构、开发指南及后续规划
• 适用对象：隐私计算开发者、需要基于 SPU 进行 PSI 开发/部署的技术人员

---

一、SPU 实现的 PSI 介绍

1. PSI 的定义与分类

（1）核心定义

• PSI（Private Set Intersection）：安全多方计算协议，参与方（如 Alice、Bob）在不泄露非交集元素的前提下，计算双方数据集的交集。

（2）分类标准（按不同维度）

分类维度	具体类型
参与方数量	两方 PSI、多方 PSI
数据集差异	Balance PSI（数据量相当）、Unbalance PSI（数据量差异极大）
安全模型	半诚实 PSI、恶意 PSI（如 miniPSI，适用于小数据集）
附加功能	交集数量统计、PSI with Payload（附加数据计算）、Sulky PSI（隐私保护增强）

2. SPU 的 PSI 功能分层

SPU 采用分层架构实现 PSI，各层职责清晰，屏蔽底层协议差异：

### 3. SPU 已实现的 PSI 协议详解
#### （1）eCdh PSI
- **核心特点**：协议简单、易理解实现、扩展性强（支持交集数量统计、Payload 计算）
- **协议流程**：
  1. Alice：将数据集 X 哈希到 eCdh 点，用私钥加密（点乘）后发送给 Bob
  2. Bob：将数据集 Y 哈希到 eCdh 点，用私钥加密；同时对接收到的 Alice 数据二次加密（点乘）后返回
  3. Alice：用自身私钥解密 Bob 返回的数据，与本地加密后的 Y 数据对比，得到交集
- **关键优化**：
  - 性能优化：支持 2519 曲线、Intel AVX512 处理器的 MatrixBuffer 加速
  - 合规支持：新增 SMR 曲线、256K1 曲线
  - 互联互通：完成标准制定，多家厂商已通过互联互通测试
- **性能数据**（2^24 数据集，约 1600 万条）：
  | 处理器                | 曲线类型 | 执行时间 |
  |-----------------------|----------|----------|
  | Intel 第三代处理器    | 4Q       | 32 秒    |
  | Intel 第三代处理器    | 256K1    | 60+ 秒   |
  | Intel 200 系列处理器  | 2519     | 140+ 秒  |

#### （2）PKrt PSI
- **核心背景**：基于 OT 扩展构造 Batch-related OPRF，是 2016 年后 PSI 性能对比的基准协议
- **协议核心组件**：Cuckoo Hash、OT 扩展、OPRF
- **Cuckoo Hash 原理**：
  - 基于多哈希函数（如 3 个），将元素映射到哈希表位置
  - 冲突处理：若目标位置被占用，替换已有元素到其其他映射位置
- **关键优化**：
  1. 矩阵转置优化（基于 Occlund 算法、Intel 比特转换指令）
  2. EIS 优化（PAP-ES 拆解计算轮次、Vector-ES 利用 CPU 指令并行加密）
  3. QHash 优化（采用 Stash-free 方案，避免冲突池带来的高复杂度）
- **性能数据**（2^24 数据集）：
  | 实现方案       | 执行时间 |
  |----------------|----------|
  | Krt 论文原生   | 58.6 秒  |
  | Lip PNC 代码库 | 48.7 秒  |
  | SPU 实现       | 44.3 秒  |

#### （3）BC2 PSI
- **核心依赖**：基于 Subfield Reveal 构造 BRKU-PRF、Generate Cuckoo Hash、Permutation-based Hash
- **Generate Cuckoo Hash 优势**：
  - 每行支持 2-3 个元素，少量哈希函数即可实现 Stash-free（无冲突池）
  - 对比 Krt 的单元素行哈希表，冲突处理效率更高
- **协议流程**：
  1. 基于 Cookhase 配置（哈希数量、每行元素数）构建 BRKU-PRF
  2. 双方插入数据到 Cookhase，交互 OPRF 值
  3. 对比 OPRF 结果得到交集
- **参数配置**：
  - Cookhase 参数：哈希数量=2，每行元素数=3
  - VR1 方案：采用 MTCK 2021 UFO 方案（需填充随机制，避免额外 Subfield VR1）
- **性能优势**：通信量、计算量优于同类型 PSI 协议（如 RZR、GPZG）

#### （4）Unbalance PSI（非对称 PSI）
- **应用场景**：双方数据集规模差异极大（如 10 亿条 vs 100 万条）
- **核心原理**：基于无状态 OPRF 构造，减少大数据集侧计算量
  - 普通 eCdh：大数据集侧计算量为 2×nY
  - Unbalance PSI：大数据集侧计算量为 nY（减少 50%）
- **性能对比**：比普通 eCdh PSI 提升约 1 倍（14.1 秒 vs 普通方案 28+ 秒）

#### （5）DP-PSI（基于同态加密）
- **核心参考**：LabelPSI 开源实现，基于多项式加密
- **协议流程**：
  1. 服务端（大数据集）：将数据集转化为多项式
  2. 客户端（小数据集）：将查询数据加密为同态密文发送
  3. 服务端：计算多项式结果并返回，客户端解密（结果为 0 表示在集合内）
- **优缺点**：
  - 优点：无需传输大数据集，通信量小
  - 缺点：计算量高，执行时间长

#### （6）三方 PSI（基于 eCdh）
- **协议设计**：内部自研，基于两方 eCdh 扩展
- **核心流程**：
  1. Alice 与 Bob 执行 eCdh PSI（对数据 shuffle，避免对应关系泄露）
  2. Alice 将双方交集发送给 Charlie，同时发送自身数据集 HZ 的加密值
  3. Bob 对 HZ 加密后返回 Alice，最终三方协同得到交集
- **注意事项**：会泄露 Alice 与 Bob 的交集数量

### 4. PSI 代码目录结构（SPU 源码库）

lib-spu/psi/
├── common/ # 公共工具类
├── core/ # 核心协议实现（eCdh、KRT、BC2 等）
├── deps/ # 外部依赖（如 MV2、Microsoft APSI）
├── tests/ # 单元测试（每个协议独立测试用例）
└── interface/ # 外部调用接口

---

## 二、SPU PSI 的调度架构
### 1. 核心调度逻辑
- **分片调度**：针对大数据集（如 1000 万条），按默认分片大小（100 万条/片）拆分，分片求交后合并结果
- **架构分层**：

┌───────────────┐
│ Batch PSI │ 顶层调度入口，负责分片、合并结果
├───────────────┤
│ MVPSI │ 协议统一封装层
├───────────────┤
│ Operator │ 协议注册接口（支持新增协议注册）
└───────────────┘

### 2. 关键配置参数
#### （1）Batch PSI 配置
```python
{
  "psi_type": "ECDH",        # 协议类型（ECDH/KRT/BC2 等）
  "receiver_rank": 0,        # 接收方标识
  "broadcast_result": True,  # 是否广播结果
  "output_path": "./output", # 结果输出路径
  "id_output_path": "./id",  # ID 输出路径
  "curve_type": "CURVE25519",# 曲线类型
  "slice_size": 1000000      # 分片大小（默认 100 万）
}

（2）Memory PSI 配置（简化版）

{
  "psi_type": "KRT",
  "receiver_rank": 1,
  "broadcast_result": False
}

3. 协议注册机制（Operator）

• 核心作用：支持新增 PSI 协议，通过 Operator 注册到 MVPSI
• 示例代码（KRT 注册）：

class KrtOperator(PsiOperator):
    def run(self, config, link):
        # KRT 协议执行逻辑
        pass

# 注册协议
PsiOperatorRegistry.register("KRT", KrtOperator)

4. Batch Provider（数据读取接口）

• 功能：分批次读取 SASV 文件，支持两种实现：
  • Memory-based：内存读取（适用于小数据集）
  • SASV File-based：文件分块读取（适用于大数据集）
• 核心参数：batch_size（每次读取数量）

---

三、SecretFlow PSI 开发指南

1. 部署模式

SecretFlow 支持两种部署模式，需根据场景选择：

模式	适用场景	核心逻辑
仿真模式	开发测试	主节点调度，从节点执行交互
生产模式	实际部署	双方节点同时执行，需配置证书

2. 开发步骤（生产模式为例）

（1）启动集群

• 部署 SecretFlow 集群，确保双方节点网络互通

（2）初始化 SecretFlow

import secretflow as sf

# 配置节点信息（双方地址、端口）
sf.init(
    parties=["alice", "bob"],
    addresses={
        "alice": "192.168.0.1:8080",
        "bob": "192.168.0.2:8080"
    },
    tls_config={
        "ca_cert": "./ca.pem",
        "cert": "./alice.pem",
        "key": "./alice.key"
    }
)

（3）启用 SPU 设备

spu = sf.SPU(
    cluster_def={
        "nodes": [
            {"party": "alice", "address": "192.168.0.1:9090"},
            {"party": "bob", "address": "192.168.0.2:9090"}
        ],
        "runtime_config": {"protocol": "REF2K"}
    }
)

（4）配置并执行 PSI

from secretflow.psi import Psi

psi_config = {
    "input_path": "./input.csv",    # 输入文件路径
    "id_col": "user_id",            # ID 列名
    "output_path": "./psi_result",  # 输出路径
    "psi_type": "ECDH",             # 协议类型
    "check_input": True,            # 检查输入合法性
    "sort_output": True             # 输出结果排序
}

# 执行 PSI
psi = Psi(spu)
psi.run(psi_config)

3. 注意事项

• 互联互通配置：需将 smodel 参数设为 True
• 证书配置：生产模式必须启用 TLS 加密，确保通信安全
• 输入数据格式：支持 CSV 格式，需指定唯一 ID 列

---

四、PSI 后续计划

1. 新协议开发

• 重点支持：Bless & Faster PSI、GVLE PSI、Occas PSI、ZoCade PSI
• 多方 PSI：作为 SPU 社区共建任务，已吸引外部开发者参与
• 其他协议：OE PSI（恶意安全增强）

2. 框架优化

• 代码库拆分：将 PSI 从 SPU 主库独立，降低依赖复杂度
• 接口与参数优化：简化上层调用接口，统一配置参数格式
• 协议封装架构优化：提升扩展性，支持快速集成新协议

3. 产品化推进

• 轻量级部署：提供独立部署包，支持边缘场景
• 可视化能力：实现双方交互流程可视化、结果校验可视化
• 性能优化：针对大规模数据集（10 亿+）优化分片策略与计算效率