Michael O. Rabin. How to exchange secrets with oblivious transfer. Technical Report TR-81, Aiken Computation Lab, Harvard University, 1981.
Introduction
Alice和Bob分别拥有一个对方想要解密的加密文件，密钥为1 bit秘密$SA\ SB$，因此两人想要交换$SA\ SB$
但是存在问题，如果密钥错误，文件会损坏不能再解密。因此Alice和Bob都想要保证能够正确解密文件
如果Bob给了Alice错误的密钥$S\neq SB$，交换得到了正确的$SA$，这是Alice不希望发生的情况
如果Bob发送一条消息， My secret is S, signed Bob. Alice可以收到$S$后不发给Bob $SA$，这是Bob不希望发生的情况，Alice也可以耍赖 “I gave Bob the password SA and he has not used it; I am willing to reveal it again right now.” 尽管Bob最终能够得到$SA$，Alice已经占据了时间优势
进行归纳，协议的流程总是分为$Alcie \to^{I_i} Bob, Bob \to^{J_i} Alice $，总会存在一个$k$满足Bob可以从$\{I_1,\dots,I_k\}$中得知$SA$，而Alice不能从$\{J_1,\dots,J_{k-1}\}$中得知$SB$，因此需要设计一种协议保证：
当Bob得知$SA$时，Alice一定可以得知$SB$
假设：当Bob发送$SA$去读文件时，Alice能够知道这一情况；反之亦然
Exchange of Secrets Protocol
假设Alice和Bob目前分别有了公钥$K_A,K_B$可以进行公钥加密与签名。为了简洁，后续的流程中省略了签名
Alice选择两个大素数$p,q$并计算一次性密钥$n_A=pq$，发送给Bob
类似地，Bob选择两个大素数$p_1,q_1$并计算一次性密钥$n_B=p_1q_1$，发送给Alice
Bob随机选$x\leq n_A$，计算$c \equiv x^2 \bmod n_A$，发送$c$给Alice
Alice已知$p,q$，计算出$x_1^2\equiv c \bmod n_A$，发送$x_1$给Bob
- 可能会有四个解$\pm x,\pm y$
- Bob可能作弊，发送自己无法求根的$c$，可能会允许R分解$n$，可以通过添加零知识证明来防御 [GMR85]
Bob计算$gcd(x-x_1,n_A)=d$，有$Pr(d=p\ or\ q)=1/2$
- 如果$x_1\neq \pm x,x_1^2 -x^2\equiv 0 \bmod n_A,(x_1-x)(x_1+x)\equiv0 \bmod n_A$
- 即得知 $p,q$，所以概率$Pr(d=p\ or\ q)=1/2$
Bob同样执行 $3-4$ 步，定义
Bob发送$\varepsilon_B=S_B\oplus v_B$
同样地，Alice发送$\varepsilon_A=S_A\oplus v_A$
Alice将秘密$S_A$放在消息$m_A$中，采用公钥加密$E_{n_A}(m_A)=C$并发送给Bob
- 提供$m_A$的一小段前缀来区分4个根
- 公钥加密算法采用依赖整数分解的算法即可
Bob将秘密$S_B$放在消息$m_B$中，采用公钥加密$E_{n_B}(m_B)=C’$并发送给Bob
证明
定理：任何参与方都不能获得秘密的概率为$1/4$
证明：如果任何参与方在协议正常结束前终止交互，另一方也会停止，两方都无法获得对方的秘密。
不妨设Alice已经发给了Bob$E_{n_A}(m_A)$，Bob成功解密并对比得到$SA$，当Bob尝试使用$SA$进行文件解密时，根据假设，Alice能够得知$v_B=0$，因此Alice能够计算出$S_B=\varepsilon_B \oplus v_B$；Bob发送$E_{n_B}(m_B)$的情况同理；
因此任何参与方都不能获得秘密的概率为两方都不能计算出$p,q,p_1,q_1$的概率，即$(1/2)^2=1/4$
Remark
协议不能迭代执行，考虑当Alice已经知道$SB$，但是直到第二轮结束才查询文件，Bob可能不知道第二轮的$v_A=0$是否成立
可以通过修改OT子协议实现正确率
- 收到$n_A$后，Bob随机选$x,y\leq n_A$，发送$x^2,y^2 \bmod n_A$，收到解$x_1,y_1$后不知道$p,q$的概率为$1/4$
- 协议总的失败率为$(1/4)^2=1/16$
- 但是这种方法存在一个上限，如果$Pr[v_B=0]\to0$，则Alice很可能认为Bob知道p，q，即$Pr[\varepsilon_B=S_B]\to 1$
Future work
- OT子协议在没有假设的前提下也是有效的，是否能找到其他应用场景
- 对EOS协议的假设能否变弱、
- 能否构造永远能终止的EOS，或者有人能证明非零的不终止概率是必要的？