不经意传输

Oblivious Transfer(OT).

假设 ~~Ob一串字母小姐~~ 有两个秘密 $m_{0}$ 和 $m_{1}$ ，要出售给 ~~Doloris小姐~~一个秘密 $m_{b}$ ，但是 ~~Doloris小姐~~ 不想让 ~~Ob一串字母小姐~~ 知道她买的是 $m_{0}$ 还是 $m_{1}$ ，而 ~~Ob一串字母小姐~~ 也不想让 ~~Doloris小姐~~ 知道另一个秘密 $m_{1 - b}$ ，这就有了我们下面的第一个协议 $O T_{2}^{1}$ 。

OT^1_2

$O T_{2}^{1}$

Sheme-1

首先，我们假设接收者 $B$ 是诚实的。

$S e t u p$ ： $B$ 选定他要选择的秘密 $b \in {0, 1}$ ，并生成公私钥对 $(p k_{b}, s k_{b})$ ，然后随机选择一个随机数作为另一个公钥 $p k_{1 - b}$ ，并将 $(p k_{0}, p k_{1})$ 发送给发送者 $A$ 。
$T r a n s f e r$ ： $A$ 收到公钥对 $(p k_{0}, p k_{1})$ 后，使用公钥 $p k_{0}$ 和 $p k_{1}$ 分别加密秘密 $m_{0}$ 和 $m_{1}$ ，得到密文 $c_{0} = E n c_{p k_{0}} (m_{0})$ 和 $c_{1} = E n c_{p k_{1}} (m_{1})$ ，然后将密文对 $(c_{0}, c_{1})$ 发送给接收者 $B$ 。
$R e c e i v e$ ： $B$ 使用私钥 $s k_{b}$ 解密密文 $c_{b}$ ，得到秘密 $m_{b} = D e c_{s k_{b}} (c_{b})$ 。

显然， $B$ 只能解密他选择的秘密 $m_{b}$ ，而无法解密另一个秘密 $m_{1 - b}$ ，同时 $A$ 也无法知道 $B$ 选择的是哪个秘密。

Sheme-2

但是，在上面的协议中， $A$ 无法确保 $B$ 确实没有持有 $p k_{1 - b}$ 对应的私钥 $s k_{1 - b}$ ，因此我们需要一个更强的协议来确保 $B$ 的诚实性。

以下以 Elgamal 为例：

$S e t u p$ ：对于 $A$ , 生成群参数 $(G, p, g)$ ，并且再生成一个随机元素 $C \in G$ , 把四元组 $(G, p, g, C)$ 发送给 $B$ 。
$B i n d$ ： $B$ 选择一个随机数 $k \in Z_{p}^{*}$ ，并且根据他想要的秘密 $b \in {0, 1}$ 计算公钥对 $(p k_{b} = g^{k}, s k_{b} = k)$ ，然后计算另一个公钥 $p k_{1 - b} = C / p k_{b}$ (此处不计算也可)，并将 $p k_{b}$ 发送给 $A$ 。
$T r a n s f e r$ : 由 $A$ 计算 $p k_{1 - b} = C / p k_{b}$ 。计算 $C_{1} = E n c_{p k_{0}} (m_{0})$ 和 $C_{2} = E n c_{p k_{1}} (m_{1})$ ，这部分可以用同一个随机数掩码 $r$ 来加密，叫做重用随机数，得到密文对 $(C_{1}, C_{2})$ 并发送给 $B$ 。
$R e c e i v e$ ： $B$ 使用私钥 $s k_{b}$ 解密密文 $C_{b}$ ，得到秘密 $m_{b} = D e c_{s k_{b}} (C_{b})$ 。

同样也是显然的， $B$ 只能解密他选择的秘密 $m_{b}$ ，而无法解密另一个秘密 $m_{1 - b}$ ，同时 $A$ 也无法知道 $B$ 选择的是哪个秘密。并且在这里可以有效防止 $B$ 作恶。

OT^{1}_n

$O T_{n}^{1}$

利用陷门置换(Trapdoor Permutation)的 $O T_{n}^{1}$ 协议的构造过程：

假设 $A$ 有 $n$ 个秘密 $a_{1}, a_{2}, \dots, a_{n}$ ，想将其中一个传递给 $B$ ，使得只有 $B$ 知道 $A$ 传递的是哪个消息，而 $A$ 不知道。

步骤1：秘密的传输

$A$ 将 Trapdoor Permutation $f$ 发送给 $B$ ，自己保留 Trapdoor 可用来求出 $f$ 的原像 $f^{- 1}$ 。
设 $B$ 想得到的是秘密 $a_{i} (1 \leq i \leq n)$ ，他从 $f$ 的定义域中选取 $n$ 个随机值 $x_{1}, x_{2}, \dots, x_{n}$ ，并将 $n$ 元组 $y_{1}, y_{2}, \dots, y_{n}$ 发送给 $A$ ，其中 $y_{k} = {\begin{cases} x_{k} & k \neq i \\ f (x_{k}) & k = i \end{cases}$
$A$ 利用 Trapdoor 计算 $z_{k} = f^{- 1} (y_{k}), k = 1, 2, \dots, n$ ，并将 $z_{k} \oplus a_{k}$ 发送给 $B$ ( $k = 1, 2, \dots, n$ )。

步骤2：秘密的恢复(假设B是半诚实的)

因为 $B$ 知道 $x_{i}$ ，故 $B$ 可通过计算 $(z_{i} \oplus a_{i}) \oplus x_{i} = a_{i}$ 得到秘密 $a_{i}$ ，而 $A$ 不知道 $B$ 拿到了哪个秘密。

什么叫半诚实的？

半诚实 (Semi-Honest) 模型，也称为 诚实但好奇 (Honest-but-Curious) 模型。

在此模型中，假设参与者（这里指 B）会：

诚实地 遵守协议的所有步骤（例如：在步骤 1 中，对于 $k \neq i$ ，B 确实是随机选取 $x_{k}$ ，而不是精心构造的：简单地说，就是对于 $k \neq i$ 我仍然使得 $y_{k} = f (x_{k})$ 。
好奇地 尝试从收到的消息中推断出额外的隐私信息。

如果 B 是 恶意 (Malicious) 的，他可以在步骤 1 中作弊：对于 $k \neq i$ ，他可以先选定 $w_{k}$ ，计算 $y_{k} = f (w_{k})$ 发送给 A。A 会计算 $z_{k} = f^{- 1} (y_{k}) = w_{k}$ 并发送 $w_{k} \oplus a_{k}$ 。因为 B 知道 $w_{k}$ ，他就能解密出所有的秘密 $a_{k}$ 。因此，该协议仅在 B 是半诚实的前提下是安全的。

不经意传输

OT^1_2

Sheme-1

Sheme-2

OT^{1}_n

步骤1：秘密的传输

步骤2：秘密的恢复(假设B是半诚实的)

OT 效率的优化

OT 扩展

利用 Random OT 构建 Correlated OT

不经意传输 ​

OT^1_2 ​

Sheme-1 ​

Sheme-2 ​

OT^{1}_n ​

步骤1：秘密的传输 ​

步骤2：秘密的恢复(假设B是半诚实的) ​

OT 效率的优化 ​

OT 扩展 ​

利用 Random OT 构建 Correlated OT ​

不经意传输

OT^1_2

Sheme-1

Sheme-2

OT^{1}_n

步骤1：秘密的传输

步骤2：秘密的恢复(假设B是半诚实的)

OT 效率的优化

OT 扩展

利用 Random OT 构建 Correlated OT