在安全多方计算（Secure Multi-Party Computation, MPC）的庞大理论体系中，不经意传输（Oblivious Transfer, OT）占据着一个极其特殊的位置——它既是最简单的两方安全计算原语之一，又被证明具有”密码学完备性”，即任何安全计算协议都可以由 OT 构建而来。与此同时，隐私信息检索（Private Information Retrieval, PIR）作为一种让用户在不泄露查询意图的前提下从远程数据库获取条目的技术，从理论上的纯粹优雅逐步走向了工程上的可部署状态。本文将从 OT 的经典定义出发，沿着 OT 扩展与静默 OT 的效率演进之路前行，再转入 PIR 的理论基础与近年来的实用化突破，最后审视这两大原语在真实系统中的应用图景。
一、不经意传输的定义与历史
不经意传输的概念最早由 Michael Rabin 于 1981 年提出。Rabin 的原始方案（Rabin OT）基于大整数分解假设：发送方（Sender）将一条消息通过 RSA 加密后发送给接收方（Receiver），接收方有约 1/2 的概率能够解密成功，而发送方无法得知接收方是否成功解密。这一模型虽然在概念上颇具启发性，但在实际应用中并不方便直接使用。
1985 年，Even、Goldreich 和 Lempel 提出了如今更为常用的”二选一不经意传输”（1-out-of-2 OT，记作 OT₂¹）。在该协议中，发送方持有两条消息 m₀ 和 m₁，接收方持有一个选择比特 b∈{0,1}。协议执行结束后，接收方恰好获得 m_b，而对 m_{1−b} 一无所知；与此同时，发送方无法判断 b 的取值。这两条安全性要求分别被称为”发送方隐私”（sender privacy）与”接收方隐私”（receiver privacy），也可以用更形式化的术语描述为：接收方的视图在计算上无法区分 m_{1−b} 的不同取值，而发送方的视图在计算上无法区分 b=0 与 b=1。
在 1-out-of-2 OT 的基础上，研究者进一步推广到”n 选一不经意传输”（1-out-of-n OT，记作 OTₙ¹）：发送方持有 n 条消息 m₀, m₁, …, m_{n−1}，接收方持有索引 i∈{0,…,n−1}，协议结束后接收方仅得到 m_i。当 n=2 时退化为经典的 OT₂¹。
一个深刻的理论结果是，Rabin OT、1-out-of-2 OT 和 1-out-of-n OT 在计算复杂性意义下是等价的——任何一种都可以通过黑盒归约高效地构造出其他形式。Crépeau 在 1987 年首先证明了 Rabin OT 与 1-out-of-2 OT 之间的等价性；后来 Brassard、Crépeau 和 Robert 进一步完善了这一结果。这种等价性意味着我们只需要关注如何高效实现其中一种形式，其余变体便自动可得。在现代密码学文献中，“OT”一词若无特别说明，通常即指 1-out-of-2 OT。
二、基于公钥的 OT 构造
实现 OT 需要某种形式的计算困难性假设——信息论意义上的安全 OT 在标准模型中是不可能的（Impagliazzo 和 Rudich 于 1989 年证明了这一不可能性结果）。因此，所有实际的 OT 协议都依赖于公钥密码学假设。
最经典的高效 OT 协议之一是 Naor 和 Pinkas 于 2001 年提出的方案（Naor-Pinkas OT）。该协议基于 Diffie-Hellman（DH）假设，在随机预言机模型（Random Oracle Model）下可证明安全。其核心思想如下：设 G 为一个素阶 q 的循环群，g 为生成元，H 为随机预言机。
协议流程概述：发送方选取随机数 a，计算 A=gᵃ 并发送给接收方。接收方根据选择比特 b 的值，若 b=0 则选取随机数 k，令 B=gᵏ；若 b=1 则令 B=A/gᵏ=gᵃ⁻ᵏ。接收方将 B 发送给发送方。此时发送方计算 k₀=H(Bᵃ) 和 k₁=H((A/B)ᵃ)，分别用 k₀ 和 k₁ 加密 m₀ 和 m₁ 后发回。接收方能够计算 Aᵏ=gᵃᵏ 从而导出 k_b，解密得到 m_b，但由于判定性 Diffie-Hellman（DDH）假设的困难性，无法计算另一个密钥 k_{1−b}。
2015 年，Chou 和 Orlandi 提出了所谓的”最简 OT 协议”（Simplest OT Protocol），将上述思想进一步精简。该协议仅需一轮半通信（即发送方发送一条消息，接收方回复一条消息，发送方再回复一条消息），在椭圆曲线群上实现时，每次执行仅需三次群指数运算和两次哈希运算，通信量也极低。该协议在随机预言机模型下基于间隙 DH（Gap-DH）假设被证明是安全的。
在安全性证明方面，OT 协议通常采用模拟范式（simulation paradigm）：分别构造一个发送方模拟器和一个接收方模拟器，证明在相应的腐败模型下，真实协议的执行与理想世界中的执行在计算上不可区分。对于半诚实（semi-honest）安全性，模拟器的构造相对直接；对于恶意（malicious）安全性，则需要额外的技巧，如零知识证明或切割-选择（cut-and-choose）技术来确保各方按照协议规定行事。
然而，公钥运算的代价是昂贵的。一次椭圆曲线标量乘法在现代硬件上大约需要数十微秒，这意味着当 MPC 协议需要数百万乃至数十亿次 OT 时，纯公钥方案的开销将变得不可承受。这直接催生了 OT 扩展技术的诞生。
三、OT 扩展
OT 扩展（OT Extension）的核心理念极为精妙：利用少量”昂贵”的公钥 OT（称为基础 OT，base OT）加上大量”廉价”的对称密码学运算（如哈希函数、伪随机生成器），将少量 OT 实例”扩展”为任意多的 OT 实例。
这一思想由 Beaver 于 1996 年首次提出，但真正使其实用化的里程碑是 Ishai、Kilian、Nissim 和 Petrank 于 2003 年提出的 IKNP 协议。IKNP 协议的巧妙之处在于，它仅需要 κ 次基础 OT（κ 为计算安全参数，通常取 128），即可将其扩展为任意 m 次 OT，其中 m 可以远大于 κ。额外的计算开销仅为 O(m) 次哈希运算和 O(m·κ) 比特的通信。
IKNP 协议的工作原理概述如下：假设我们需要执行 m 次 OT，其中在第 i 次 OT 中接收方的选择比特为 rᵢ。令 r=(r₁,…,rₘ) 为接收方的选择比特向量。
（一）基础 OT 阶段：此处的角色发生了巧妙的反转——原来的接收方在基础 OT 中充当发送方，原来的发送方充当接收方。发送方（在基础 OT 中作为接收方）选取 κ 个随机比特 s₁,…,sκ 作为选择比特，执行 κ 次基础 OT。对于第 j 次基础 OT，接收方（在基础 OT 中作为发送方）准备两个随机种子 kⱼ⁰ 和 kⱼ¹，发送方根据 sⱼ 的值获得其中一个。
（二）扩展阶段：接收方利用获得的种子，通过伪随机生成器（PRG）生成 κ 对 m 比特长的列向量。具体地，对于第 j 列，接收方计算 tⱼ⁰=PRG(kⱼ⁰) 和 tⱼ¹=PRG(kⱼ¹)，并构造矩阵使得 tⱼ¹=tⱼ⁰⊕r（其中 ⊕ 表示逐比特异或，r 为选择比特向量）。接收方将纠正向量 uⱼ=tⱼ⁰⊕tⱼ¹⊕r 发送给发送方。发送方据此可以计算出自己所需的矩阵行。
（三）去随机化阶段：发送方对矩阵的每一行使用哈希函数 H 导出两个密钥，分别用于加密自己的两条消息。接收方则利用自己拥有的行信息，仅能解密出对应于选择比特的那条消息。
IKNP 协议发表后，研究者们持续优化其效率。2013 年，Asharov、Lindell、Schneider 和 Zohner 提出了 ALSZ 优化方案，通过引入相关鲁棒性（correlation robustness）的更弱假设替代随机预言机，以及利用 AES-NI 等硬件加速指令来实现对称运算的极高吞吐量。在现代实现中（如 libOTe 库），IKNP 类协议可以在每秒钟内完成数百万次 OT，每次 OT 的摊销成本仅为几次 AES 加密运算。
此外，研究者还发展了”相关 OT”（Correlated OT）和”随机 OT”（Random OT）等变体。在随机 OT 中，发送方的两条消息和接收方的选择比特都是随机生成的而非预先指定的，这在许多 MPC 子协议中已经足够使用，并且可以在预处理阶段提前生成，进一步提升在线阶段的效率。
在深入更高级的 OT 变体之前，让我们用一张依赖关系图来俯瞰从基础 OT 到上层应用的完整技术栈：
OT 技术栈的依赖关系
┌─────────────────────────────────────────────────────┐
│ 应用层 │
│ ┌──────────┐ ┌──────────┐ ┌───────────────────┐ │
│ │ MPC │ │ PSI │ │ PIR │ │
│ │(GMW,SPDZ │ │(隐私集合 │ │ (隐私信息检索) │ │
│ │ TinyOT) │ │ 求交) │ │ │ │
│ └────┬─────┘ └────┬─────┘ └────────┬──────────┘ │
└───────┼─────────────┼────────────────┼──────────────┘
│ │ │
v v v
┌─────────────────────────────────────────────────────┐
│ OT 扩展层（大量、廉价） │
│ ┌──────────────────────────────────────────────┐ │
│ │ IKNP / ALSZ / Silent OT / VOLE │ │
│ │ 基于对称密码（哈希、PRG、AES） │ │
│ │ 每秒数百万次 OT，摊销成本 ≈ 几次 AES 运算 │ │
│ └──────────────────────┬───────────────────────┘ │
└─────────────────────────┼───────────────────────────┘
│ 仅需 κ 次（κ=128）
v
┌─────────────────────────────────────────────────────┐
│ 基础 OT 层（少量、昂贵） │
│ ┌──────────────────────────────────────────────┐ │
│ │ Naor-Pinkas / Simplest OT / Chou-Orlandi │ │
│ │ 基于公钥密码（DH、DDH、Gap-DH） │ │
│ │ 每次需要数次椭圆曲线标量乘法（数十微秒） │ │
│ └──────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────┘个人观察： OT 扩展是我认为应用密码学中最漂亮的结果之一。它的优美之处在于一个看似不可能的「炼金术」——用少量昂贵的公钥运算「引燃」大量廉价的对称运算，从而将公钥密码学的信任假设「传染」给对称密码学的效率。IKNP 的核心洞察（角色反转 + 矩阵转置）简洁到令人惊叹：仅 128 次基础 OT 就能扩展出任意多次 OT，增量成本几乎就是哈希运算的成本。这种「自举」思想在密码学中反复出现——FHE 的 bootstrapping、SNARKs 的递归组合——但 OT 扩展是最早也最干净的实例。它本质上回答了一个深刻的问题：公钥密码学的「高贵」究竟有多少需要为每一次使用买单？答案是：只需要买单一次，之后的边际成本趋近于零。
四、Silent OT 与最新进展
尽管 IKNP 及其变体已经将 OT 的计算成本压缩到了对称密码学的量级，但通信复杂度仍然是一个瓶颈——扩展 m 次 OT 需要 O(m·κ) 比特的通信，对于大规模应用场景来说依然可观。
2019 年，Boyle、Couteau、Gilboa 和 Ishai 提出了基于伪随机相关生成器（Pseudorandom Correlation Generator, PCG）的”静默 OT”（Silent OT）范式，实现了通信量的根本性突破。PCG 的核心思想是：两方各自持有一个短种子，通过本地计算即可”无声地”扩展出大量伪随机相关随机性（如 OT 相关或向量不经意线性求值 VOLE 相关），而无需进行与输出长度成正比的通信。
具体而言，Silent OT 协议的流程分为两个阶段。在种子分发阶段，双方通过少量的基础 OT（通常只需要 O(κ) 或 O(κ·log m) 次）交换 PCG 种子，通信量为次线性于 m 的。在本地扩展阶段，双方各自在本地运行 PCG 的扩展算法，将短种子扩展为 m 组 OT 相关。该阶段完全不需要通信，因此被称为”静默”的。
PCG 的构造通常基于学习奇偶性（Learning Parity with Noise, LPN）假设或其环上变体。Boyle 等人利用了一种称为”稀疏 LPN”友好的相关生成技术，使得 PCG 种子长度仅为 O(κ·√m) 甚至 O(κ·log²m)，相比 IKNP 的 O(m·κ) 通信量实现了指数级别的改进。
2020 年以来，Yang、Sarkar、Weng 和 Wang 等研究者在 VOLE（Vector Oblivious Linear Evaluation）方向取得了进一步突破。VOLE 可以看作 OT 的推广：发送方持有 (a,b)，接收方持有 x，协议使接收方获得 y=a·x+b，而不泄露 a 或 b。VOLE 与 OT 之间存在高效的归约关系，并且 VOLE 在许多零知识证明协议（如 Wolverine、Quicksilver）和 MPC 协议中具有更直接的应用。基于 PCG 的静默 VOLE 协议已经在 libOTe 等开源库中得到了高效实现。
一个经常被忽视的观点是：Boyle-Couteau-Gilboa-Ishai 的 Silent OT 工作的潜在影响力，可能不亚于当年 IKNP 对 OT 扩展的开创性贡献。IKNP 解决的是将 OT 的计算成本从公钥级降到对称级，但通信量仍然是线性的——扩展 m 次 OT 需要 O(m·κ) 比特的通信。Silent OT 则从根本上改变了通信的渐近图景：通过伪随机相关生成器（PCG），两方在交换 O(κ·log m) 级别的短种子后，可以在本地「静默地」扩展出 m 组 OT 相关，完全不需要进一步通信。这意味着 MPC 协议中 OT 相关的预处理阶段可以从「通信密集型」变成「计算密集型」——在带宽受限的广域网环境中，这种转变的实际意义是巨大的。笔者认为，Silent OT 的成熟可能会重新定义 MPC 协议的性能瓶颈分布，使得未来的优化重心从「减少通信」全面转向「加速本地计算」。
五、OT 在 MPC 中的核心角色
OT 在安全多方计算理论中的地位可以用一个定理概括——OT 完备性定理（OT Completeness Theorem）：任何可以安全计算的函数，都可以仅使用 OT 作为唯一的密码学原语来安全地计算。这一定理由 Kilian 于 1988 年首先证明，后来由 Ishai、Prabhakaran 和 Sahai 进一步完善和推广。
OT 完备性定理的意义在于：它将”构造任意安全计算协议”这一宏大问题，归约为了”高效实现 OT”这一具体问题。而正如我们在前几节所见，OT 的高效实现已经取得了长足的进步。
在实际的 MPC 协议构造中，OT 的应用无处不在。最经典的例子是 GMW 协议（Goldreich-Micali-Wigderson, 1987）。GMW 协议将任意布尔电路的安全计算分解为对每个门的逐门处理：对于异或门（XOR gate），各方可以通过本地计算完成；对于与门（AND gate），则需要一次 OT 来实现乘法的秘密共享。由于一个典型的布尔电路可能包含数十亿个与门，OT 扩展技术的效率直接决定了 GMW 协议的实用性。
另一个重要的应用是 TinyOT 协议族（Frederiksen、Jakobsen、Nielsen 等人的工作）。TinyOT 在预处理模型下运行：在离线阶段，双方使用 OT 扩展生成大量”认证比特”（authenticated bits）和”认证与三元组”（authenticated AND triples）；在在线阶段，利用这些预处理材料实现高效的恶意安全计算。TinyOT 的思想后来被 SPDZ 系列协议（Damgard、Pastro、Smart、Zakarias 等人的工作）推广到了算术电路上。
在混淆电路（Garbled Circuits）范式中，OT 同样不可或缺。Yao 的混淆电路协议要求对电路的每个输入线执行一次 OT，以便评估方获得与其输入对应的线标签。当使用 Free-XOR 和 Half-Gates 等优化技术时，混淆电路的主要开销转移到了通信上，而输入相关的 OT 往往可以通过预计算的随机 OT 在在线阶段以极低的延迟完成。
六、隐私信息检索定义
隐私信息检索（Private Information Retrieval, PIR）解决的是这样一个问题：服务器持有一个包含 n 个条目的数据库 D=(d₁,d₂,…,dₙ)，客户端希望获取第 i 个条目 dᵢ，但不希望让服务器知道 i 的值。最朴素的解决方案是让服务器将整个数据库发送给客户端，但这显然在通信效率上是灾难性的。PIR 的目标就是在保护查询隐私的同时实现亚线性（甚至多项对数级）的通信复杂度。
根据服务器数量的不同，PIR 分为两类。多服务器 PIR（Multi-Server PIR）假设数据库被复制到多台不共谋的服务器上。Chor、Goldreich、Kushilevitz 和 Sudan 于 1995 年开创性地证明了在双服务器模型下，可以实现信息论安全（information-theoretic security）的 PIR 方案，通信复杂度为 O(n^{1/3})。在这种模型中，只要服务器之间不共谋，即使服务器拥有无限的计算能力，也无法确定客户端查询的是哪个条目。
单服务器 PIR（Single-Server PIR）仅有一台服务器，此时信息论安全是不可能实现的（Chor 等人也证明了这一下界），因此必须依赖计算复杂性假设。单服务器 PIR 通常也称为计算性 PIR（Computational PIR, cPIR）。在 cPIR 中，服务器在多项式时间内无法区分对不同索引的查询，但若拥有无限计算能力则可以。
此外，PIR 还有一个更强的变体——对称 PIR（Symmetric PIR, SPIR）。在 SPIR 中，不仅服务器不知道客户端查询的索引，客户端也不会获得除 dᵢ 之外的任何信息。SPIR 可以看作 PIR 与 1-out-of-n OT 的结合体；事实上，在单服务器场景下，SPIR 恰好等价于 OTₙ¹。这一等价关系深刻地揭示了 OT 与 PIR 之间的内在联系。
从工程实践来看，PIR 只解决了隐私数据库访问问题的一半——它保护的是读操作的访问模式（服务器不知道你查了哪条记录），但真实的数据库应用还需要写操作，而写操作的访问模式同样是敏感的。不经意 RAM（Oblivious RAM, ORAM）正是为保护读写访问模式而设计的原语，但它付出的代价令人望而却步：最优 ORAM 方案的开销是 O(log n) 到 O(log²n) 的乘法因子，这意味着对一个 10 亿条目的数据库，每次访问需要额外的 30-900 倍开销。笔者认为，这个巨大的效率鸿沟——PIR 的读保护已经接近实用，但 ORAM 的读写保护仍然代价高昂——是密码学中最困难的未解工程问题之一。它深刻地揭示了一个不对称性：隐藏「你读了什么」比隐藏「你改了什么」在本质上更容易，因为读操作可以利用同态加密的非交互性，而写操作不可避免地涉及状态更新，必须以某种方式反映在服务器端的数据结构中。
七、经典 PIR 方案
1997 年，Kushilevitz 和 Ostrovsky 提出了第一个单服务器计算性 PIR 方案（KO 方案）。该方案基于二次剩余（Quadratic Residuosity, QR）假设，通信复杂度为 O(n^ε)（对任意 ε>0），首次突破了信息论下界。KO 方案的核心思想是利用同态加密（homomorphic encryption）的性质：客户端对索引进行加密后发送给服务器，服务器在密文上进行计算，将整个数据库”压缩”到一个加密的结果中返回给客户端，客户端解密即可获得目标条目。
2005 年，Gentry 和 Ramzan 提出了基于 Paillier 加密的 PIR 方案（GR 方案），在通信复杂度上实现了进一步优化。Paillier 加密系统支持加法同态性，使得服务器可以高效地将数据库条目”叠加”到密文上。GR 方案的查询大小仅为 O(log n) 个密文，响应大小与单个条目的大小相当，在通信效率上已经相当接近理论最优。
Lipmaa 在 2005 年提出了基于 Damgard-Jurik 加密的递归 PIR 方案，利用递归结构将通信复杂度进一步压低。该方案将数据库视为多维数组，客户端在每个维度上发送一个加密查询向量，服务器逐维处理，逐步缩减中间结果的规模。这种递归策略后来成为许多高效 PIR 方案的标准技术。
进入格密码（lattice-based cryptography）时代后，PIR 的效率获得了质的飞跃。基于环上学习带误差（Ring Learning with Errors, RLWE）假设的全同态加密（Fully Homomorphic Encryption, FHE）或层级同态加密（Leveled Homomorphic Encryption）为 PIR 提供了新的构造范式。与传统方案相比，格基方案的优势在于：（一）格上的运算可以利用数论变换（Number Theoretic Transform, NTT）进行高效的多项式乘法，速度远超大整数模运算；（二）RLWE 密文可以天然地打包多个明文槽（plaintext slots），实现批量处理；（三）格基假设目前被认为可以抵抗量子攻击，具有后量子安全性。
八、实用 PIR 突破
尽管理论上的 PIR 方案已经发展了二十余年，但长期以来，它们在实用性上一直受到严苛的计算开销制约——服务器需要对整个数据库进行至少一次完整的线性扫描，这在数据库规模达到数 GB 时意味着数秒乃至数分钟的延迟。近年来，一系列工作开始打破这一实用性壁垒。
2022 年，Henzinger、McMahan、Pirber、Raykova 和 Upadhyay 提出了 SimplePIR，这是迄今为止计算开销最低的单服务器 PIR 方案之一。SimplePIR 基于 LWE（Learning with Errors）假设，其核心洞察是：如果将数据库排列为一个 √n × √n 的矩阵，客户端的查询可以表示为一个 LWE 加密的单位向量，服务器只需计算一个矩阵-向量乘法即可生成响应。由于矩阵-向量乘法可以高度并行化，并且可以利用 SIMD 指令集（如 AVX-512）进行加速，SimplePIR 在一台普通服务器上处理 1 GB 数据库时，吞吐量可达每秒数十 GB，单次查询的服务器计算时间仅约 10 毫秒。
SimplePIR 的通信开销与 √n 成正比，这对于非常大的数据库来说仍然可观。为此，同一研究团队提出了 DoublePIR，通过引入两层递归结构，将通信复杂度降低到 O(∛n) 量级，代价是服务器计算量略有增加。在实际参数下，对于 1 GB 的数据库，DoublePIR 的查询和响应大小均可控制在数百 KB 以内。
2022 年，Menon 和 Wu 提出的 Spiral 方案则代表了另一个重要方向。Spiral 基于 RLWE 的全同态加密，利用密文在环上的紧凑表示和 Galois 自同构（Galois automorphism）操作实现高效的”密文选择”。Spiral 的一个关键优化是利用了 RLWE 密文的”免费”旋转操作来替代显式的乘法，从而在保持低通信开销的同时降低了服务器的计算量。对于百万级条目的数据库，Spiral 的查询大小约为 14 KB，响应大小约为 15 KB，通信效率极为优异。
OnionPIR（Mughees、Chen 和 Ren，2021）则采用了基于 TFHE（Torus FHE）的技术路线，利用可编程自举（programmable bootstrapping）实现了对查询的非线性处理能力，在某些参数配置下具有竞争力。
以下给出一些代表性方案在 1 GB 数据库上的典型性能基准（近似值，具体取决于硬件和参数配置）：SimplePIR 的服务器吞吐量约为 10 GB/s，单次查询延迟约 10ms，通信量约 121 MB（以 √n 为主要开销）；DoublePIR 的吞吐量约 6 GB/s，延迟约 50ms，通信量约 200 KB；Spiral 的吞吐量约 1-2 GB/s，延迟约 200ms，通信量约 30 KB。这些数据表明，PIR 已经从”理论上可能但实际不可行”迈入了”在特定场景下可部署”的新阶段。
九、应用场景
OT 与 PIR 的应用场景涵盖了隐私保护的众多方面。除了下文详述的具体场景外，这两大原语还在医疗健康领域（如基因组隐私查询——患者希望在不向医疗数据库暴露自身基因位点信息的前提下获取遗传病风险评估结果）、金融合规领域（如反洗钱名单筛查——银行需要将客户信息与制裁名单进行匹配，但不希望将完整客户名单泄露给名单提供方）以及供应链管理领域（如多方价格比较——参与方希望得知最低报价但不愿公开各自的出价）展现出广泛的应用潜力。随着隐私保护计算平台的成熟和法规驱动力的增强，OT 与 PIR 正从学术原语演变为实际产品的核心组件。
在隐私 DNS 查询（Private DNS）领域，用户向 DNS 解析器发起域名查询时，传统的明文 DNS 协议会暴露用户的浏览意图。虽然 DNS-over-HTTPS（DoH）和 DNS-over-TLS（DoT）加密了传输通道，但解析器本身仍然知道用户查询了哪些域名。基于 PIR 的隐私 DNS 方案可以让用户在不向解析器泄露查询域名的前提下获得解析结果。Cloudflare 的 Oblivious DNS-over-HTTPS（ODoH）方案结合了代理转发与加密，而纯 PIR 方案则提供了更强的隐私保障。
证书透明度检查（Certificate Transparency Checking）是另一个重要的应用场景。在 Web PKI 体系中，浏览器需要验证网站证书是否已被正确地记录在证书透明度（CT）日志中。然而，直接向 CT 日志服务器查询会泄露用户正在访问的网站。Chrome 团队和学术研究者探索了基于 PIR 的隐私保护 CT 检查方案，使用户能够在不暴露浏览行为的前提下验证证书的有效性。
私密联系人发现（Private Contact Discovery）在端对端加密通讯应用中至关重要。当用户注册 Signal 或 WhatsApp 等应用时，应用需要确定用户通讯录中哪些联系人也使用了该应用。如果简单地将通讯录上传到服务器进行匹配，用户的社交关系图将完全暴露。Signal 采用了基于 SGX 可信执行环境和 PIR 技术相结合的方案来实现私密联系人发现。近年来，基于 OT 和隐私集合求交（Private Set Intersection, PSI）的纯密码学方案也取得了显著进展，KKRT（Kolesnikov、Kumaresan、Rosulek、Trieu）协议利用 OT 扩展实现了高效的 PSI，每秒可比对数百万个元素。
在隐私保护广告定向（Privacy-Preserving Ad Targeting）领域，广告商希望根据用户的兴趣投放广告，但用户不希望暴露自己的行为数据。PIR 可以使用户在本地持有兴趣标签的情况下，从广告数据库中私密地检索相关广告。Google 的 Privacy Sandbox 项目中的若干提案就借鉴了类似的密码学原语来平衡广告效果与用户隐私。
Python 示例：简化的 1-out-of-2 OT 协议演示
以下代码演示了一个基于离散对数假设的简化 1-out-of-2 OT 协议。为了说明核心思想，我们使用小素数群并省略了某些安全性加固措施。在生产环境中应使用标准的椭圆曲线库和经过审计的实现。
"""
简化 1-out-of-2 OT 协议演示（基于离散对数）
安全性假设：DDH（Decisional Diffie-Hellman）
注意：此代码仅用于教学目的，参数不满足实际安全需求
"""
import hashlib
import secrets
# ============ 公共参数 ============
# 选取一个安全素数 p 和生成元 g（此处使用小参数仅做演示）
p = 0xFFFFFFFFFFFFFFC5 # 一个 64 位素数（演示用，实际需 2048+ 位）
g = 5 # 生成元
def mod_pow(base, exp, mod):
"""模幂运算"""
return pow(base, exp, mod)
def hash_to_key(value: int) -> bytes:
"""将群元素哈希为对称密钥（模拟随机预言机 H）"""
return hashlib.sha256(value.to_bytes(32, 'big')).digest()
def xor_bytes(a: bytes, b: bytes) -> bytes:
"""逐字节异或，用作一次性密钥加密"""
return bytes(x ^ y for x, y in zip(a, b))
def pad_message(msg: str) -> bytes:
"""将消息填充到 32 字节以匹配密钥长度"""
raw = msg.encode('utf-8')
assert len(raw) <= 32, "消息长度不能超过 32 字节"
return raw.ljust(32, b'\x00')
# ============ 发送方 ============
class Sender:
def __init__(self, m0: str, m1: str):
self.m0 = pad_message(m0)
self.m1 = pad_message(m1)
self.a = secrets.randbelow(p - 2) + 1 # 随机私钥 a
self.A = mod_pow(g, self.a, p) # 公钥 A = g^a mod p
def get_public_key(self) -> int:
"""第一步：发送方将 A 发送给接收方"""
return self.A
def encrypt_messages(self, B: int) -> tuple:
"""第三步：发送方根据 B 加密两条消息"""
# k0 = H(B^a mod p)
k0 = hash_to_key(mod_pow(B, self.a, p))
# k1 = H((A/B)^a mod p) = H((A * B^{-1})^a mod p)
B_inv = mod_pow(B, p - 2, p) # 费马小定理求逆
A_div_B = (self.A * B_inv) % p
k1 = hash_to_key(mod_pow(A_div_B, self.a, p))
e0 = xor_bytes(k0, self.m0)
e1 = xor_bytes(k1, self.m1)
return e0, e1
# ============ 接收方 ============
class Receiver:
def __init__(self, choice_bit: int):
assert choice_bit in (0, 1), "选择比特必须为 0 或 1"
self.b = choice_bit
self.k = secrets.randbelow(p - 2) + 1 # 随机私钥 k
def choose(self, A: int) -> int:
"""第二步：接收方根据选择比特构造 B"""
if self.b == 0:
# b=0: B = g^k
self.B = mod_pow(g, self.k, p)
else:
# b=1: B = A * g^{-k} = A / g^k
gk_inv = mod_pow(mod_pow(g, self.k, p), p - 2, p)
self.B = (A * gk_inv) % p
self._A = A
return self.B
def decrypt(self, e0: bytes, e1: bytes) -> str:
"""第四步：接收方解密所选消息"""
if self.b == 0:
# 接收方知道 k，可计算 A^k = g^{ak}，与发送方的 B^a 相同
shared = mod_pow(self._A, self.k, p)
key = hash_to_key(shared)
plaintext = xor_bytes(key, e0)
else:
# 接收方知道 k，可计算 A^k = g^{ak}
# (A/B)^a = g^{ak}，而 B = A/g^k => B^a 不可直接算
# 但 A^k = g^{ak} = (A/B)^a（因为 B = A·g^{-k}）
shared = mod_pow(self._A, self.k, p)
key = hash_to_key(shared)
plaintext = xor_bytes(key, e1)
return plaintext.rstrip(b'\x00').decode('utf-8')
# ============ 协议执行 ============
def run_ot_protocol():
print("=" * 56)
print(" 简化 1-out-of-2 OT 协议演示")
print("=" * 56)
# 发送方持有两条消息
m0, m1 = "Hello-OT-Msg-0", "Hello-OT-Msg-1"
print(f"\n发送方的两条消息：m0 = '{m0}', m1 = '{m1}'")
for choice in (0, 1):
print(f"\n--- 接收方选择比特 b = {choice} ---")
sender = Sender(m0, m1)
receiver = Receiver(choice)
# 第一步：发送方 → 接收方：公钥 A
A = sender.get_public_key()
# 第二步：接收方 → 发送方：选择值 B
B = receiver.choose(A)
# 第三步：发送方 → 接收方：两个密文 (e0, e1)
e0, e1 = sender.encrypt_messages(B)
# 第四步：接收方解密
result = receiver.decrypt(e0, e1)
expected = m0 if choice == 0 else m1
other = m1 if choice == 0 else m0
print(f" 接收方成功获得：'{result}'")
print(f" 验证：结果 == m{choice}? {result == expected}")
print(f" 接收方无法获得 m{1 - choice} = '{other}'")
print(f"\n{'=' * 56}")
print(" 协议演示完成：发送方不知道 b，接收方只得到 m_b")
print("=" * 56)
if __name__ == "__main__":
run_ot_protocol()上述代码中，Sender 类和
Receiver 类分别模拟了 OT
协议中的发送方和接收方。协议的关键在于接收方构造 B
的方式：当 b=0 时，B=gᵏ，接收方知道离散对数 k
从而可以计算共享密钥；当 b=1 时，B=A·g⁻ᵏ，此时
A/B=gᵏ，接收方同样可以通过 k
计算共享密钥，但此时对应的是第二个密钥 k₁。在 DDH
假设下，发送方无法从 B 判断接收方选择了哪个比特，因为 gᵏ 和
A·g⁻ᵏ 在群中具有相同的分布。
总结来看，OT 与 PIR 这两大原语虽然诞生于理论密码学的土壤，却正在以愈发坚实的步伐走向实用。OT 扩展与静默 OT 将单次 OT 的成本压缩到了对称密码学的水平，使得亿级规模的安全计算成为可能；PIR 从 SimplePIR 到 Spiral 的演进则让私密数据库查询从学术论文走进了可部署的系统原型。随着后量子安全需求的日益迫切和隐私法规的不断强化，OT 与 PIR 必将在下一代隐私保护基础设施中扮演更加关键的角色。
密码学百科系列 · 第 45 篇