隐私集合计算学习笔记：从基础概念到各类 PSI 协议

这是一篇持续更新的复习笔记，用来整理《隐私集合计算中的关键技术》PPT 的学习内容。目前已经整理到 第 29 页。重点不是记住一堆缩写，而是理解各种 PSI 协议为什么出现、怎样运行，以及它们之间有什么联系。

以后学习这份 PPT 的新内容都会继续追加在本文末尾，并注明页码范围，已经讲过的内容不再重复。

先建立整张知识地图 #

隐私保护技术包含安全多方计算、差分隐私、同态加密、零知识证明、匿名化、联邦学习和可信执行环境等多个方向。

其中，安全多方计算（Secure Multi-Party Computation，MPC）研究的是：多方怎样在不公开各自输入的情况下，共同完成一个计算。

隐私集合计算（Private Set Operation，PSO）是 MPC 中的一类具体问题，当前最先接触的是：

• PSI（Private Set Intersection）：隐私集合求交；
• PSU（Private Set Union）：隐私集合求并。

假设 Alice 持有集合：

Bob 持有集合：

普通集合运算很简单：

“隐私”二字增加了一个重要要求：完成运算时，不应把交集之外的私有元素随意泄露给对方。

因此可以先这样记：

PSI 回答“我们共同拥有哪些元素”，PSU 回答“合起来一共有哪些元素”，同时尽量隐藏不该公开的集合信息。

PSI 到底能用来做什么 #

PSI 的本质是跨主体的数据匹配。两个主体不能直接交换完整名单，但又需要知道双方有哪些共同记录。

私有联系人发现 #

手机里有 500 个联系人，社交平台有大量注册用户。用户想知道通讯录里谁已经注册，却不希望把完整通讯录直接交给平台。

这里两个集合分别是：

• 用户的通讯录；
• 平台的注册用户。

PSI 输出共同联系人，而不是公开两边的完整名单。

广告转化率计算 #

广告平台知道“哪些人看过广告”，电商平台知道“哪些人购买了商品”。两边求交后可以得到：

这个交集能够帮助计算广告转化效果。广告平台不必交出全部曝光用户，电商也不必公开全部购买用户。

有时业务只需要交集大小，例如“共有 357 人完成购买”，不需要具体名单。这类功能称为 PSI Cardinality（PSI-CA）。

拼车和位置匹配 #

两名用户各有一组候选位置或路线。系统需要寻找共同上车点，却不应暴露双方的完整活动轨迹。PSI 可以用于寻找共同位置。

纵向联邦学习的数据对齐 #

这是最容易混淆、也最值得理解的应用。要讲清楚它，需要把“数据对齐”和“联合训练”分开。

数据对齐和纵向联邦学习不是一回事 #

假设银行掌握：

电商平台掌握：

双方想联合训练信用风险模型，但用户并不完全重合。第一步要找出双方都有记录的用户：

这一步叫作数据对齐、样本对齐或实体对齐。

数据对齐只是找姓名吗 #

不一定。姓名可能重名，也可能存在不同写法。真实系统常使用手机号、身份证号、邮箱、用户 ID，或者经过规范化和密码学处理的标识。

数据对齐真正解决的是：

银行中的这条记录和电商中的那条记录，是否属于同一个实体？

因此，找到共同用户并建立对应关系才叫数据对齐。找到以后，把双方没有的数据直接补到一张表中，并不叫数据对齐。

“逻辑上拼成一张表”是不是纵向联邦学习 #

也不是。对齐后，我们在逻辑上知道：

1

李四：银行掌握收入、贷款；电商掌握消费金额、购物频率。

但双方的原始数据仍然留在各自机构，并没有真的集中到同一张表。

纵向联邦学习的完整过程可以分成三步：

1. 数据对齐：用 PSI 找到共同用户；
2. 逻辑关联：确认两边哪些记录属于同一个人；
3. 联合训练：双方基于各自的特征计算必要的中间结果，共同训练一个模型。

所以更准确的定义是：

纵向联邦学习是多个参与方针对大致相同的用户，利用各自掌握的不同特征，在不直接集中原始数据的情况下联合训练模型。

训练模型是什么意思 #

训练模型就是让计算机从历史样本中学习规律。例如：

1

收入 + 贷款 + 消费金额 + 购物频率 → 是否违约

给模型许多已经知道结果的历史用户，模型逐渐学习输入特征与违约风险之间的关系。以后面对新用户，就可以输出风险预测。

PSI 不负责训练模型。它发生在训练之前，解决的是“参与训练的共同用户是谁”。

横向联邦学习与纵向联邦学习 #

两者可以用“行”和“列”来记：

横向联邦学习像增加更多“行”，纵向联邦学习像增加更多“特征列”。

PSI 中谁是发送方，谁知道结果 #

一种常见定义是：

• Sender 持有集合 $X$；
• Receiver 持有集合 $Y$；
• Receiver 最终获得 $X\cap Y$；
• Sender 不应得到 $Y$ 的私有信息；
• Receiver 不应得到 $X$ 中交集之外的元素。

但 Sender 和 Receiver 描述的是协议角色和输出权限，并不等同于“谁发送了网络消息”。多数 PSI 协议中双方都会发送数据。

更不能死记 Alice 永远是 Sender、Bob 永远是 Receiver。具体哪个参与方获得交集，要看协议设计：

• 可以只让一方得到完整交集；
• 可以让双方都得到交集；
• 可以只输出交集大小；
• 也可以把结果以秘密共享形式输出，双方都不能单独看到。

在当前学习的三种具体流程中：

因此，看协议时应先问三件事：双方各持有什么、交换什么、谁获得什么输出。

第 10 页：Hash PSI #

Hash PSI 是理解后续方案的起点。

假设 Alice 持有：

她用公开且统一的哈希函数 $H$ 计算：

Alice 把 $Z$ 发给 Bob。Bob 对自己的每个 $y_i$ 计算 $H(y_i)$，然后判断：

如果答案为真，Bob 就认为 $y_i$ 位于交集中。

相同的数据由不同的人计算，哈希值一样吗 #

只要满足下面两个条件，结果一定相同：

1. 输入的字节完全相同；
2. 使用相同的哈希算法和参数。

哈希函数是确定性的，不会因为计算者是 Alice 还是 Bob 而改变结果。

但“人眼看起来相同”不代表计算机收到的字节相同。例如：

1
2

李四
李四[末尾多一个空格]

两者的哈希完全不同。13800138000 与 +8613800138000 也不同。因此真实 PSI 系统在哈希前还需要进行数据规范化，例如统一手机号格式、大小写、空格和字符编码。

哈希碰撞会不会影响判断 #

理论上可能存在两个不同输入得到相同哈希：

这叫哈希碰撞。现代密码学哈希函数的目标是让攻击者极难构造这种碰撞。入门理解 Hash PSI 时，可以先把碰撞概率视为足够低，但工程设计仍需要选择安全的哈希函数。

Hash PSI 为什么不够安全 #

Alice 发送的是公开哈希值。如果元素来自很小、很容易猜测的空间，Bob 可以准备候选值逐个计算哈希。

例如，若集合元素只是 11 位手机号，Bob 可以对大量候选手机号计算哈希，再和 Alice 发来的哈希表比较。这叫字典攻击或穷举攻击。

所以“只发哈希”并不等于安全。Hash PSI 的优点是快、通信轮数少，缺点是对低熵数据的猜测攻击抵抗力不足。

第 11 页：DH PSI #

DH PSI 在哈希结果外又增加一层只有参与者自己知道的秘密指数。

Alice 随机选择秘密数 $\alpha$，对自己的元素计算：

Bob 随机选择秘密数 $\beta$，对自己的元素计算：

双方交换这些结果后，再分别进行一次指数运算，得到：

关键公式是：

如果 $x=y$，双方最终会得到相同的双重指数结果，因此可以进行匹配。

这里的直觉是：Alice 和 Bob 各自给数据上了一把秘密锁。由于指数运算顺序可以交换，相同元素最终会得到同样的“双锁结果”；外部观察者又不知道 $\alpha$ 和 $\beta$，不能像简单 Hash PSI 那样直接建立字典表。

DH PSI 与 ElGamal 有什么关系 #

RSA、ElGamal 都属于公钥密码，但数学体系不同。

ElGamal 中常见：

其中 $x$ 是私钥，$y$ 是公钥；加密时还会选择随机数 $k$：

DH PSI 与 ElGamal 都大量使用群上的指数运算，安全性与离散对数、Diffie-Hellman 类困难问题有关。因此，学过 ElGamal 后再看 $H(x)^\alpha$、$H(x)^{\alpha\beta}$，会比直接从零理解更自然。

严格实现时，$H(x)$ 不能只是任意整数，还要通过合适的 Hash-to-Group 方法映射到协议使用的密码群中。

第 12 页：RSA PSI 与盲签名 #

RSA 生成一对密钥：

教科书中的基础 RSA 关系可以写成：

也就是公钥加密、私钥解密。

数字签名解决的是身份与完整性问题，正确表述是：私钥签名、公钥验证。现实中的 RSA 加密和签名分别需要 OAEP、RSA-PSS 等安全编码，不能把“签名”简单等同为“私钥加密”。

现实系统都是公钥加密、私钥解密吗 #

大量数据通常不会直接用 RSA 或 ElGamal 加密，因为公钥运算较慢。实际系统通常使用混合方式：

1
2
3
4
5
6
7

公钥密码或 DH
        ↓
协商或封装一个会话密钥
        ↓
AES、ChaCha20 等对称密码
        ↓
高速加密大量数据

HTTPS 就采用这类总体思路。公钥密码常负责密钥协商、身份认证和数字签名，对称密码负责数据传输。

RSA PSI 的盲化、盲签名与去盲 #

设 Alice 的集合较小，Bob 的集合很大。Bob 持有 RSA 公私钥 $(N,e)$ 和 $d$。

Alice 对自己的元素 $x_i$ 先计算：

然后选择随机数 $r_i$，构造：

这一步叫盲化。Bob 看到的是掺入随机因子的 $m’$，不能直接看到原来的 $m$。

Bob 使用私钥对盲化后的消息计算：

代入 $m’$：

这个动作叫盲签名：Bob 完成了私钥运算，却不知道自己处理的原始消息。

Alice 收到 $s’$ 后，使用 $r_i$ 的模逆去盲：

最终得到：

三个概念要分清：

可以把它类比成把文件放进一个特殊信封：Bob 不打开信封就在外面盖章；Alice 拆掉信封后，得到等价于直接盖在文件上的章。

怎样通过盲签名找到交集 #

Bob 对自己的每个 $y_j$ 直接计算：

并把结果发给 Alice。Alice 已经通过盲签名和去盲得到了自己的 $H(x_i)^d$。如果 $x_i=y_j$，则：

Alice 比较两组结果，就能找出交集。

为什么让小集合方生成随机数 #

RSA 私钥运算比较昂贵。若 Alice 只有 1000 个元素，Bob 有 100 万个元素，让 Alice 对 1000 个元素盲化，Bob 在线处理这 1000 个盲化值，通常比反过来更合适。Bob 自己的大集合表示还可能提前预计算。

因此这类方法适合：

也就是非平衡 PSI。

三种 PSI 放在一起比较 #

这三种方法形成了一条清楚的学习路线：

1
2
3
4
5
6
7

直接比较 Hash
      ↓ 发现容易被猜测
加入 DH 秘密指数
      ↓ 需要理解公钥群运算
使用 RSA 盲化与盲签名
      ↓ 适配非平衡集合
根据业务规模和安全要求选择方案

PPT 第 13～14 页：同态加密 PSI 与多项式判零 #

前面已经学习了 Hash、DH 和 RSA PSI。第 13～14 页继续回答同一个问题：怎样在不暴露集合元素的情况下判断成员关系？这一部分引入同态加密，并用“乘积为零”和“多项式的根”完成判断。

先理解同态加密：密文也能参加计算 #

普通加密通常可以抽象成：

其中 $m$ 是明文，$c$ 是密文。没有私钥的人看到 $c$，无法知道 $m$。但普通密文主要用于保存和传输，要计算时通常需要先解密。

同态加密的特别之处在于：某些运算可以直接在密文上完成，解密后的结果等价于在明文上计算。

例如一种支持加法的同态加密满足：

这里的 $\oplus$ 表示某种“密文运算”，不一定是普通整数加号。计算方不知道 $a$ 和 $b$，却能得到 $a+b$ 的密文。持有私钥的人解密后得到：

一个容易理解的例子

医院甲保存患者人数 $120$，医院乙保存患者人数 $80$。双方不想公开各自人数，但需要得到总数。

如果使用加法同态加密，计算方可以拿到：

然后在密文上相加，得到：

计算方全程没有看到 120 和 80。最后由有解密权的一方得到 200。

因此可以先记住：

普通加密重点是“把数据藏起来”，同态加密还允许“藏着数据做计算”。

FHE 和 PHE 有什么区别 #

部分同态加密 PHE

PHE 是 Partially Homomorphic Encryption。它只支持一种运算，或支持范围有限的运算。

常见例子包括：

• Paillier：典型的加法同态；
• 某些形式的 ElGamal：典型的乘法同态。

例如加法同态方案通常能完成：

以及“密文乘明文常数”对应的：

但它不能随意把加法和乘法无限组合。

全同态加密 FHE

FHE 是 Fully Homomorphic Encryption。它支持足够丰富的密文加法和密文乘法，因此原则上可以组合出任意有限电路的计算。

这并不意味着 FHE 没有限制。真实方案还要考虑：

• 密文比明文大很多；
• 密文运算远慢于普通运算；
• 运算会引入噪声；
• 参数、乘法深度和是否需要自举都会影响性能。

所以 PPT 说 FHE 能力强，但“密文长度大、计算性能不占优势”，原因就在这里。

第 13 页：基于 FHE 的 PSI #

假设 Alice 持有：

Bob 持有：

目标是让 Bob 找到：

这一方案的直觉是：Bob 把自己的元素加密，Alice 不知道这些元素，却可以在密文上检测它们是否等于自己集合中的某个元素。

第一步：Bob 加密自己的集合

Bob 生成 FHE 密钥：

其中 $pk$ 是公钥，$sk$ 是私钥。然后对每个 $y_i$ 加密：

Bob 把 $c_i$ 发给 Alice，自己保留私钥。Alice 只看到密文，不知道 $y_i$。

第二步：Alice 在密文上构造“判零表达式”

Alice 针对每个 $c_i$ 计算：

严格来说，Alice 实际操作的是 $c_i=\operatorname{Enc}(y_i)$，上式写的是密文计算所对应的明文逻辑。$r_i$ 是 Alice 选择的非零随机数。

为什么这个乘积能判断成员关系？

如果 $y_i$ 等于 $X$ 中的某个元素，例如 $y_i=x_j$，乘积中一定出现：

于是：

反过来，如果 $y_i$ 不等于 $X$ 中的任何元素，每个差值通常都非零，乘积也非零。

因此：

第三步：Bob 解密并判断

Alice 把 $d_i$ 返回给 Bob。Bob 使用私钥解密：

如果：

就说明 $y_i\in X$；否则说明 $y_i\notin X$。Bob 对自己的每个元素都做判断，便得到交集。

用数字完整走一遍

假设：

先忽略密文，只观察计算的明文含义。

对于 $y=5$：

无论非零随机数 $r$ 是多少，$r\times0$ 仍然是 0，所以 Bob 解密后知道 5 属于交集。

对于 $y=3$：

乘积不是 0，因此 Bob 知道 3 不在 Alice 的集合中。

最终得到：

为什么要乘随机数 r_i

成员对应的结果必须保持为 0：

非成员对应的结果则被随机化：

如果 Alice 直接返回确定的非零计算结果，Bob 可能从结果大小、重复关系或其他结构中获得额外信息。随机数的作用是遮蔽这些非零值，让 Bob 主要只区分“0”和“非 0”。

需要注意，正式协议是在选定的有限域或模环中运算，并要求随机数和参数满足协议条件。本文的整数例子只用于解释判零思想。

第 14 页：基于 PHE 的多项式 PSI #

第 14 页不直接加密 Bob 的每个元素，而是让 Alice 把自己的集合编码成一个多项式。

一句话概括：

Alice 把集合元素变成多项式的根，加密多项式系数；Bob 用自己的元素在密文上求值，Alice 解密后识别交集。

第一步：把集合写成多项式

Alice 根据集合 $X$ 构造：

假设：

那么：

把集合中的元素代入，多项式的值一定是 0：

数学中，如果 $P(a)=0$，就称 $a$ 是 $P$ 的一个根。所以 $P(t)$ 的根恰好就是 Alice 的集合元素。

这就把集合成员判断转换成了多项式判零：

第二步：展开并加密多项式系数

把多项式展开：

Alice 不发送明文系数，否则 Bob 可能分析甚至还原多项式的根。Alice 加密每个系数：

然后把这些密文发给 Bob。

第三步：Bob 在密文上计算多项式值

Bob 知道自己的明文 $y_i$，因此知道 $y_i^j$。利用加法同态和“密文乘明文常数”，他可以计算：

这里有个容易产生的疑问：计算多项式不是需要乘法吗，为什么 PHE 也能做？

原因是 Bob 并没有把两个加密系数相乘。$a_j$ 是加密的，$y_i^j$ 是 Bob 已知的明文常数。很多加法同态方案可以把密文按明文常数缩放，再把结果相加，所以不需要 FHE 那样的任意密文乘法。

第四步：随机化并带回元素

Bob 选择非零随机数 $r_i$，计算：

然后发给 Alice 解密。

为什么还要加上 $y_i$？分两种情况看。

情况一：Bob 的元素属于交集

如果 $y_i\in X$，那么：

所以：

Alice 解密后直接得到这个共同元素，并能确认它属于自己的集合。

情况二：Bob 的元素不属于交集

如果 $y_i\notin X$，那么 $P(y_i)\neq0$，结果为：

由于 $r_i$ 是随机的，这个值被随机化，不应直接暴露 Bob 原来的 $y_i$。Alice 只把能与自己集合元素匹配的解密结果识别为交集。

用数字走完第 14 页 #

设 Alice 持有：

Alice 构造：

她加密系数 $1,-7,10$，把系数密文发给 Bob。Bob 持有：

Bob 处理元素 5

假设 Bob 选择 $r=13$：

Alice 解密得到 5。因为 $5\in X$，所以确认它是共同元素。

Bob 处理元素 3

假设 Bob 选择 $r=11$：

Alice 解密得到的值不是自己集合中的元素，于是不会把它加入交集。

最终得到：

同样，这只是帮助理解的整数演示。实际协议在有限域或模空间内计算，并需要避免编码冲突、模运算造成的误判以及恶意参与方攻击。

第 13 页和第 14 页到底有什么关系 #

两页看起来使用了不同技术，底层的成员判断却完全一致。

第 13 页直接计算：

第 14 页先定义：

再计算：

所以它们都依靠：

区别在于怎样安全完成这次判零计算。

把两页记成两条流程 #

第 13 页

第 14 页

常见疑问 #

为什么不直接把多项式发给 Bob

因为多项式的根就是 Alice 的集合元素。直接公开完整多项式，可能让 Bob 通过求根等方法恢复 Alice 的集合。加密系数正是为了让 Bob 能求值，却看不到系数和根。

为什么“结果为 0”能判断相等

因为构造中包含每一个差值 $(y_i-x)$。只要 $y_i$ 等于某个 $x$，对应差值就是 0，整个乘积也必然为 0。

随机数会不会把交集结果弄错

不会破坏成员对应的 0，因为：

它主要改变非零结果，用来减少非交集信息的泄露。正式协议还会限定随机数的取值范围，并在选定代数结构中证明正确性和安全性。

FHE 越强，为什么不全部使用 FHE

密码方案不仅要“能算”，还要考虑时间、内存、带宽和实现复杂度。如果任务只需要加法同态和明文常数乘法，PHE 已经够用，使用更重的 FHE 未必划算。

PPT 第 15 页：先弄懂一次 1-out-of-2 OT #

第 15～21 页属于同一条知识链：

第 15 页已经完整实现了一次 OT：Alice 把明文消息 $m_0,m_1$ 分别加密成 $C_0,C_1$ 发给 Bob，Bob 算出自己所选分支的密钥并解出 $m_b$。

什么是 1-out-of-2 OT #

OT 是 Oblivious Transfer，中文通常译为“不经意传输”。在 1-out-of-2 OT 中：

• Alice 是 Sender，持有两条消息 $m_0,m_1$；
• Bob 是 Receiver，持有选择位 $b\in{0,1}$；
• Bob 只得到 $m_b$，不能同时得到另一条消息；
• Alice 不知道 Bob 选择了 0 还是 1。

因此，“1-out-of-2”就是“从两条消息中秘密选择一条”。这里的 0 和 1 是两个分支的编号。

第 15 页的完整通信顺序 #

双方约定一个循环群、生成元 $g$ 和相应安全参数。以下指数都在协议规定的群中计算。

第一步：Alice 随机选择秘密指数。

Alice 随机选择秘密数 $\alpha$，计算：

然后把 $A$ 发给 Bob。Alice 不发送 $\alpha$。

第二步：Bob确定选择位并随机选择秘密指数。

Bob 决定选择位 $b\in{0,1}$。$b$ 是 Bob 想选哪条消息的输入，不一定是随机数；在某些随机 OT 场景中它才会随机产生。

Bob 再随机选择秘密数 $\beta$，计算：

然后把 $B$ 发给 Alice。Bob 不发送 $b$ 和 $\beta$。

第三步：Alice在本地生成两把候选密钥。

实际系统通常还会把这些群元素送入 KDF 或 Hash，得到固定长度的对称密钥。Alice 使用两把密钥分别保护消息：

Alice 把 $C_0,C_1$ 都发给 Bob，但不会发送 $K_0,K_1$。

第四步：Bob自己计算解密密钥。

Bob 在本地计算：

这把密钥不是 Alice 通过网络发来的。协议利用 DH 的交换性质，让它自动等于 Alice 两把密钥中的一把。

为什么 Bob 的密钥恰好匹配一把 #

如果 Bob 选择 $b=0$：

于是：

所以 Bob 能用 $K_B$ 解开 $C_0$，得到 $m_0$。

如果 Bob 选择 $b=1$：

因此：

所以 Bob 能解开 $C_1$，得到 $m_1$。

这不是双方把密钥发出来进行比较，而是：

Bob 自己算出的密钥天然落在所选分支上。

Bob 解出明文，为什么还不一定等于求出了交集 #

PPT 中的 $m_0,m_1$ 的确是 Alice 持有的两条明文消息。Alice 用两把密钥加密它们：

Bob 根据选择位 $b$ 算出对应密钥 $K_B$，因此可以解开 $C_b$，得到 $m_b$。到这里，1-out-of-2 OT 已经成功完成。

但“得到所选消息”和“得到集合交集”是两个层次：

• OT 只保证 Bob 从两条消息中秘密取得一条；
• PSI 还要定义这两条消息分别表示什么，以及 Bob 怎样根据解出的内容判断自己的某个元素是否也属于 Alice 的集合；
• 如果后续已经把 $m_0,m_1$ 设计成某个元素的匹配结果、标签或解密材料，那么 Bob 解出 $m_b$ 就是在执行 PSI 的一个具体步骤；
• 如果 $m_0,m_1$ 只是普通消息，那么这次 OT 本身不会自动产生交集。

例如，Alice 的两条消息只是“苹果”和“香蕉”，Bob 解出“香蕉”，只能说明他秘密选择了第二条消息。若协议另行规定“能正确解出的标签表示元素存在于交集”，Bob 才能据此完成相应的交集判断。因此，第 15 页完成了 OT；它是否已经产生 PSI 信息，取决于 PPT 后续怎样定义 $m_0,m_1$ 的含义。

这种公式是固定规则吗 #

OT 的功能目标是固定的：Sender 有两条消息，Receiver 秘密选择其中一条。但 $B=A^bg^\beta$ 并不是所有 OT 必须采用的公式，它是这个 DH-based OT 为实现功能目标而设计的数学结构。

可以把设计思路反过来看：协议希望实现“$b=0$ 时匹配 $K_0$，$b=1$ 时匹配 $K_1$”，因此构造了 $B,K_0,K_1$ 的上述关系。

容易混淆的提醒： 这里使用了 DH 的共享值性质，但没有使用 ElGamal 的完整加密格式；也没有通过“比较两把密钥”决定结果。

PPT 第 16～21 页：IKNP OT 扩展 #

如果 PSI 需要上百万次 OT，而每次都运行第 15 页的公钥运算，成本会很高。OT Extension 的作用是：

这里学习的是 IKNP 的核心构造。它不改变 OT 的功能，只降低批量生成 OT 的成本。

先看最终想得到什么 #

设最终要扩展出 $n$ 个 OT。对于每个 $i$：

• Alice 最终拥有两个候选密钥 $(K_i^0,K_i^1)$；
• Bob 拥有选择位 $r_i\in{0,1}$；
• Bob 只拥有 $K_i^{r_i}$；
• Alice 不知道每个 $r_i$。

安全参数记作 $\lambda$，一般远小于 $n$。PPT 的小矩阵只是演示，实际 $\lambda$ 会按安全要求选取。

五个符号先分清 #

$r_i$ 和 $s_j$ 不是同一个选择：$r_i$ 控制第 $i$ 个最终 OT，$s_j$ 控制第 $j$ 个 Base OT。

用到的知识： 第 15 页的 1-out-of-2 OT、比特 XOR、矩阵的行列、Hash。

暂时不用： 集合元素、交集判断、同态加密和 RSA。此处生成的是后续协议要用的密钥材料。

第一步：Bob把最终选择编码成矩阵 R #

Bob 有选择向量：

每个 $r_i$ 表示第 $i$ 个最终 OT 选择 0 分支还是 1 分支。它是协议输入；如果 PPT 的特定构造要求随机 OT，可以随机选择，但一般不能把所有选择位都默认说成随机数。

Bob 把每个 $r_i$ 横向重复 $\lambda$ 次，得到 $n\times\lambda$ 矩阵 $R$。若 $r_i=0$，第 $i$ 行全为 0；若 $r_i=1$，第 $i$ 行全为 1。

第二步：Bob随机生成 T，再构造 T' #

Bob 随机生成 $n\times\lambda$ 比特矩阵 $T$，然后定义：

$\oplus$ 表示逐位 XOR：

因此：

对第 $i$ 行有：

“逐位相反”就是相同位置一个为 0、另一个为 1，所以两行 XOR 后得到全 1。

第三步：角色暂时反转，按列做 Base OT #

最终大量 OT 中 Alice 是 Sender、Bob 是 Receiver；但在 $\lambda$ 次 Base OT 中角色反过来：

• Bob 是 Base OT 的 Sender；
• Alice 是 Base OT 的 Receiver。

Bob 把 $T$ 的第 $j$ 列 $T^{(j)}$ 和 $T’$ 的第 $j$ 列 $T’^{(j)}$ 作为两条消息。Alice 随机选择长度为 $\lambda$ 的秘密比特串：

在第 $j$ 次 Base OT 中：

这不是从矩阵推导出的自然规律，而是 1-out-of-2 OT 接口中事先约定的分支编号：选择位 0 取第一条，选择位 1 取第二条。

因为矩阵只有 $\lambda$ 列，所以这里只运行 $\lambda$ 次昂贵的 Base OT，而不是 $n$ 次。

第四步：Alice把收到的列拼成 Q #

Alice 每次 Base OT 得到一列，把 $\lambda$ 列按原顺序拼起来，形成 $n\times\lambda$ 矩阵 $Q$。

这一步的视角切换非常关键：

前半段按列做 $\lambda$ 次 Base OT，后半段按行解释成 $n$ 个扩展 OT。

$Q$ 不是交集，也不是集合匹配结果；它是 Alice 得到的相关随机比特矩阵。

第五步：推导 q_i 与 t_i 的关系 #

观察第 $i$ 行、第 $j$ 列。Alice 根据 $s_j$ 选 $T$ 或 $T’$ 的第 $j$ 列，而：

因此：

$\land$ 表示 AND。把一整行合起来：

于是得到：

这个关系不是所有 OT 天生遵守的定律，而是采用 $T’=T\oplus R$ 和按 $s_j$ 选列之后推导出的必然结论。

第六步：为什么 Alice 还要形成两个候选值 #

仅有 $q_i$ 与 $t_i$ 的相关性，还没有明确形成标准 OT 的两个分支。Alice 对每一行定义：

Bob 始终持有 $t_i$：

所以 Bob 的 $t_i$ 恰好等于 Alice 两个候选值中的一个。这时第 $i$ 个扩展 OT 的“二选一”结构才真正形成。

第七步：Hash 成为可用的密钥 #

Alice 计算：

Bob 计算：

于是：

这里的 $\parallel$ 表示拼接，$i$ 是第几次 OT 的编号。把编号放进哈希输入，可以让不同行即使碰巧出现相同的比特串，也使用不同的密钥。Hash 在这里用于把相关比特串变成适合后续使用的密钥材料。它不是第 10 页那种“直接对集合元素做 Hash 再求交”的 Hash PSI，也没有用 Hash 直接判断交集。

用一个小矩阵走完 OT 扩展 #

下面的数字仅用于教学演示，安全参数很小，不能用于真实系统。

设最终需要 $n=3$ 个 OT，演示用 $\lambda=2$。Bob 的选择向量取：

这里 $r$ 表示示例中希望选择的分支，不把它说成随机数。扩展后：

Bob 随机选择示例矩阵：

计算：

Alice 随机选择 Base OT 选择向量：

第 1 次 Base OT 中 $s_1=1$，Alice 取得 $T’$ 的第 1 列；第 2 次中 $s_2=0$，取得 $T$ 的第 2 列。拼接得到：

逐行检查：

还差最后一步：把每一行的关系变成真正可使用的一次 OT。Alice 对每行算出两个候选比特串；Bob 用自己持有的 $t_i$ 算出其中一个：

例如第 2 行，$q_2=11$，而 $s=10$，所以第 1 个候选是 $11\oplus10=01$。Bob 手中的 $t_2$ 恰好也是 $01$；他能算出第 1 个分支的密钥 $H(2\parallel01)$。Alice 则同时算出 $H(2\parallel11)$ 和 $H(2\parallel01)$，但不知道 Bob 选了哪个分支。这里的 0、1 都是分支编号，不是集合元素。

现在给三次 OT 分别放入两条示例明文：

Alice 用每行的两把密钥分别加密两条明文，并把两个密文都发给 Bob。以第 2 次 OT 为例：

Bob 用 $H(2\parallel t_2)=H(2\parallel01)$ 解开 $C_2^1$，得到“小狗”。第 1、3 次同理，分别解出“红色”和“高山”。Bob 只掌握每行所选分支的密钥；Alice 不知道他的选择向量 $r=(0,1,0)^T$。

至此，例子才完整展示了三次扩展 OT。 这些明文只是教学用的普通消息，不能从“红色、小狗、高山”推得集合交集。只有后续 PSI 协议规定消息与集合匹配的关系，才能用 OT 的输出判断交集。示例中的 $\lambda=2$ 仅便于手算，真实协议需要足够大的安全参数、正确的密钥派生与安全加密；这里展示的是功能关系，不是可直接使用的安全实现。

PPT 第 22～29 页：把基础工具接回 PSI #

前面已经知道怎样完成一次 OT，也知道怎样批量扩展 OT。接下来要回答的是：这些工具怎样处理集合元素，最后得到交集？读这几页时，先把“最终想完成的功能”“实现功能的密码工具”和“存放数据的结构”分开。

这里有三条学习路线：OT + BF 用二选一计算位数组的 AND；DH 或 VOLE + OKVS 先实现 OPRF，再比较标签；GC + BF 把相关位运算放进安全电路。 它们可以实现相近的匹配目标，使用的中间表示不同。下面各例都把执行步骤接到最终判断，随机选取的量会明确标明。

PPT 第 22～23 页：布隆过滤器与 OT 如何配合 #

布隆过滤器的插入、查询和误判 #

布隆过滤器由长度为 \(m\) 的位数组和 \(k\) 个哈希函数组成。位数组初始全为 0；插入元素 \(x\) 时，将 \(h_1(x),\ldots,h_k(x)\) 指定的位置全部置为 1。查询一个元素时，重新计算这些位置：只要有一个位置为 0，就能确定它没有插入；全部为 1，则只能判断它可能存在。

原因是不同元素可以共用位置。一个没有插入的元素，其全部查询位置可能碰巧已被其他元素置为 1，这叫假阳性。普通 BF 在没有删除操作、构造和查询保持一致时，对已经插入的元素没有假阴性。PPT 的误判率近似式为：

这里的 \(m,k,n\) 分别是数组长度、哈希函数数目、已插入元素数目。这个概率由数据结构参数决定，与 OT 能否安全传输消息是两件不同的事。

用一个位数组例子走完流程 #

设 Alice 持有 \(X=\{A,B\}\)，Bob 持有 \(Y=\{B,C\}\)。教学用数组长度为 6，下标从 0 开始，使用两个公开哈希函数。约定本例中计算出的哈希位置如下；这些位置是哈希输出，不是每次查询重新随机选择的位置。

插入各自的集合后，双方分别得到：

1
2
3

下标     0 1 2 3 4 5
BF_X     1 1 1 0 1 0
BF_Y     0 1 0 1 1 1

第一步：Alice 为每个位置准备两条 OT 消息。 在位置 \(i\) 上，她提供 \((m_i^0,m_i^1)=(0,BF_X[i])\)。这里两条消息的内容可能相同，例如 \(BF_X[i]=0\) 时两条消息都是 0；二选一说的是两个分支，并不要求消息内容不同。

第二步：Bob 用自己对应的 BF 位作选择。 他令 \(b_i=BF_Y[i]\)。这里 \(b_i\) 由集合编码决定，不是随机选择位：选 0 得到 0，选 1 得到 \(BF_X[i]\)。

第三步：Bob 拼接所有 OT 输出。 每个输出恰好为 \(BF_X[i]\land BF_Y[i]\)，得到：

1

AND结果  0 1 0 0 1 0

第四步：Bob 用自己的元素查询。 B 的位置 1、4 都为 1，因而被保留；C 的位置 3、5 为 0，因而被排除。本例的候选交集为 \(\{B\}\)。

这里完成了从集合、位数组、OT 消息到匹配判断的完整功能链。若数组很长，就需要很多次 OT；前面学的 OT 扩展正好用于减少这些 OT 的公钥运算成本。直接重复 Base OT 也可以完成这些二选一，效率会不同。

位数组 AND 为什么还要谨慎理解 #

PPT 用 \(BF_{X\cap Y}\) 表示 AND 结果，这是方便讲解的记号。一般情况下，两个 BF 的 AND 不等于只用真实交集重新构造的 BF：不同的非交集元素也可能把共同位置置为 1。用 Bob 的元素查询时仍会产生假阳性。

此外，上述朴素流程让 Bob 学到一些 Alice 的 BF 位，不能仅凭“用了 OT”就断言完整 PSI 隐私已经成立。PPT 提到的 GBF（混淆布隆过滤器）用多比特字符串和分享关系等机制保护表示，带来额外通信成本。BF 与 GBF 的具体编码规则不同，不能把普通 0/1 BF 例子直接当作 GBF 的安全实现。

本块用到： 哈希定位、位数组、AND、OT 和 OT 扩展。暂时不用： 同态加密、多项式判零、OPRF。哈希负责定位，OT 负责保护选择；准确性和隐私性还需分别检查。

PPT 第 24～25 页：OPRF 先生成标签，再完成匹配 #

第 24 页先给功能接口 #

伪随机函数 PRF 写为 \(F_k(x)\)：在同一密钥 \(k\) 下，相同输入总得到相同输出；输出从没有密钥的一方看来应像随机值。函数名称和算法可以公开，秘密的是密钥。OPRF 让 Bob 在不直接向 Alice 公开输入 \(y\) 的情况下，取得 \(F_k(y)\)，同时保护 Alice 的密钥。这个功能定义也可参考 RFC 9497 对 OPRF 的说明。

用 \(X=\{A,B\}\)、\(Y=\{B,C\}\) 说明第 24 页的完整流程：Alice 持有秘密密钥 \(k\)，本地计算 \(Z=\{F_k(A),F_k(B)\}\)；Bob 通过 OPRF 取得 \(F_k(B),F_k(C)\)。Alice 将自己的标签集合 Z 发给 Bob，Bob 检查自己的两个标签是否出现在 Z 中，最后识别出 B。

OPRF 阶段本身只负责取得函数值；Alice 发标签、Bob 比较并恢复对应的本地元素，才把它接成 PSI。它与普通 Hash PSI 都会比较标签，但普通公开哈希可被任何人离线计算，OPRF 的计算受秘密密钥和协议查询控制。接收方仍可能提交自己选择的查询，具体 PSI 还应说明允许的输入、查询次数和威胁模型。

第 25 页用 DH 实现这个接口 #

设双方约定阶为素数 \(q\) 的合适群，\(H_G(y)\) 把输入映射到群元素。Alice 随机选择非零秘密密钥 \(k\)；Bob 对每次输入随机选择非零盲化指数 \(\beta\)。流程是：

1. Bob 发 \(H_G(y)^\beta\) 给 Alice。
2. Alice 对收到的群元素做 \(k\) 次幂，返回 \(H_G(y)^{\beta k}\)。
3. Bob 使用 \(\beta^{-1}\) 去盲，得到 \(H_G(y)^k\)。
4. Alice 本地计算自己元素的相同形式，双方再按第 24 页完成标签比较。

这里的逆元是在模群阶 q 的指数运算中计算的，满足 \(\beta\beta^{-1}\equiv1\pmod q\)，并非负数 \(-\beta\)。PPT 第 25 页的去盲写法需要按这个含义理解；其 H 也应理解为合适的群映射，不能对任意比特串直接做群运算。规范中的去盲步骤同样使用盲化标量的逆元，实际输出还包含约定的最终哈希处理，见 RFC 9497 的 OPRF 协议。

可手算的 DH 例子 #

仅为演示，使用模 23 乘法群中的阶 11 子群，因此群元素运算模 23，指数逆元模 11。设教学映射得到 \(H_G(A)=2,H_G(B)=4,H_G(C)=8\)。Alice 本次随机选得 \(k=3\)，Bob 对 B、C 的查询分别随机选得 \(\beta_B=2,\beta_C=3\)。

Alice 对自己的 A、B 本地计算，分别得到 \(2^3\bmod23=8\) 和 \(4^3\bmod23=18\)。因此 Alice 的比较值集合是 \(\{8,18\}\)；Bob 将 B 对应到 18、C 对应到 6，只有 B 匹配。本例小参数和教学映射仅用于验证等式，实际系统还需要足够大的群、规范的群映射与最终哈希。

本块用到： PRF/OPRF 接口、群指数、模群阶的逆元、盲化和标签比较。暂时不用： BF、OKVS、VOLE、密文多项式。第 24 页讲“接口怎样用于 PSI”，第 25 页讲“怎样实现接口”。

PPT 第 26～27 页：VOLE 与线性 OKVS 如何实现 OPRF #

先统一 Encode 和 Decode 的记号 #

OKVS 将若干键值关系编码到一个结构中。本文统一使用“查询键在前，编码结构在后”的记号：

这里 \(u_i\) 是 key，\(v_i\) 是 value；\(\mathbf D\) 是编码向量，并不是明文键值表。PPT 第 26 页与第 27 页对 Decode 参数的先后顺序不同；读图时应先辨认哪个是查询键、哪个是编码结构，不要把参数顺序变化当成新运算。符号 u 用来区分普通查询键与 OPRF 秘密密钥。

Encode 的正确性要求保证已编码的键解出约定值；对未编码的键，不保证固定值，也不保证一定非零。一个确定的编码结构 D 和查询键 x，通常会得到确定的解码结果，并非每调用一次就重新抽随机数。其“像随机值”的表现来自编码随机性和构造的分布性质。

还要注意，OKVS 的键隐藏性质依赖具体定义、值的分布和使用方式。知道某些期望值后，查询者可能利用输出做判断。第 27 页全部编码为零，因此协议额外用随机向量遮住 D；不能仅凭“OKVS”这个名称就认定裸露 D 也安全。

第 27 页默认需要线性 Decode #

第 27 页用到的 OKVS 对编码向量的解码必须满足以下线性性质：

运算在同一个有限域中进行，所有向量长度和公共解码参数相同。这里“线性”针对向量 U、V、D，不表示可以把查询键 x 随意相加拆分。一种理解方式是：对于固定查询键 x，Decode 选取向量中的若干位置，或计算一个由 x 决定的线性组合。具体安全 OKVS 可能使用稀疏线性系统等结构，但本阶段先掌握上述两个等式即可。

VOLE 提供哪一种关系 #

OLE 让一方秘密持有线性函数参数 a、b，另一方秘密持有输入 x，后者取得 \(ax+b\)。VOLE 把相关关系批量扩展到向量。第 27 页所用相关随机性分配如下：

相关随机量通过协议产生，不能把 A、B、C 都独立随机选好后再要求它们恰好满足等式。举例时可先随机选 A、B、Δ，再按关系计算 C；真实协议要同时保证正确分配和隐私。PPT 第 26 页介绍 OLE/VOLE 接口，第 27 页使用相关随机性，左右两方持有什么应以当前图为准。

完整流程：从零值编码到标签匹配 #

第一步：双方取得 VOLE 输出。 Alice 得到 Δ、B，Bob 得到 A、C，满足上表关系。这里暂时没有输入双方集合的匹配信息。

第二步：Bob 把自己的集合编码为零值。 对 \(Y=\{y_1,\ldots,y_n\}\)，构造：

于是每个 Bob 的真实输入都保证 \(\operatorname{Decode}(y_i,\mathbf D)=0\)。value 设为零是本构造的设计选择，用来消除随后出现的附加项。

第三步：Bob 发送被随机向量遮住的结构。 他发 \(\mathbf M=\mathbf A+\mathbf D\)；不直接发送集合 Y 或裸编码 D。在适合本构造的相关随机性与安全模型下，A 起遮罩作用。保护效果来自完整协议的条件，并非“把两个向量相加”天然能保护任意输入。

第四步：Alice 生成自己的函数密钥向量。 她利用 B、Δ、M 计算：

Alice 可直接用前半个表达式计算 K，无需知道 Bob 的 A、C、D。后半个表达式用于证明正确性。K 一般不同于 C；两者的差仍然是 ΔD。

第五步：各自对本地元素生成标签。 Alice 对 \(x\in X\) 算 \(H(\operatorname{Decode}(x,\mathbf K))\)；Bob 对 \(y\in Y\) 算 \(H(\operatorname{Decode}(y,\mathbf C))\)。Alice 把自己的标签集合发给 Bob，Bob 用自己标签与本地元素的对应关系恢复交集，这一步接回第 24 页的 OPRF-PSI 框架。

Alice 不知道 y_i，为什么红框写 Decode(y_i,K) #

红框是在证明共同输入处的输出一致，并没有新增一次消息发送。真实执行时 Alice 使用自己的 x，Bob 使用自己的 y；若某个 \(x_j=y_i\)，证明者就可以用同一个变量 \(y_i\) 比较两个理论结果。

最后一步成立，是因为 Bob 已将 \((y_i,0)\) 编入 D。消失的是解码后的附加项 \(\Delta\operatorname{Decode}(y_i,\mathbf D)=\Delta\times0\)，并不是整个向量 ΔD 变为零。Alice 可以不知道某个查询点，却仍然拥有在该点定义的函数；证明者分析该函数，也不意味着 Alice 获得了那个点。

从 Encode 开始手算的线性例子 #

之前直接指定几个 Decode 输出，会让人不清楚数字是否符合编码规则。下面给出实际向量，并定义公开解码规则，所有结果都从向量算出来。这是验证线性等式的教学模型，不具备实际安全 OKVS 的键隐藏和高强度安全保证。

设 \(X=\{2,7\}\)，\(Y=\{2,5\}\)，所有加减乘法都在 \(\mathbb F_{101}\) 中进行，也就是结果模 101。编码向量有三个分量，针对本例的三个键，公开解码规则如下：

这些规则只展示本例用到的查询点。它们是教学参数，参与方无需知道对方具体持有哪些键；真实结构要有覆盖输入域的公共解码算法。

先完成 Encode。 为了把 (2,0)、(5,0) 编进去，需要解两个约束：\(d_0+d_1=0\)、\(d_1+d_2=0\)。Bob 随机选得自由分量 \(d_1=3\)，据约束算得：

因此 Decode(2,D) 和 Decode(5,D) 都是 \(101\bmod101=0\)；未编码的键 7 则解出 \(196\bmod101=95\)。95 是从本次随机编码得到的向量推出来的，不是另外随意指定的随机数。 本模型中若自由分量改了，未编码键的输出也会改变；固定 D 后重复查询 7，仍得到 95。

再产生相关随机性。 教学中假设这次随机选得 \(\Delta=3\)、\(\mathbf A=(4,7,9)\)、\(\mathbf B=(6,2,8)\)，据关系计算：

实际 VOLE 按协议将这些量分配给双方；此处把它们写在一张纸上，仅供验证，并非双方互相公开全部向量。

Bob 发 M，Alice 算 K。 分量均模 101：

也可以核对 \(\mathbf C+3\mathbf D=(9,32,26)\)，两种算法一致。最后按同一解码规则逐点检查：

真实执行时，Alice 只计算自己元素 2、7 对应的 \(H(41),H(35)\)；Bob 只需要自己元素 2、5 对应的 \(H(41),H(58)\)。Alice 发送这两个标签后，Bob 识别到标签 H(41) 对应自己的元素 2，于是得到 \(\{2\}\)。表中为 5 计算 K、为 7 计算 C，是旁观者的验证，不是要求双方知道对方元素。

本例不同输出没有碰撞。实际参数中，未编码键的解码结果仍可能偶然为零，不同键或最终哈希也可能碰撞；需要足够大的域、足够长的标签和构造的整体分析。哈希不能把已经相同的两个域值变成不同值，也不能靠把小域值哈希得很长就补回安全强度。

本块用到： 有限域、相关随机向量、Encode 正确性、Decode 对向量的线性、哈希标签比较。暂时不用： DH 指数、BF、GC、FHE/PHE。重点是区分真实执行、正确性证明和教学者的全知算例。

PPT 第 28～29 页：混淆电路如何计算，怎样接到 BF #

输入比特与导线标签 #

把目标函数拆成 AND、XOR、NOT 等逻辑门后，GC 用随机字符串代表每根导线上的 0 和 1。一根导线有两个不同的随机标签，例如 \(W_a^0,W_a^1\)。上标 0、1 是说明书中的含义；计算方拿到一个标签字符串时，并没有自动得到两种标签与比特含义的完整映射。

PPT 把 GC 概括为“OT + 逻辑电路”，适合记住连接关系；完整过程还包括随机标签生成、门的混淆、输入标签传递和输出解码。这里可以先用一个 AND 门弄清每一方在做什么。

一个 AND 门的完整执行例子 #

目标是 \(c=a\land b\)。设 Alice 的输入 \(a=1\)，Bob 的输入 \(b=0\)；这两个输入是本例的私有数据，不把它们说成随机数。Alice 则为三根导线随机生成标签 \((A_0,A_1)\)、\((B_0,B_1)\)、\((C_0,C_1)\)。

第一步：Alice 混淆真值表。 用两个输入标签保护对应的输出标签，并打乱表项。下面表示加密前的逻辑关系；实际发出的表项不直接写明输入比特：

第二步：双方交付正确的输入标签。 Alice 根据自己的 \(a=1\) 发送 A₁。对于 Bob 的输入导线，Alice 通过 OT 提供 B₀、B₁，Bob 使用私有选择位 \(b=0\)，只拿到 B₀；Alice 不应从 OT 得知 b。输入位数多时，这些 OT 也可用 OT 扩展执行。

第三步：Bob 计算这个门。 Bob 持有 A₁、B₀，按照混淆方案找到并打开对应表项，取得 C₀。教学上可以理解为只有对应的一项能正确打开；实际方案通常有标签标记等机制帮助定位，并不一定需要逐项尝试。

第四步：解读约定输出。 Bob 根据输出解码信息知道 C₀ 表示 0，得到 \(1\land0=0\)。多门电路中，中间的输出标签会作为下一个门的输入标签；不必把中间比特逐门公开。最后哪些结果给 Bob、哪些给 Alice，由目标功能规定，并非 GC 一律向双方公开。

“保护输入”也不是说输出无法透露任何信息。输出本身可能推出某个输入，例如 Bob 知道 b=1，若 AND 结果为 0，他就能推知 a=0。协议要保护的是约定输出和允许泄露信息之外的内容。

用同一个 BF 例子接回第 29 页 #

沿用前面 \(BF_X=111010\)、\(BF_Y=010111\) 的数组，Alice 为自己各位交付对应导线标签；Bob 通过六次 OT 取得自己各位的标签；Bob 计算六个混淆 AND 门，按约定解码得到 010010。再查询 B 的位置 1、4，保留 B；查询 C 的位置 3、5，排除 C。

这展示了“GC 安全执行位运算，再做 BF 查询”的功能。若直接输出完整 AND 数组，它仍可能泄露协议不打算公开的结构；需要更严格输出控制时，可把成员查询等后续步骤也纳入安全计算，并只输出约定结果。GC 不会自动消除 BF 的假阳性。

PPT 第 29 页以共同元素落到下标 0、6 来说明匹配。但图中画出的两条输入位数组相同，AND 输出却少了其他若干个 1，数字之间并不一致。相同数组逐位 AND 后应保持原样，复习时请按正确的位运算规则计算。

本块用到： 逻辑门、随机导线标签、门表混淆、输入 OT、输出解码，以及 BF 查询。暂时不用： VOLE/OKVS 的代数消项、DH 去盲、密文多项式。现阶段先能沿着输入标签走到输出，后续研究 GC 时再深入 Free-XOR、Half-Gates 等优化。

第 22～29 页的复习对照 #

这几条路线中的集合元素、密钥、随机遮罩和标签承担不同职责。看到一个公式时，先标出谁实际持有它的输入，再判断它是本地计算、消息发送，还是正确性证明；尤其不要因证明中出现了对方的变量，就认为协议泄露了对方的数据。

当前整理进度：PPT 第 29 页，已合并本阶段关于流程联系、Encode/Decode、去盲和 GC 的追问。第 30 页为目录，后续新增学习从第 31 页继续整理。