摘  要  

隐匿查询是指在不向数据提供方暴露查询方的查询意图，同时又能在保护数据提供方数据库中其他数据的情况下让查询方获得相关查询结果。实际使用的场景大多是跨广域网环境下基于关键字的查询。当前的常用方法要么需要传输大量的数据，而单一业务的远距离传输专线带宽经常是10Mbps甚至更低，这会导致传输时间无法接受，要么只能做到基于序号（index）的查询，但实际使用时查询方很难知道自己要查询的信息位于数据方数据库的第几号，而实际使用中更普遍的情况是查询方使用关键字（如身份证号）进行查询。

我们可以想象这样一种场景：金融机构或医疗单位掌握了大量有价值的数据，但出于隐私保护、数据安全和法律法规方面的考虑，这些机构无法将所有数据开放给其他用户；另一方面，作为查询方，其查询条件（如客户身份证号和手机号）有时候也具有较高的敏感性和商业价值。在这类场景下，查询方需要保护查询条件，数据方需要保护数据源（即除了被查的信息外不泄露任何其他信息），这便是隐匿查询的典型场景。

我们可以使用一个简单的例子加以说明：某信用机构拥有一系列居民的征信分数及征信记录等信息，某贷款机构想从征信机构查询一个借贷客户的信用分数，但贷款机构出于保护客户资源的考量，不愿泄露这位客户的身份证号，同时征信机构也不想泄露除了这位被查询的借贷客户信息之外的其他信息（如其他居民的征信分数）。在这类场景下隐匿查询可解决该问题。

隐匿查询是当前隐私保护计算应用场景中最常见的场景之一。典型的隐匿查询有两个参与方：查询方和数据方，这也意味着隐匿查询一般是一种跨广域网的点对点计算，且计算直接发生在参与方（即端侧）。由于跨广域网通讯的带宽限制使得隐匿查询的性能对通讯量非常敏感，因此用端侧计算量的增加来换取通讯量的减少是一个合理的选择。我们使用软硬结合的方案解决了隐匿查询实用化的问题：使用半同态计算专用芯片针对基于半同态加密且通讯量极少的隐匿查询软件方案进行加速。

隐匿查询根据实际使用情况可分为两类：基于序号的查询和基于关键字的查询。基于序号的查询是指查询方已经知道需要查询的数据位于数据源中的具体位置（类似于使用数组的下标访问），这在实际使用中并不常见；而基于关键字的查询则只需要查询方提供全局唯一的关键字（如身份证号、手机号、房产证编号等）即可，这种情况更为常见与通用。因此，本文只讨论基于关键字的查询场景。

在密码学领域，隐匿查询有多种实现方法，包括不经意传输（OT）、全同态加密、半同态加密等。这些方法各有优劣，有的方法计算极快但需要消耗很多带宽，有的方法对算力要求很高但传输的数据量较少。在实际使用中，通过广域网进行远程查询时能够使用的带宽资源有限，即便是跨省专线，很多时候为查询类业务能够分配的带宽可能也只有10Mbps甚至更少，因此而像KKRT这种基于OT扩展的方法，虽然计算量较少，但即便是在量级为100万且单条数据长度为200字节的数据集上进行隐匿查询时传输的数据量就在700MB以上，这便导致了在10Mbps的带宽情况下仅花在数据传输上的时间就有将近10分钟；这在实用使用中是很难接受的。而基于同态的方法（包括半同态和全同态）可构造出使用极小带宽的软件方案，代价是消耗巨大的算力。

华控清交专注于打造业界最快、最强、高安全性的密文计算引擎，在密文计算算法、软件优化、硬件加速方面都做了大量业界领先的工作。对于使用范围极广的隐匿查询场景，我们设计了基于关键字的查询算法（已申请专利），该算法借助半同态加密的特性，能够在算法上做到高可扩展并且数据传输量极少，其代价是需要消耗大量算力。为了解决半同态计算耗时长的痛点，华控清交李艺博士带领的安全与芯片团队打造了业界第一块半同态加密计算芯片，王雪强博士负责了该芯片的架构实现与验证。该芯片极大地加速了Paillier等半同态加密计算，使得跨广域网的隐匿查询可以极快地完成。如此，在新算法与半同态加密芯片的双重加持下，隐匿查询可实现计算时间与通讯量的双重最优，真正实现在广域网环境中较大数据量的隐匿查询的实用化。

本文将简要介绍我们的算法构造，以及业界第一块半同态加密芯片对隐匿查询的加速作用。

我们以金融场景为例展示我们设计的针对低带宽消耗的基于关键字的隐匿查询算法。

场景一：使用关键字在单数据源上查询

我们假设某金融机构拥有用户姓名、联系方式、家庭住址、借贷历史等信息，这些信息一般有几百字节或更多。我们解决这个问题的大致思路如下：

• 步骤一：将数据源分组构造多项式：假定数据方总共有N条数据，将其分为n1组，每组约有n2条数据（即N=n1×n2），每条数据是一个键值对(k, x)，其中k是关键字，x是对应的数据，然后使用每组数据构造多项式，一般情况下我们可以取n=n1=n2，如此便有n2=N；
   
• 步骤二：计算密文多项式：查询方将其密文的关键字k加密后得到若干密文[k],[k2], [k3],...，并将其发送给数据方。数据方可根据加密算法的同态性质计算得到每个多项式的值的密文，并使用特定的方法混淆并打乱，然后返还给查询方；
   
• 步骤三：解密得到查询结果：查询方解密得到的信息，即可得到是否查询成功以及查询成功后的查询结果。
   

• 通讯复杂度为O(√N)，极大降低了通讯复杂度，而且实际上我们只要求分组数与每组元素个数的乘积等于元素总数，也就意味着实际上可以用更多的计算换取更少的通讯；
   
• 计算复杂度为O(N)，但可完全并行进行，且计算占比较高，因此硬件加速效果明显；
   
• 多项式的生成在数据方拥有查询方公钥的情况下完全可以离线完成，也就是说之后的查询无需重复构造这些多项式；
   
• 只要求加密方法满足密文上的加法同态以及密文与明文的乘法同态，如此一来很多经典的同态算法都可满足此性质，如Paillier、ElGamal、BGV等，不同加密方法的计算与通讯特性不同，可根据实际需要灵活选择。
   

场景二：多数据源查询结果的聚合与比较

• 通讯复杂度同样为O(√N)，适用于低带宽场景；
   
   
• 计算复杂度依然为O(N)，同样可以由硬件加速极大地提升效率；
   
   
• 只要求加密方法满足密文上的加法同态以及密文与明文的乘法同态，避免了直接在密文上进行比较操作（直接在密文上计算比较电路要求加密方案支持全同态（FHE）或部分同态（Somewhat HE），且比较电路要求同态加密支持若干层的操作，这会导致整体计算效率很低），因此支持半同态操作的加密方案如Paillier、Elgama、BGV、FV皆可使用。但需要注意的是，我们的方法要求最后一步解密随机分布的数据，因此椭圆曲线类的算法不适用。
   
   
   

• 每块板卡可达到极高的吞吐量——计算模幂的性能可媲美约1000个CPU核；
   
• 单块板卡满负荷运载时的功率仅为约120W，能效比极高；
   
• 我们开发相应的驱动程序，可以在应用层无感知的情况下支持一卡多芯片、一机多卡、多机并行，提供极佳的数据并行能力，同时能在最小的空间中布置最多的算力。
   
   

测试场景

• 场景一：两方隐匿查询，数据方有100万条数据，每条数据大小为240字节，关键字长度为8字节（足以编码身份证号）；
   
• 场景二：一个查询方和两个数据方，每个数据方同样有100万条数据，关键字长度为8字节，每条数据是一个4字节的整数（如借款额度）。
   

测试环境

对比算法

• KKRT[5]：参数选择参考原论文，此方案算力消耗极少，计算效率高，可以说是目前学术领域两方查询的state-of-the-art，奈何中间依赖OT Extension的变种方法做OPRF，导致通讯量极高，不适合带宽有限的广域网场景；
   
• ECC-ElGamal[6]：原生的ElGamal和Paillier一样是基于模幂的，相对Paillier而言并无优势，但近来有些工作将ElGamal中的模幂替换为椭圆曲线（elliptic curve, ECC），计算效率相较于CPU版本的Paillier有所提升，同时通讯量虽然比基准方案稍大但也远小于KKRT，当然由于ECC本身只能用于椭圆曲线上点的加法，而无法直接用于数值加法，因此需要一些工作将数值编码成椭圆曲线上的点，这些本身也会耗费一些计算量，我们选择的曲线是NID_X9_62_prime256v1。
   

测试数据

• 多：应用场景广、能处理的数据量大；
   
• 快：省流算法有利于快速完成传输，专用芯片则极大提升了计算效率；
   
• 好：多+快+省=好；
   
• 省：省流量、省时间、省功耗、省空间。