杜宝坤

V1

2023/01/30阅读:22主题:全栈蓝

安全多方计算概述

一 背景

本章主要介绍安全多方计算Secure Multi-Party Computation,MPC,安全多方计算是隐私计算三大方向之一,也是隐私计算最开始研究的方向。

在编写本章的时候,我也犹豫了很久。原因在于在以往的很多材料中,安全多方计算与隐私计算五大基座之隐私组件基座在很多情况下是一起来讲的,基本就是隐私组件基座的应用。

但是从隐私计算的整体角度来看,隐私组件基座是一个公共的基础组件,因为在隐私计算的三大方向里面安全多方计算与联邦学习都应用到了隐私基座的内容,所以隐私基座属于一个基座性质的基础能力,安全多方计算与联邦学习都是应用了这个基座。同时安全多方计算还需要数学、安全以及工程方面的支撑,所以本书对于安全多方计算的体系结构等进行了重新的定义。

那么安全多方计算针对五大基座的要求是什么呢?

  1. 数学基座

  2. 安全基座

  3. 工程基座

  4. 隐私组件基座

安全多方计算是一个多学科的交叉领域,要想将安全多方计算做好,需要有充足的知识储备。

二 MPC的定义

安全多方计算隶属于隐私计算的第一代,其理念的提出比较早,1982年,姚期智教授在论文《Protocols for Secure Computations》中提出了“百万富翁问题”,开创性地引入了安全多方计算概念,后来经过不断的发展和完善,成为了隐私计算领域的重要研究方向,开创了隐私计算的新纪元。

  • 百万富翁问题提出

下面我们介绍下百万富翁问题,来看下这个场景:

我们的老朋友Alice和Bob都是百万富翁了(假定Alice财富为x百万,Bob财富为y百万,有一天他们在街上相遇,两人想知道到底谁更有钱一些,但是又不想告诉对方自己真实的财富值。那么如何在不暴露各自财富的前提下比较出谁更富有?

  • 百万富翁问题的通俗解法

回到百万富翁问题,一个简单的解决方案如下步骤:

  1. 第一步:张三找10个一模一样的箱子,按照1~10的顺序摆好并且标记箱子(分别代表一千万到一亿),并按照自己的财富值分别往里面放入苹果、梨和橙子,具体操作为:如果序号小于自己的财富之放入苹果,相等则放入梨,大于自己的财富值放入橙子;
  2. 第二步:张三把10个箱子都加上锁,然后交给李四(箱子上有1-10的编号以及对应的财富值);
  3. 第三步:在张三不在场的情况下,李四根据自己的财富值对相应序号的箱子再加一把锁,并把这个选择的箱子交给张三(同时抹掉箱子的序号,这样箱子本身就看不出分别了),其他的箱子可以处理掉(李四也打不开)。
  4. 张三看到送回来的箱子,但他不知道李四选择的是第几个箱子,因为每个箱子都是一样的(序号已经抹掉);
  5. 张三李四分别开锁,看里面是什么水果:
    1. 如果是苹果,张三比李四富有;
    2. 如果是梨,两人一样富有;
    3. 如果是橙子,李四比张三富有

通过以上步骤可知,在最后阶段,虽然Alice和Bob都看到了箱子里放的是香蕉(MPC算法的计算结果)。

  1. 对于Alicee老说,由于箱子序号被Bob撕掉,所以Alice并不知道Bob选的是第几个箱子(实现了Bob财富y对Alice的隐藏);

  2. 对于Bob来说,并不能确定序号1-6的6个箱子里,从第几个箱子开始,由苹果变成了香蕉(实现了Alice财富x对Bob的隐藏)。

这个问题就是百万富翁问题的安全多方计算解法。具体实现可以参看五大基座之一的隐私组件基座。

​ 从上面的例子我们可以得出安全多方计算的定义:安全多方计算是一种在参与方不共享各自数据且没有可信第三方的情况下安全地计算约定函数的技术和系统。通过安全的算法和协议,参与方将明文形式的数据加密后或转化后再提供给其他方,任一参与方都无法接触到其他方的明文形式的数据,从而保证各方数据的安全。

三 MPC体系结构

安全多方计算技术体系架构如图所示,多方安全计算技术体系中,最重要的支撑技术就是隐私组件基座,比如同态加密(Homomorphic Encryption)、秘密分享(Secret Sharing)、不经意传输(Oblivious Transfer) 、混淆电路(Garbled Circuit)、零知识证明(Zero-knowledge)等。

但是同时安全多方计算还需要数学基座、安全基座、工程基座的加持,总结下来,安全多方计算需要五大基座中的四大基座支持。

  1. 数学基座

  2. 安全基座

  3. 工程基座

  4. 隐私组件基座

上面提到四大基座中在前面都有介绍,建议大家在学习安全多方计算之前要仔细学习,安全多方计算主要是上述技术的综合应用。

从上图可以看到,MPC的整体模式主要分为三层

  1. 应用层:行业应用,可以应用于智慧城市、健康医疗、保险服务、金融风控等场景。

  2. 计算工具层:中间层是安全多方计算的计算路线,主要分为通用型MPC和专用型MPC路线。

  3. 基座层:最底层是支撑技术层,包含数学基座、安全基座、工程基座与隐私组件基座;

基座层主要是四大基座,已经前面的章节中进行过阐述,这里主要介绍下计算工具层的相关内容。

  • 通用型计算工具MPC

通用型MPC是指可以支持任何类型计算任务的MPC解决方案。由于其要支持通用类型,所以一般由混淆电路(GC)实现,不受限于计算类型。

通用型MPC是将计算逻辑编译成电路,然后混淆执行。缺点是对于复杂计算逻辑,混淆电路的效率会有不同程度的降低,与专用算法相比效率会有很大的差距,真正落地可能比较困难。

  • 专用型计算工具MPC

专用型MPC是指为解决特定问题而构造出的特殊的MPC解决方案。由于其是针对特定问题进行构建与优化,所以其算法的效率会比通用MPC的算法效率高很多。

当前MPC专用算法包含四则运算,比较运算,矩阵运算,隐私集合求交集(纵向联邦也需要),隐私数据查询等。

虽然专用型MPC与通用型MPC相比效率更高,但同样存在一些缺点,如只能支持单一计算逻辑,场景无法通用;另外专用算法设计需要领域专家针对特定问题精心设计,设计成本高。

四 MPC的工程架构

从安全多方计算定义我们得知,其本质就是解决多方数据的隐私融合计算。比如有n个计算参与方,并且分别持有数据 ,但是各个计算参与方需要计算的函数需要其他几个参与方的数据进行支撑,但是又不能泄露各方的秘密数据。

即利用各方的秘密数据计算一个预先设定的共识函数 ,最终结果是各个参与方都可以得到对应的最终计算结果yi,但无法获得其他任何信息。

按照是否存在可信的第三方,分为以下两种架构:

  • 可信第三方

这种有可信第三方的模式属于有中心的分布式计算,分为计算中心节点与N个计算客户端节点。计算中心节点即是可信第三方,负责协调各个客户端节点的计算进程,计算最终的结果。

但是在这个过程中,不可避免的要收集各参与方的输入信息或者知晓加密秘钥可以解密密码文,所以各参与方的原始数据对第三方来说毫无秘密可言。

但是现实中,一个可靠的第三方基本是不存在的。

  • 无可信第三方、无中心

在这种模式下,没有计算中心节点,只要N个计算客户端节点。

在计算的过程中,只需要各客户端节点之间相互交换数据即可。

交换的是经过隐私组件基座加密后的数据,如同态加密、秘密共享等处理方法的数据,保证其他参与节点拿到数据后,也无法反推原始明文数据,确保了各参与方数据的私密性。

五 MPC的特点与挑战

安全多方计算属于隐私计算第一代,其理念提出比较早,大概在二十世纪80年代,就已经出现,得益于秘密分享、同态加密等底层技术进行构建。 但是受限于算力、技术复杂性与隐私重要性等因素,一直处于不温不火的状态,近年来随着算力与隐私重要性的提升,尤其是联邦学习的火爆,安全多方计算也跟着重新火爆了起来。那么什么是安全多方计算呢?

安全多方计算是一种在参与方不共享各自数据且没有可信第三方的情况下安全地计算约定函数的技术和系统。通过安全的算法和协议,参与方将明文形式的数据加密后或转化后再提供给其他方,任一参与方都无法接触到其他方的明文形式的数据,从而保证各方数据的安全。(待修改)

安全多方计算的特性:

  1. 理论可证明,安全多方计算的隐私保护算法是可以证明的,可以通过推导证明其理论。

  2. 安全性:通用场景的安全性无法证明,但是局限于某些固定场景可以定制化的证明与实践。

  3. 合规性:原始数据不出库,出库的都是经过加密的;

  4. 硬件依赖:无特定的硬件依赖。

  5. 计算性能:约比明文本地计算慢100万 倍;

  6. 计算模式:分布式;

安全多方计算技术在需要秘密共享和隐私保护的场景中具有重要意义,能解决比较底层的精确计算和数据库查询,其主要适用的场景包括联合数据分析、数据安全查询、数据可信交换等。

安全多方计算具有如下特点及优势:

  1. 输入数据安全。安全多方计算过程中各方数据输入独立,计算时不泄露任何本地原始数据。

  2. 计算结果准确。安全多方计算算法得到结果和原始明文数据本地计算结果保持一致。

六 番外篇

介绍:杜宝坤,互联网行业从业者,十五年老兵。精通搜广推架构与算法,并且从0到1带领团队构建了京东的联邦学习解决方案9N-FL,同时主导了联邦学习框架与联邦开门红业务。 个人比较喜欢学习新东西,乐于钻研技术。基于从全链路思考与决策技术规划的考量,研究的领域比较多,从工程架构、大数据到机器学习算法与算法框架、隐私计算均有涉及。欢迎喜欢技术的同学和我交流,邮箱:baokun06@163.com

七 公众号导读

自己撰写博客已经很长一段时间了,由于个人涉猎的技术领域比较多,所以对高并发与高性能、分布式、传统机器学习算法与框架、深度学习算法与框架、密码安全、隐私计算、联邦学习、大数据等都有涉及。主导过多个大项目包括零售的联邦学习,社区做过多次分享,另外自己坚持写原创博客,多篇文章有过万的阅读。公众号秃顶的码农大家可以按照话题进行连续阅读,里面的章节我都做过按照学习路线的排序,话题就是公众号里面下面的标红的这个,大家点击去就可以看本话题下的多篇文章了,比如下图(话题分为:

  • 一、隐私计算
  • 二、联邦学习
  • 三、机器学习框架
  • 四、机器学习算法
  • 五、高性能计算
  • 六、广告算法
  • 七、程序人生),知乎号同理关注专栏即可。

一切有为法,如梦幻泡影,如露亦如电,应作如是观。

分类:

后端

标签:

后端

作者介绍

杜宝坤
V1