隐衷比拟是指在不裸露单方具体数值的前提下，获取单方数值的大小关系。最早起源于姚期智的百万富翁问题：有两个百万富翁想要比拟下谁更富裕，然而又不想走漏本人有多少钱，如何在没有可信第三方的状况下进行比拟？这个问题是由中国第一个也是目前为止惟一一个图灵奖获得者姚期智在 1980 年代提出的，他是中国计算机学术和教育的第一人，为古代密码学关上了一道新的大门。
在之前的文章《优雅的求职——隐衷比拟算法实例》中曾经通过求职案例介绍了隐衷比拟的利用场景以及如何实现，本文则次要介绍一种在以后效率比拟高的隐衷比拟协定。
该协定是[1] CrypTFlow2: Practical 2-Party SecureInference 中提出的一个子协定，并基于此协定实现 DRelu 激活函数利用于神经网络中。
– 相干技术 –
该协定次要应用了布尔机密分享和不经意传输两种技术进行构建：
▲ 不经意传输
不经意传输 (OT，Oblivious Transfer) 是指数据发送方有 n 个数据，数据接管方接管其中的一个数据，且数据接管方不能获取其余的数据，数据发送方也不晓得接管方抉择接管的数据具体是哪一个。在之前的文章《基于平安多方计算 (MPC) 的隐衷计算技术(一)》中已介绍过一种实现计划，故本文不再赘述。
▲ 布尔机密分享
在平安多方计算中会应用机密分享将数据进行拆分后分享进来，每一方拿到每个数据的相应碎片，对于原始数据的计算逻辑都会转为对碎片的计算，在整个计算逻辑实现后，再将碎片的计算结果进行汇聚还原以获取原始数据的计算结果。
布尔机密分享是指将一个布尔值 b 拆分成两个碎片 b0、b1，将两个碎片汇聚到一起即可还原出原始数据 b。
碎片生成：随机生成一个布尔值 b0，并和 b 执行异或计算出 b1=b0⊕b
碎片还原：对两个碎片执行异或操作
b=b0⊕b1
异或运算：布尔机密分享在异或操作上是满足同态性质的，在本地通过对碎片进行异或操作再还原就等价于对原始数据的异或操作
a=a0⊕a1，b=b0⊕b1
a⊕b=(a0⊕b0)⊕(a1⊕b1)
与运算：布尔机密分享对于与操作不满足同态性质，应用不经意传输技术以实现平安的与操作：
Alice 持有碎片 a0 和 b0，Bob 持有碎片 a1 和 b1，通过与运算使得 Alice 获取 c0，Bob 获取 c1，c0⊕c1=(a0⊕a1)∧(b0⊕b1)，并保障单方碎片的平安；
Alice 作为不经意传输的发送方，随机生成一个布尔值 r 作为 c0，并按下图生成不经意传输的输出：
Bob 作为不经意传输的接管方将本人的碎片 a1，b1 拼接成 a1||b1 作为不经意传输的选择项获取数据 r⊕((a0⊕a1)∧(b0⊕b1))作为 c1；
可验证 c0⊕c1= r⊕r⊕((a0⊕a1)∧(b0⊕b1))=(a0⊕a1)∧(b0⊕b1)；实质是将与运算的所有可能性列举进去，退出随机项后由另一方依据本人的数据抉择混同后的计算结果。
– 实现思路 –
▲ 明文比拟
首先不思考比拟运算的隐衷性，平时状况下两个数是如何比拟大小的：
将两个数对齐为雷同长度的数字数组，长度不够的则在后面补 0
a=123，b=5879，a=>[0,1,2,3]，b=>[5,8,7,9]
对两个数组外面的数字进行程序比拟，如果对应位的数字相等，则持续比拟下一位，直到有一位不相等，最早不相等那位的比拟后果即为两个数据的比拟后果，若所有位的数字都相等，则两个数据相等。整个过程可演绎为以下公式：
X，Y 都是长度为 n 的数据，1{X<Y}，1{X=Y}是求值表达式，满足大括号内条件时为 1 否则为 0
X=x0||x1||x2||…||x(n-1)，Y=y0||y1||y2||…||y(n-1)，xi，yi 示意拆分后的第 i 位数据
Xi=xi||…||x(n-1)，Yi=yi||…||y(n-1)，用于示意去除前 i - 1 位后的数据
1{X<Y} = 1{x0 <x0} ⊕ (1{x0 = y0} ∧ 1{X1< Y1})
1{X1<Y1} = 1{x1<x1} ⊕ (1{x1= y1} ∧ 1{X2 < Y2})
...
1{X(n-1)<Y(n-1) } = 1{x(n-1) <y(n-1)}
▲ 不平安的隐衷比拟
如果要将上述比拟计划转为隐衷比拟，最容易想到的计划是将两个最小比拟单位的数的比拟隐衷化，在之前的文章《优雅的求职——隐衷比拟算法实例》中曾经介绍过：对于两个最小比拟单位的比拟可通过不经意传输协定来实现。这样的确是保障了单个最小比拟单位的安全性，然而对于某些状况，会暴露出数据的一些状况：
a=1230 b=1231，对于这两个数字的比拟，如果 b 作为 ot 的接受方也就是最小比拟单元数据比拟后果的获取方，依照上述计划进行比拟，会有两点额定信息被泄露：
1）在前几位雷同的状况下：b 会晓得 a 的前三位是 123；
2）两个最小单元的数据是最小单元范畴的两端数据：b 会晓得 a 的最初一位是 0；
而依据以上两个信息 b 甚至能够间接反推出 a 的数据，在这种状况隐衷比拟也就不隐衷了。
▲ 打消不平安
本论文中的隐衷比拟协定，整个比拟思路和下面不平安的隐衷比拟是统一的，然而该协定引入了机密分享技术，在通过不经意传输协定获取比拟后果时发送方对每个数据都混同上一个随机项，这样单方都不会获取到最小比拟单元数据的比拟后果，而是比拟后果的碎片，并应用碎片依照明文比拟的流程递归的进行比拟，所有最小比拟单元都比拟实现后，再将比拟后果的碎片进行还原以获取整个数据的比拟后果。
因为最小单元的比拟后果都是碎片，到比拟完结才会还原递归计算的后果，就防止了获取最小比拟单元比拟后果导致的信息泄露。
– 协定流程 –
Alice 领有数据 x，Bob 领有数据 y，数据的二进制长度为 l，最小比拟单元的二进制长度为 m，划分的最小比拟单元个数为 q =l/m，最小比拟单元的十进制最大值为 M =2^m-1
1）单方别离划分数据：x=x0||…||x(q-1)，y=y0||…||y(q-1)
2）对于所有的最小比拟单元 xi(0<=i<q)，通过不经意传输获取每个最小比拟单元比拟后果的碎片
Alice 作为不经意传输的发送方筹备数据：随机生成布尔值 <lt_i>_0，<eq_i>_0，别离作为 xi 是否小于和等于 yi 的布尔分享碎片，对于 0 <=j<=M，别离设置两个不经意传输实例的输出为：
sij=<lt_i>_0 ⊕ 1{xi<j}
tij=<eq_i>_0 ⊕ 1{xi=j}
Bob 将 yi 作为输出别离执行两个不经意传输实例，获取两个比拟后果的碎片：
<lt-i>1 和 <eq-i>1
例如当 m 取 2 时，Alice 的第一个最小比拟单元 x0=2，Bob 的第一个最小比拟单元 y0=1，Alice 随机生成 <lt_0>_0，<eq_0>_0，并按下表生成两个不经意传输的输出：
Bob 应用 y0 作为两个不经意传输的选择项，获取：
<lt_0>_1=0⊕<lt_0>_0，<eq_0>_1=0⊕<eq_0>_0
3）所有最小比拟单元比拟实现后，单方都获取了对应的最小比拟单元间是否小于和是否等于的布尔分享碎片，即可依照明文比拟流程，应用碎片递推计算出最终比拟后果的碎片。
对于碎片的异或操作，只须要进行本地对碎片进行异或就行。对于碎片的与操作，则须要依照下面介绍的计划通过不经意传输计算出后果的碎片。
在递推过程中次要有两个中央须要执行与操作：
当后面所有比拟单元相等，须要比拟下一个时：
1{x0||x1 = y0||y1} ∧ 1{x2 < y2}
计算后面所有比拟单元是否都相等时：
1{x0||x1 = y0||y1} = 1{x0 = y0} ∧ 1{x1 = y1}
– 总结 –
该协定整体思路和明文的比拟流程统一，并应用不经意传输和机密分享技术保证数据的隐衷性，也是以后效率比拟高的协定。
对于单个元素的比拟，与运算的 OT 实例，无奈通过 OT 扩大进行优化，因为须要进行递归的计算，前后有依赖关系。对于批量元素的比拟则可在纵向对于雷同地位与运算的 OT 实例通过 OT 扩大来优化效率。
作者简介
刘敬
趣链科技数据网格实验室 BitXMesh 团队
参考文献
原论文：Rathee D, Rathee M, Kumar N, et al. CrypTFlow2: Practical 2-party secure inference[C]//Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 2020: 325-342.