单方比拟

之前曾经介绍过了利用加密电路或者比特合成来实现平安多方比拟。本次再介绍一种利用不经意传输来实现单方比拟的办法。

不经意传输在之前的科普进行过介绍，该比拟协定的次要思路为：将须要比拟的两个比特串分为多个局部，每个局部再进行比拟，最初利用树形构造进行组合。假如有比特串和比特串，将比特串划分为两个局部，别离为\( _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} \)可得：


由此得证。