共计 7930 个字符，预计需要花费 20 分钟才能阅读完成。
一 背景
近年来，随着大数据与人工智能的流行，针对集体的个性化的举荐技术的一直倒退，人们在享受便当的同时，也深深的感觉到无处不在的监控与监督，比方
- 刚刚浏览了一个网站的商品，当去其余网站拜访的时候就会举荐相似的产品；
- 刚刚搜寻了某件商品，在很多其余的场景中都会给你举荐。
这种体验，提供了一些便当，刚开始大家都感觉互联网十分智能化，然而如果认真想想，就感觉本人的网上进行裸奔，你做了什么，他人都是一清二楚，个人信息毫无隐衷可言，如果用这些信息进行欺骗等，会造成重大的损失，细思极恐。
不过随着宽广用户对于个人隐私的器重水平不断加强，以及法律法规的不断完善，针对个人隐私的爱护提出了更高的要求，什么样的数据能够采集、收集与应用，如何应用都是一个比拟敏感的问题。十三届全国人大常委会第三十次会议表决通过了《中华人民共和国个人信息保护法 》，并与 2021 年 11 月 1 日起实施。确立个人信息爱护准则、标准解决流动保障权利、禁止“大数据杀熟”标准自动化决策、严格爱护敏感个人信息、赋予集体充沛权力等。新规实施后，守法的主体将 最高可处五千万以下或者上一年度营业额百分之五 以下的罚款。
鉴于上述情况，近年来隐衷计算技术被一直的提及，源于其有优良的数据保护作用，使得“数据不出域、数据可用不可见、数据可算不可见”，限定了数据的应用场景，避免了数据的泄露，而引起了业界的热捧。
那么如何学习隐衷计算呢？笔者认为这门技术是门综合性十分强的畛域，波及到泛滥方向，比方密码学、数学、大数据、实时计算、高性能计算、分布式、传统机器学习框架与算法，深度学习框架与算法等等，整体技术非常复杂，对于从业者的要求极高。依据目前市场上隐衷计算的次要相干技术个性，可分为四大方向与五大基座：：
《隐衷计算根底组件》系列文章会和大家一起介绍下基座二：隐衷计算的根底技术，本章次要介绍重要的根底组件：混同电路的第一局部。；
二 平安模型的定义
在隐衷计算的场景中，依据各个参与方的可信水平能够定义三种平安模型，用于形容在隐衷计算过程中的可信水平度量与定义。
- Real-Ideal Paradigm（现实模型）：在现实模型中，每一个参与方都是可信的，一方将其信息发送给另一方，另一方不会去查看这份信息，只会依据规定计算出后果，并发送给下一方或者所有参与方。
- Semi-Honest Security（半诚恳模型）：半诚恳模型就是参与方会诚恳的运行协定，然而他会依据其它方的输出或者计算的两头后果来推导额定的信息。
- Malicious Security（歹意模型）：歹意模型则可能不会诚恳的运行协定，甚至会搞破坏。
在事实世界中，感性模型是不存在的，但相比于歹意模型，参与方其实更想真的想获取到对本人有用的信息以及以外更多的信息（比方推导两头计算环节），所以少数状况下合乎半诚恳模型。因而上面的探讨都是基于半诚恳模型下的。
三 前置常识 – 不经意传输
不经意传输：针对不经意传输的具体的解释，请看我以前写的文章 隐衷计算根底组件系列 - 不经意传输
这里在简略说下，对于不经意传输，我集体认为有几点比拟重要：
- 须要参加运算的元素的个数是确定的；
- 须要参加运算的元素的程序是绝对固定的；
- 异或操作的可逆性；
流程：
- 第一步：音讯发送者 Alice 有两个待发送音讯 M0 与 M1。生成两对 RSA 秘钥对，而后将两个公钥 Puk0、Puk1 发送给接受者 Bob。
-
第二步：Bob 生成一个随机数 R，并用收到的两个公钥之一加密随机数 R，用哪个秘钥取决于 Bob 想获取 M0 还是 M1（参照百万富翁的案例，这个时候须要晓得程序或者标记）
- 如果想要失去音讯 M0，就用 Puk0 加密随机数 R 生成 $R^
$，并将密文后果 $R^$ 发送给 Alice。 - 如果想要失去音讯 M1，就用 Puk1 加密随机数 R 生成 $R^
$，并将密文后果 $R^$ 发送给 Alice。
- 如果想要失去音讯 M0，就用 Puk0 加密随机数 R 生成 $R^
- 第三步：Alice 生成的两对秘钥对的私钥（Pr0，Pr1）别离解密收到随机数密文（只有一个还原了随机数，然而 Alice 不晓得是哪个），并失去两个解密后果（D0，D1），并将两个解密后果（D0，D1）别离与要发送的两条信息进行异或（D0 异或 M0，D1 异或 M1，留神不是笛卡尔积，是依照协定程序来进行异或操作），并将两个后果 E0，E1 依照协定程序发给 Bob。
- 第四步：Bob 用以前生成的随机数 R 与收到的 E0 或 E1 别离做异或操作（如果要获取 M0 音讯就异或 E0，如果要获取 M1 音讯就异或 E1），失去最终的后果。
四 混同电路（Garbled Circuits，GC）
如上图所示，外面咱们的两个老朋友 Alice 和 Bob 想要搞点事件，还是比拟谁更富裕，然而不心愿相互颁布本人的财产值。这次咱们不实用机密分享、不经意传输来解决，咱们将问题转化为数字电路来解决（比方比拟电路，或者 emmmm 什么电路）。电路外面有一些门，每个门包含输出线（input wire）和输入线（output wire）。混同电路就是通过加密和调整序列的值来覆盖信息的。在最经典的混同电路中，加密和扰乱是以门为单位的。每个门都有一张真值表。
混同电路具体是什么含意呢？其实从他的名字咱们能够得出一个论断，他肯定是用到了电路（数字电路），咱们推断他应该是将原始的多维混合运算转化为一个一个的简略的根底电路，继而进行组合，失去最初的后果。同时因为在运算的过程中，须要针对运算各方进行隐衷爱护，所以应用了不经意传输的隐衷计算技术进行加强，最终失去最初的后果。
运算的性能随着是由整体原始的运算量决定的，因为采纳的是不经意传输的技术，所以绝对于同态加密这种耗时耗力的模式，性能还是能够承受的。
4.1 场景设定
假如场景外面的人物依然是咱们的老朋友 Alice 和 Bob，两个人接着进行炫富比拟，这两个人假如都是百万富翁，在某个较为私密的场合，他们想比拟下谁更加富裕，然而又不想让对方晓得彼此具体的财产值。
这个问题咱们在后面介绍过，应用不经意传输是能够解决的，而且算法协定也和大家分享过，这里咱们不间接应用不经意传输进行解决，而是应用混同电路。
假如，咱们设定 Alice 的财产值是 X，Bob 的财产值是 Y，那么咱们就是要求解 X 与 Y 谁大的问题，那么这个问题如何转化为混同电路问题呢？
要害就在这个 电路 上，咱们接着看。
4.2 数字电路转化
在应用混同电路之前，须要先对原始问题进行数字电路表白。咱们晓得可计算问题都能够转换为一个个电路，于是就有了加法电路、比拟电路和乘法电路等等。当然，更简单的计算过程，如深度学习等等，也是能够转换成电路的，只不过转换后的电路较为简单与宏大。一个电路是由一个个门（gate）组成的，比方与门、非门、或门、与非门等等。
数字电路是有一些简略的门（比方与门、非门、或门、与非门等等）组合而成，输出是 0、1 的数值，将一个简单的运算替换成若干个简略的门（gate）的组合。
对于下面的问题，咱们看下对应的数字电路是如何进行电路转化的。
- 1 位数值比拟
- 2 位数值比拟
由此可见，通过将运算转化成数字电路是可行的，并且转化后须要一个真值表和多个门。
本文并不打算过多介绍数字电路的常识，有趣味的读者能够去看下《数字电路》这本书，所以本文设定一个门与相应的真值表进行解说，请大家持续往下看。
4.3 算法协定
这里咱们针对 与门 进行解说，整体流程次要蕴含四大步骤。
-
第一步：Alice 生成混同电路
- 首先，Alice 生成电路的 Truth Table，并且对于真值表依照与门进行计算标注（如下图所示）。
- 而后，Alice 进行电路的 Truth Table 替换（替换值代替实在值，对实在值进行暗藏），例如输出 $X_0$ 代表 X =0，输出 $X_1$ 代表 X =1，输出 $Y_0$ 代表 Y =0，输出 $Y_1$ 代表 Y =1，输入 $Z_0$ 代表 Z =0，输出 $Z_1$ 代表 Z =1（这些值，咱们称之为替换值，随机生成，无规律；原始的输出称之为实在值）。
-
而后，Alice 针对替换后的 Truth Table 的输入进行两次对称加密（加密与加密的秘钥雷同），并且加密的秘钥别离是 Truth Table 的两个输出。比方 Truth Table 的某行两个输出别离是 $X_0$ 与，输入是 $Z_0$，那么替换后的真值表的某行就是 $Enc_{X_0, Y_1}(Z_0)$;
- 而后，Alice 将加密过后的 Truth Table 的行打乱失去 Garbled Table。所以 Garbled Table 的内容和行号就无关了。这越是混同电路中的混同二字的由来。
-
第二步：Alice 和 Bob 通信
- 首先，Alice 将本人的输出发送给 Bob。比方取输出 $X=0$，Alice 就会发送替换值 $X_0$ 给 Bob。因为 Bob 只是收到 $X_0$ 对应的替换值，也就无从通晓 Alice 的原始值了。
- 而后，Bob 通过不经意传输协定，从 Alice 那里取得他的输出对应的替换值，并且通过协定，能够让 Alice 不晓得 Bob 具体应用的是那个原始值，这里假如 Bob 的输出是 1，所以通过不经意传输最终获取 $Y_1$ 的替换值。具体流程：通过不经意传输协定保障了 Bob 在替换值 $Y_0，Y_1$ 中取得一个，然而 Alice 并不知道 Bob 取得了哪一个。（具体流程能够加入 隐衷计算根底组件系列 - 不经意传输）
-
而后，Alice 将 与门 的 Garbled Table 发给 Bob。在这个例子中，一共有四个 Garbled Table。
-
第三步，Bob evaluate 混同电路
- 首先，Alice 和 Bob 通信实现之后，Bob 尝试进行电路解密，目前 Bob 已知的信息有输出 $X_0$ 和 $Y_1$，所以应用这两个值，对于 Garbled Table 的四行进行解密，能够看到，这里只有第三行是能够解密胜利的。
- 而后，Bob 尽管解密胜利，然而因为解密出的 $Z_0$ 依然是替换值（非原始值 0），所以无奈取得其余信息。
-
第四步，Alice 和 Bob 共享后果
- 最初 Alice 和 Bob 共享后果。Bob 分享解密后替换值后果 $Y_0$ 给 Alice，Alice 晓得替换值与原始值的替换关系，进行替换，并且能够将最终后果分享给 Bob。
一个与门的混同电路流程到此曾经分享结束，因为事实中应用的运算较为简单，所以波及到将运算转化成数字电路，并且将数字电路优化的过程，最终分解成一个一个的门。所以想对这块有深刻钻研的同学，须要对数字电路多下些功夫。
然而万变不离其宗，所有的简单的事件都是简略的形成，置信大家在相熟了下面的流程的根底上，对于混同电路会有一个正确的认知。
五 参考资料
- [1] A. Yao. Protocols for secure computations. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, SFCS’82, pages 160–164, 1982.
- [2] A. Yao. How to generate and exchange secrets. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, SFCS’86, pages 162–167, 1986.
- [3] O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC’87, pages 218–229, 1987.
- [4] D. Bogdanov, R. Talviste, and J. Willemson. Deploying secure multi-party computation for financial data analysis. In Financial Cryptography and Data Security: 16th International Conference, FC 2012, Kralendijk, Bonaire, Februray 27-March 2, 2012, Revised Selected Papers, pages 57–64, 2012.
- [5] Y. Lindell and B. Pinkas. Secure multiparty computation for privacy-preserving data mining. The Journal of Privacy and Confidentiality, 1(1):59–98, 2009.
- [6] B. Hemenway, S. Lu, R. Ostrovsky, and W. Welser IV. High-precision secure computation of satellite collision probabilities. In Security and Cryptography for Networks: 10th International Conference, SCN 2016, Amalfi, Italy, August 31 – September 2, 2016, Proceedings, pages 169–187, 2016.
- [7] R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. In Advances in Cryptology — EUROCRYPT’97: International Conference on the Theory and Application of Cryptographic Techniques Konstanz, Germany, May 11–15, 1997 Proceedings, pages 103–118, 1997.
- [8] P. Bogetoft, D. Christensen, I. Damgård, M. Geisler, T. Jakobsen, M. Krøigaard, J. Nielsen, J. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach, and T. Toft. Financial cryptography and data security. chapter Secure Multiparty Computation Goes Live, pages 325–343, 2009.
- [9] M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design. In Proceedings of the 1st ACM Conference on Electronic Commerce, EC’99, pages 129–139, 1999.
- [10] R. Kulkarni and A. Namboodiri. Secure hamming distance based biometric authentication. In 2013 International Conference on Biometrics (ICB), pages 1–6, June 2013.
- [11] J. Bringer, H. Chabanne, and A. Patey. Shade: Secure hamming distance computation from oblivious transfer. In Financial Cryptography and Data Security: FC 2013 Workshops, USEC and WAHC 2013, Okinawa, Japan, April 1, 2013, Revised Selected Papers, pages 164–176, 2013.
- [12] M. Kiraz, Z. Genç, and S. Kardaş. Security and efficiency analysis of the hamming distance computation protocol based on oblivious transfer. Security and Communication Networks, 8(18):4123–4135, 2015.
- [13] J. Launchbury, D. Archer, T. DuBuisson, and E. Mertens. Application-scale secure multiparty computation. In Programming Languages and Systems: 23rd European Symposium on Programming, ESOP 2014, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014, Grenoble, France, April 5-13, 2014, Proceedings, pages 8–26, 2014.
- [14] O. Biçer. Efficiency Optimizations on Yao’s Garbled Circuits and Their Practical Applications. Cryptography and Security, 2017.
- [15] O. Goldreich. Cryptography and Cryptographic Protocols. Distributed Computing – Papers in Celebration of the 20th Anniversary of PODC, 16 (2–3): 177–199, 2003.
- [16] Beaver D, Micali S, Rogaway P, et al. The round complexity of secure protocols[C]. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC’90, pages 503–513, 1990.
六 番外篇
集体介绍：杜宝坤，隐衷计算行业从业者，从 0 到 1 率领团队构建了京东的联邦学习解决方案 9N-FL，同时主导了联邦学习框架与联邦开门红业务。
框架层面：实现了电商营销畛域反对超大规模的工业化联邦学习解决方案，反对超大规模样本 PSI 隐衷对齐、平安的树模型与神经网络模型等泛滥模型反对。
业务层面：实现了业务侧的开门红业务落地，创始了新的业务增长点，产生了显著的业务经济效益。
集体比拟喜爱学习新货色，乐于钻研技术。基于从全链路思考与决策技术布局的考量，钻研的畛域比拟多，从工程架构、大数据到机器学习算法与算法框架均有波及。欢送喜爱技术的同学和我交换，邮箱：baokun06@163.com
七 公众号导读
本人撰写博客曾经很长一段时间了，因为集体涉猎的技术畛域比拟多，所以对高并发与高性能、分布式、传统机器学习算法与框架、深度学习算法与框架、明码平安、隐衷计算、联邦学习、大数据等都有波及。主导过多个大我的项目包含批发的联邦学习，社区做过屡次分享，另外本人保持写原创博客，多篇文章有过万的浏览。公众号 秃顶的码农 大家能够依照话题进行间断浏览，外面的章节我都做过依照学习路线的排序，话题就是公众号外面上面的标红的这个，大家点击去就可以看本话题下的多篇文章了，比方下图（话题分为：一、隐衷计算 二、联邦学习 三、机器学习框架 四、机器学习算法 五、高性能计算 六、广告算法 七、程序人生），知乎号同理关注专利即可。
<font color=red> 所有有为法，如梦幻泡影，如露亦如电，应作如是观。</font>
本文由 mdnice 多平台公布