【隐私计算笔谈】MPC系列专题（十四）：双方比较

双方比较

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

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

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

思考如下的比较：

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

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

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

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

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

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

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

即对于，Alice将比特中下标为的全都设置为随机数，将下标为的全都设置为。例如段，则𝑀=16。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通过OT获得的为。又由于Bob 通过OT获得的或者异或上 Alice的随机数, 即为的比较结果，因此可以将Bob获得的记为，看做是的比较结果的一个子秘密。只有当Bob的子秘密和 Alice的子秘密, 进行异或才能获得的比较结果。

同理可将Alice的输入为，Bob的输入为，OT后Bob获得的记为，作为Bob获得的的子秘密。

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

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