基于点函数秘密共享的私有信息检索协议

袁大曾，何明星，李 虓，曾晟珂

(1.西华大学 理学院，成都 610039； 2.西华大学 计算机与软件工程学院，成都 610039)

(*通信作者电子邮箱yuan_dz34@163.com)

基于点函数秘密共享的私有信息检索协议

袁大曾1,2*，何明星2，李 虓1，曾晟珂2

(1.西华大学 理学院，成都 610039； 2.西华大学 计算机与软件工程学院，成都 610039)

(*通信作者电子邮箱yuan_dz34@163.com)

针对私有信息检索(PIR)中的隐私安全问题，提出了一个基于点函数秘密共享的私有信息检索协议。该协议将检索的索引看成一个特殊的0- 1点函数，利用点函数秘密共享技术生成这个点函数的密钥组，分别发送给p个服务器，根据p个服务器返回的响应作异或运算得到检索结果。对协议进行了正确性、安全性和效率分析,验证了这个协议是安全且高效的，并给出了一个具体实例来说明该协议的有效性。最后介绍了将该协议推广到多项私有信息检索和基于关键字的私有信息检索中的应用情况。

点函数;函数秘密共享;私有信息检索;隐私安全;异或运算

0 引言

私有信息检索(Private Information Retrieval, PIR)[1]是指参与查询的用户与数据库所有者在不泄露各自私有信息的情况下，完成对数据库的查询操作。PIR问题作为安全多方计算[2]的一个重要的研究方向,在实际生活中，例如：多个公司之间的合作查询、医药数据库、专利数据库及实时股票报价等对检索隐私有较高要求的领域，有着很大的应用空间[3-5]。

解决PIR问题的一种最简单方法是数据库所有者将整个数据库中的文件全部发送给用户，然后由用户自己去完成检索过程。这样虽然可以保障用户的隐私，但其通信开销太大，无法应用到实际情况中；同时数据库所有者也并不希望用户得到数据库中的所有文件；而且如果有一些数据没有参与到用户查询中，数据库所有者就可以推断出用户对这些数据不感兴趣，从而泄露用户的隐私。

1995年，Chor等[1]首次对PIR问题进行了形式化的定义，并提出了一个有效的解决方案，即通过多个互不通信的拥有相同数据库副本的服务器共同协作完成查询，而任何一个数据库服务器的子集合作都不能获得用户的任何检索信息。将这种通过多个数据库副本实现的PIR的研究方法称为信息论私有信息检索(Information-theoretic Private Information Retrieval, IPIR)。随后，文献[6-10]相继又提出了一些PIR协议。2002年,Yang等[11]将秘密共享技术应用到私有信息检索中，解决了数据库所有者的恶意攻击问题。2008年，廖干才等[12]运用秘密共享技术，构造了单项和多项的PIR协议。PIR协议中，由于可能存在若干数据库服务器互相串通，或发生崩溃无法返回正确查询结果的情况，对此，文献[11-14]等将秘密共享方法应用到PIR问题中，提出了能够抵挡若干恶意服务器共谋、崩溃或返回错误结果的鲁棒性的PIR方法。

函数秘密共享(Function Secret Sharing, FSS)的概念最早是由De Santis等[15]于1994年出于分发一方的加密功能的目的而提出的，但由于其应用的局限性，很少有关于它的研究。直到2015年，为了有效地实现安全搜索和更新分布式数据的目的，Boyle等[16]根据分布式点函数(Distributed Point Function, DPF)[17]对FSS进行了介绍和研究，讨论了DPF的两个典型应用场景：多服务器私有信息搜索的安全关键字检索和增量式秘密共享，并基于异或运算提出了一个点函数秘密共享(Point Function Secret Sharing, PFSS)方案；Komargodski等[18]也提到了函数秘密共享的概念。受此启发，本文考虑将点函数秘密共享应用到PIR问题中。

本文针对PIR的隐私安全问题，运用点函数秘密共享方案构造了一个新的私有信息检索协议。在协议中，将检索的索引看成一个点函数，利用点函数秘密共享技术生成这个点函数的密钥组，分别发送给p个服务器，最后根据p个服务器返回的p个响应作异或运算得到检索结果。但通过分析发现，对点函数fa,b:{0,1}n→{0,1}m,在m>1时，点函数秘密共享方案不能很好地构造一个私有信息检索协议，反而在m=1(即0- 1点函数秘密共享方案)时，能有效地构造一个新的私有信息检索协议，并且可以提高协议的通信和计算效率。为此，本文在用点函数秘密共享方案构造新的私有信息检索协议时，所用的点函数是一个特殊的0- 1点函数。本文主要工作如下：

1)基于点函数秘密共享提出一个新的私有信息检索协议，并对协议进行了正确性、安全性和效率的分析。

2)给出了协议的一个具体实例，便于对协议的理解。

3)将该协议推广到多项私有信息检索[12]和基于关键字的私有信息检索[19]中，并简单描述了多项私有信息检索协议的过程。

1 相关知识

1.1 点函数

定义1 点函数。对于a∈{0,1}n,b∈{0,1}m，点函数fa,b:{0,1}n→{0,1}m，满足：fa,b(a)=b和fa,b(a′)=0m(a′≠a)。

定义2 0- 1点函数。对于a∈{0,1}n，0- 1点函数fa,1:{0,1}n→{0,1}，满足：fa,1(a)=1和fa,1(a′)=0(a′≠a)。0- 1点函数是一种特殊的点函数。

1.2 函数秘密共享

定义3 函数秘密共享(FSS)[16]。令p∈N,T⊆[p]([p]表示{1,2,…,p}的所有子集)，函数群F的一个T-安全的函数秘密共享(FSS)方案有三个算法(Gen,Eval,Dec)，且满足：

Gen(1λ,f)→(k1,k2,…,kp)：输入安全参数1λ和共享的函数f∈F，通过密钥生成算法输出密钥(k1,k2,…,kp)。

Eval(i,ki,x)→yi：输入i∈[p]，x∈Df(其中Df为函数f的定义域)，通过响应求值算法输出第i个共享者的响应。

Dec({yi}i∈T)→y：输入合法的共享者集合T的响应{yi}i∈T，通过重建算法输出对应的值y。

正确性和安全性的要求如下所示。

1)正确性。对所有f∈F,x∈Df，满足：y=f(x)。

2)安全性。考虑一个损坏的参与方集T⊂[p]的不可分辨性挑战实验，即敌手首先选取f0,f1∈F,Df0=Df1；然后挑战者选取样本{0,1}→b,Gen(1λ,fb)→(k1,k2,…,kp)；对损坏参与者集T的密钥，敌手输出一个猜测A((ki)i∈T)→b′。在上述实验中，敌手猜测b的优势为Adv(1λ,A):=Pr[b=b′]-2-1。如果对于所有非均匀PPT的敌手A，都存在一个不可忽略的函数v,有Adv(1λ,A)≤v(λ)，则认为方案(Gen,Eval,Dec)是T-安全。

1.3 点函数秘密共享方案

假设p表示共享者个数，fa,b:{0,1}n→{0,1}m表示共享的秘密点函数。令u=[2n/2·2(p-1)/2]和v=[2n/u]；G表示一个伪随机生成器G：{0,1}λ→{0,1}mu；Op(Ep)表示每列1 bit的个数为奇数(偶数)的p×2p-1维比特矩阵集；eδ表示一个长度为2|δ|在位置δ为1和在其他位置都为0的向量。

具体的PFSS方案包括如下三个算法：

算法1 密钥分发算法Gen(1λ,fa,b)→(k1,k2,…,kp)。

1)令a=(γ,δ),γ∈[v],δ∈[u]。

2)选取v个矩阵Aγ′(1≤γ′≤v)，满足：Aγ∈Op和Aγ′∈Ep(γ′≠γ)。

3)随机选择v·2p-1个字符串:s1,1,s1,2,…,s1,2p-1，…,sv,1,sv,2,…,sv,2p-1∈{0,1}λ。

5)令σjγ′=(sγ′,1·Aγ′[j,1])‖(sγ′,2·Aγ′[j,2])‖…‖

(sγ′,2p-1·Aγ′[j,2p-1])(1≤γ′≤v);再令σj=σj1‖σj2‖ …‖σjv(1≤j≤p)。

6)令kj=(σj‖cw1‖cw2‖…‖cw2p-1)(1≤j≤p)。

7)将密钥kj发送给第j个共享者。

算法2 份额构建算法Eval(j,kj,x)→yj。

1)令x=(γ′,δ′),γ′∈[v],δ′∈[u]。

2)解析：kj=(σj,cw1,cw2,…,cw2p-1)和σj=s1,1‖s1,2‖…‖s1,2p-1‖…‖sv,1‖sv,2‖…‖sv,2p-1。

4)计算：yj=dj[δ′]。

算法3 函数值重建算法Dec(y1,y2,…,yp)→y。

2 基于PFSS的PIR协议

本章首先介绍了私有信息检索(PIR)的问题，然后针对PIR的隐私安全问题，结合点函数秘密共享技术，提出了一个基于点函数秘密共享的PIR协议，并分析了协议的正确性、安全性和效率。

2.1 PIR问题描述

一般的PIR问题的具体描述为：假设Alice是查询者,Bob是数据库拥有者,Bob存储的数据用N个字符串X={x1,x2,…,xN}来表示,当查询者Alice想从Bob那里查询索引为i∈{1,2,…,N}的数据xi,但又不希望Bob知道“i”的信息，而Bob也不想Alice知道除xi以外的数据库信息，这样的问题就是PIR问题。

2.2 基于点函数秘密共享的PIR协议

基于点函数秘密共享的PIR协议的描述如下：假设有p个服务器S1,S2,…,Sp,每个服务器都有一样的N条数据记录数据库X={x1,x2,…,xN}(其中：xi∈{0,1}h表示第i条记录，一般p≪N)。用户想在没有泄露查询索引i给服务器的任何严格子集情况下从X中查询第i条记录xi，就构造一个特殊的0- 1点函数fi,1:{0,1}n→{0,1}(其中:n=「lb |N|⎤,符号「⎤表示N≤「N⎤

在协议中，由于0- 1点函数相当于一般点函数中m=1时，因此，重新定义伪随机生成器G为G：{0,1}λ→{0,1}u，而其他符号定义同上。协议的检索阶段执行步骤如下所示：

输入 索引i;

输出xi。

步骤1 用户通过算法Gen(1λ,fi,1)得到密钥组(k1,k2,…,kp)。

1)令i=(γ,δ),γ∈[v],δ∈[u]。

2)选取v个p×2p-1维矩阵集Aγ′(1≤γ′≤v)，满足：Aγ∈Op和Aγ′∈Ep(γ′≠γ)。

3)随机选择v·2p-1个字符串：s1，1,s1，2,…,s1，2p-1,…,sv，1,sv，2,…,sv，2p-1∈{0,1}λ。

5)令σj,γ′=(sγ′,1·Aγ′[j,1])‖(sγ′,2·Aγ′[j,2])‖ …‖(sγ′,2p-1·Aγ′[j,2p-1])(1≤γ′≤v*);再令σj=σj1‖σj2‖…‖σjv(1≤j≤p)。

6)令kj=(σj‖cw1‖cw2‖…‖cw2p-1)(1≤j≤p)。

步骤2 用户将步骤1所得的密钥kj分别发送给服务器Sj(1≤j≤p)。

步骤3 服务器Sj通过算法Eval(j,kj,X)得到响应yj。

1)令t=(γt,δt),γt∈[v],δt∈[u](1≤t≤N)。

2)解析：kj=(σj,cw1,cw2,…,cw2p-1)和σj=s1,1‖s1,2‖…‖s1,2p-1‖…‖sv,1‖sv,2‖…‖sv,2p-1。

5)得到响应yj。

步骤4 将每个服务器Sj(1≤j≤p)利用步骤3计算所得的响应yj发送给用户。

2.3 协议的分析

2.3.1 正确性分析

定理1 按照上述PIR协议，如果用户可以恢复出xi，则协议是正确的。

2.3.2 安全性分析

定理2 按照协议，一方面用户能恢复出xi,且得不到其他数据信息，另一方面，数据库服务器的任何严格子集不能够得到检索i的任何信息。

证明 因为xt(t=1,2,…,i-1,i+1,…,N)都在检索中相互抵消了，从而保证了用户得不到xi外的其他数据信息，即协议能够保证查询者无法通过多次查询获取更多的信息；又因为上面点函数秘密共享技术的安全保证，因此数据库服务器的任何严格子集不能够得到0- 1点函数fi,1的任何信息，即得不到检索i的任何信息。因此,该协议是安全的。

2.3.3 效率分析

对于协议的通信复杂度分析，因为在上述PIR协议中算法Gen输出密钥kj长度包括σj的比特长度v·λ·2p-1和向量集cw1,cw2,…,cw2p-1的比特长度u·2p-1。所以协议的通信量为：O((λ+1)·2「lb |N|⎤/2·2(p-1)/2)。对于协议的计算复杂度分析，因为协议主要运用到异或运算，因此计算效率是较高的。

由于在将点函数秘密共享应用到PIR问题中时，本文用一个特殊的0- 1点函数代替一般点函数，而这样不仅可以提高通信效率，还可以提高计算效率。因此，本文所提协议的效率是较高的。

3 协议的数据实例

为方便对于上述基于点函数秘密共享的PIR协议的理解，下面给出协议的一个小数据实例。

令λ=4,p=3,N=16,X={x1,x2,…,x16}，其中：xi∈{0,1}h表示第i条记录。从而u=8,v=2，伪随机发生器G：{0,1}4→{0,1}8。协议的具体执行步骤如下所示：

输入 索引i=11；

输出xi。

步骤1 通过算法Gen(14,fi,1)得到密钥组(k1,k2,k3)。

1)将i=11分解成γ=2,δ=4，其中“1010”、“1”和“010”分别表示i-1、γ-1和δ-1的二进制式。

2)生成v=2个p×2p-1=3×4维矩阵A1∈O3,A2∈E3，具体如下：

3)随机选取v·2p-1=2×4个字符串：s11,s12,s13,s14,s21,s22,s23,s24∈{0,1}λ。

5)令:

6)令kj=(σj‖cw1‖cw2‖cw3‖cw4)(j=1,2,3)。

步骤2 3个服务器分别根据X通过算法Eval计算如下:

1)解析16个索引值为：(γ1,δ1)=(1,1),(γ2,δ2)=(1,2),…,(γ8,δ8)=(1,8),…,(γ9,δ9)=(2,1),(γ10,δ10)=(2,2),…,(γ16,δ16)=(2,8)。

2)根据kj(j=1,2,3)，可以计算得到：

d1t=(cw2⊕G(s1,2))⊕(cw3⊕G(s1,3))⊕ (cw4⊕G(s1,4))

d1(t+8)=(cw1⊕G(s2,1))⊕(cw3⊕G(s2,3))⊕ (cw4⊕G(s2,4))

d2t=(cw2⊕G(s1,2))⊕(cw3⊕G(s1,3))

d2(t+8)=cw3⊕G(s2,3)

d3t=cw4⊕G(s1,4)

d3(t+8)=(cw2⊕G(s2,2))⊕(cw3⊕G(s2,3))

其中：系数1≤t≤8。

步骤3 用户根据3个服务器返回的响应y1、y2、y3通过算法Dec计算y。

因为:

4 协议的推广

输入 索引i1,i2,…,il(l≥2;1≤i1<…

输出xi1,xi2,…,xil。

步骤1 用户通过算法Gen(1λ,fi1,1,fi2,1,…,fil,1)得到密钥组(k1,k2,…,kp)，如下。

1)令iβ=(γβ,δβ),γβ∈[v],δβ∈[u](1≤β≤l)。

6)令kj=(σj,cw1,cw2,…,cw2p-1+(l-1))(1≤j≤p)。

步骤2 用户将所得kj分别发送给Sj(1≤j≤p)。

步骤3 服务器Sj通过算法Eval(j,kj,X)得到一个l维响应向量zj=(zj1,zj2,…,zjl)(1≤j≤p)。

1)令t=(γt,δt),γt∈[v],δt∈[u](1≤t≤N)。

3)计算：

其中：1≤β≤l,1≤t≤N。

5)得到响应向量zj=(zj1,zj2,…,zjl)。

步骤4 每个服务器将所得的响应zj分别发送给用户。

综上所述，点函数秘密共享可以在多项私有信息检索协议[12]和基于关键字的私有信息检索协议[19]中有很好的应用。

5 结语

本文针对私有信息检索(PIR)中的隐私安全问题，首次利用点函数秘密共享技术解决该问题，提出了一个基于点函数秘密共享的私有信息检索协议，在协议中将点函数定义为一个特殊的0- 1点函数以提高效率，然后通过效率分析验证该协议是高效的，并给出了一个具体实例验证该协议的有效性。最后简单介绍了将该协议推广到多项私有信息检索和基于关键字的私有信息检索中的运用情况。在以后的研究中，将提出更高效、安全的点函数秘密共享方案来解决PIR中的隐私安全问题以及扩展点函数秘密共享方案的新应用。

)

[1]CHORB,KUSHILEVITZE,GOLDREICHO,etal.Privateinformationretrieval[J].JournaloftheACM, 1998, 45(6): 965-981.

[2]YAOAC.Protocolsforsecurecomputations[C]//SFCS’ 08:Proceedingsofthe23rdAnnualSymposiumonFoundationsofComputerScience.Washington,DC:IEEEComputerSociety, 1982: 160-164.

[3]BAR-YOSSEFZ,GUREVICHM.Efficientsearchenginemeasurements[C]//Proceedingsofthe16thInternationalConferenceonWorldWideWeb.NewYork：ACM, 2007: 401-410.

[4]OSTROVSKYR,SKEITHⅢWE.Asurveyofsingle-databaseprivateinformationretrieval:Techniquesandapplications[C]//PKC2007:Proceedingsofthe10thInternationalConferenceonPracticeandTheoryinPublic-KeyCryptography,LNCS4450.Berlin:Springer-Verlag, 2007: 393-411.

[5]BEIMELA.Privateinformationretrieval:aprimer[EB/OL].(2008- 01- 14) [2016- 03- 06].http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=269B3ED5340FC31979EDA78A3172A559?doi=10.1.1.218.4195&rep=rep1&type=pdf.

[6]AMBAINISA.Upperboundonthecommunicationcomplexityofprivateinformationretrieval[C]//ICALP’97:Proceedingsofthe24thInternationalColloquiumonAutomata,LanguagesandProgramming,LNCS1256.Berlin:Springer-Verlag, 1997: 401-407.

[7]BEIMELA,ISHAIY.Information-theoreticprivateinformationretrieval:aunifiedconstruction[C]//ICALP2001:Proceedingsofthe28thInternationalColloquiumonAutomata,LanguagesandProgramming,LNCS2076.Berlin:Springer-Verlag, 2001: 912-926.

[8]ITOHT.EfficientPrivateinformationretrieval(specialsectiononcryptographyandinformationsecurity[J].IEICETransactionsonFundamentalsofElectronics,CommunicationsandComputerSciences, 1999,E82-A(1): 11-20.

[9]ISHAIY,KUSHILEVITZE.Improvedupperboundsoninformation-theoreticprivateinformationretrieval[C]//STOC’99:ProceedingsoftheThirty-FirstAnnualACMSymposiumonTheoryofComputing.NewYork:ACM, 1999: 79-88.

[10]BEIMELA,ISHAIY,KUSHILEVITZE,etal.BreakingtheO(n^(1/(2k-1))) barrier for information-theoretic private information retrieval [C]// FOCS ’02: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science.Washington, DC: IEEE Computer Society, 2002: 261-270.

[11] YANG E Y, XU J, BENNETT K H.Private information retrieval in the presence of malicious failures [C]// COMPSAC ’02: Proceedings of the 26th Annual International Computer Software and Applications Conference on Prolonging Software Life: Development and Redevelopment.Washington, DC: IEEE Computer Society, 2002: 805-812.

[12] 廖干才，罗守山.一种基于秘密共享的对称私有信息检索协议[EB/OL].(2008- 05- 05) [2016- 03- 05].http://www.paper.edu.cn/releasepaper/content/200805- 65.(LIAO G C, LUO S S.A protocol of symmetrically private information retrieval based on secret sharing [EB/OL].(2008- 05- 05) [2016- 03- 05].http://www.paper.edu.cn/releasepaper/content/200805- 65.)

[13] BEIMEL A, ISHAI Y, KUSHILEVITZ E.General constructions for information-theoretic private information retrieval [J].Journal of Computer and System Sciences, 2005, 71(2): 213-247.

[14] BEIMEL A, STAHL Y.Robust information-theoretic private information retrieval [C]// SCN 2002: Proceedings of the Third International Conference on Security in Communication Networks, LNCS 2576.Berlin: Springer-Verlag, 2003: 326-341.

[15] DE SANTIS A, DESMEDT Y, FRANKEL Y, et al.How to share a function securely [C]// STOC ’94: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing.New York: ACM, 1994: 522-533.

[16] BOYLE E, GILBOA N, ISHAI Y.Function secret sharing [C]// EUROCRYPT 2015: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 9057.Berlin: Springer-Verlag, 2015: 337-367.

[17] GILBOA N, ISHAI Y.Distributed point functions and their applications [C]// EUROCRYPT 2014: Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 8441.Berlin: Springer, 2014: 640-658.

[18] KOMARGODSKI I, ZHANDRY M.Cutting-edge cryptography through the lens of secret sharing [C]// TCC 2016-A: Proceedings of the 13th International Conference on Theory of Cryptography, LNCS 9563.Berlin: Springer, 2016: 449-479.

[19] 俞志斌,周彦晖.基于关键字的云加密数据隐私保护检索[J].计算机科学,2015,42(S1):365-369.(YU Z B, ZHOU Y H.Keyword based privacy-preserving retrieval over cloud encrypted data [J].Computer Science, 2015, 42(S1): 365-369.)

This work is partially supported by the National Natural Science Foundation of China (U1433130), the Ministry Basic Research Program (Chunhui Program) of China (Z2014045).

YUAN Dazeng, born in 1992, M.S.candidate.Her research interests include security protocol, network security, big data.

HE Mingxing, born in 1964, Ph.D., professor.His research interests include modern cryptographic algorithm, security protocol, key management, electronic commerce/e-government security.

LI Xiao, born in 1972, Ph.D., associate professor.His research interests include information security, cryptography.

ZENG Shengke, born in 1982, Ph.D., associate professor.Her research interests include information security, cryptography.

Private information retrieval protocol based on point function secret sharing

YUAN Dazeng1,2*, HE Mingxing2, LI Xiao1, ZENG Shengke2

(1.SchoolofScience,XihuaUniversity,ChengduSichuan610039,China;2.SchoolofComputerandSoftwareEngineering,XihuaUniversity,ChengduSichuan610039,China)

Focusing on the privacy security problem of Private Information Retrieval (PIR), a private information retrieval protocol based on point Function Secret Sharing (FSS) was proposed.The index of the retrieval was regarded as a special 0- 1 point function, and the key group of the point function was generated by using the point function secret sharing technique, which was sent topservers respectively.The retrieval results were obtained by XOR operation according to the responses returned by thepservers.The correctness, security and efficiency of the protocol were analyzed, which proves that the proposed protocol is secure and efficient.A concrete example was given to illustrate the validity of the protocol.Finally, the applications of the protocol to multi-term private information retrieval and keyword-based private information retrieval were introduced.

point function; Function Secret Sharing (FSS); Private Information Retrieval (PIR); privacy security; XOR operation

2016- 08- 10;

2016- 09- 09。 基金项目:国家自然科学基金资助项目(U1433130)；教育部春晖计划项目(Z2014045)。

袁大曾(1992—)，女，四川达州人，硕士研究生，CCF会员，主要研究方向：安全协议、网络安全、大数据； 何明星(1964—)，男，四川南江人，教授，博士，CCF会员，主要研究方向：现代密码算法、安全协议、密钥管理、电子商务/电子政务安全； 李虓(1972—)，男，四川达州人，副教授，博士，CCF会员，主要研究方向：信息安全、密码学； 曾晟珂(1982—)，女，重庆人，副教授，博士，CCF会员，主要研究方向：信息安全、密码学。

1001- 9081(2017)02- 0494- 05

10.11772/j.issn.1001- 9081.2017.02.0494

TP

A