隐私计算团队荣获第十届国际iDash大赛机密大赛赛道冠军

2023年11月，第10届iDASH国际隐私计算竞赛落下帷幕，字节跳动安全研究 - Jeddak可信隐私计算团队联合南京大学、南方科技大学、香港城市大学组建的Jeddak Team联合战队，获得机密计算赛道第一名、同态加密赛道第二名的优异成绩。作为Best-Performing Team，团队成员受邀在耶鲁大学举行的 iDASH Workshop 2023上展示了参赛方案。

iDASH是数据隐私与安全计算领域的国际最高规格竞赛，由美国国立卫生研究院（NIH）主办，历年来吸引了全球顶尖高校和科技公司的积极参与。今年的大赛共吸引了来自12个国家的62支队伍参赛，包括哈佛大学、耶鲁大学、麻省理工学院、加州大学圣迭戈分校以及英特尔、腾讯、蚂蚁集团、阿里巴巴等队伍，在机密计算、同态加密、区块链共3个赛道展开了激烈的角逐。组委会根据各赛题场景筛选出满足要求的方案设计和代码实现，然后从性能、精度等指标维度对各参赛队进行排名。

隐私计算是一种能够保护数据隐私的计算解决方案，通过前沿密码学、可信硬件等先进技术手段，为用户提供安全合规的数据流通交易与融合共享，以此发挥更大价值；同时也满足了数据的“可用不可见”。隐私计算通常可由“软/硬”两类技术实现：前者本质是围绕数据自身做隐私保护，例如此次赛道之一的同态加密；而后者是对数据所处的计算环境做安全防护，例如另一赛道的机密计算。一般情况下的常规计算都是在数据明文基础上进行的，而同态加密计算是指：在其对应的密文基础上执行运算。两者分别针对明、密文数据的基本操作，如加法和乘法也都是一一对应的、并且最终计算结果相同；区别只是其中之一被加密，所以只有该数据的所有者因掌握了密钥才能解密获得结果。形象地讲，两者是计算等效的“平行世界”关系，其中同态加密额外提供了隐私保护能力，因为在整个过程中数据始终处于密态。另外一类以硬件机制为代表的机密计算，可简单理解为：构建了一个与外界隔离的沙箱环境，于是敏感数据在里面的计算使用不受干扰，实现了机密性和完整性保护。
在生物信息领域，一方面对个人数据的隐私保护至关重要，另一方面医疗单位和研究机构又迫切需要打通各方数据。因此，隐私计算已逐渐成为该领域的关键技术，促进多方共同参与、合规挖掘利用数据的宝贵价值：来自不同数据源的生信数据经过加密处理后，存储在具备隐私计算能力的云平台上，进而为泛在数据使用提供所需服务。例如，隐私计算能够帮助医疗、保险机构利用个体基因数据有效地预测潜在疾病风险，从而作出综合评判。研究人员也可以通过隐私计算挖掘数据多维度价值，建立精准模型辅助诊疗、加速新药物研发等，推动生物信息领域的研究和应用创新。
在本届iDASH竞赛中，机密计算赛道要求在确保全过程基因数据的安全隐私前提下，实现高效的基因组推断。Jeddak团队提出了基于可信执行环境（TEE）的解决方案，该方案可以有效应对各类高负载的计算任务（如数据清洗、结构预测、差异表达分析、突变检测等），不但能够准确完成、同时也提供了能效更高的安全隐私保障。
同态加密赛道要求根据基因数据的密文、来识别基因样本和基因数据库之间的亲属关系。Jeddak团队通过分析基因数据的特征，提出了亲属关系判别算法，以及相应的基因数据编码方式和高性能密文计算方案。不仅能够高效处理基因组数据，还适用于各种高维度的隐私数据密态分析。

机密计算赛题是加固并优化现有的基因组推断算法PanGenie，以提高其在处理人类基因数据过程中的计算性能与数据安全。目前，变异感知的泛基因组图（Variation-aware Pangenome Graph）已成为一种更为有效的人类参考基因组表示形式，而短序列片段测序（Short-reads Sequencing）由于其高效性和低成本仍然是最实用的测序方式。PanGenie则是基于这两类信息设计的一类高效基因组推断算法。今年的iDASH竞赛首次引入了基于AMD SEV技术的可信执行环境，以确保在数据处理过程中的安全隐私性。此外，比赛还对资源使用进行了严格限制，规定参赛队伍最多使用2台虚拟机，每台虚拟机只能使用4个计算核心，并要求可信计算基（TCB）不超过1MB。本次比赛主要考察机密计算系统的设计与优化水平。
针对本次赛题的考核要求，我们对指定算法PanGenie与其实现进行了细致全面的分析，从并行化、内存优化、执行流程优化、编译期优化等多个角度对原有实现进行了重构创新，在保证方案的安全性前提下，高效发挥利用给定的计算资源、突破能效瓶颈。下面介绍我们方案的主要优化点：
首先参考下图，我们基于赛题中最多使用2台虚拟机的条件，将整个基因组推断的工作负载拆分到了2个虚拟机中并行执行。而在每个工作节点（Worker）中，工作流被分为了两个阶段：预处理阶段和PanGenie工作负载阶段。

预处理阶段

1. 在本阶段，2个工作节点首先会对预先放置于其磁盘内的数据文件进行数据提取，该过程中节点会提取出数据中的关键信息，用作后续的参数选择。
2. 在前期调研中我们发现：一个关键的哈希表的大小会对整体的性能造成极大的影响，而适当地选择较大的规模会比选择小哈希表所造成的开销少很多。为此我们采用了自适应的哈希表规模选取策略，会根据实际的数据规模自适应地选择参数。
3. 在实际情况下，一份样本包含了多个染色体，而不同染色体对应的基因数据的分布并不均衡，所以简单粗暴地按照编号来进行分配会导致工作节点负载的不平均，为此我们采用了贪心算法以实现节点间的负载均衡。

PanGenie工作负载阶段
在这个阶段工作节点会根据分配到的染色体编号来并行化数据处理，因为每个染色体对应的计算逻辑是独立的。于是能够最大发挥工作节点的计算能力。
由于任务是分配到2个节点上执行，该过程中需要对统计信息（Read Variant、Load KMer Statistics）、计算结果（Genotyping）进行同步，我们对所有的通信数据进行加密以保证数据安全。

针对PanGenie的工作负载阶段，我们也采用了多个优化方案来一并提高整体的算法执行效率：

• PanGenie算法中使用了隐马尔可夫模型（Hidden Markov Model，HMM）来进行基因型的推断，我们针对算法中HMM的发射概率以及转移概率进行了优化。具体来说，我们通过预处理部分概率值，降低每次实时计算的开销，从而减少了整个HMM在计算过程中的复杂度。
• 充分发挥AMD CPU提供的AVX指令集来提高对浮点型数据处理的效率。相较于分别计算多个浮点数，我们通过单指令流多数据流（Single Instruction Multiple Data，SIMD）技术，实现了对四个浮点数的同时运算，从而成倍提高了计算效率。

根据主办方设置的两个测试样例，我们的方案在仅使用2台安全虚拟机、共计8个可用线程的的严格限制下，最多耗费2.6小时就运行完成了测试，成为机密计算领域13个参赛队伍中唯一完赛的团队；同时我们的方案保证了准确率在99%以上，且可执行代码（TCB）也仅有920KB大小。

整个方案是Jeddak Team联合香港城市大学、南方科技大学共同设计与实现。最终在本届iDash大赛上取得了第一名的优异成绩。

同态加密赛题设定的场景是：法医鉴定时，检查机构使用嫌犯基因、向数据机构的基因数据库去查询是否存在嫌疑人的亲属，从而快速定位嫌疑人身份。赛题要求检查机构和数据机构的基因数据都需要使用同态加密技术保护，数据经过加密后会交由一个第三方计算机构进行密文预测，最后得到的密文结果可以被检查机构解密作为判断亲属关系的依据。

比赛要求判别400条查询样本在一个拥有2000条基因数据的数据库中是否存在亲属。其中正负查询样本的数量相同。在整个计算流程中，检查机构与数据机构的基因数据不能被泄露，计算机构必须在密文状态下处理基因数据，并且检查机构与数据机构在数据加密前不能进行相关预处理，即提高了系统能效要求。为此，我们基于全同态技术提出了两种安全高效的密文关系预测方案。
在第一个方案中，我们分析了基因数据的特点：发现当一条待查询的基因数据在数据库中存在亲属时，它更有可能与数据库样本维度的中心点有较大的距离。进一步讲，如果将基因数据与数据库中心、待查询数据集中心的距离相减，这种距离差异可以更清晰地划分有、无亲属关系的查询样本。

基于以上数据集特点，我们设计了使用同态加密方案来计算样本距离数据库、查询数据集中心的距离差异。首先，我们将距离差异的计算方法优化成若干加减法和一次内积运算组成的算法。在加密数据时，我们采用CKKS加密算法并通过系数编码的方式将多个基因数据加密到一条密文多项式的系数上。基于这种编码方式，可以通过一次多项式乘法计算出两组密文数据向量的内积，从而得到一条样本对应的预测得分。最后，查询机构可以解密、并根据得分大小判断出查询样本是否在数据库内存在亲属的可能性。

第二个方案则是从直观认识出发：如果两条基因数据存在亲属关系，那它们应当有更小的距离。基于此，我们首先通过条件概率的方法，计算得到每个等位基因对判断样本亲属关系的权重。实操中选取1000个权重值最大的基因作为判别亲属关系的依据。该方案使用了被选取的基因来计算每个查询样本与数据库中心点的距离，从而作为每个样本的预测结果。

我们依然采用CKKS算法实现了第二个方案，并利用复数的特点将每两个相邻的查询数据加密分别加密到同一条密文的实部和虚部。在密文计算的过程中，我们首先将被选取基因的明文掩码作用在每一条加密数据上，然后将计算后的数据库中心点和每条查询数据均提取到密文的实部上。最终，查询样本与数据库中心点的距离可以通过密文乘法和移位操作完成。
上述两个方案是Jeddak Team与南京大学共同设计与实现，最终在iDASH 2023竞赛中以0.977的得分获得了第二名的成绩。

iDASH竞赛通常设定的是医学场景，因为医疗数据极其敏感，故要求使用隐私计算技术在密态数据基础上执行运算，从而既实现业务目标、又保障数据的安全隐私。此次Jeddak Team所使用的核心技术均源于自研的Jeddak可信隐私计算平台，涵盖机密计算、联邦学习、多方安全计算、同态加密、差分隐私、区块链等多种形态的产品技术；近两年来在字节内外实施了70余个隐私计算相关项目，典型如ToB侧火山引擎和公司内部的抖音用数管控等。
隐私计算在数据要素价值释放过程中发挥着越来越重要的作用，但因处于早期发展阶段，无论相关技术、产品和市场都亟待深入探索。字节跳动安全研究团队基于Jeddak的大量应用实践，总结出隐私计算基础建设的三个关键问题：技术突破、产品创新、领域洞察，以下简要介绍我们的相关工作。

• 技术突破：核心是解决隐私计算的能效问题。例如此次iDASH竞赛，不但要求分析建模精准安全、而且对计算能效也提出很高要求。尤其是后者，被认为是隐私计算大规模应用和产业化的主要瓶颈。为此我们从相关理论创新到工程优化的多个层面做了大量努力，包括自主研发更高效的安全协议、硬件加速、以及特有的隐私计算网络等，已全面接入内外部业务。基于有限资源使用、端到端全链路执行效果如：百亿级数据的PSI隐私求交50分钟完成；亿级千维数据的XGB联邦学习训练约4小时完成、十亿级推理40分钟内完成；面向百亿级数据的PIR匿踪查询约4小时完成；亿级数据的MPC多方安全计算聚合查询约1小时完成。这些真实业务场景下的能效突破，不但体现了Jeddak的技术先进性、也奠定其成为工业级产品的基础。
• 产品创新：现阶段隐私计算产品的表现形式相对单一，主要面向解决数据流通共享中的一些特定隐私保护问题，缺乏广泛赋能的平台级和杀手级应用。原因除了上述能效问题外，也缺乏集中呈现的丰富场景、以驱动更多尝试探索。我们充分结合公司内外部大量实际需求不断实践，逐步形成了隐私计算产品的三类应用范式：
  • （1）与数据基础设施融合。即隐私计算能力下沉、完整接管上游业务的用数过程。例如，针对抖音业务中台的用数申请以满足多源数据共享的联合建模需求，Jeddak不但为此实现了数据的安全隐私保护及其所有权和使用权分离，同时也示范了隐私计算与大规模基础设施的深度融合实践。
  • （2）与数据产品融合。目的是把隐私计算功能集成进数据套件以方便用户触达，例如以插件的形式结合。于是当使用套件服务来处理敏感数据时，便可直接开启保序加密、同态加密等功能，完成相关密文计算，类似把ChatGPT能力与Office套件的各种应用关联打通。另一类创新是，Jeddak数据安全沙箱与一方敏感数据组合并集成进便携式服务器，形成数信一体机产品，从而满足用户数据不出域条件下、在TEE内实现了多源数据的安全汇聚计算。
  • （3）与数据应用开发工具融合。目标是辅助用户便捷拓展领域应用，例如Jeddak联邦学习已嵌入公司AI推荐平台、并配套研发了支持调用的SDK工具。使得平台上游业务可同时获取到联邦学习能力、轻易构建出自己的AI隐私计算应用，从而打通利用更多敏感数据源、大幅提升建模质量，其作用类似于大模型的领域开发工具链LangChain。从实践效果看，这三种应用范式基本覆盖和满足了公司内外业务的相关需求，摸索出隐私计算广泛赋能的实施方法和路径。
• 领域洞察：除了技术突破和产品创新外，还需深入结合业务的属性特征才能发挥隐私计算的最大效用。原因在于，利用这些特定约束可助力实现成本控制与目标达成的最佳平衡。例如，基于可信计算的Jeddak数据安全沙箱大量服务了公司职能线（e.g.人力/财务/研效等），其业务场景特征是：数据流转共享常见、处理逻辑灵活多变、且有准实时计算要求。对此Jeddak充分结合利用了TEE技术特长和业务特点，体现出较高实施效用。另一类典型案例如，一些金融行业的应用对安全隐私提出极高要求，为此我们基于多方安全计算MPC技术、设计实现了全密态机器学习系统以满足数学可证安全性，并且在营销预测建模场景中实际落地。因此，对业务领域的深入洞察不但能帮助提升应用效果、甚至可挖掘和推动更多的技术服务创新。

对于隐私计算的应用发展还有两类问题特别值得关注。一是对私域数据的保护和价值重视：很多实体往往并不清晰自身数据的潜在效用，平时可能疏于积累和防护，而最近GPT4 Turbo展现的基于私域数据的微调、能够为用户创建出高质量领域大模型，凸显其重要性。二是从顶层设计的高度来推动隐私计算的大规模应用、赋能数字经济：除了产业政策促进外，AI大模型的普及很可能是重要的需求牵引。为此我们正积极探索相关技术，包括基于软件实现的大模型联邦精调、以及构建由GPU所组成的可信计算环境。

最后，通过本次iDASH竞赛我们检验了自身能力水平、同时也学习到很多先进经验，期待未来与业界伙伴密切交流合作、共同推进隐私计算的技术进步与蓬勃发展。