SecureNN
SecureNN是SecureML与ABY后面的工作。
Context
在基于安全多方计算的隐私保护机器学习（Privacy Preserving Machine Learning，PPML）语境下，最先开始考虑的神经网络便是CNN，这类网络简单，但是效果很好。
SecureML与ABY3是两个较早的工作，并向我们展示了要实现CNN的PPML工作，需要关注两点，乘法后的截断操作以及比较大小操作。
Background
SecureML对于截断，是本地截断，并且证明了其出错的概率很小。但实际情况中，这个出错概率并不小，所以SecureML的截断协议其实是完全不可用的。他们能在实验中取得较好的结果是因为他们的秘密共享使用了固定的随机数进行分割，这点可以在Bicoptor2中找到相关证据。
对于非线性操作，SecureML直接使用一个全新的激活函数，并用GC来计算。
ABY3在SecureML基础上，沿用了大致思路，但是将秘密共享从两方改成了三方，来减轻离线阶段产生乘法三元组的压力。
SecureNN
SecureNN是在SecureML和ABY3的直接继承，主要思路是改进非线性函数的计算，也就是比较大小操作。
SecureML和ABY3的思路来自ABY框架，主要思路都是通过在不同世界之间转换，获取最好的协议效率。
SecureNN的主要观察是，比较大小并不需要GC。通过在不同的环中切换与一定的数学性质，也可以计算比较大小。
Observation
比较两个数的大小关系，可以归结为提取一个数的MSB。
SecureNN的观察是，当我们在一个奇数环上时，例如\(\mathbb{Z}_{2^{64}-1}\)中，\(\text{MSB}(a)=\text{LSB}(2a)\)。
这是因为，假设我们在一个阶数为\(n\)的环上，当\(a\)的MSB是1时，有\(a>n/2\)，则\(2a>n\)会产生溢出，导致\(2a \mod n\)是个奇数，也就是\(\text{LSB}(2a)=1\)。
反之，同样成立。
因此当我们需要比较大小操作时，我们只需要从偶数环例如\(\mathbb{Z}_{2^{64}}\)上转换到环\(\mathbb{Z}_{2^{64}-1}\)计算LSB即可，而LSB的计算相对容易。
这样整体协议就要比GC高效多了。
也就是说，SecureNN的主要贡献是通过多个环的组合，将比较大小操作从GC中解放出来，从而提高了协议的效率。
Protocol for DReLU
从DReLU开始，有\(\text{DReLU}(x) = 1, x \ge 0\)且\(\text{DReLU}(x) = 0,x<0\)。
我们直接有\(\text{DReLU}(x) = 1\oplus \text{MSB}(x)\)。
因而可以将DReLU函数规约为求解MSB。
而对于MSB，无论是ABY、ABY3还是SecureML，都是通过一个GC来计算，即需要一个A2Y将算术秘密共享转化为Yao共享，再调用GC的GT电路求解得到MSB的Yao共享，最后通过Y2A转换回算术秘密共享。其中A2Y是对算术秘密共享进行比特分解后，评估一个GC下的加法电路获得Yao秘密共享。
SecureNN的主要观察是，MSB的求解可以绕开GC。
具体来说，我们需要三个不同大小的环，\(\mathbb{Z}_{2^{64}},\mathbb{Z}_{2^{64}-1}\) 和 \(\mathbb{Z}_{p}\)，其中\(p\)是一个小素数，可以是67。
在一个奇数环上，\(\text{MSB}(a) = \text{LSB}(2a)\)。
这是因为，当MSB是1时，代表\(a>n/2\)，那么\(2a \mod{n} = 2a-n\)就是个奇数，则LSB为1。
否则当MSB为0时，\(a<n/2\)，那么\(2a \mod{n} = 2a\)是个偶数，则LSB等于0。到这里，我们将\(\text{MSB}\)规约为求\(\text{LSB}\)。
为了求解\(\text{LSB}\)，我们注意到对于奇数环上的\(u,v,w\)，如果有\(w=u+v\)，则有\(\text{LSB}(w) = \text{LSB}(u) \oplus \text{LSB}(v)\)当且仅当\(u+v<n\)，否则有\(\text{LSB}(w) = \text{LSB}(u) \oplus \text{LSB}(v) \oplus 1\)。
也就是说，为了求解\(y\)的LSB，记为\(y[0]\)，我们可以产生一个随机数\(x\)并且令\(r=y+x\)，那么只要知道\(r[0],x[0]\)，\(y+x < n?\)即可。
假设三个参与方分别为\(P_0,P_1\)和\(P_2\)，其中，所有秘密共享以两方共享的形式共享在\(P_0,P_1\)手上，\(P_2\)只负责一些辅助的计算，类似于预处理过程。
我们让\(P_2\)产生一个随机数\(x\)，这个随机数只有\(P_2\)直到，并且\(P_2\)不会以任何形式和其他参与方共享这个信息。
那么\(P_0\)与\(P_1\)之间就可以在奇数环上求出\(r=y+x\)。
\(x[0]\)可以由\(P_2\)提供，\(P_0\)与\(P_1\)共同恢复\(r\)，可获得\(r[0]\)。
注意到，\(r\)不可以被\(P_2\)知晓。
最后只需要知道\(y+x<n?\)。
为了求解\(y+x < n?\)，我们注意到\(y+x > n\)当且仅当\(x>r\)。这是因为如果\(y+x > n\)， 则有\(r = y+x \mod{n} = y+x -n = x + (y-n)\)。
因此最终问题被规约为比较\(x\)与\(r\)的大小关系。
至此，似乎我们又绕回来了。
但注意到虽然\(x\)共享在\(P_0\)与\(P_1\)之间，但\(r\)对于\(P_0\)与\(P_1\)是公开的。
但其实我们是将DReLU规约为一个秘密共享与一个公开值之间的比较大小关系。而后者的实现更加简单，并且可以不需要GC。
Comparison
Sharing semantics
SecureNN虽然是三方协议，包含\(P_0,P_1,P_2\)。其中\(P_0\)与\(P_1\)是掌握秘密共享的参与方，\(P_2\)主要起到辅助计算的作用，是非对称的三方架构，只有\(P_0\)与\(P_1\)对称。这个架构和Bicoptor的架构相似。
Comparison、MSBExtract，ReLU，DReLU，Millionaire都有什么区别？
这些名词都涉及到一个核心操作，即在秘密共享的基础上比较大小，但这些协议都有什么区别呢？
通常来说，Comparison是将秘密共享值和一个明文值比较大小
Millionaire是各个参与方持有的值之间的比较大小
MSB、DReLU是秘密共享值的符号位
我们能立即想到，MSB和Comparison是相通的
Question:
- 一定要建立在三方基础上吗？
- 是否可以拓展到两方基础上？