共计 2920 个字符，预计需要花费 8 分钟才能阅读完成。
OT 扩大协定
首先假如 Alice 是发送方，Bob 是接管方，Bob 的𝑚比专长的抉择比特串为𝑟，\(𝑟_𝑗 \) 示意抉择比特串𝑟的第𝑗比特。Bob 产生两个𝑚 × 𝑘的随机矩阵 A 和 B：
用 \(𝑎^𝑖,𝑏^𝑖 \) 别离示意矩阵𝐴和𝐵的第𝑖列向量，用 \(𝑎_𝑗,𝑏_𝑗 \) 别离示意矩阵𝐴和𝐵的第𝑗行向量。矩阵𝐴和𝐵满足 \(𝑎_𝑗⊕𝑏_𝑗=𝑟_𝑗.1^k \)，即若 \(𝑟_𝑗= 1 \)，则 \(𝑎_𝑗⊕𝑏_𝑗=1^k \)；若 \(𝑟_𝑗=0 \)，则 \(𝑎_𝑗 ⊕𝑏_𝑗=0^k \)，其中 \(1^k \) 示意𝑘比专长的 1 组成的比特串，\(0^k \) 示意𝑘比专长的 0 组成的比特串。
发送方 Alice 随机产生一个𝑘比专长的串𝑠。Alice 和 Bob 之间利用 2 选 1 不经意传输协定，依据比特串𝑠的各个比特 \(𝑠_1,…,𝑠_𝑘 \) 的值，Bob 向 Alice 发送不同的值。若 \(𝑠_𝑖=0 \)，则 Bob 发送 \(𝑎^𝑖 \)；若 \(𝑠_𝑖=1 \)，则 Bob 发送 \(𝑏^𝑖 \)。
当 Bob 发送完后，Alice 取得了一个𝑚×𝑘的矩阵，记为𝐶，
记 \(𝑐^𝑖 \) 示意矩阵𝐶的第𝑖列向量，\(𝑐_𝑗 \) 示意矩阵𝐶的第𝑗列向量。那么有论断：\(𝑐_𝑗=𝑎_𝑗\oplus[𝑟_𝑗.𝑠] \)，即若 \(𝑟_𝑗=0 \)，则 \(𝑐_𝑗=𝑎_𝑗\oplus[𝑟_𝑗.𝑠]=𝑎_𝑗 \)；若 \(𝑟_𝑗=1 \)，则 \(𝑐_𝑗=𝑎_𝑗\oplus[𝑟_𝑗.𝑠]=𝑎_𝑗\oplus𝑠 \)。
假如有一个哈希函数𝐻，则 Bob 能够计算 \(𝐻(𝑐_𝑗) \) 和 \(𝐻(𝑐_𝑗\oplus𝑠) \)，对于每一个 \(𝑐_𝑗 \)，都等于 \(𝑎_𝑗 \) 或者 \(𝑎_𝑗\oplus𝑠 \)。Alice 别离应用 \(𝐻(𝑐_𝑗) \) 和 \(𝐻(𝑐_𝑗\oplus𝑠) \) 来加密机密 \(𝑥_0 \) 和 \(𝑥_1 \)，失去 \(𝑒_0=𝐻(𝑐_𝑗)\oplus𝑥_0,𝑒_1= 𝐻(𝑐_𝑗\oplus𝑠)\oplus𝑥_1 \)。
加密之后 Alice 将 \(𝑒_0 \) 和 \(𝑒_1 \) 发送给 Bob。因为 \(𝑐_𝑗 \) 的值为 \(𝑎_𝑗 \) 或 \(𝑎_𝑗\oplus𝑠 \)，而 \(𝑐_𝑗\oplus𝑠 \) 的值为 \(𝑎_𝑗\oplus𝑠 \) 或 \(𝑎_𝑗 \)，依据 \(𝑟_𝑗 \) 的值而定，若 \(𝑐_𝑗 \) 为 \(𝑎_𝑗 \) 则 \(𝑐_𝑗\oplus𝑠 \) 为 \(𝑎_𝑗\oplus𝑠 \)；若 \(𝑐_𝑗 \) 为 \(𝑎_𝑗\oplus𝑠 \) 则 \(𝑐_𝑗\oplus𝑠 \) 为 \(𝑎_𝑗 \)，二者中必有一个是 \(𝑎_𝑗 \)。
Bob 只把握 \(𝑟_𝑗 \) 而不晓得 \(𝑠_𝑗 \)，Bob 又把握着 \(𝑎_𝑗 \)，因而对于 Alice 发送过去的 \(𝐻(𝑐_𝑗)\oplus𝑥_0 \) 和 \(𝐻(𝑐_𝑗\oplus𝑠)\oplus𝑥_1 \)，Bob 能够本地计算 \(𝐻(𝑎_𝑗) \) 来解密 \(𝐻(𝑐_𝑗)\oplus𝑥_0 \) 或者 \(𝐻(𝑐_𝑗\oplus𝑠)\oplus𝑥_1 \) 中的一个，具体解密哪个取决于 \(𝑟_𝑗 \) 的值。矩阵 C 的每一列都可用来进行一次 OT 协定，因而可进行𝑘次𝑚比特的 OT 协定。
假如 Bob 的抉择比特串为𝑟=101，Bob 产生两个 3×3 的随机矩阵 A 和 B，且矩阵 A 和矩阵 B 合乎 \(𝑎_𝑗\oplus𝑏_𝑗=𝑟_𝑗.1^k \)：
能够看到，\(𝑎_1\oplus𝑏_1= 1.1^k =[1 1 1]^T，𝑎_2\oplus𝑏_2=0.1^k=[0 0 0]^T，𝑎_3\oplus𝑏_3= 1.1^k =[1 1 1]^T \)。
联合具体例子来看：发送方 Alice 随机产生一个𝑘= 3 比专长的抉择比特串𝑠=[0 0 1]，Alice 和 Bob 间利用二选一的不经意传输协定，如之前介绍过的 Naor-Pinkas 协定，接管依据比特串𝑠的各个比特 \(𝑠_1,𝑠_2,𝑠_3 \) 的值，Bob 向 Alice 发送矩阵 A 和 B 的不同列。若 \(𝑠_𝑖=0 \)，则 Bob 发送 \(𝑎^𝑖 \)；若 \(𝑠_𝑖=1 \)，则 Bob 发送 \(𝑏^𝑖 \)。则 Alice 将收到 \(𝑎^1={[1 0 0]}^T, 𝑎^2={[1 0 0]}^T,𝑏^3={[1 1 1]}^T \)。
将最初 Alice 收到的矩阵记为𝐶：
能够看到矩阵𝐶满足 \(𝑐_𝑗=𝑎_𝑗\oplus[𝑟_𝑗.𝑠] \)，如 \(𝑐_1=𝑎_1\oplus[𝑟_𝑗.𝑠]=𝑎_1\oplus[1.𝑠]= [1 1 0]\oplus[0 0 1]=[1 1 1]，𝑐_2= 𝑎_2\oplus[𝑟_2.𝑠]=𝑎_2\oplus[0.𝑠]=𝑎_2=[0 0 1]，𝑐_3=𝑎_3\oplus[𝑟_3.𝑠]=𝑎_3 \oplus 𝑠 = [0 1 0]\oplus [0 0 1]=[0 1 1] \)。能够看到矩阵𝐶的各行都满足关系式 \(𝑐_𝑗=𝑎_𝑗 \oplus [𝑟_𝑗.𝑠] \)。
Alice 应用矩阵哈希函数 H 和矩阵 C 对机密进行加密，Alice 应用 \(𝐻(𝑐_1) \) 来加密 Alice 的机密 \(𝑥_0 \)，应用 \(𝐻(𝑐_1 \oplus 𝑠) \) 来加密机密 \(𝑥_1 \)，失去加密后的密文 \(𝑒_0=𝐻(𝑐_1) \oplus 𝑥_0,𝑒_1=𝐻(𝑐_1 \oplus 𝑠) \oplus 𝑥_1 \)，之后 Alice 将 \(𝑒_0 \) 和 \(𝑒_1 \) 发送给 Bob。
留神此时 \(𝐻(𝑐_1)= 𝐻([1 1 1])=𝐻(𝑎_1 \oplus 𝑠)，𝐻(𝑐_1 \oplus 𝑠) = 𝐻(𝑎_1 \oplus 𝑠 \oplus 𝑠)=𝐻(𝑎_1) \)，Bob 是不晓得𝑠的，Bob 只晓得 \(𝑎_1 \)，当 \(𝑟_1=1 \) 时，因为 \(𝐻(𝑐_1 \oplus 𝑠)=𝐻(𝑎_1) \)，Bob 又把握 \(𝑎_1 \)，因而 Bob 能够间接计算𝐻(𝑎)，由此通过计算 \(𝐻(𝑐_1 \oplus 𝑠) \oplus 𝑥_1 \oplus 𝐻(𝑎_1)=𝑥_1 \)，能够解密出 \(𝑥_1 \)。而 Bob 不晓得𝑠，因而 Bob 无奈计算 \(𝐻(𝑎_1 \oplus 𝑠) \)，也就无奈计算出 \(𝑥_2 \)。
Alice 接着又应用 \(𝐻(𝑐_2) \) 来加密机密 \(𝑥_0′ \)，应用 \(𝐻(𝑐_2 \oplus 𝑠) \) 来加密机密 \(𝑥_1′ \)，失去加密后的密文 \(𝑒_2=𝐻(𝑐_2) \oplus 𝑥_0′, 𝑒_3= 𝐻(𝑐_2 \oplus 𝑠) \oplus 𝑥_1′ \)，之后 Alice 将 \(𝑒_2 \) 和 \(𝑒_3 \) 发送给 Bob。
因为 \(𝑟_2=0 \)，因而 \(𝐻(𝑐_2)=𝐻([0 0 1])=𝐻(𝑎_2 \oplus 𝑠) \)
\(𝐻(𝑐_2 \oplus 𝑠)=𝐻(𝑎_2 \oplus 𝑠 \oplus 𝑠)=𝐻(𝑎_2) \)，Bob 又把握 \(𝑎_2 \)，因而 Bob 能够间接计算 \(𝐻(𝑎_2) \)，由此通过计算 \(𝐻(𝑐_2) \oplus 𝑥_0′ \oplus 𝐻(𝑎_2)=𝑥_0′ \)，能够解密出 \(𝑥_0 \)。而 Bob 不晓得𝑠，因而 Bob 无奈计算 \(𝐻(𝑎_2 \oplus 𝑠) \)，也就无奈计算出 \(𝑥_2 \)。Bob 能解密哪个取决于 Bob 的抉择比特串𝑟的各比特值，正如下面的例子，\(𝑟_0=1 \) 时 Bob 可解密 \(𝑥_1 \)；\(𝑟_1=0 \) 时 Bob 可解密 \(𝑥_0′ \)，由此实现不经意传输。