彭力强瓴羊数据安全专家 目录 概述及方案简介01单次查询的隐匿查询方案02批量查询的隐匿查询方案03 概述及方案简介01 隐匿查询隐匿查询 Ø隐匿查询(Private Information Retrieval,简称“PIR”),用于数据库检索的隐私计算方案 Ø对服务器数据库检索时,PIR方案可以保护用户的查询隐私,即服务器无法获取用户的检索信息,而用户可以正确获取检索信息 Ø适用于个人信贷数据库、医药数据库等对用户检索信息的隐私性有较高要求的数据库查询场景 解决方案 Ø数据库的所有数据下载到用户本地,用户在本地对数据库检索 Ø查询过程在用户本地进行,不需要其他方参与,不存在泄露风险 解决方案 方案分类 ØPIR方案可以根据服务器的数目,分为多服务器PIR方案和单服务器PIR方案 Ø多服务器PIR ü多服务器是指同一份数据复制存储在多个服务器,由不同的数据服务方管理ü在各数据服务方不共谋的安全假设下,可以提供信息论安全性•即使攻击者有无限的计算能力,也无法获取用户的检索信息 ü计算过程不包含密码学运算,计算开销小 多服务器PIR方案 Ø方案描述 ①数据复制存储在多个数据库②查询方向所有数据库发送“检索信息”③数据库根据“检索信息”返回“查询结果”④查询方从多个“查询结果”恢复出最终正确的查询结果 ü安全性假设:服务器之间不共谋(若服务器之间存在共谋,可以恢复出检索信息) 多服务器PIR方案-双服务器方案 Ø方案示例 数据服务方拥有12个比特信息 𝑛=12 查询方检索第“𝑖”个位置的信息 多服务器PIR方案-双服务器方案 Ø方案示例 ①数据复制存在两个服务器 多服务器PIR方案-双服务器方案 Ø方案示例 ①数据复制存在两个服务器 ②查询方:构造集合{1,𝑛}的一个子集𝑄!,并且𝑖∉𝑄! 多服务器PIR方案-双服务器方案 Ø方案示例 ①数据复制存在两个服务器 ②查询方:构造集合{1,𝑛}的一个子集𝑄!,并且𝑖∉𝑄! 多服务器PIR方案-双服务器方案 Ø方案示例 数据复制存在两个服务器 多服务器PIR方案-双服务器方案 Ø方案示例 数据复制存在两个服务器 多服务器PIR方案-双服务器方案 Ø方案示例 数据复制存在两个服务器 多服务器PIR方案-双服务器方案 Ø方案示例 数据复制存在两个服务器 方案分类 ØPIR方案可以根据服务器的数目,分为多服务器PIR方案和单服务器PIR方案 Ø单服务器PIR ü数据只存储在一个数据库中,由一个数据服务方进行管理ü基本都是由密码学算法构造的,其安全强度依赖于所涉及密码学算法的安全性ü通信量损耗降低了很多,响应耗时较长 单服务器PIR方案-预备知识 Ø同态加密 ü公钥加密算法,允许对密文进行特定形式的代数运算(加法、乘法)得到仍是加密的结果 •明文𝑚!,𝑚",密文𝑐!=𝐸𝑛𝑐𝑚!,𝑐"=𝐸𝑛𝑐(𝑚")•加法同态:对密文进行加法操作𝑐&''=𝑐!+𝑐",对𝑐&''解密可以得到𝐷𝑒𝑐(𝑐&'')=𝑚!+𝑚"•乘法同态:对密文进行乘法操作𝑐()#=𝑐!×𝑐",对𝑐()#解密可以得到𝐷𝑒𝑐(𝑐()#)=𝑚!×𝑚" Ø同态加密的优势 ü隐私性高&信任成本低 •只需要将信息以密文的形式发送给服务器,服务器不需要解密,就可以完成对数据的处理•只有生成密钥的一方可以恢复计算结果,计算过程不泄漏任何信息 ü低交互次数 单服务器PIR方案 Ø方案示例 查询方 •第一步:生成加密算法的公私钥对𝑝𝑘,𝑠𝑘•第二步:构造向量(0, 0,1, 0) 坐标等于查询行号的元素设置为1,其余为0 单服务器PIR方案 Ø方案示例 查询方 •第一步:生成加密算法的公私钥对𝑝𝑘,𝑠𝑘•第二步:构造向量(0, 0, 1, 0) 坐标等于查询行号的元素设置为1,其余为0 •第三步:用公钥𝑝𝑘,分别加密向量中的元素,得到𝑞!,𝑞",𝑞.,𝑞/=(𝐸𝑛𝑐0,𝐸𝑛𝑐0,𝐸𝑛𝑐1,𝐸𝑛𝑐(0)) 公钥算法为概率性加密算法,在加密过程中会填充随机数。对于同样的明文,加密后的密文是不一样的 单服务器PIR方案 Ø方案示例 查询方 •第一步:生成加密算法的公私钥对𝑝𝑘,𝑠𝑘•第二步:构造向量(0, 0, 1, 0) 坐标等于查询行号的元素设置为1,其余为0 •第三步:用公钥𝑝𝑘,分别加密向量中的元素,得到𝑞!,𝑞",𝑞.,𝑞/=(𝐸𝑛𝑐0,𝐸𝑛𝑐0,𝐸𝑛𝑐1,𝐸𝑛𝑐(0)) 公钥算法为概率性加密算法,在加密过程中会加入随机数。 数据服务方 𝑟=𝑣!×𝑞!+𝑣"×𝑞"+𝑣.×𝑞.+𝑣/×𝑞/=𝑣!×𝐸𝑛𝑐0+𝑣"×𝐸𝑛𝑐0+𝑣.×𝐸𝑛𝑐1+𝑣/×𝐸𝑛𝑐0=𝐸𝑛𝑐0+𝐸𝑛𝑐0+𝐸𝑛𝑐𝑣.+𝐸𝑛𝑐0=𝐸𝑛𝑐(𝑣.) 单服务器PIR方案 Ø方案示例 查询方 •第一步:生成加密算法的公私钥对𝑝𝑘,𝑠𝑘•第二步:构造向量(0, 0, 1, 0) 坐标等于查询行号的元素设置为1,其余为0 •第三步:用公钥𝑝𝑘,分别加密向量中的元素,得到𝑞!,𝑞",𝑞.,𝑞/=(𝐸𝑛𝑐0,𝐸𝑛𝑐0,𝐸𝑛𝑐1,𝐸𝑛𝑐(0)) 公钥算法为概率性加密算法,在加密过程中会加入随机数。 数据服务方 查询结果:𝑟 𝑟=𝑣!×𝑞!+𝑣"×𝑞"+𝑣.×𝑞.+𝑣/×𝑞/ 查询方用私钥𝑠𝑘解密𝑟𝐷𝑒𝑐𝑟=𝐷𝑒𝑐(𝐸𝑛𝑐𝑣.)=𝑣. 单服务器PIR方案 Ø方案小结 ü安全性 •依赖于公钥密码算法的安全强度。通常会选取参数,使得方案满足128比特计算安全强度ü通信量 •查询方需要发送n个密文•数据服务方返回1个密文 ü性能问题 •明文和密文乘法运算、密文和密文加法运算 Ø单服务器PIR方案不需要各数据服务方之间不共谋的安全假设,适合在实际场景中部署 单次查询的PIR方案02 预备知识--BFV加密算法 BFV加密算法的所有运算在多项式环𝑅=𝑍/(𝑥0+1) Ø私钥 其中,系数𝑠3的取值范围很小,例如{−1,0,1} Ø公钥 其中,𝑎∈𝑅𝑚𝑜𝑑𝑞是随机选取的,𝑒是噪声多项式,其系数服从有界的高斯分布随机采样 Ø明文 其中,𝑚3∈0,𝑡,可以表示为𝑚∈𝑅𝑚𝑜𝑑𝑡 Ø密文 其中,𝑐2,3,𝑐!,3∈0,𝑞,可以表示为c2,c!∈𝑅𝑚𝑜𝑑𝑞 预备知识--BFV加密算法 BFV加密算法的所有运算在多项式环𝑅=𝑍/(𝑥0+1) Ø加密过程 其中,Δ=⌊𝑞/𝑡⌋,𝑒′是噪声多项式。可以看出,明文𝑚隐藏在密文第二个多项式𝑐!的系数最高有效位中Ø解密过程 因为噪声𝑒的系数很小,消息𝑚可以从最高有效位中提取出来 Ø密文扩展系数 密文扩展系数定义为密文比特长度和明文比特长度的比值。对于BFV算法来说,密文为两个多项式,且所有系数的比特长度为log"(𝑞),明文为一个多项式,系数的比特长度为log"(𝑡)。因此,BFV算法的密文扩展系数为, 同态加密算法 Ø部分全同态加密算法 ü部分全同态加密算法是指参与方可以对密文进行有限数量的加法、乘法等同态运算ü部分全同态加密方案的构造会在生成密文中添加随机的噪声ü如果同态运算的次数超过约定数量后,密文无法被正确解密 Ø如何控制噪声增长是PIR方案中的一个关键问题 单服务器PIR方案 Ø为了解决查询向量长度过大的问题,可以将数据库表示成多维的数组 Ø如上图,用户的检索值为两个长度为4的向量(0,0,1,0)和0,1,0,0 Ø一般来讲,如果将数据库𝑛个元素表示成𝑑维的数组,查询向量的元素个数为𝑑⋅𝑛!/' EyalKushilevitzandRafailOstrovsky. Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. In 38thAnnual Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, Miami Beach, Florida, USA, 364–373. XPIR方案 第一步:服务端数据库编码 Ø假设服务器数据库有𝑛个数据,(𝑑𝑏2,𝑑𝑏!,⋯,𝑑𝑏71!),且数据的比特长度均为𝑙 Ø需要将数据库中的元素编码成多项式。不妨假设数据的长度𝑙=log"(𝑡)−1,其中log"(𝑡)表示𝑡的比特长度Ø可以将𝑑𝑏2,⋯,𝑑𝑏01!编码到一个多项式, Ø经过编码后,数据库的原始数据变换为⌈𝑛/𝑁⌉个BFV算法的明文多项式 Ø服务端将⌈𝑛/𝑁⌉个多项式表示成𝑑维的数组,每一维的向量长度为𝑛/𝑁!/' Carlos Aguilar Melchor, Joris Barrier, LaurentFousse, and Marc-OlivierKillijian. XPIR : Private Information Retrieval for Everyone. Proc. Priv.Enhancing Technol. 2016, 2 (2016), 155–174. XPIR方案 第二步:客户端生成查询密文 Ø用户将检索值𝑖𝑛𝑑𝑒𝑥∈[1,𝑛]转换为对明文多项式的检索值,即𝑖𝑛𝑑𝑒𝑥′=⌈𝑖𝑛𝑑𝑒𝑥/𝑁⌉。之后,再通过𝑖𝑛𝑑𝑒𝑥′计算出各维度的检索值 ü构造两个长度为𝑛/𝑁!/"的向量,即第一个向量只有第𝑖个分量为1,其余分量为0,第二个向量只有第𝑗个分量为1,其余分量为0 Ø用户将向量中的所有分量,表示成BFV算法的明文 ü0对应的明文多项式中所有系数均为0ü1对应的明文多项式中只有常数项为1,其余系数为0 Ø用户对所有分量进行加密,并将加密结果发送给服务器 XPIR方案 第三步:服务端计算查询结果 Ø服务器收到查询向量后,用数据库的每一列与行查询向量做内积运算 Ø服务器进一步用列的检索向量密文,与行的检索结果密文进行同态运算 ü注意到,行的检索结果是BFV算法密文,列的检索向量也是BFV算法密文 ü服务器将密文拆分成多个明文,之后再与列检索向量的密文做明密文的乘法运算 XPIR方案 第三步:服务端计算查询结果 ØBFV加密算法的密文为两个多项式,其系数为模𝑞的整数,明文为一个多项式,系数为模𝑡的整数 Ø例如,模数𝑞的比特长度为100,模数𝑡的比特长度为20;Ø密文多项式的每一个系数可以拆分成5段,每一段的比特长度为20;Ø拆分后,每一段的数据可以用一个明文多项式的系数表示;Ø因此,一个BFV加密算法的密文表示成10个BFV加密算法明文,即此时BFV算法的密文扩展系数为10 XPIR方案 第三步:服务端计算查询结果 Ø服务器逐段将拆分后的明文,与列检索向量密文做内积运算,得到逐段拆分的密文,并将该结果作为检索结果返回 XPIR方案 第四步:客户端恢复检索结果 Ø收到检索结果后,用户逐一对密文进行解密,得到(𝑡"!,𝑡"",⋯,𝑡"8)Ø将明文组合在一起,即将F个明文组合成一个密文,也就是𝑥."的密文,再对其解密Ø用户根据检索值,进一步由明文多项式的若干系数,恢复想要查询的数据 XPIR方案 小结 Ø在XPIR方案中,对于更高的维度𝑑,服务器和用户只需要递归地执行上述步骤即可 ü维