2. 西华大学 计算机与软件工程学院, 成都 610039
2. School of Computer and Software Engineering, Xihua University, Chengdu Sichuan 610039, China
私有信息检索(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}λ。
4) 随机选择2p-1个向量cw1,cw2,…,cw2p-1∈{0,1}mu,满足:
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。
3) 计算:
4) 计算:yj=dj[δ′]。
算法3 函数值重建算法Dec(y1,y2,…,yp)→y。
计算:
本章首先介绍了私有信息检索(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条记录,一般
在协议中,由于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}λ。
4) 选择2p-1个随机字符串cw1,cw2,…,cw2p-1∈{0,1}u,满足公式:
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。
3) 计算:
4) 计算:
5) 得到响应yj。
步骤4 将每个服务器Sj(1≤j≤p利用步骤3计算所得的响应yj发送给用户。
步骤5 当用户收到p个响应y1,y2,…,yp后,通过算法Dec计算得到检索值
定理1 按照上述PIR协议,如果用户可以恢复出xi,则协议是正确的。
证明 在协议过程中,对于t(1≤t≤N),可以将t表示为一对t=(γt,δt)。如果γt≠γ,则Aγt∈Ep,在
定理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。所以协议的通信量为:
由于在将点函数秘密共享应用到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,具体如下:
${{\mathit{\boldsymbol{A}}}_{1}}=\left[ \begin{matrix} 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{matrix} \right]\mathit{\boldsymbol{,}}{{\mathit{\boldsymbol{A}}}_{2}}=\left[ \begin{matrix} 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ \end{matrix} \right]$ |
3) 随机选取v·2p-1=2×4个字符串:s11,s12,s13,s14,s21,s22,s23,s24∈{0,1}λ。
4) 在满足:
5) 令:
$\left\{ \begin{align} & {{\sigma }_{1}}=0\ \left\| {{s}_{12}} \right\|{{s}_{13}}\left\| {{s}_{14}} \right\|{{s}_{21}}\left\| \,0\ \right\|{{s}_{23}}\left\| {{s}_{24}} \right. \\ & {{\sigma }_{2}}=0\ \left\| {{s}_{12}} \right\|{{s}_{13}}\left\| \ 0\ \right\|\ 0\ \left\| \ 0\ \right\|\,\,{{s}_{23}}\left\| \ 0 \right. \\ & {{\sigma }_{3}}=0\ \left\| \ 0\ \right\|\ 0\ \left\| \ {{s}_{14}} \right\|\ 0\ \left\| {{s}_{22}} \right\|\,{{s}_{23}}\,\left\| \ 0\, \right. \\ \end{align} \right.$ |
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) ,可以计算得到:
$\begin{align} & {{\mathit{\boldsymbol{d}}}_{1t}}=\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{2}}\oplus G\left( {{s}_{1,2}} \right) \right)\oplus \left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{3}}\oplus G\left( {{s}_{1,3}} \right) \right)\oplus \\ & \left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{4}}\oplus G\left( {{s}_{1,4}} \right) \right) \\ & {{\mathit{\boldsymbol{d}}}_{1\left( t+8 \right)}}=\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{1}}\oplus G\left( {{s}_{2,1}} \right) \right)\oplus \left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{3}}\oplus G\left( {{s}_{2,3}} \right) \right)\oplus \\ & \left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{4}}\oplus G\left( {{s}_{2,4}} \right) \right) \\ & {{\mathit{\boldsymbol{d}}}_{2t}}=\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{2}}\oplus G\left( {{s}_{1,2}} \right) \right)\oplus \left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{3}}\oplus G\left( {{s}_{1,3}} \right) \right) \\ & {{\mathit{\boldsymbol{d}}}_{2\left( t+8 \right)}}=\mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{3}}\oplus G\left( {{s}_{2,3}} \right) \\ & {{\mathit{\boldsymbol{d}}}_{3t}}=\mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{4}}\oplus G\left( {{s}_{1,4}} \right) \\ & {{\mathit{\boldsymbol{d}}}_{3\left( t+8 \right)}}=\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{2}}\oplus G\left( {{s}_{2,2}} \right) \right)\oplus \left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{3}}\oplus G\left( {{s}_{2,3}} \right) \right) \\ \end{align}$ |
其中:系数1≤t≤8。
3) 计算
步骤3 用户根据3个服务器返回的响应y1、y2、y3通过算法Dec计算y。
因为:
$\left\{ \begin{matrix} \underset{j=1}{\overset{3}{\mathop{\oplus }}}\,{{\mathit{\boldsymbol{d}}}_{jt}}=\underset{j=1}{\overset{{{2}^{p-1}}}{\mathop{\oplus }}}\,\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{j}}\oplus G\left( {{s}_{2,j}} \right) \right)={{0}^{u}}\quad \\ \underset{j=1}{\overset{3}{\mathop{\oplus }}}\,{{\mathit{\boldsymbol{d}}}_{j\left( t+8 \right)}}=\underset{j=1}{\overset{{{2}^{p-1}}}{\mathop{\oplus }}}\,\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{j}}\oplus G\left( {{s}_{2,j}} \right) \right)={{\mathit{\boldsymbol{e}}}_{4}} \\ \end{matrix} \right.;\left( 1\le t\le 8 \right)$ |
所以:
本文提出的基于点函数秘密共享的PIR协议可以推广应用到多项私有信息检索协议[12]和基于关键字的私有信息检索协议[19]中。其中基于关键字的私有信息检索协议类似上述基于点函数秘密共享的PIR协议,只是将检索的索引变成关键字w,即将共享的0- 1点函数变成fw,1。将点函数秘密共享应用到多项私有信息检索协议中的具体协议描述如下:
输入 索引i1,i2,…,il(l≥2;1≤i1<…<il≤N);
输出 xi1,xi2,…,xil。
步骤1 用户通过算法Gen(1λ,fi1,1,fi2,1,…,fil,1)得到密钥组(k1,k2,…,kp),如下。
1) 令iβ=(γβ,δβ),γβ∈[v],δβ∈[u](1≤β≤l)。
2) 选取l组v个p×2p-1维矩阵集A1,A2,…,Al,满足:Aγββ∈Op和Aγ′β∈Ep(γ′≠γβ,1≤β≤l)。
3) 随机选择l·v·2p-1个字符串:s1,1β,s1,2β,…,s1,2p-1β,…,sv,1β,sv,2β,…,sv,2p-1β∈{0,1}λ(1≤β≤l)。
4) 选择2p-1+(l-1) 个随机向量cw1,cw2,…,cw2p-1,…,cw2p-1+(l-1) ∈{0,1}u,满足:
5) 令:σjγ′=(sγ′,11·Aγ′1[j,1])‖(sγ′,21·Aγ′1[j,2])‖…‖(sγ′,2p-11·Aγ′1[j,2p-1])‖…‖(sγ′,1l·Aγ′l[j,1])‖(sγ′,2l·Aγ′l[j,2])‖…‖(sγ′,2p-1l·Aγ′l[j,2p-1]) (1≤γ′≤v
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)。
2) 解析:kj=(σj,cw1,cw2,…,cw2p-1+(l-1) )和σj=s1,11‖s1,21‖…‖sv,2p-11‖s1,12‖…‖sv,2p-12‖…‖s1,1l‖…‖sv,2p-1l。
3) 计算:
$\mathit{\boldsymbol{d}}_{jt}^{\beta }=\underset{1\le j\le {{2}^{p-1}},s_{{{\gamma }_{t}}}^{\beta },j\ne 0}{\mathop{\oplus }}\,\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{j+\left( \beta -1 \right)}}\oplus G\left( s_{{{\gamma }_{t}},j}^{\beta } \right) \right)$ |
其中:1≤β≤l,1≤t≤N。
4) 计算:
5) 得到响应向量zj=(zj1,zj2,…,zjl)。
步骤4 每个服务器将所得的响应zj分别发送给用户。
步骤5 用户收到p个响应向量zj(1≤j≤p,然后计算检索的l个数据
综上所述,点函数秘密共享可以在多项私有信息检索协议[12]和基于关键字的私有信息检索协议[19]中有很好的应用。
5 结语本文针对私有信息检索(PIR)中的隐私安全问题,首次利用点函数秘密共享技术解决该问题,提出了一个基于点函数秘密共享的私有信息检索协议,在协议中将点函数定义为一个特殊的0- 1点函数以提高效率,然后通过效率分析验证该协议是高效的,并给出了一个具体实例验证该协议的有效性。最后简单介绍了将该协议推广到多项私有信息检索和基于关键字的私有信息检索中的运用情况。在以后的研究中,将提出更高效、安全的点函数秘密共享方案来解决PIR中的隐私安全问题以及扩展点函数秘密共享方案的新应用。
[1] | CHOR B, KUSHILEVITZ E, GOLDREICH O, et al. Private information retrieval[J]. Journal of the ACM, 1998, 45 (6) : 965-981. doi: 10.1145/293347.293350 |
[2] | YAO A C. Protocols for secure computations[C]//SFCS'08:Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. Washington, DC:IEEE Computer Society, 1982:160-164. |
[3] | BAR-YOSSEF Z, GUREVICH M. Efficient search engine measurements[C]//Proceedings of the 16th International Conference on World Wide Web. New York:ACM, 2007:401-410. |
[4] | OSTROVSKY R, SKEITH Ⅲ W E. A survey of single-database private information retrieval:Techniques and applications[C]//PKC 2007:Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography, LNCS 4450. Berlin:Springer-Verlag, 2007:393-411. |
[5] | BEIMEL A. Private information retrieval:a primer[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] | AMBAINIS A. Upper bound on the communication complexity of private information retrieval[C]//ICALP'97:Proceedings of the 24th International Colloquium on Automata, Languages and Programming, LNCS 1256. Berlin:Springer-Verlag, 1997:401-407. |
[7] | BEIMEL A, ISHAI Y. Information-theoretic private information retrieval:a unified construction[C]//ICALP 2001:Proceedings of the 28th International Colloquium on Automata, Languages and Programming, LNCS 2076. Berlin:Springer-Verlag, 2001:912-926. |
[8] | ITOH T. Efficient Private information retrieval (special section on cryptography and information security[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 1999, E82-A (1) : 11-20. |
[9] | ISHAI Y, KUSHILEVITZ E. Improved upper bounds on information-theoretic private information retrieval[C]//STOC'99:Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing. New York:ACM, 1999:79-88. |
[10] | BEIMEL A, ISHAI Y, KUSHILEVITZ E, et al. Breaking the O(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. doi: 10.1016/j.jcss.2005.03.002 |
[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. ) |