不经意传输协议的外包化优化与实践

1. 不经意传输协议的技术演进与外包化实践

不经意传输（Oblivious Transfer, OT）作为密码学领域的基石协议，自1981年由Rabin首次提出以来，已经发展出多种变体。在传统1-out-of-2 OT协议中，发送方持有两个消息(m₀,m₁)，接收方通过选择位s∈{0,1}可以获取其中一个消息mₛ，而发送方无法确定接收方选择了哪个消息。这种看似简单的交互背后，蕴含着丰富的密码学原理和工程实现挑战。

1.1 基础OT协议的工作原理

典型的不经意传输协议基于离散对数难题（Discrete Logarithm Problem, DLP）构建，其核心流程包含四个阶段：

1. 初始化阶段：发送方选择大素数p和生成元g∈ℤₚ*，计算随机元素C=gᵃ（a为随机数）
2. 查询生成阶段：接收方根据选择位s生成查询对(β₀,β₁)，其中βₛ=gˣ，β₁₋ₛ=C/gˣ
3. 响应生成阶段：发送方验证β₀·β₁=C后，对每个消息计算响应：

   y₀,y₁ ← ℤₚ e₀ = (gʸ⁰, H(β₀ʸ⁰)⊕m₀) e₁ = (gʸ¹, H(β₁ʸ¹)⊕m₁)

4. 消息提取阶段：接收方使用私密参数x计算H((gʸˢ)ˣ)⊕eₛ获得mₛ

该方案的安全性依赖于CDH假设（Computational Diffie-Hellman）——给定(g,gˣ,gʸ)，计算gˣʸ是困难的。即使攻击者观察到β₀ʸ⁰和β₁ʸ¹，也无法提取出m₁₋ₛ的信息。

1.2 传统方案的性能瓶颈

在实际部署中，我们发现基础OT协议存在两个主要性能问题：

1. 接收方计算瓶颈：查询生成需要执行模幂运算，当消息规模增大时（如扩展到1-out-of-n OT），计算复杂度呈线性增长
2. 交互次数限制：标准OT协议要求发送方和接收方进行多轮交互，这在跨机构协作场景中会引入显著延迟

我们在金融数据共享项目中实测发现，当单次传输包含1000条记录（每条256位）时，接收方的查询生成时间达到120ms，成为系统吞吐量的主要瓶颈。

2. 外包化不经意传输协议设计

2.1 协议架构创新

本文提出的Delegated-Query OT（DQ-OT）通过引入第三方计算节点实现查询生成任务的外包，系统包含四个参与方：

1. 发送方(Sender)：持有消息对(m₀,m₁)，提供OT服务
2. 接收方(Receiver)：拥有选择位s，最终获取mₛ
3. 查询服务器(P₁,P₂)：协助生成OT查询，不接触最终消息

关键创新在于将原始OT中接收方的计算任务分解为两个可并行执行的轻量级操作：

接收方： 1. 使用秘密分享SS(1^λ,s,2,2)→(s₁,s₂) 2. 生成随机数r₁,r₂←ℤₚ 3. 将(s₁,r₁)发送给P₁，(s₂,r₂)发送给P₂ P₂服务器： 1. 计算δₛ₂ = gʳ², δ₁₋ₛ₂ = C/gʳ² 2. 发送(δ₀,δ₁)给P₁ P₁服务器： 1. 计算βₛ₁ = δ₀·gʳ¹, β₁₋ₛ₁ = δ₁/gʳ¹ 2. 发送(β₀,β₁)给发送方

2.2 安全性证明框架

在模拟安全模型下，我们需要证明对于任何现实世界的攻击者A，存在理想世界的模拟器Sim，使得两个世界的视图不可区分。以腐败接收方为例：

真实世界视图： Viewᴿ = {r_R, g, C, p, e₀, e₁, mₛ} 包含所有交互记录

模拟器构造：

1. 初始化空视图，添加随机数r'_R
2. 随机选择C',r'₁,r'₂,y'₀,y'₁←ℤₚ
3. 构造模拟响应：
   • e'_ₛ = (gʸ'ˢ, H(β'ˢʸ'ˢ)⊕mₛ)
   • e'₁₋ₛ = (gʸ'¹⁻ˢ, u) ← 随机数填充

通过CDH假设和随机预言机模型，可以证明真实响应与模拟响应在计算上不可区分。关键点在于：

• 当s=0时，β₀ = gʳ²⁺ʳ¹，β₁ = gᵃ⁻ʳ²⁻ʳ¹
• 当s=1时，β₀ = gᵃ⁻ʳ²⁺ʳ¹，β₁ = gʳ²⁻ʳ¹

攻击者无法通过β的分布推断s的信息，因为所有β值在ℤₚ上均匀分布。

3. 协议优化与性能分析

3.1 批量处理扩展（DQMR-OT）

为支持批量消息传输，我们设计多轮次优化版本：

# 发送方初始化 def Init(λ): p ← 安全素数(λ) g ← ℤₚ*的生成元 C ← gᵃ (a←ℤₚ) return pk = (C,p,g) # 批量响应生成 def GenRes(messages, pk, q): for t in 0...z-1: y₀ᵗ,y₁ᵗ ← ℤₚ e₀ᵗ = (gʸ₀ᵗ, H(β₀ʸ₀ᵗ)⊕m₀ᵗ) e₁ᵗ = (gʸ₁ᵗ, H(β₁ʸ₁ᵗ)⊕m₁ᵗ) return (e₀⁰,e₁⁰),...,(e₀ᶻ⁻¹,e₁ᶻ⁻¹)

性能测试显示，当z=1000时：

• 传统OT总耗时：约450ms
• DQ-OT总耗时：约180ms（其中接收方本地计算仅15ms）
• 网络开销：增加约12%（主要来自服务器间协调）

3.2 通信模式优化

协议支持发送方推送模式（Sender-push），其形式化定义为：

∀t: Action_R(t) ∩ {SendRequest(R,S)} = ∅ ∀t: Action_S(t) ⊆ {SendMessage(S,R)}

该特性使得在物联网数据采集场景中，设备可以预先配置OT参数，之后无需接收方在线请求即可推送加密数据。我们在智能电表项目中应用此模式，使通信延迟降低40%。

4. 工程实现中的关键问题

4.1 参数选择建议

根据NIST标准，我们推荐以下安全参数组合：

4.2 典型错误排查

1. 验证失败：

   • 现象：发送方检测到β₀·β₁ ≠ C
   • 原因：服务器P₁或P²被恶意篡改
   • 解决方案：启用Schnorr签名验证服务器身份

2. 消息解密错误：

   • 检查点：
     • 确认所有参与方使用相同的群参数(p,g)
     • 验证秘密分享的完整性（如使用Feldman VSS）
   • 调试方法：

     # 调试输出中间值 debug_print(f"x={r2 + r1*(-1)**s2}") debug_print(f"Hash input: {pow(g_y_s, x, p)}")

3. 性能下降：

   • 常见原因：
     • 使用非优化的大数库（应选择GMP或OpenSSL）
     • 网络延迟高于预期
   • 优化策略：
     • 预计算gʳ等固定基指数
     • 采用流水线化批处理

5. 应用场景实例

5.1 隐私保护的数据检索

在医疗研究数据共享平台中，DQ-OT可实现以下隐私保障：

• 研究员（接收方）选择获取特定患者的某项检测结果
• 医院（发送方）不知道被查询的患者ID
• 查询服务器无法获知最终传输的内容

具体实现流程：

1. 医院预先加密所有患者记录{(m₀ⁱ,m₁ⁱ)} i=1...n
2. 研究员对目标索引s生成外包查询
3. 第三方服务器协助完成OT传输
4. 研究员仅能解密mₛ，无法获取其他患者信息

5.2 安全外包计算

结合同态加密，DQ-OT可构建安全函数评估协议：

客户端输入x，服务端持有函数f 1. 服务端生成真值表(f(0),f(1)) 2. 通过DQ-OT传输f(x) 3. 查询服务器协助计算但不知x和f(x)

我们在联合信用评估模型中应用此方案，使银行能在不暴露客户收入等敏感数据的情况下，获取风险评估结果。

6. 协议限制与改进方向

当前方案存在以下待解决问题：

1. 主动安全性：现版本仅针对半诚实敌手，需添加零知识证明来抵抗恶意行为
2. 前向安全性：长期密钥泄露会导致历史通信被解密
3. 量子抵抗：基于离散对数的构造易受量子算法攻击

一个可行的改进是采用格密码基元替换现有方案。初步实验表明，基于RLWE的外包OT可实现：

• 量子安全性
• 接收方计算复杂度降至O(λ²)
• 密文膨胀率约3.5倍（相比经典方案）

在实际部署中，我们建议根据具体场景的安全需求，在经典效率和量子安全之间做出权衡选择。对于医疗、金融等高价值数据，即使性能有所下降，也应优先考虑后量子安全方案。