基于同态加密实现的隐匿查询方案

基于同态加密的隐匿查询方案 彭力强瓴羊数据安全专家 DataFunSummit2023 目录 01概述及方案简介 02单次查询的隐匿查询方案 03批量查询的隐匿查询方案 01概述及方案简介 隐匿查询（PrivateInformationRetrieval，简称“PIR”），用于数据库检索的隐私计算方案 对服务器数据库检索时，PIR方案可以保护用户的查询隐私，即服务器无法获取用户的检索信息，而用户可以正确获取检索信息 适用于个人信贷数据库、医药数据库等对用户检索信息的隐私性有较高要求的数据库查询场景 数据库的所有数据下载到用户本地，用户在本地对数据库检索 查询过程在用户本地进行，不需要其他方参与，不存在泄露风险 不存在隐私泄漏风险，但需要下载完整的数据库是否存在通信量小于O(n)的方案 设计PIR方案的目标 PIR方案可以根据服务器的数目，分为多服务器PIR方案和单服务器PIR方案 多服务器PIR 多服务器是指同一份数据复制存储在多个服务器，由不同的数据服务方管理 在各数据服务方不共谋的安全假设下，可以提供信息论安全性 •即使攻击者有无限的计算能力，也无法获取用户的检索信息 计算过程不包含密码学运算，计算开销小 方案描述 ①数据复制存储在多个数据库 ②查询方向所有数据库发送“检索信息” ③数据库根据“检索信息”返回“查询结果” ④查询方从多个“查询结果”恢复出最终正确的查询结果 安全性假设：服务器之间不共谋（若服务器之间存在共谋，可以恢复出检索信息） 方案示例 数据服务方拥有12个比特信息 �=12 0 1 0 0 1 1 0 1 0 0 1 0 �=7 查询方检索第“𝑖”个位置的信息 ①数据复制存在两个服务器 方案示例 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 𝑆1𝑆2 ①数据复制存在两个服务器 方案示例 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 𝑆1𝑆2 𝑄1 ②查询方：构造集合[1,𝑛]的一个子集𝑄1，并且�∉𝑄1 0 1 0 0 1 1 0 1 0 0 1 0 方案示例 ①数据复制存在两个服务器 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 𝑆2 𝑆1 � 𝑄1 𝑎1=⊕𝑙∈%1𝑥�=0 ③检索结果 ②查询方：构造集合[1,𝑛]的一个子集𝑄1，并且�∉𝑄1 数据复制存在两个服务器 方案示例 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 𝑄1+[𝑖] 0 1 0 0 1 1 0 1 0 0 1 0 𝑆1𝑆2 𝑎1=⊕𝑙∈%1𝑥� 𝑄1 𝑄2= ②查询方：构造集合𝑄2=𝑄1+[𝑖] 数据复制存在两个服务器 方案示例 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 𝑄1+[𝑖] 𝑎2=⊕𝑙∈%2𝑥� ③检索结果 0 1 0 0 1 1 0 1 0 0 1 0 𝑆1𝑆2 𝑎1=⊕𝑙∈%1𝑥� 𝑄1 𝑄2= ②查询方：构造集合𝑄2=𝑄1+[𝑖] 数据复制存在两个服务器 方案示例 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 𝑆1𝑆2 𝑎1=⊕𝑙∈%1𝑥� 𝑄1 𝑄2=𝑄1+[𝑖] 𝑎2=⊕𝑙∈%2𝑥� ④查询方：查询结果𝑎1⊕𝑎2 方案示例 0 1 0 0 1 1 0 1 0 0 1 0 数据复制存在两个服务器 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 110 1 0 0 1 0 𝑆1𝑆2 �� 𝑎1=⊕𝑙∈%1𝑥�=0 𝑄1 𝑄2=𝑄1+[𝑖] 𝑎2=⊕𝑙∈%2𝑥�=1 ④查询方：查询结果𝑎1⊕𝑎2=0⊕1=1 PIR方案可以根据服务器的数目，分为多服务器PIR方案和单服务器PIR方案 单服务器PIR 数据只存储在一个数据库中，由一个数据服务方进行管理 基本都是由密码学算法构造的，其安全强度依赖于所涉及密码学算法的安全性 通信量损耗降低了很多，响应耗时较长 同态加密 公钥加密算法，允许对密文进行特定形式的代数运算（加法、乘法）得到仍是加密的结果 𝑚1 •明文𝑚1,𝑚2，密文𝑐1=𝐸𝑛�,𝑐2=𝐸𝑛𝑐(𝑚2) •加法同态：对密文进行加法操作𝑐𝑎𝑑�=𝑐1+𝑐2，对𝑐𝑎𝑑�解密可以得到𝐷𝑒𝑐(𝑐𝑎𝑑𝑑)=𝑚1+𝑚2 •乘法同态：对密文进行乘法操作𝑐𝑚𝑢�=𝑐1×𝑐2，对𝑐𝑚𝑢�解密可以得到𝐷𝑒𝑐(𝑐𝑚𝑢𝑙)=𝑚1×𝑚2 只支持加法同态、或者乘法同态的算法称为半同态算法 •例如，Paillier等公钥密码学算法 支持对密文进行有限数量的加法、乘法等同态运算称为部分全同态算法 •例如，BFV、BGV等公钥密码学算法 同态加密的优势 隐私性高&信任成本低 •只需要将信息以密文的形式发送给服务器，服务器不需要解密，就可以完成对数据的处理 •只有生成密钥的一方可以恢复计算结果，计算过程不泄漏任何信息 低交互次数 1 𝒗� 2 𝒗� 3 𝒗� 4 𝒗� 检索信息：3 𝑝𝑘,𝑠� 查询方 坐标等于查询行号的元素设置 为1，其余为0 • • 第一步：生成加密算法的公私钥对第二步：构造向量（0,0,1,0） 1 𝒗� 2 𝒗� 3 𝒗� 4 𝒗� 检索信息：3 𝑝𝑘,𝑠� 查询方 坐标等于查询行号的元素设置 为1，其余为0 • • 第一步：生成加密算法的公私钥对第二步：构造向量（0,0,1,0） 𝑞1,𝑞2,𝑞.,𝑞/ (𝐸𝑛�0,𝐸𝑛�0,𝐸𝑛�1,𝐸𝑛𝑐(0)) 公钥算法为概率性加密算法，在加密过程中会填充随机数。 对于同样的明文，加密后的密文是不一样的 • 第三步：用公钥𝑝𝑘，分别加密向量中的元素，得到 = 1 𝒗� 2 𝒗� 3 𝒗� 4 𝒗� 检索信息：3 𝑝𝑘,𝑠� 查询方 坐标等于查询行号的元素设置 为1，其余为0 • • 第一步：生成加密算法的公私钥对第二步：构造向量（0,0,1,0） 𝑞1,𝑞2,𝑞3,𝑞/ 0 0 1 • 公钥算法为概率性加密算法， 在加密过程中会加入随机数。 第三步：用公钥𝑝𝑘，分别加密向量中的元素，得到 =(𝐸𝑛� ,𝐸𝑛𝑐 ,𝐸𝑛𝑐 ,𝐸𝑛𝑐(0)) 数据服务方 1 �=𝑣1×𝑞1+𝑣2×𝑞2+𝑣3×𝑞3+𝑣/×𝑞/ =𝑣1×𝐸𝑛�0+𝑣2×𝐸𝑛�0+𝑣3×𝐸𝑛� 检索信息：𝑞1,𝑞2,𝑞3,𝑞/ 0 +𝑣/×𝐸𝑛� 0 𝑣3 0 =𝐸𝑛�0+𝐸𝑛�+𝐸𝑛�+𝐸𝑛� =𝐸𝑛𝑐(𝑣3) 1 𝒗� 2 𝒗� 3 𝒗� 4 𝒗� 检索信息：3 𝑝𝑘,𝑠� 查询方 坐标等于查询行号的元素设置 为1，其余为0 • • 第一步：生成加密算法的公私钥对第二步：构造向量（0,0,1,0） 𝑞1,𝑞2,𝑞3,𝑞/ 0 0 1 • 公钥算法为概率性加密算法， 在加密过程中会加入随机数。 第三步：用公钥𝑝𝑘，分别加密向量中的元素，得到 =(𝐸𝑛� ,𝐸𝑛𝑐 ,𝐸𝑛𝑐 ,𝐸𝑛𝑐(0)) 检索信息：𝑞1,𝑞2,𝑞3,𝑞/ 数据服务方 �=𝑣1×𝑞1+𝑣2×𝑞2+𝑣3×𝑞3+𝑣/×𝑞/查询结果：� 用私钥𝑠�解密� 𝐷𝑒��=𝐷𝑒𝑐(𝐸𝑛�𝑣3)=𝑣3 查询方 方案小结 安全性 •依赖于公钥密码算法的安全强度。通常会选取参数，使得方案满足128比特计算安全强度 通信量 •查询方需要发送n个密文 •数据服务方返回1个密文 性能问题 •明文和密文乘法运算、密文和密文加法运算 多服务器PIR 单服务器PIR 安全强度 信息论安全 计算安全 计算开销 底 高 通信量 高 底 单服务器PIR方案不需要各数据服务方之间不共谋的安全假设，适合在实际场景中部署 02单次查询的PIR方案 私钥 𝑠�=𝑠𝑁–1𝑥𝑁–1+𝑠𝑁–2𝑥𝑁–2+⋯+𝑠1𝑥1+𝑠2， 其中，系数𝑠3的取值范围很小，例如[−1,0,1] 公钥 𝑎,�⋅�+� 𝑝�= 其中，�∈�𝑚𝑜��是随机选取的，�是噪声多项式，其系数服从有界的高斯分布随机采样 明文 其中，𝑚3∈ 密文 �=𝑚𝑁–1𝑥𝑁–1+𝑚𝑁–2𝑥𝑁–2+⋯+𝑚1𝑥1+𝑚2 0,� ，可以表示为�∈�𝑚𝑜�� 𝑐2,𝑐1 𝑐2,𝑁–1𝑥𝑁–1+𝑐2,𝑁–2𝑥𝑁–2+⋯+𝑐2,1𝑥1+𝑐2,2,𝑐1,𝑁–1𝑥𝑁–1+𝑐1,𝑁–2𝑥𝑁–2+⋯+𝑐1,1𝑥1+𝑐1,2 = 0,� 其中，𝑐2,3,𝑐1,3∈，可以表示为c2,c1∈�𝑚𝑜�� 加密过程 𝑐2,𝑐1 𝑎,�+𝑒5+Δ� = 其中，Δ=⌊𝑞/𝑡⌋，𝑒′是噪声多项式。可以看出，明文�隐藏在密文第二个多项式𝑐1的系数最高有效位中 解密过程 c1−𝑐2⋅�=�+Δ� 因为噪声�的系数很小，消息�可以从最高有效位中提取出来 密文扩展系数 密文扩展系数定义为密文比特长度和明文比特长度的比值。对于BFV算法来说，密文为两个多项式，且所有系数的比特长度为log2(𝑞)，明文为一个多项式，系数的比特长度为log2(𝑡)。因此，BFV算法的密文扩展系数为， � �=2log2(𝑞)log2 部分全同态加密算法 部分全同态加密算法是指参与方可以对密文进行有限数量的加法、乘法等同态运算 部分全同态加密方案的构造会在生成密文中添加随机的噪声 如果同态运算的次数超过约定数量后，密文无法被正确解密 运算开销 噪音增长 BFV密文加法 -- 𝑂(𝐸𝑟�𝑐𝑡1+𝐸𝑟𝑟(𝑐𝑡2)) BFV明密文乘法 2 𝑂(𝐸𝑟�𝑐�⋅�) BFV密文乘法 4+2� 𝑂(𝑡(𝐸𝑟�𝑐𝑡1+𝐸𝑟�𝑐𝑡2)) 如何控制噪声增长是PIR方案中的一个关键问题 为了解决查询向量长度过大的问题，可以将数据库表示成多维的数组 0,1,0,0 如上图，用户的检索值为两个长度为4的向量(0,0,1,0)和 一般来讲，如果将数据库�个元素表示成�维的数组，查询向量的元素个数为�⋅ � 1/� EyalKushilevitzandRafailOstrovsky.ReplicationisNOTNeeded:SINGLEDatabase,Computationally-PrivateInformationRetrieval.In38thAnnualSymposiumonFoundationsofComputerScience,FOCS.IEEEComputerSociety,MiamiBeach,Florida,USA,364–373. 第一步：服务端数据库编码 