前言：
本文为阿里CRO密码学与隐私保护技术负责人：洪澄老师 ，在“隐语开源社区meet up 北京场“的分享内容。从什么是半诚实模型和恶意模型讲起，以OT协议、神经网络推理、ECDH PSI作为例子，讲述了恶意安全性的重要性。随后围绕恶意安全性常见的三大误解进行一一纠正，探讨了学术届与工业界对恶意安全模型隐私性&正确性要求的异同。最后展开分享了实现恶意模型的两种方案:消息校验码MAC，以及DZKP分布式零知识证明。点击可跳转观看：全场内容精华+视频
哔哩哔哩，，，
安全多方计算中的半诚实模型与恶意模型
小程序
首先从什么是半诚实模型和恶意模型讲起。
在讲半诚实模型和恶意模型之前，先介绍安全多方计算。通俗地讲，安全多方计算是多人合作计算一个函数，并且除了这个函数的计算结果之外，参与者得不到任何其他消息，这就是安全多方计算。大家比较熟知的是姚氏百万富翁问题，即一个人想跟另一个人比较谁的财富多，但是互相不想透露给对方自己具体的财富值。那么，安全多方计算是否可以无条件达到除计算结果之外不泄露任何中间信息的安全目标呢？答案是：它是有条件的。
条件之一就是到底存在什么样的攻击者。大体可以将攻击者划分为两种：一种是半诚实攻击者，会忠实地按照既定的协议去运行，比如百万富翁问题规定比大小那就只是比大小，再比如打牌的时候要先切牌再抽牌，那就必然先切牌再抽牌，不会作弊；还有一种攻击者则是恶意攻击者，也就是并不会按照协议规定去做，比如规定是比大小，但其可能会更改协议运行，试图从中得到一些别的好处。
对于这两种攻击者防御他们的难度显然是不一样的，如果能防御半诚实的攻击者，那这种安全多方计算协议就满足半诚实安全性，它只需要保证这个协议的过程中不会泄露任何其他信息，比如说百万富翁问题比大小，除了大小结果没有任何中间泄露即可；如果我们要抵挡恶意攻击者的话，那我们不仅要满足半诚实安全性，我们还需要额外的机制来验证参与方是否按照预定的协议去运行，比如说不仅要保证比大小的过程中不会泄露其他信息，还要强制确保除了比大小之外，没有进行其他不相干的事。那么恶意安全性到底有没有必要呢？我们通过一个例子来看：
一个协议满足半诚实安全性，但是恶意敌手可能会将它攻破。如一个OT协议是半诚实安全的（OT即不经意传输：Bob有两条数据，Alice想抽其中的一条，但是她不想告诉Bob具体是哪一条，最后Alice拿到一条且Bob并不知道是哪一条），一个简单的构造方法是，Alice构造两个公钥，并知晓其中一个的离散对数（也就是私钥），然后Bob用这两个公钥加密两条数据发回。因为Alice知道其中一条私钥，所以可以解密其中一个，并且Bob不知道解密的是哪一个，因为对于Bob来说，两个公钥是没有差别的。在半诚实情况下，因为Alice只有其中一个的离散对数，那么只能解密其中一个，确实只拿到了其中一条数据。但是如果Alice是恶意的，她只需要构造两个都知晓私钥的公钥，即可将Bob返回的两条数据都解密，就可以成功危害到Bob的隐私。这个例子可以看出，在某些情况下如果协议只做到半诚实安全是不够的。（此例只说一种OT协议，不是说所有半诚实OT协议都有这种危险，因为OT协议有很多种构造方法。）再举一个例子说神经网络推理：
以保险场景为例，服务器有一个神经网络模型，需要以客户的病历为输入，从而判断是否可以投保或者保费如何定价。那么安全神经网络推理就是要求服务器不能知道客户的病历细节，客户也不能知道服务器的模型逻辑，最后双方只要一个推理结果，就是保费定价是多少。安全神经网络推理是可以满足半诚实安全的，如我们去年的猎豹就已经做到了，并且是目前世界上最快的安全神经网络推理。但是，如果这个客户是恶意的，他是可以通过多次推理来推算出服务器的模型参数的。例如一个恶意的客户他的输入是没有限制的，他可以先输入一个全零的数据，到最后一层时把自己的share加上1，此时服务器神经网络的最后一层数据就被他获取了，进而他可以再来一次推导第二层，即使倒数第二层有点难，有一个非线型的Relu没法直接解出，但是客户再进行一个恶意操作，将自己的Share加上一个巨大的正数， Relu就无效化了，就变成了纯线性变化，此时如同解倒数第一层一样，倒数第二层也可以被解出，由此类推，直至整个服务器的模型全部被解出，这明显这是违背了服务器的隐私需求的。
这篇工作叫做Muse，来自USENIX’Sec21，因其是解方程的原理，需要推理的次数跟模型的参数个数相关，但绝对不大于模型参数的个数，可能远小于模型的个数即可解出方程，如几千次到几万次推理，就可以将整个服务器的模型都窃取过来。可以看到我们半诚实的安全多方计算推理工作是没办法抵挡这种攻击的。再来一个例子，说明半诚实安全的协议并不一定会被恶意攻击者完全破解，如PSI中我们经常用的ECDH PSI：
大家可能经常用这个ECDH的PSI。首先这个协议只是半诚实的，因为并没有对对方发过来的数做任何检测，一个恶意攻击者可以让这些协议产生一些非预期的结果。上海交大的郁昱教授团队曾经做了一项工作：如果恶意的Bob跟Alice进行多次合作，这个恶意的Bob可以篡改自己的数据来得到Alice数据的交集，即Alice两次合作中有没有重复数据，这显然是PSI中额外的信息。但是，要想获取Alice的原文依然是困难的。所以，半诚实协议遭到恶意攻击时究竟会造成何种损失，是需要case by case去看的。讲完了半诚实跟恶意的定义之后，我们来看一些常见的误解。第一个误解：如果做到恶意安全性，就可以防止机器学习中的投毒攻击了。
答案是并不能，因为恶意安全性不防换输入，而投毒是将自己的输入更换，这不属于恶意攻击的范畴。恶意攻击是保证发过来的数据确实对应了一个输入，但这个输入是否是原始数据，协议密码学则无法保证。如百万富翁协议，我实际有100元，但输入却是100万，这个密码协议检查不了，协议只能保证输入的数确实是一个钱数。CCS’22也收录了一篇文章：可以通过投毒攻击来攻破各种隐私计算框架，包括具备恶意安全性的MPC框架。投毒攻击需要通过其他的机制来保护，而不能仅通过实现协议的恶意安全性来保护。第二个误解：只要做到恶意安全性就可以防止合谋攻击。
答案是并不能，恶意安全性与合谋攻击是两个完全独立的安全指标，一个恶意安全的模型可能没法抗合谋，比如说三方计算里面如果两个人合谋可以危害第三个人的隐私，这是完全可能的。而一个半诚实安全的协议它完全可能可以抗合谋，如点对点的两方计算是抗合谋攻击的，但只能满足半诚实安全性，也就是说它两个属性是完全独立的。第三个误解：通过审计日志检测攻击，就实现了恶意安全性。
答案是事后的检查并不能达到恶意安全性，恶意安全性的定义是需要在攻击者成功泄露任何信息之前就终止协议，这叫做恶意安全性with abort（终止），当然这只是恶意安全性最低要求，更高要求是就算有恶意攻击者，整个协议还是能够正常的运行，这个安全性要求就非常高，不是所有的场景都能达到。此处我们不展开探讨，只要满足abort就认为能达到恶意安全性。接下来一起看看现在工业界的标准中对恶意模型有什么要求，结合实际生产进行探讨。
第一个是国际标准ISO 4922-1，另一个是国内信通院的行标《隐私计算产品安全测试方法》，它们都对恶意安全性提出了类似的两个要求，第一个要求隐私性，第二个要求正确性。
学术界常常将这两个指标合二为一，因为隐私性与正确性是很难严谨的分开的。例：Alice和Bob想计算一个函数F，现有一个恶意攻击者攻击导致最后结果变成了G，除了显然违背了正确性，但结果G泄露是否多于F有时候无从比较，所以有没有违反隐私性无法定论。所以学术界一般不区分两者，通常可以通过一个模拟器构造完全随机的交互内容，这个内容跟真实交互是不可区分的，如此隐私性跟正确性就同时保证，只要一个证明就全部覆盖。
工业界为什么需要区分隐私性和正确性呢？我们曾参加了ISO标准的讨论，也参加了信通院这项行业标准的讨论，并且都支持这两个指标的拆分。因为工业中确实存在一些需要区分的场景，如数据方、结果方、计算方分离，数据方以秘密共享的方式输入数据到计算节点后下线，由计算方计算并将结果直接发送给另外的结果方，这里面计算方是不获取任何结果的，结算方就算做任何的恶意行为都无法获得更多的信息，充其量是对正确性造成一些破坏。所以在这个场景中，只需要计算方执行一个半诚实协议就可以保证针对计算方的隐私性。但要实现正确性难度就比较大，如果我们要实现正确性，只能做一个真*恶意安全的协议执行才行。可以看到在这个里面隐私性和正确性出现了一个阶梯性的区分，所以划分成两个不同的要求，主要是与特殊的场景所对应的。恶意模型在学术上有非常重要的意义，而且在工业界也有这样的标准要求，所以接下来我们探讨怎样实现恶意模型。
核心思想是要提供一种机制，让各个参与方向其他的参与方自证行为是正确的，没有违背协议。这个机制有很多种，比如MAC或分布式ZKP零知识证明，我们简要介绍一下。第一个方案是消息校验码MAC，MAC主要用在不诚实大多数中，首先需要一个私钥，这个私钥秘密共享放在两方之间，也就是说没有任何一方知道私钥是多少。那么一个数据的MAC值就是私钥乘以数据，也是秘密共享的。有了MAC之后，原来在半诚实协议下是做秘密共享，但现在所有的秘密共享都是带着MAC值的，包括乘法三元组也都是带MAC的。
可以看到在这种状态下，做加法、常数乘法都跟半诚实一样的，本地完成就行了，因为MAC是线性的。不同之处在于，做乘法的时候需要额外的步骤，熟悉MPC算法的同学知道，拿着乘法三元组运行如图的协议就可以实现乘法，但是在恶意协议里面这一步行不通，这里面需要把E和D复原出来，这里面没办法保证对方发过来的E是正确的，所以需要MAC来验证E跟D的正确性。
检查E跟D的正确性，首先如同半诚实一样将E复原出来，然后需要将即将E的秘密共享跟E的MAC的秘密共享做一个计算，然后把计算结果互相发送，如果结果是0则E是正确的，如果不是0则E就是错的，便是发现了恶意行为，就终止协议。这里有一个小小的思考：为什么要“commit to z”？因为网络延迟总有一方是早一点得到那个Z的，那么如果他恶意的返回发送一个负Z，结果是0就对对方形成了欺骗，不能允许这样的行为出现，这就需要commit，事先对后面要发的z形成一个约束，不能恶意发送。通过这样的步骤可以成功完成恶意安全的乘法。基本上有了乘法跟加法之后就可以构成任何协议了，这里面核心难点是我们需要三元组也是带MAC的，带三元组MAC的生成是一个非常困难的事情，而且历史也悠久，已经有非常多的研究，从2012年的SPDZ开始，MASCOT，Overdrive，它一直在快速的发展中，目前还在不停的进展。一句话总结，目前恶意安全的MAC的乘法三元组生成协议，它的成本达到了半诚实的100倍以上，唯一的好处就是它可以在预处理阶段完成，跟真正的数据没有关系。这个100倍还是有优化空间的，我们可以在这方面再进行一些研究。
第二种是零知识证明，前面的D即分布式零知识证明，这个主要用在诚实大多数的场景。我们看一个半诚实的协议ABY3，ABY3的乘法是很简单的，三个share乘以三个share，就是9项，每人算3项即可。但是如果放到恶意协议里面这么做就不够了，P2需要知道P1发过来的三项是对的才行，需要把这个等式记做一个五元方程，这里一共出现了五个未知数，其中有三个未知数是P2知道，有两个未知数是P3知道，如果用普通的零知识证明是无法做到的，因为一个验证者有两个未知数不知道，所以P2和P3必须合作一起验证P1是否做了正确的事。
P1首先通过插值生成5个一次多项式F1-F5，然后把这5个一次多项式乘起来得到一个二次多项式，把二次多项式的系数以秘密分享的方式发送给另外两方，另外两方各得到了一个二次多项式，他们检查一下这个二次多项式在P1点的值是不是0，如果是0就确认成立。
但这还不够，因为还无法确认发过来的多项式是真的用五个未知数构造的，还是随便发了一个P1等于0的多项式，还需要如下的协议，首先我们刚才插值用到了五个随机数，随机数需要以秘密共享的方式发送给另外两个人，另外两个人根据未知数的秘密共享以及自己知道的那个未知数，每个人都生成五个一次多项式，P2可以生成五个，P3可以生成五个，P2和P3协商一个随机数，计算这5个多项式，10个多项式在随机数上的取值再加起来，可见这个东西就是F1在R上的取值。然后把这么多项都在R上计算一下，跟P1发过来的多项式在R上的结果对比一下看是否成立，成立则说明这个多项式真的是用我们共同知道的那五个未知数构造的。这个验证就通过了，证明收到的那些数真的是P1诚实构造的。由于ABY3的乘法要做三次，三个自证之后乘法就满足恶意安全性了。这与半诚实协议相比额外的代价首先来自于插值生成多项式。虽然这个例子里面只是一次多项式，但是如果并行验证很多个乘法，这会是一个不只一次的多项式，插值过程还是耗不少计算量的，插值之后高次多项式的相乘也是比较耗计算量的。它的成本来说，是半诚实的2-10倍，如ABY3可能会达到10倍，而经过一些优化可能会达到2倍。看了目前两种主流恶意模型的实现方式，可以总结一下，目前半诚实模型安全多方计算的研究已经接近极限，low hanging fruit基本上都被摘完了，例如半诚实的神经网络推理，在猎豹成果基础上再大幅提升已经非常困难了。接下来在半诚实方面还能做的工作可能是硬件或者网络优化，或者说针对一个特定的场景进行一些特定的应用优化，密码学角度是很难再改进了。
而恶意模型具备更强的安全性，而且确实存在一些高安全场景，没法假设只有半诚实敌手，确实可能存在恶意的攻击者。但是目前恶意模型方面可以直接用的成果还比较少，因为成本远超于半诚实模型，半诚实模型已经比明文慢不少倍了，恶意模型慢更多倍。从好处看，说明恶意模型这方面的研究还有很多可以做，里面涉及不少额外的技术栈，包括零知识证明等等。我们在这方面已经取得了一定的成果，并且这个成果将来会贡献到隐语中，有望让隐语成为国内唯一一个具备恶意安全性的隐私计算开源框架。以上就是我今天的报告内容，谢谢大家。
