双方比较

之前已经介绍过了利用加密电路或者比特分解来实现安全多方比较。本次再介绍一种利用不经意传输来实现双方比较的方法。

不经意传输在之前的科普进行过介绍，该比较协议的主要思路为：将需要比较的两个比特串分为多个部分，每个部分再进行比较，最后利用树形结构进行组合。假设有比特串和比特串，将比特串划分为两个部分，分别为，将比特串也划分为和。

表达式1{<} 表示若<，则表达式1{<} 的值为1，否则为0。同理，表达式1{= } 表示若=则表达式的值为1，反之为0。

思考如下的比较：

把比特串和比特串分为两部分后，先比较和的大小，由于和都是高位部分，因此若则比特串<；反之若则>，在这两种情况下无需在比较的大小了。只有当时，需要通过比较的大小关系来确定, 的大小关系。

式1就是该比较协议的核心思想。该协议的详细流程为：

首先假设Alice掌握比特串，Bob掌握比特串，先考虑最简单的情况，和等长均为比特且为2的指数倍。

1. Alice和Bob分别对和进行等分：

Alice：把进行等分，每份比特：

Bob：把进行等分，每份比特：

2. Alice产生两个随机数，将其分别记为。Alice利用个比特，分别为来标识的大小关系；利用个比特，分别为来标识的相等关系：

即对于，Alice将比特中下标为的全都设置为随机数设置为。

即下标比的值小的为随机数异或0，下标大于等于的异或1。对于，则是只有当下标和相等时为随机数异或1，否则均为随机数异或0。

若用黄色表示比特值为1，蓝色表示比特值为0，则Alice在完成上述步骤后，和如下所示：

对于0≤≤−1，Alice对每个都进行上述的步骤，因此能得到共∙比特，得到共∙比特。

3. Alice和Bob间调用次选1的OT协议，Alice在 OT 协议中的输入为，Bob在OT中的输入为：

次选1的OT结束后，Bob会获得{}。

Alice和Bob再调用次选1的OT协议，Alice在OT协议中的输入为，Bob在OT中的输入为：

次选1的OT结束后，Bob会获得{}。将{}记为{}。

Alice的输入为，Bob的输入为，那么当时，Bob通过OT获得的为的比较结果，因此可以将Bob获得的记为，看做是的比较结果的一个子秘密。只有当Bob的子秘密和 Alice的子秘密同理可将Alice的输入为，Bob的输入为，OT后Bob获得的{}记为，作为Bob获得的1{}的子秘密。

4. Alice和Bob运行如下算法（Alice运行则=0，Bob 运行则=1）：

该算法的目的为将需要比较的比特串分成多个部分，每个部分进行比较， 再将比较结果进行组合。举个例子来解释这个算法，假设=16，则，要比较和先比较和的大小，只有当和相等时才需要接着去比较和间的大小关系。而比较和间的大小关系可以先比较和间的大小关系，若二者相等再比较和，以此类推，则形成了一个树形结构。

最后最先需要比较的为和间的大小关系。用：表示该树形结构，()表示位于第几层，如

树形结构如下图所示：

正确性证明：

是多方函数，需要Alice和Bob共同完成操作。如掌握和，Bob掌握和，二者都调用后，对Alice的输出为，对Bob的输出为，具体实现可以使用之前介绍过的Beaver Triple完成，因此：

输出为：

则:

又由于:

因此对异或上可得：

由此得证。