单方比拟
之前曾经介绍过了利用加密电路或者比特合成来实现平安多方比拟。本次再介绍一种利用不经意传输来实现单方比拟的办法。
不经意传输在之前的科普进行过介绍，该比拟协定的次要思路为：将须要比拟的两个比特串分为多个局部，每个局部再进行比拟，最初利用树形构造进行组合。假如有比特串𝑥和比特串𝑦，将比特串𝑥划分为两个局部，别离为 \(𝑥_1,𝑥_0 \)，将比特串𝑦也划分为 \(𝑦_1 \) 和 \(𝑦_0 \)。
表达式 1{𝑥<𝑦} 示意若𝑥<𝑦，则表达式 1{𝑥<𝑦} 的值为 1，否则为 0。同理，表达式 1{𝑥=𝑦} 示意若𝑥=𝑦则表达式的值为 1，反之为 0。
思考如下的比拟：
$$
\begin{array}{c}
x=x_{1} \| x_{0} \\
y=y_{1} \| y_{0} \\
1\{x<y\}=1\left\{x_{1}<y_{1}\right\} \oplus\left(1\left\{x_{1}=y_{1}\right\} \wedge 1\left\{x_{0}<y_{0}\right\}\right) \quad \text {式} 1
\end{array}
$$
把比特串𝑥和比特串𝑦分为两局部后，先比拟 \(𝑥_1 和𝑦_1 \) 的大小，因为 \(𝑥_1 和𝑦_1 \) 都是高位局部，因而若 \(𝑥_1<𝑦_1 \) 则比特串𝑥<𝑦；反之若 \(𝑥_1>𝑦_1 \) 则𝑥>𝑦，在这两种状况下无需在比拟 \(𝑥_0,𝑦_0 \) 的大小了。只有当 \(𝑥_1=𝑦_1 \) 时，须要通过比拟 \(𝑥_0,𝑦_0 \) 的大小关系来确定𝑥, 𝑦的大小关系。
式 1 就是该比拟协定的核心思想。该协定的具体流程为：
首先假如 Alice 把握比特串𝑥，Bob 把握比特串𝑦，先思考最简略的状况，𝑥和𝑦等长均为𝑙比特且 \(\frac{l}{m} \) 为 2 的指数倍。
1. Alice 和 Bob 别离对𝑥和𝑦进行𝑞等分：Alice：把𝑥进行𝑞等分，每份𝑚比特：
$$
x=x_{q-1}\|\cdots\| x_{0}
$$
Bob：把𝑦进行𝑞等分，每份𝑚比特：
$$
y=y_{q-1}\|\cdots\| y_{0}
$$
2. Alice 产生两个随机数，将其别离记为 \({<It_0,j>}_{B}^{0} , {<eq_0,j>}_{B}^{0} \)。Alice 利用 \(M=2^m \) 个比特，别离为 \(s_{j,0}…s_{j,M-1} \) 来标识 \(x_j \) 的大小关系；利用𝑀个比特，别离为 \(t_{j,0}…t_{j,M-1} \) 来标识 \(x_j \) 的相等关系：
即对于 \(x_j \)，Alice 将比特 \(s_{j,0}…s_{j,M-1} \) 中下标为 \(s_{j,0}…s_{j,x_j-1} \) 的全都设置为随机数 \({<It_0,j>}_{B}^{0}\oplus 0 \)，将下标为 \(s_{j,x_j}…s_{j,M-1} \) 的全都设置为 \({<It_0,j>}_{B}^{0}\oplus 1 \)。例如段 \(x_j=(1010)_2=(10)_{10} \)，则𝑀=16。Alice 将 \(s_{j,0}…s_{j,9} \) 设置为 \({<It_0,j>}_{B}^{0}\oplus 0 \)，将 \(s_{j,10}…s_{j,15} \) 设置为 \({<It_0,j>}_{B}^{0}\oplus 1 \)。
即下标比 \(x_j \) 的值小的为随机数 \({<It_0,j>}_{B}^{0} \) 异或 0，下标大于等于 \(x_j \) 的异或 1。对于 \(t_{j,0}…t_{j,M-1} \)，则是只有当下标和 \(x_j \) 相等时为随机数 \({<eq_0,j>}_{B}^{0} \) 异或 1，否则均为随机数 \({<eq_0,j>}_{B}^{0} \) 异或 0。
若用黄色示意比特值为 1，蓝色示意比特值为 0，则 Alice 在实现上述步骤后，\(s_{j,0}…s_{q-1,M-1} \) 和 \(t_{j,0}…t_{j,M-1} \) 如下所示：
对于 0≤𝑗≤𝑞−1，Alice 对每个 \(x_j \) 都进行上述的步骤，因而能失去 \(s_{0,0}…s_{j,M-1} \) 共𝑞∙𝑀比特，失去 \(t_{0,0}…t_{q-1,M-1} \) 共𝑞∙𝑀比特。
3. Alice 和 Bob 间调用𝑞次𝑀选 1 的 OT 协定，Alice 在 OT 协定中的输出为 \(s_{j,0}…s_{j,M-1} \)，Bob 在 OT 中的输出为 \(y_i \)：
𝑞次𝑀选 1 的 OT 完结后，Bob 会取得 \(s_{0,y_0}…s_{q-1,y_{q-1}} \)。
Alice 和 Bob 再调用𝑞次𝑀选 1 的 OT 协定，Alice 在 OT 协定中的输出为 \(t_{j,0}…t_{j,M-1} \)，Bob 在 OT 中的输出为 \(y_i \)：
𝑞次𝑀选 1 的 OT 完结后，Bob 会取得 \(t_{0,y_0}…t_{q-1,y_{q-1}} \)。
将 \(s_{0,y_0}…s_{q-1,y_{q-1}} \) 记为 \({<It_{0,0}>}_{B}^{1} ,…, {<It_{0,q-1}>}_{B}^{1} \)，将 \(t_{0,y_0}…t_{q-1,y_{q-1}} \) 记为 \({<eq_{0,0}>}_{B}^{1},… {<eq_{0,q-1}>}_{B}^{1} \)。
Alice 的输出为 \(s_{j,0}…s_{j,M-1} \)，Bob 的输出为 \(y_i \)，那么当 \(y_i≥x_i \) 时，Bob 通过 OT 取得的为 \({<It_{0,j}>}_{B}^{0}\oplus 1 \)，当 \(y_i<x_i \) 时，Bob 通过 OT 取得的为 \({<It_{0,j}>}_{B}^{0}\oplus 0 \)。又因为 Bob 通过 OT 取得的 \({<It_{0,j}>}_{B}^{0}\oplus 1 \) 或者 \({<It_{0,j}>}_{B}^{0}\oplus 0 \) 异或上 Alice 的随机数 \({<It_{0,j}>}_{B}^{0} \), 即为 \(x_j < y_j \) 的比拟后果，因而能够将 Bob 取得的记为 \({<It_{0,j}>}_{B}^{1} \)，看做是 \(x_j < y_j \) 的比拟后果的一个子机密。只有当 Bob 的子机密 \({<It_{0,j}>}_{B}^{1} \) 和 Alice 的子机密 \({<It_{0,j}>}_{B}^{0} \), 进行异或能力取得 \(x_j < y_j \) 的比拟后果 \({<It_{0,j}>}^{B} \)。
同理可将 Alice 的输出为 \(t_{j,0}…t_{j,M-1} \)，Bob 的输出为 \(y_i \)，OT 后 Bob 取得的 \({<eq_{0,j}>}_{B}^{0}\oplus 1 {x_j=y_j} \) 记为 \({<eq_{0,j}>}_{B}^{1} \)，作为 Bob 取得的 \(1{x_j=y_j} \) 的子机密。
4. Alice 和 Bob 运行如下算法（Alice 运行则𝑏=0，Bob 运行则𝑏=1）：
该算法的目标为将须要比拟的比特串分成多个局部，每个局部进行比拟，再将比拟后果进行组合。举个例子来解释这个算法，假如𝑞=16，则 \(x=x_{15} | … | x_{0} ,y=y_{15} | … | y_{0}\)，要比拟𝑥和𝑦先比拟 \(x_{15} | … | x_{8} \) 和 \(y_{15} | … | y_{8} \) 的大小，只有当 \(x_{15} | … | x_{8} \) 和 \(y_{15} | … | y_{8} \) 相等时才须要接着去比拟 \(x_{7} | … | x_{0} \) 和 \(y_{7} | … | y_{0} \) 间的大小关系。而比拟 \(x_{15} | … | x_{8} \) 和 \(y_{15} | … | y_{8} \) 间的大小关系能够先比拟 \(x_{15} | … | x_{12} \) 和 \(y_{15} | … | y_{12} 间的大小关系，若二者相等再比拟 \(x_{11} | … | x_{8} \) 和 \(y_{11} | … | y_{8} \)，以此类推，则造成了一个树形构造。
最初最先须要比拟的为和间的大小关系。用：
$$
x=x^{(i)}=\frac{x^{i}_q}{2^i}-1 \| … \| {x_{0}}^i
$$
示意该树形构造，(𝑖) 示意位于第几层，如
树形构造如下图所示：
正确性证实：
\(F_{𝑎𝑛𝑑} \) 是多方𝑎𝑛𝑑函数，须要 Alice 和 Bob 共同完成𝑎𝑛𝑑操作。如𝐴𝑙𝑖𝑐𝑒把握 \(a_0 \) 和 \(b_0 \)，Bob 把握 \(a_1 \) 和 \(b_1 \)，二者都调用 \(F_{𝑎𝑛𝑑} \) 后，\(F_{𝑎𝑛𝑑} \) 对 Alice 的输入为 \((a\wedge b)_0 \)，对 Bob 的输入为 \((a\wedge b)_1 \)，具体实现能够应用之前介绍过的 Beaver Triple 实现，因而：
输入为：
则:
又因为:
因而对 \({<It_{i,j}>}_{B}^{b} \) 异或上 \({<It_{i,j}>}_{B}^{1-b} \) 可得：
由此得证。