不经意传输及其扩展 · 某 Lolicon 的自白

不经意传输及其扩展

發佈於 2024-06-29 評論杂谈 Oblivious Transfer Oblivious Transfer Extension OT OTe

密码学众多原语中璀璨而不为人熟知的隐秘角落。

百万富翁问题

百万富翁问题也称为姚氏百万富翁问题：
假设有两个百万富翁：Alice 和 Bob。
他们想在不透露自己具体有多少钱的情况下比较谁更富有。

通俗的解法可以像这样的：

Alice 准备 9 个箱子，若 ta 的财产小于 X 百万，则将前 X-1 个箱子里放入苹果，剩下的放进香蕉；
Bob 拿到这 9 个箱子，若 ta 的财产小于 Y 百万，则在 Alice 看不到的地方取出第 Y+1 个箱子，并在不打开的情况下丢掉其他的箱子；
Bob 当着 Alice 的面开启箱子，此时如果箱子里是香蕉，则 Bob 更富有；如果是苹果则 Alice 更富有。

不经意传输

在百万富翁问题中，核心是在不披露双方原始数值的情况下进行数值比较。

而不经意传输（Oblivious Transfer, OT）将这个概念稍微扩展：
允许发送方将潜在信息传递给接收方，而对接收方接受到何种信息保持未知。

在密码学中，OT 应用常见是 n 选 1 OT，常被抽象为以下过程：

Alice 持有 n 个结果；
Bob 持有一个选择 c (c<n)；
Alice 和 Bob 执行 n 选 1 OT；
Bob 得到 Alice 持有的第 c 个结果，但并不知道其他结果如何；
Alice 不知道 Bob 选择了哪一个结果。

不难发现以上过程可以实现百万富翁问题的通俗解法，可问题是这个 n 选 1 OT 该如何实现呢。

第一例实用 OT

第一例 OT 实现
1981 年，迈克尔·拉宾提出并使用 RSA 密码系统构造了第一例 2 选 1 OT 协议。
图中 k0/k1 可以作为对称密钥使用，加密真正传输的内容（Beaver91 方案）。
同时这一协议可以简单扩展为 n 选 1 OT，用于解决百万富翁问题。
到此，本篇本应结束了，可是密码学研究者看到了 OT 的潜力没有停止研究。

OT 演进

既然 OT 可以用来做比较，那么用来做计算也是可以的吧？
到 1985 年，Shimon Even、Oded Goldreich 和 Abraham Lempel 提出了可用于 MPC 的实用 OT 方案。

紧接着，研究者开始尝试优化 OT。
Beaver91 方案虽然很优雅，但因为使用了 RSA 作为原语实现，计算性能低下。
如果有办法换成计算量更小的对称密码（SKE，例如 AES）那应该能快上许多。

可是，这一想法在两年前就被浇上了冷水：
1989 年，Russell Impagliazzo & Steven Rudich 从数学上证明仅使用对称密码无法构造 OT 协议。

那么有没有一种方法能够借助对称密码在已有少量 OT 的基础上产生新的 OT 呢？

不经意传输扩展 OT Extension

2003 年国际密码年会上 Yuval Ishai、Joe Kilian、Kobbi Nissim、Erez Petrank 共同发表『Extending Oblivious Transfers Efficiently』，简称 IKNP03。
正式开启 OT 实用化阶段。

Simplest OT

在正式介绍 IKNP03 之前，首先允许我介绍一下现代的 2 选 1 OT 构造方案 Simplest OT。
前文提到，构造 OT 必须使用非对称密码即 PKE，而第一例 OT 便是使用 RSA 构造的。
那么既然可以使用 RSA，椭圆曲线密码应该也是可以的。这便是 Simplest OT 的出发点。

使用椭圆曲线实现 DH 协议：

Simplest OT 协议：

Simplest OT 协议设置

需要注意的是，这一协议在以上设置下仅能提供半诚实安全的 n 选 1 OT，需要注意：

单向函数使用 (S, Ri) 作为盐；
对协议传输内容进行数字签名。

如需更严格的恶意安全，需要参考原文进行修改，此处不做详细介绍。
包括但不限于将 n 限制为 2，并将椭圆曲线换成 Ed25519。
使用 Python 实现的 PoC 可以参考：gist。

从零开始的 IKNP03

IKNP03 到底做了什么？
IKNP03 提出了使用 SKE 将有限个 PKE 1-2 OT （即 2 选 1 OT）无限扩展的方法，从此 OT 再也不用担心 PKE 的计算复杂度。

那么 IKNP03 是怎么做到的呢？
可以简单分为三个步骤：构造列 OT、行列变换、相关性打破。

构造列 OT
a. Bob 产生 k 个选择 r，并将 r 横向复制 128 次产生矩阵 R

b. Bob 随机产生与 R 形状相同的随机矩阵 T，与 R 异或得到 T’

c. Alice 随机产生字符串 s，长度为 128bit，将每一位作为选择执行 1-2 OT（例如使用 Simplest OT），最终得到矩阵 Q。

例如：s 的第一位为 0, 则将 Q 的第一列赋值为 T 的第一列，若为 1 则赋值 T’ 的第一列。
由于 OT 协议性质可知：Alice 选择 T 中的某列时，不能够解开 T’ 对应的列；同时 Bob 亦无法得知 Alice 选择的是哪些列。
行列变换
a. 对照 XOR 真值表，观察此时 Alice 持有的 Q 矩阵与 Bob 做出的选择 r。

b. 确认性质：
Alice 不知道 Bob 的 r，因此 Bob 不知道 t 等于 q 还是 q⊕s。
Bob 不知道 Alice 的 s，因此只知道 t 等于 q、q⊕s 中的一个，而并不知道另一个。

c. 得到 k 个 1-2 OT：
Alice 拥有 q 和 q⊕s，Bob 根据 r 可以得到其中的一个而不知道另一个。
Alice 不知道 r，因此不知道 Bob 选择的是 q 还是 q⊕s。
Q、T、T’ 矩阵为 k*128，因此仅使用 128 次基于公钥体系的 1-2 OT，得到了 k 个 1-2 OT。
问题：
对于 Q 的每一行，Bob 知道另一个等于 t⊕s，而 s 仅有一个。
经过若干次传输，Bob 即可猜解出 s 的每一位，进而得到 Alice 发送的每一条信息。
如何避免 s 被猜出来？
打破相关性
不直接使用 q/q⊕s, 而是经过一个 Random Oracle（使用安全哈希近似的单向函数）：

最后 Alice 使用 H(q) 和 H(q⊕s) 作为对称密钥分别加密消息 m0 及 m1，得到 E0 及 E1。
当 r=0 时，Bob 使用 H(t) 解开 E0；当 r=1 时，使用 H(t) 解开 E1。

我能用 IKNP03 干啥

IKNP03 实现的是以更低的成本获取大量的 OT，而 IKNP03 产生的 1-2 OT 与 PKE 产生的 1-2 OT 并无区别。
因此 PKE OT 能干啥，IKNP03 的 OT 也能干啥。

例如百万富翁问题可以用 n 选 1 OT 实现，只需要将 n 转为二进制位（假设为 k 位），接着构造 k 个 1-2 OT 即可替代 n 选 1 OT。
需要注意的是，实际为满足统计安全实际 k 需要至少要比 n 多 30 位，以充分降低 n 被猜到的可能性。

稍微扩展一下，将 OT 中的选择视作密码，用于加密被查询的内容。
这便是密码学中匿踪查询（Private Information Retrieval, PIR）的实现方式之一。

再往前一步，1-2 OT 也可以用来实现逻辑门电路，例如常用于实现加法计算的异或门。
因此只要有足够多廉价的 OT，就可以在可行时间内构造出任意有限计算。
这便是密码学中多方安全计算混淆电路实现的基础。

IKNP03 发表已经超过二十年了，OT 不再是学者们研究的核心，而变成了类似哈希函数和 AES 的原语。
你能在各种 SOTA 密码应用中看到 OT 的身影，人们可能不会说自己使用的方案，但请不要忘记推动 OT 向前迈进的 IKNP03 方案。

OT Extension 演进

IKNP03 的设计是用于扩展 1-2 OT 的，但很显然我们的日常使用会以 1-n OT 为主。
以下是一些演进方案，用于将 IKNP03 方案升级到 1-n OT。
介绍较为简单，具体的还请移步原文。

KK13

KK13 提出 IKNP03 中 r -> R 的过程可以看作一种重复编码：

C(0) = r ⊕ 000…0128
C(1) = r ⊕ 111…1128

这一编码的汉明距离为 128bit。
假如使用同样具有等距汉明距离特性的线性纠错码，则可以在满足相同安全假设的前提下实现 n-1 OT 的 IKNP03。

线性纠错码的主要有三个属性：
码字长度 n、消息长度 k 和汉明距离 d，这样的线性编码也称 [n, k, d] 码（国内资料称 (n, k 码)）。

在 KK13 的实现中，编码使用的是 [256, 8, 128] (2) 普通型 Hadamard 码。
相较于 IKNP03，可在列 OT 翻倍的情况下（128->256），安全特性不变（128bit 汉明距离）。
可将行 OT 的单次传输的消息由 1bit 提升至 8bit（如果换成增强型 Hadamard 码则是 9bit）。

Hadamard 码的码表可以采用以下脚本产生：

from scipy.linalg import hadamard

k = 128
e = ((hadamard(k)+1)/2).astype(int)
e = [''.join([f'{j:01b}' for j in i]) for i in e]
# 普通 Hadamard 码
e = [int('0b'+i, 2) for i in e]
# 增强型 Hadamard 码
e += [i^(2**k-1) for i in e]

KK13 将 Hadamard 码作为 C(r) 后，行 OT 相应需要做出改动：
即发送方 Alice 得到对称密钥的方式需要由 q/q⊕s 变为 q⊕C(r)^s。

OOS16

OOS16 的方案比 KK13 更迈进了一步，将编码效率低的 Hadamard 换成了 BCH。
例如 256 bit 的 KK13 仅能实现每个行 OT 最大 9bit，而 511bit 的 OOS16 采用 BCH-511 可以达到 76bit。

使用 Python 实现的 PoC 可以参考：gist。

KKRT16

KKRT16 是目前最常用于实现 PIR 的方案，其动机非常简单：
使用线性纠错码只是为了利用其码字间距相等的特性，并没有使用到其纠错的特性。
而线性码的纠错特性需占据码字中一大部分 bit，因而有没有一种替代原语具有码字间距几乎相等的特性？

当然有了，最典型的就是伪随机数发生器：
将一个输入作为种子，产生一定长度的伪随机数。
输入空间足够小的情况下，产生出来的伪随机数不会发生碰撞，相当于是一对一编码。
并且即便输入仅有一个 bit 的不同，编码之间的码字距离也能轻松满足计算安全的 128bit。

于是 KKRT16 提出了伪随机编码 Oblivious PRF：
PRF 即伪随机数函数，可以视作一个将输入映射到某个看似随机的输出域的函数。
PRF 可以被简化为两个输入：随机种子和随机输入。

OPRF 可实现以下效果：
Alice 持有 PRF f 和随机数种子 s，Bob 持有数值 X。
Bob 通过 OPRF 过程得到 f(s, X) 的值，但并不知道随机数种子 s。
同时 Alice 不知道 Bob 持有 X 的数值。

基于这一特性实现样本对齐的：

Alice 持有若干样本 A，若干随机数种子 S，伪随机数函数 F；
Bob 持有若干样本 B，通过 OPRF 得到样本对应映射 Hb；
Alice 使用每个随机数种子计算样本 A 的 PRF 结果，得到 Ha；
Alice 将 Ha 发给 Bob；
Bob 求 Ha 和 Hb 的交集 Hx，得到样本交集；
Bob 将 Hx 发回 Alice；
Alice 使用交集 Hx 得到样本交集。

在此期间，由于 OPRF 效果 Alice 不知道 Bob 的样本数值，故不知道未相交部分的样本。
Bob 由于不知道随机数种子，因此无法在一次求交过程中进行碰撞攻击，同时无法碰撞 Ha 中未相交部分。

参考

下一篇: Tokenizer 小记

Yet another otaku

某ロリコン的自白