第1章
隐私计算概述

本章将主要介绍隐私计算，机密计算（Confidential Computing）是隐私计算的一种方法。

1.1 隐私计算的目标

根据联合国全球大数据工作组（BigData UN Global Working Group）发布的“隐私计算技术手册”（UN Handbook on Privacy-Preserving Computation Techniques）白皮书，统计分析过程可以抽象为三部分：输入方（源数据）、计算方（统计分析）、结果方（统计结果），如图1-1所示，对应的隐私计算目标分为以下三类：

输入隐私 （Input Privacy）：计算方不能访问或衍生出输入方提供的输入数据，也不能访问计算过程中的中间数据或中间结果。需要注意的是，即使计算方不能直接访问数据，也可能通过侧信道攻击衍生出输入数据，这都是输入隐私需要虑的。

输出隐私 （Output Privacy）：除了输入方允许的内容之外，发布的结果不能包含任何可识别的输入数据。输出隐私要解决的是测量和控制计算结果的泄露问题。

策略强制 （Policy Enforcement）：由策略来控制输入方把哪些敏感数据提供给计算方，并且控制输出方输出哪些数据结果。

1.2 隐私计算技术

目前，工业界常用的隐私计算技术有 同态加密 （Homomorphic Encryption，HE）、 安全多方计算 （Secure Multi-Party Computation，MPC）、 零知识证明 （Zero Knowledge Proof，ZKP）、 差分隐私 （Differential Privacy，DP）以及 可信执行环境 （Trusted Execution Environment，TEE）等。

图1-2展示了隐私计算技术和隐私计算目标之间的关系。

1.2.1 同态加密

在“RSA三人组”发明了大名鼎鼎的RSA算法之后，Rivest、Adleman和Dertouzos在1978年发表了题为“On data banks and privacy homomorphisms”的文章，首次阐述了同态加密的概念。同态加密可以直接对密文数据进行计算，得出结果后再解密。这个特性称为同态性。

RAS和之后的ElGamal算法只能做到乘法半同态（Partially Homomorphic Encryption，PHE），只有乘法运算可以实现同态性，其他运算则不行。Paillier在1999年发表的论文“Public-key cryptosystems based on composite degree residuosity classes”中提出了落地的加法半同态算法（也称为Paillier算法），弥补了不足。

同态加密在2009年取得了突破。Gentry在“ Fully homomorphic encryption using ideal lattices”中首次实现了基于理想格（Ideal Lattice）的全同态（Fully Homomorphic Encryption，FHE）算法。目前，同态加密还在持续发展中，如Brakerski和Vinod Vaikuntanathan在2011年的论文“Efficient fully homomorphic encryption from (standard) LWE”中提出了BV算法，Brakerski、Gentry和Vaikuntanathan在2012年的论文“(Leveled) fully homomorphic encryption without bootstrapping”中提出了BGV算法，Brakerski在2012年的论文“Fully homomorphic encryption without modulus switching from classical GapSVP”中提出了Bra算法，Fan和Vercauteren在2012年的论文“Somewhat practical fully homomorphic encryption”中提出了BFV算法，Gentry、Sahai和Waters在2013年的论文“Homomorphic encryption from learning with errors: conceptually-simpler，asymptotically-faster，attribute-based”中提出了GSW算法，Cheon、Kim、Kim和Song在2017年的论文“Homomorphic encryption for arithmetic of approximate numbers”中提出了CKKS算法，但这些算法需要解决计算开销和性能问题。

同态加密通过直接对密文数据进行计算来保护数据的隐私性，如图1-3所示，同态加密算法有以下功能模块：

HE:KeyGen（）：密钥生成，根据参数生成临时HE密钥。

HE:Encrypt（）：加密，使用HE密钥加密明文输入数据，生成加密输入数据。

HE:Evaluate（）：评估，对加密输入数据进行运算，生成加密输出数据。

HE:Decrypt（）：解密，使用HE密钥解密加密输出数据，生成明文输出数据。

同态加密非常适合云计算应用的场景。用户希望利用云端的计算能力，但是不希望暴露自己的隐私数据，于是可以把机密数据上传到云端进行计算，得到结果之后再返回到本地解密。

目前，同态加密的安全性是由底层的密码学原语（Primitive）保证的，这就是容错学习问题（Learning with Error，LWE）。如果容错学习问题不被攻破，就意味着同态加密具有安全性。

同态加密只是密码学原语而不是协议。同态加密在单独使用的情况下不能够完全提供输入隐私功能，如果计算时需要多方的输入，同态加密不能保证每个输入只能被密钥拥有者看见。另外，同态加密只提供不可区分性（Indistinguishability，IND），即对手不能获得明文信息；而不提供不可延展性（Non-Malleability，NM），即对手可以修改密文信息。

“隐私计算技术手册”白皮书中指出，基于同态加密构造的安全协议需要密码专家的帮助，而且多数基于同态加密的安全协议是半诚实（Semi-Honest）安全的 。

1.2.2 安全多方计算

图灵奖得主姚期智院士在1982年发表的“Protocols for secure computations”一文中提出了“百万富翁难题”，开启了保护隐私的安全多方计算研究。目前，安全多方计算包括不经意传输（Oblivious Transfer，OT）、混淆电路（Garbled Circuit，GC）和秘密共享（Secret Sharing，SS）等方法。

1.不经意传输

Rabin在1981年发表的文章“How to exchange secrets with oblivious transfer”中提出了不经意传输的概念。假设通信双方都有自己的秘密，并且希望在没有可信第三方的情况下交换秘密，但是他们有一个要求，就是秘密的拥有者不能知道对方是否获得了秘密。举个例子来说，Alice有一个秘密要发送给Bob，但是当Alice发送秘密时，Bob只能以概率的方式获得秘密，这使得Alice无法知道Bob是不是真的获得了秘密。

之后，Evan、Goldreich和Lempel在1985年的文章“A randomized protocol for signing contract”中提出了真正意义上的不经意传输，称为二选一不经意传输（1-out-of-2 OT）。Alice在通信中发送两个秘密（ m ₀ ， m ₁ ），Bob选择接收其中的一个秘密，但是Alice不知道Bob选择的是哪一个秘密，而且Bob一旦选择了一个秘密，就不能知道另一个秘密。这个过程如图1-4所示。Brassard、Crepeau和Robert在1986年发表的“Information theoretic reductions among disclosure problems”一文中将二选一不经意传输扩展到了 N 选一不经意传输（1-out-of -N OT），也就是说，Alice一次发送 N 个秘密，让Bob选择其中一个。之后，又扩展到了 N 选 K 不经意传输。

2.混淆电路

混淆电路这个概念是由姚期智院士在1986年发表的“How to generate and exchange secrets”一文中提出的。该方法可达到如下效果：Alice和Bob想一起输入些数据得出计算结果，双方都知道自己的输入和最后的结果，但是双方都不愿让对方知道自己的输入是什么。图1-5展示了混淆电路和工作流程的一个简单例子。

我们假设双方的计算通过一个电路完成。以与（AND）操作真值表为例，Alice的输入为0或1，使用密钥Key _A0 和Key _A1 表示；Bob的输入为0或1，使用密钥Key _B0 和Key _B1 表示；输出结果为0或1，使用密钥Key _C0 和Key _C1 表示。Alice生成真值表，使用对应的密钥加密结果并且打乱顺序，这个加密打乱的过程就是混淆电路的工作原理。

混淆电路的工作流程如下所示：

① 混淆电路生成 。Alice生成混淆电路真值表。

② 双方通信 。Alice把真值表、Alice的输入（例如Key _A0 ）、Bob的两个密钥Key _B0 和Key _B1 发送给Bob。这里的通信使用二选一不经意传输，因此Bob只能选择其中的一个密钥，而不知道另一个密钥。同时Alice不知道Bob到底选择了哪一个密钥。

③ 混淆电路评估 。Bob选择自己的输入（例如Key _B1 ），解密真值表，得出结果的密钥（例如Key _C0 ）。

④ 结果分享 ：Bob把结果的密钥发送给Alice，Alice查出对应的明文0或1后告诉Bob。

Bob不知道Alice的输入Key _A0 所代表的含义，只是结合自己的输入Key _B1 尝试解密真值表的各项，唯一可以解密出来的那一项就是结果Key _C0 。Alice只看到最后的结果Key _C0 ，但是Alice不知道Bob使用真值表的哪一项来解密，所以也不知道Bob使用的密钥，由此满足了不泄露输入信息这个条件。

注意：姚氏混淆电路只对忠实的参与方有效，对恶意参与方无效。

Goldreich、Micali和Wigderson在1987年发表的“How to play ANY mental game”一文中将姚氏混淆电路扩展为GMW协议，从两方扩展到多方、从布尔电路扩展到算术电路，而且可以抵御部分恶意参与方。Beaver、Micali和Rogaway在1990年的论文“The round complexity of secure protocols”中提出的BMR协议则采用分布式执行混淆电路生成过程，使得任何参与方都无法单独获得混淆电路的秘密信息，同时使生成过程的通信复杂度与待计算电路的深度无关。

3.秘密共享

Shamir的“How to share a secret”和Blakley的“Safeguarding cryptographic keys”分别在1979年提出了多方秘密共享方案。（ K ， N ）门限方案（Threshold Scheme）的核心思想就是将一个秘密 S 用 N 把子密钥保护起来，凑齐其中任意 K 把子密钥就能还原这个原始秘密，但是小于 K 把子密钥就不能还原出原始秘密。图1-6展示了一个基于（3，5）门限方案的秘密共享示意图。在这个方案中，一个秘密由5把子密钥保护，凑齐3把子密钥可以破解这个秘密。

Shamir采用了一个简单的数学原理：给定多项式 f ( x )= a _{k -1} x ^{k -1} +…+ a ₂ x ² + a ₁ x + a ₀ ，已知任意 k 个点( x ， f ( x ))即可解出这个多项式，而已知的点小于 k 个则无法解出多项式。对于密文 S 和（ K ， N ）门限，随机生成 K -1个参数作为 a _{k -1} ，…， a ₂ ， a ₁ ，秘密 S 作为 a ₀ ，这样得到 K -1阶多项式 f ( x )，然后随机产生 N 个非零数 x 代入多项式得到 N 个 f ( x )，最后把这 N 个( x ， f ( x ))分别发送给 N 个用户即可。这样，任意 K 个用户在一起就可以构造 K 个方程的方程组解出这 K 个系数，而系数 a ₀ 就是秘密 S 。

Blakley则采用了另一种方法。假设这个秘密是三维空间中的一点，可以用5个经过这个点的平面作为子秘密，凑齐其中任意3个平面就可以确定空间的这一点。把这个三维空间扩展到 K 维空间就是Blakley算法，即把秘密作为 K 维空间的一个点，用 N 个经过这个点的平面作为子秘密发送给各个参与方，凑齐其中任意 K 个平面就可以确定这个秘密。

多数情况下，我们采用（ N ， N ）门限方案，即拥有全部 N 个子秘密是重新构建出秘密的充要条件。MPC可以利用秘密共享方案的同态特征，即对于各个子秘密进行加法或乘法的同态计算，最后合并得到计算结果。图1-7展示了一个秘密共享的加法示例，工作步骤如下：

1） 输入方秘密拆分 。Alice把秘密A拆分为S _A1 和S _A2 ，Bob把秘密B拆分为S _B1 和S _B2 。

2） 子秘密发送 ：Alice把S _A1 发给计算方1，把S _A2 发给计算方2。Bob把S _B1 发给计算方1，把S _B2 发给计算方2。

3） 计算方计算 ：计算方1算出CP ₁ =S _A1 +S _B1 ，计算方2算出CP ₂ =S _A2 +S _B2 。这时，计算方无法得知原始秘密A和秘密B。

4） 发送计算结果 ：计算方分别把结果发送给输出方。

5） 输出方结果计算 ：输出方计算CP ₁ +CP ₂ ，即秘密A+秘密B。这样，结果方就在不知道原始秘密A和秘密B的情况下得知了秘密之和。

Ben-Or、Goldwasser和Wigderson在1988年的论文“Completeness theorems for non-cryptographic fault-tolerant distributed computation”中提出的BGW协议就是基于Shamir提出的秘密共享方案。Chaum、Crepeau和Damgard也在1988年的论文“Multiparty unconditionally secure protocols”中提出了类似的CCD协议。

4.安全模型

安全多方计算的威胁模型增加了一个特殊的对手（Adversary）—内部威胁者（Insider）。我们需要考虑以下特性：

诚实性 （Honesty）：诚实性分为三类：半诚实、隐匿和恶意。在半诚实（Semi-Honesty）模式下，受害的参与者只是读取数据；在隐匿（Covert）模式下，对手可能会修改或破坏已经同意的协议，并且隐藏自己；在恶意（Malicious）模式下，对手可能会修改或破坏已经同意的协议，但是隐藏自己并不是目标，可以采取更多措施。

移动性 （Mobility）：移动性分为两类：固定对手和非固定对手。在固定对手模式下，只有固定的参与者被渗透，从而受到影响，这些被渗透的参与者不会变化；在非固定对手模式下，被渗透参与者可以发生变化，从一个参与者移动到另一个参与者。例如，在A、B、C、D、E五个参与者中，开始是A和B作为对手，但在计算一段时间后，对手变成了A和C。

被渗透方的比例 （Portion of Compromised Parties）：被渗透方的比例分为两类：诚实的占大多数和不诚实的占大多数。

不同的安全多方计算协议具有不同的性质，涉及以下方面：

输入隐私 ：参与者不把数据暴露给其他参与者。

输出正确性 ：所有参与者得到的输出是正确的输出。

公正性 ：要么所有参与者得到输出，要么所有参与者都没有得到输出。

保证的输出 ：不管不诚实的参与者做什么，所有诚实的参与者都做正确的计算。

关于安全多方计算的优秀参考书籍有Evans、Kolesnikov和Rosulek编写的《实用安全多方计算导论》，其中包含了对于GMW协议、BMR协议、BGW协议和CCD协议的介绍。

1.2.3 零知识证明

Goldwasser、Micali和Rackoff在1985年的论文“The knowledge complexity of interactive proof-systems”中提出了零知识证明的概念，即证明者（Prover）在不向验证者（Verifier）提供有用信息的情况下使证明者相信某个陈述（Statement）。

我们使用Quisquater等在1989年发表的“How to explain zero-knowledge protocols to your children”一文中提到的山洞问题来说明这个概念。如图1-8所示，山洞内的C点和D点之间有一道密门，证明者陈述自己知道密门的口令，但不想把口令告诉验证者，那该怎么办呢？验证者可以重复以下步骤：

1）验证者站在A点，证明者站在B点。

2）证明者随机走到C点或D点，但验证者看不见证明者的选择。

3）验证者走到B点，要求证明者从左边或右边的通道出来。

4）证明者根据要求从左边或右边的通道出来。

如果证明者知道密门的口令，就一定能正确地从验证者要求的通道中出来；如果证明者不知道密门的口令，则每次有1/2的概率从验证者要求的通道中出来。只要重复的次数足够多，验证者就有理由相信证明者确实知道密门的口令。

零知识证明分为交互式零知识证明和非交互式零知识证明两种。密码学中的数字签名可以作为一种典型的交互式零知识证明方式，例如Schnorr在1991年的论文“Efficient signature generation by smart cards”中提到的身份认证协议。

在零知识证明中，经典的方法包括Groth在2010年的论文“Short pairing-based non-interactive zero-knowledge arguments”和Bitansky、Canetti、Chiesa和Tromer在2012年的论文“From extractable collision resistance tosuccinct non-interactive arguments of knowledge，and back again”中正式提出的零知识简明非交互式知识论证（Zero-Knowledge Succinct Non-interactive Argument of Knowledge，zk-SNARK），以及Ben-Sasson、Bentov、Horesh和Riabzev在2018年的论文“Scalable，transparent，and post-quantum secure computational integrity”中提出的零知识可扩展透明知识论证（Zero-Knowledge Scalable Transparent Arguments of Knowledge，zk-STARK），它可以抵御量子攻击。

零知识证明需要满足以下性质：

完备性 （Completeness）：如果陈述为真，而且证明者和验证者都遵循协议，那么验证者将接受证明。

可靠性 （Soundness）：如果陈述为假，而且验证者遵循协议，那么验证者将无法接受证明。

零知识 （Zero-Knowledge）：如果陈述为真，而且验证者都遵循协议，那么除了证明为真之外，验证者将无法获得其他任何机密信息。

零知识证明的安全性由不同的数学难题保证。例如，简明非交互式证明（Succinct Non-interactive Proof）基于不可伪造性（Non-Falsifiable）假设，即如果对手破坏了这个假设，验证者就不能进行有效的验证，而有效的验证将成为整个系统有效性的瓶颈。

1.2.4 差分隐私

Dwork、Kenthapadi、McSherry、Mironov和Naor在2006年的论文“Our data，ourselves:privacy via distributed noise generation”中提出了差分隐私的概念。在隐私保护统计数据库中，差分隐私引入随机噪声对真实回答进行扰动。和其他的隐私计算不同，差分隐私属于对输出结果的隐私保护。

我们使用Warner在1965年的论文“Randomized response: A survey technique for eliminating evasive answer bias”中使用的方法来举个简单的例子。假设在一个有300人的学校里，如果想知道作弊学生的百分比，可以找到每个学生问：“你曾经在考试中作过弊吗？”由于这是个非常敏感的问题，作过弊的学生可能不会诚实回答。这时，怎么解决这个问题呢？

一个基于差分隐私的方案如图1-9所示。在向每个学生提问之前，你拿出一个硬币给他，让他抛两次硬币之后再回答问题，但是学生不会告诉你每次抛硬币的结果是正面还是反面。第一次是正面的话，不管第二次的结果，只回答真实情况；第一次是反面的话，看第二次的结果；第二次是正面的话，永远回答“是”，第二次是反面的话，永远回答“否”，而无论真实情况如何。由于硬币引入了随机性，因此你不可能知道每个学生的情况。随着学生人数的增加，抛硬币的随机性可以固定在1/2。假设学生真实作弊率是 c ，那么通过这种方法得出的结果就是 c /2+1/4，所以可以反推回去得出真实结果。

这只是差分隐私的一个简单例子。由于抛硬币的引入，导致每一个回答被匿名化了，每一个回答中都存在合理推诿（Plausible Deniability），但是我们仍然能推断出真实的结果。

差分隐私背后的原则是多样性（Versatility）和健壮性（Robustness）。根据隐私算法应用的时机，差分隐私分为以下两种模式：

本地 （Local）模式：在收集（Collection）和聚集（Aggregation）之前，差分隐私直接应用于每个人提供的数据。

馆长 （Curator）模式：一个可信方（Trusted Party）从每个人处收集数据，然后使用差分隐私算法输出结果。

差分隐私需要提供这样一种能力，数据库中的单个记录对整个数据结果的输出可以忽略不计。由于概率噪声的引入，无论有没有这条记录，最终输出的结果都非常接近，而且是概率分布，如图1-10所示。因此，对手无法从有无记录的两次查询中获得和这条记录有关的信息，这样就可以防止对手获得附带知识（Side Knowledge），这就是差分隐私所要求的统计学不可区分性（Statistically Indistinguishable）。

1.3 隐私计算的应用

除了以上四类之外，隐私计算还包括基于可信执行环境的机密计算，我们将在下一章详细介绍。

目前，隐私计算的应用除了安全多方计算和可信执行环境之外，最有名的是联邦学习（Federated Learning，FL），它主要用于人工智能模型的训练和预测，也称为联邦机器学习（Federated Machine Learning，FML）。联邦学习由McMahan等在2017年的论文“Communication-efficient learning of deep networks from decentralized data”中提出，主要思想是把训练数据放在移动终端设备上，通过聚集本地设备计算的结果而学习到一个共享模型。联邦学习采用了一种去中心化的思想。为了遵守隐私保护法规，机器学习应用需要以一种分布式的方式去使用数据，即不能直接交换原始数据，也不能使任何一方推理出其他一方的隐私数据，这就是联邦学习在人工智能领域要解决的问题。2020年，IEEE发布了IEEE 3652.1-联邦机器学习架构框架和应用指导（IEEE Guide for Architectural Framework and Application of Federated Machine Learning），规范化了联邦机器学习的流程。联邦学习的参考架构如图1-11所示，不同地方的数据所有者的隐私数据通过学习成为子模型（Sub-model），然后再被协调员（Coordinator）聚集成为联邦模型（Federated Model）后使用。

表1-1比较了隐私计算中的安全多方计算、可信执行环境和联邦学习。关于隐私计算的介绍性书籍可参考陈凯和杨强编写的《隐私计算》以及李伟荣编写的《深入浅出隐私计算》等。

可信执行环境和其他隐私计算技术并不矛盾，安全多方计算、同态加密、零知识证明、差分隐私等隐私计算技术以及联邦学习都可以部署在可信执行环境内部。即使一个技术存在安全隐患，还可以用另一个技术保护数据隐私，这就是纵深防御的典型例子。 jZANgIeCQaYSR08ghWw4OmcEpgTYdMAooAYZJ5vbmgU0Mx73bfRUOpK2XB9mik8M