1.2 数据隐私技术

自20世纪60年代至今，伴随数据隐私问题的发展，诸多隐私保护技术被提出。本质上，隐私保护技术是用数据的效用或效率来换取隐私。例如，基于扰动的差分隐私技术使用数据可用性换取隐私保证，加密技术则使用数据计算的计算代价或通信代价来换取隐私保证。因此，如何平衡隐私、效率与效用，是隐私技术研究中亘古不变的主题。

从方法上，我们可以将隐私保护的技术分为模糊技术、扰动技术、加密技术、混合隐私技术、分布式计算框架和区块链技术。接下来，我们将对其进行一一的介绍，分析其特征，并进行对比。

1.2.1 模糊技术

模糊技术指针对数据的属性进行模糊，即通过压缩、聚类、划分、泛化等操作切断数据标识属性（可表示一条数据的属性或属性组）与隐私属性间的一对一关系，以隐藏单条数据或单个数据点的隐私信息，适用于数据发布的场景。该项技术由于会对信息造成损失，因此如何在保证数据隐私保护的前提下，尽量减少信息损失和信息扭曲度是该技术的核心问题。

该技术中最典型的是k-匿名技术[5]，k-匿名技术由Latanya Sweeney和Pierangela Samarati于1998年提出，可保证发布的个人数据与其他至少k-1条数据不能区分。在具体实现时，可基于发布数据的准标识符划分等价组，使每个等价组至少包含k条数据。对准标识符进行k-匿名时，可通过删除部分信息、用区间范围代替具体信息等方法，使至少k条数据的准标识符相等。但该技术易遭受同质攻击（homogeneity attack）[9]，即当根据准标识符确定的等价类保护相同敏感信息时，攻击者若能通过其背景知识确定某用户对应的等价类，即可获取其敏感信息。

为改进该问题，抵御同质攻击，Machanavajjhala Ashwin提出了l-多样性[9]，它的基本思想是在k-匿名的基础上要求一个等价组中至少保护一种内容不同的敏感属性，即保证等价组中敏感属性的多样性。但l-多样性相比k-匿名而言更难实现，同时也易遭受偏斜攻击（skewness attack）。如为保证l-多样性，使某等价组中人群是否患有癌症的概率相同，但事实上癌症患者的比例远低于此。在没有考虑敏感属性总体分布的情况下，保证l-多样性可能使个人隐私泄露的风险增大。为弥补l-多样性的局限性，防御偏斜攻击，t-closeness[10]被提出，它保证在同一个等价组中，敏感属性的分布与该属性的全局分布一致，其差别不超过阈值t。同时，针对动态的数据插入、修改、删除操作，m-不变性（m-invariance）[11]被提出，其主要思想是保证同时出现在先后两个发布版本中的记录所在的等价组具有完全相同的隐私属性集合。

然而，上述技术均不能避免攻击者针对敏感属性的背景知识攻击。另外，基于模糊的方式，其信息损失相对其他技术较大，近年来，其应用已逐渐减少。

1.2.2 扰动技术

扰动技术对数据本身进行扰动，主要指差分隐私技术，同时适用于数据发布和大数据收集的场景。该技术通过在数据上直接添加随机噪声，或者将原本的值以一定概率扰动为随机值来实现。通过扰动的方式保护数据隐私，同样会造成数据可用性的降低，即影响计算结果的准确性，因此如何在保护数据隐私的前提下，尽可能提高扰动所影响的数据可用性是该技术的核心问题。

差分隐私（Differential Privacy，DP）于2006年由微软研究院的Cynthia Dwork提出[6]，可以保证任意一条数据的改变都不会影响最终的输出结果的分布，从而隐藏输出结果中的个人隐私信息。也就是说，对于给定的任意两个仅相差一条记录的相邻数据集D和D′，满足差分隐私的随机化算法M需保证，扰动后的输出满足Pr(M(D)∈S)≤eεPr(M(D′)∈S)+δ，其中S表示任意输出的子集。生成一个满足差分隐私的算法，通常有两种数据扰动的方式：一种是直接在计算结果上添加噪声，常用的包括拉普拉斯机制、指数机制等（具体介绍见第4章）；另一种是以一定的概率对数据进行扰动，即随机响应机制（具体介绍见第5章）。

依据不同的安全假设，差分隐私技术可分为中心化差分隐私和本地化差分隐私。中心化差分隐私，即传统的差分隐私概念，假设存在一个可信的服务器拥有用于发布的所有用户数据，该服务器在由原始数据计算得到的结果上直接添加满足差分隐私的噪声，最后发布该扰动后的结果。但现实中，可信的服务器难以部署，它可以看到所有原始数据，一旦被攻击，用户的数据隐私将受到极大的威胁。由此，本地化差分隐私[7]被提出，该模型不依赖任何可信的第三方，用户在其本地直接对数据进行一定概率的扰动，使其满足差分隐私。虽然该技术在可信假设上有所提高，但相比中心化差分隐私算法仅在结果上添加一次噪声，本地化差分隐私在每个用户端都进行数据的扰动，其数据可用性约为中心化差分隐私数据可用性的1/O()倍，其中n表示参与的用户数量。

以差分隐私为主的扰动技术相比以匿名为主的数据模糊技术，可抵御任意的背景知识攻击。也就是说，即使攻击者拥有除被攻击对象外其他所有用户的个人信息作为背景知识，也不能推测出个体的隐私信息。目前该技术在工业界的应用最为广泛，尤其是本地化差分隐私技术。该技术更适用于当下数据监控和数据收集场景，如谷歌使用该技术收集用户浏览器的主页设置等信息，苹果使用该技术收集用户常用的emoji表情和新单词。

1.2.3 加密技术

加密技术不同于模糊和扰动的技术，该技术不会损害数据的可用性，但随之而来的是，基于密码学的技术需付出额外的计算代价和通信代价。其主要原因是，经数据加密后的密文通常较大，对密文进行计算会造成产生较大的计算代价和通信代价。因此，如何在保护数据隐私的前提下尽可能降低加密技术与密文计算的技术代价和通信代价是该技术的核心问题。

当下常用的密码学技术主要包括同态加密技术和秘密共享技术。同态加密（Homomorphic Encryption，HE）的概念最早于1978年被Ron Rivest[4]等人提出，允许用户对密文进行特定的代数计算，结果仍是加密数据，且该结果与对明文做相应计算后再加密的结果相同。抽象地，用E(·)表示加密，⊕表示特定的代数操作，同态加密具有以下两个性质：

• 加法同态性质：E(a)⊕E(b)=E(a+b)

• 乘法同态性质：E(a)⊕E(b)=E(a*b)

仅满足加法同态或乘法同态的算法称为半同态加密（semi-homomorphic encryption）或部分同态加密（somewhat-homomorphic encryption），典型的有满足乘法同态的RSA（Rivest，Shamir，Adleman）算法和ElGamal算法[12]，满足加法同态的Paillier加密[13]和DGK（Damgård，Geisler，Krøigaard）加密[14]。以上两种性质都满足的同态加密算法称为全同态加密（full homomorphic encryption）。实际应用时，大多隐私保护方案基于半同态加密方法设计，全同态加密过长的加密解密时间、过大的计算代价不符合实际应用的需求。

秘密共享技术也支持密文的加法计算，但更适用于分布式计算的场景。该技术假设有n个参与者，数据拥有者拥有数据a，他将数据均匀地分成n个分片a_i，并将这n个分片随机分给n个参与者。在该过程中没有一个参与方知道原始的值a是什么，只有当这n个参与者合作才能通过a_i计算得到a的值。除此之外，常用的还有基于多项式方程组构建的(t,n)-门限秘密共享，仅需其中n个分片中的t个就可恢复原数据的值。

同态加密技术有较大的计算代价，而秘密共享技术有较大的通信代价。除此之外，加密技术还包括一些基础的对称加密算法，如DES算法、AES算法，以及基础的散列算法，如信息摘要算法第五版（Message-Digest Algorithm 5，MD5）、安全散列算法256位（Secure Hash Algorithm 256，SHA-256）等。在面对诸多实际问题时，如隐私保护的查询问题、机器学习等，通常需将多种加密算法结合起来使用。

1.2.4 混合隐私技术

模糊和扰动的技术会降低数据的可用性，加密技术会降低数据的计算和通信效率，那么能否将二者结合，各取其优点呢？出于该目的，混合隐私技术得以发展。混合隐私技术主要指将扰动技术与加密技术进行混合，根据其组合方式与目的的差异，可分为Cryptography for Differential Privacy和Differential Privacy for Cryptography两种[15]。

Cryptography for Differential Privacy即C4DP，是用密码学改进差分隐私的方法，该类方法以提升差分隐私方法的隐私性与可用性为目标，探索差分隐私方法隐私性与可用性的最优平衡。该类方法又可进一步分为基于密文计算改进和基于安全混洗改进两个部分。前者将中心化差分隐私方法中的可信第三方替换为不可信第三方，并将该第三方的所有操作替换为密文操作，从而在保证较小计算误差的差分隐私基础上，提高系统隐私性。后者在本地化差分隐私方法的基础上引入安全混洗的操作，使用户本地扰动后的数据实现完全的匿名，从而通过分析匿名与差分隐私联合带来的隐私放大效果，提高最终计算结果的准确性。

Differential Privacy for Cryptography即DP4C，是用差分隐私改进密码学的方法，该类方法将差分隐私扰动的思想引入密码学协议中，以改善其计算代价与通信代价。在复杂密码学协议执行的过程中，攻击者们可以通过计算过程中一些中间结果的大小、通信的次数等信息，来对计算的数据或结果进行推断，进行推理攻击。我们可以基于差分隐私的思想，对密码学协议中中间结果的大小、通信的次数进行适度的扰动，一方面避免过多假的密文数据或通信消息的引入，另一方面防止推理攻击。

基于混合隐私技术，我们可以尽可能实现数据隐私、效率与效用之间的平衡。当前基于混洗改进差分隐私的技术，即编码-混洗-分析（Encode-Shuffle-Analyze，ESA）框架[16]，可基于本地化差分隐私框架直接部署，被谷歌和苹果等企业广泛关注。

1.2.5 分布式计算框架

上述隐私保护技术直接对数据进行保护，防止隐私泄露。除此之外，还有另一种思路可以防止隐私泄露，即分布式计算框架，包括安全多方计算和联邦学习。这两种技术不直接对数据进行保护，旨在不直接发送真实数据的分布式情况下完成较高准确度的数据计算。

安全多方计算（Secure Multi-Party Computation，SMPC）[17]，通过多次多方之间的密文通信，支持多方安全地计算任意函数。该技术最初于1982年由姚期智教授提出，用于解决百万富翁问题，即两个富翁Alice和Bob如何在不暴露各自财富的前提下比较出谁更富有。根据参与方的数量不同，安全多方计算分为安全两方计算和参与方多于两人的安全多方计算。通用的安全多方计算包括BMR（Beaver，Micali，Rogaway）、GMW（Goldreich，Micali，Wigderson）、BGW（Ben-Or，Goldwassert，Wigdemon）、SPDZ（Smart，Pastro，Damgård，Zakarias）等多种协议[18]，涉及混淆电路、秘密共享、同态加密、不经意传输等多种密码学技术。

联邦学习的思想是保证数据不出本地，参与的多方之间仅分享模型参数，从而联合完成模式的训练。此工作的典型代表为2017年谷歌提出的联邦学习（federated learning）框架[19]。联邦学习框架具备数据隐私保护的特质，其训练数据无须集中存放，不会产生由大规模数据收集带来的直接隐私泄露问题。但研究表明，尽管联邦学习使用户拥有了个人数据的控制权，却依然无法完全防御潜在的间接隐私攻击。直观上，我们可以理解为，用户端训练的模型参数是对用户数据在某些维度上的提炼，因此仍包含用户的隐私信息。具体实现时，该技术仍需与差分隐私或安全聚集技术结合，以保证用户隐私。

分布式计算框架在保护隐私时，往往存在通信开销昂贵的问题，因此如何在保护隐私的同时控制通信开销是该技术的关键问题。特别地，对联邦学习而言，保护模型参数的隐私信息对用户隐私也十分重要。

1.2.6 区块链技术

区块链技术旨在通过溯源问责方式保护隐私。面对当前的大规模数据收集的现状，传统的隐私保护技术不可能做到面面俱到，在隐私保护技术无效的情况下，可以采用溯源问责的形式去保护隐私。区块链具有透明、去中心和不可篡改的特性，这些特性与溯源问责的需求天然匹配[20]。

区块链起源于比特币。在2008年，化名为中本聪的学者发表“比特币：一种点对点的电子现金系统”一文，并提出比特币的概念。这种数据货币支持互不可信的双方在无可信第三方介入的情况下进行货币交易。区块链作为比特币的核心技术，是将数据区块按照顺序链接得到的链式数据结构，它通过密码学方式保证记录的不可伪造和不可篡改。

目前，区块链的不可能三角问题是影响其应用的主要问题之一。区块链系统的不可能三角是指去中心化、可扩展性和安全性三个需求不可能同时做到最优。

• 去中心化是区块链系统的最基本原则。比特币在设计上完全实现去中心化，它采用工作证明（Proof of Work，PoW）共识算法。但是，在完全去中心化的系统中，可扩展性会相对较差。与此同时，在某种程度上，这些系统的安全性也受到很大挑战。例如，比特币和以太坊的密钥被盗、智能合约漏洞、隐私泄露等问题也比较突出。

• 可扩展性是区块链技术在各个领域应用的关键性能要求。已有很多研究提出了兼顾去中心化和可扩展性的方法，包括侧链、跨链、权益证明（Proof of Stake，PoS）、委托权益证明（Delegate Proof of Stake，DPoS）、分片、闪电网络等。

• 安全性是每一个区块链系统都要面对的问题，也是区块链技术应用的重要保障。通常，安全性涉及网络安全、数据安全、计算节点安全、智能合约安全、钱包安全，以及隐私保护等多个方面。

总体而言，对去中心化、可扩展性和安全性三者最大限度地均衡，就是通用型区块链系统的技术创新的主要方向。

1.2.7 技术的比较

在本节所阐述的隐私技术中，模糊技术、扰动技术、加密技术、混合隐私技术和分布式计算框架主要用于解决隐私保护问题，区块链技术主要用于解决隐私问责问题。由此，我们从数据隐私性与效用、隐私性与效率两个方面对这几种隐私防护技术进行比较，如图1.2和图1.3所示。分布式计算框架由于其实现依赖于其他几种基础技术的组合，因此不列入该比较。

通过比较可发现，加密技术和模糊技术分别代表了“高隐私、高效用、低效率”和“低隐私、低效用、高效率”两个极端。而扰动技术和混合隐私技术在这两个方面相对较为平衡。混合隐私技术通过融合加密技术和扰动技术，实现了隐私、效用和效率之间的最优平衡。由此，本书主要基于扰动的差分隐私技术和混合差分隐私技术，对不同的隐私挑战问题及其解决方案进行探讨。