隐衷比拟是指在不裸露单方具体数值的前提下，获取单方数值的大小关系。最早起源于姚期智的百万富翁问题：有两个百万富翁想要比拟下谁更富裕，然而又不想走漏本人有多少钱，如何在没有可信第三方的状况下进行比拟？这个问题是由中国第一个也是目前为止惟一一个图灵奖获得者姚期智在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.