计算机应用   2017, Vol. 7 Issue (2): 494-498  DOI: 10.11772/j.issn.1001-9081.2017.02.0494
0

引用本文 

袁大曾, 何明星, 李虓, 曾晟珂. 基于点函数秘密共享的私有信息检索协议[J]. 计算机应用, 2017, 7(2): 494-498.DOI: 10.11772/j.issn.1001-9081.2017.02.0494.
YUAN Dazeng, HE Mingxing, LI Xiao, ZENG Shengke. Private information retrieval protocol based on point function secret sharing[J]. JOURNAL OF COMPUTER APPLICATIONS, 2017, 7(2): 494-498. DOI: 10.11772/j.issn.1001-9081.2017.02.0494.

基金项目

国家自然科学基金资助项目(U1433130);教育部春晖计划项目(Z2014045)

通信作者

袁大曾(1992-),女,四川达州人,硕士研究生,CCF会员,主要研究方向:安全协议、网络安全、大数据,yuan_dz34@163.com

作者简介

何明星(1964-),男,四川南江人,教授,博士,CCF会员,主要研究方向:现代密码算法、安全协议、密钥管理、电子商务/电子政务安全;
李虓(1972-),男,四川达州人,副教授,博士,CCF会员,主要研究方向:信息安全、密码学;
曾晟珂(1982-),女,重庆人,副教授,博士,CCF会员,主要研究方向:信息安全、密码学

文章历史

收稿日期:2016-08-10
修回日期:2016-09-09
基于点函数秘密共享的私有信息检索协议
袁大曾1,2, 何明星2, 李虓1, 曾晟珂2    
1. 西华大学 理学院, 成都 610039;
2. 西华大学 计算机与软件工程学院, 成都 610039
摘要: 针对私有信息检索(PIR)中的隐私安全问题,提出了一个基于点函数秘密共享的私有信息检索协议。该协议将检索的索引看成一个特殊的0-1点函数,利用点函数秘密共享技术生成这个点函数的密钥组,分别发送给p个服务器,根据p个服务器返回的响应作异或运算得到检索结果。对协议进行了正确性、安全性和效率分析,验证了这个协议是安全且高效的,并给出了一个具体实例来说明该协议的有效性。最后介绍了将该协议推广到多项私有信息检索和基于关键字的私有信息检索中的应用情况。
关键词: 点函数    函数秘密共享    私有信息检索    隐私安全    异或运算    
Private information retrieval protocol based on point function secret sharing
YUAN Dazeng1,2, HE Mingxing2, LI Xiao1, ZENG Shengke2     
1. School of Science, Xihua University, Chengdu Sichuan 610039, China;
2. School of Computer and Software Engineering, Xihua University, Chengdu Sichuan 610039, China
Abstract: 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 to p servers respectively. The retrieval results were obtained by XOR operation according to the responses returned by the p servers. 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.
Key words: point function    Function Secret Sharing (FSS)    Private Information Retrieval (PIR)    privacy security    XOR operation    
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)=bfa,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]。令pN,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],xDf(其中Df为函数f的定义域),通过响应求值算法输出第i个共享者的响应。

Dec({yi}iT)→y:输入合法的共享者集合T的响应{yi}iT,通过重建算法输出对应的值y

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

1) 正确性。对所有fF,xDf,满足:y=f(x)。

2) 安全性。考虑一个损坏的参与方集T⊂[p]的不可分辨性挑战实验,即敌手首先选取f0,f1F,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}muOp(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γOpAγ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,满足:$\underset{i=1}{\overset{{{2}^{p-1}}}{\mathop{\oplus }}}\,\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{i}}\oplus G\left( {{s}_{\gamma ,i}} \right) \right)={{\mathit{\boldsymbol{e}}}_{\delta }}\cdot b$

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≤jp)。

6) 令kj=(σjcw1cw2‖…‖cw2p-1)(1≤jp)。

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

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

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

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

3) 计算:${{\mathit{\boldsymbol{d}}}_{j}}=\underset{1\le i\le {{2}^{p-1}},{{s}_{\gamma ',j}}\ne 0}{\mathop{\oplus }}\,\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{i}}\oplus G\left( {{s}_{\gamma ',i}} \right) \right)$

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

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

计算:$y=\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,{{y}_{j}}$y就为所求结果fa,b(x)。

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\ll N$)。用户想在没有泄露查询索引i给服务器的任何严格子集情况下从X中查询第i条记录xi,就构造一个特殊的0- 1点函数fi,1:{0,1}n→{0,1}(其中:$n=\left\lceil \text{lb}\left| N \right| \right\rceil $,符号$\left\lceil {} \right\rceil $表示$N\le \left\lceil N \right\rceil <N+1$,然后通过算法Gen生成密钥kj,再将密钥kj发送给服务器Sj(1≤jp),服务器Sj通过算法Eval生成响应yj并发送给用户,最后用户通过每个服务器的响应利用算法Dec计算得到第i条记录xi

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

输入 索引i;

输出 xi

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

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

2) 选取vp×2p-1维矩阵集Aγ(1≤γ′≤v),满足:AγOpAγ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,满足公式:$\underset{j=1}{\overset{{{2}^{p-1}}}{\mathop{\oplus }}}\,\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{j}}\oplus G\left( {{s}_{\gamma ,i}} \right) \right)={{\mathit{\boldsymbol{e}}}_{\delta }}$

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≤jp)。

6) 令kj=(σjcw1cw2‖…‖cw2p-1)(1≤jp

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

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

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

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

3) 计算:${{\mathit{\boldsymbol{d}}}_{jt}}=\underset{1\le i\le {{2}^{p-1}},{{s}_{{{\gamma }_{t}}}},j\ne 0}{\mathop{\oplus }}\,\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{j}}\oplus G\left( {{s}_{{{\gamma }_{t}},j}} \right) \right),\left( 1\le t\le N \right)\,;$

4) 计算:${{y}_{j}}=\underset{1\le t\le N}{\mathop{\oplus }}\,\left( {{\mathit{\boldsymbol{d}}}_{jt}}\left[ {{\delta }_{t}} \right]\cdot {{x}_{t}} \right)$

5) 得到响应yj

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

步骤5 当用户收到p个响应y1,y2,…,yp后,通过算法Dec计算得到检索值${{x}_{i}}=\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,{{y}_{j}}$,即可得到想要的检索结果xi

2.3 协议的分析 2.3.1 正确性分析

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

证明 在协议过程中,对于t(1≤tN),可以将t表示为一对t=(γt,δt)。如果γtγ,则AγtEp,在$\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,{{\mathit{\boldsymbol{d}}}_{jt}}$中每一项cwjG(sγt,j)出现的次数为偶数,因此相互抵消,即$\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,{{\mathit{\boldsymbol{d}}}_{jt}}={{0}^{u}}$,从而有$\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,\left( {{\mathit{\boldsymbol{d}}}_{jt}}\left[ {{\delta }_{t}} \right]\cdot {{x}_{t}} \right)={{0}^{h}}$,即xt相互抵消。如果γt=γ,则$\underset{j=1}{\overset{p}{\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}_{\gamma ,i}} \right) \right)={{\mathit{\boldsymbol{e}}}_{\delta }}$,如果δtδ(即ti),则$\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,\left( {{\mathit{\boldsymbol{d}}}_{jt}}\left[ \delta ' \right]\cdot {{x}_{t}} \right)={{0}^{h}}$,即xt相互抵消;如果δt=δ(即t=i),则$\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,{{\mathit{\boldsymbol{d}}}_{jt}}\left[ {{\delta }_{t}} \right]=1$,即$\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,\left( {{\mathit{\boldsymbol{d}}}_{jt}}\left[ {{\delta }_{t}} \right]\cdot {{x}_{t}} \right)={{x}_{t}}$。因为i∈{1,2,…,N},所以存在一个t值满足t=i,即$\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,\left( {{\mathit{\boldsymbol{d}}}_{jt}}\left[ {{\delta }_{t}} \right]\cdot {{x}_{t}} \right)={{x}_{t}}$,而对于另外N-1个t(t≠i)值,则有$\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,\left( {{\mathit{\boldsymbol{d}}}_{jt}}\left[ \left[ {{\delta }_{t}} \right] \right]\cdot {{x}_{t}} \right)={{0}^{h}}$,所以$\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,{{y}_{j}}={{x}_{i}}$,即用户能恢复出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\left( \left( \lambda +1 \right)\cdot {{2}^{\left\lceil \text{lb}\left| N \right| \right\rceil /2}}\cdot {{2}^{\left( p-1 \right)/2}} \right)$。对于协议的计算复杂度分析,因为协议主要运用到异或运算,因此计算效率是较高的。

由于在将点函数秘密共享应用到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维矩阵A1O3,A2E3,具体如下:

${{\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) 在满足:$\underset{j=1}{\overset{4}{\mathop{\oplus }}}\,\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{j}}\oplus G\left( {{s}_{2,i}} \right) \right)={{\mathit{\boldsymbol{e}}}_{4}}$的情况下,随机选择2p-1=4个向量:cw1,cw2,cw3,cw4∈{0,1}u

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=(σjcw1cw2cw3cw4)(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) 计算${{y}_{j}}=\underset{t=1}{\overset{16}{\mathop{\oplus }}}\,\left( {{\mathit{\boldsymbol{d}}}_{jt}}\left[ {{\delta }_{t}} \right]\cdot {{x}_{t}} \right)\left( j=1,2,3 \right)$

步骤3 用户根据3个服务器返回的响应y1y2y3通过算法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)$

所以:$y=\underset{j=1}{\overset{3}{\mathop{\oplus }}}\,{{y}_{j}}\underset{t=1}{\overset{16}{\mathop{\oplus }}}\,\left( \underset{j=1}{\overset{3}{\mathop{\oplus }}}\,\left( {{\mathit{\boldsymbol{d}}}_{jt}}\left[ {{\delta }_{t}} \right]\cdot {{x}_{t}} \right) \right)=\underset{t=9}{\overset{16}{\mathop{\oplus }}}\,\left( {{\mathit{\boldsymbol{e}}}_{4}}\left[ {{\delta }_{t}} \right]\cdot {{x}_{t}} \right)$。最后得到${{x}_{11}}=y=\underset{j=1}{\overset{3}{\mathop{\oplus }}}\,{{y}_{j}}$

4 协议的推广

本文提出的基于点函数秘密共享的PIR协议可以推广应用到多项私有信息检索协议[12]和基于关键字的私有信息检索协议[19]中。其中基于关键字的私有信息检索协议类似上述基于点函数秘密共享的PIR协议,只是将检索的索引变成关键字w,即将共享的0- 1点函数变成fw,1。将点函数秘密共享应用到多项私有信息检索协议中的具体协议描述如下:

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

输出 xi1,xi2,…,xil

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

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

2) 选取lvp×2p-1维矩阵集A1,A2,…,Al,满足:AγββOpAγβ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,满足:$\underset{j=1}{\overset{{{2}^{p-1}}}{\mathop{\oplus }}}\,\left( \mathit{\boldsymbol{c}}{{\mathit{\boldsymbol{w}}}_{j+\left( \beta -1 \right)}}\oplus G\left( s_{\gamma ,j}^{\beta } \right) \right)={{\mathit{\boldsymbol{e}}}_{{{\delta }_{\beta }}}}\left( 1\le \beta \le l \right)$

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);再令σj=σj1σj2‖…‖σjv(1≤jp

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

步骤2 用户将所得kj分别发送给Sj(1≤jp

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

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

2) 解析:kj=(σj,cw1,cw2,…,cw2p-1+(l-1) )和σj=s1,11s1,21‖…‖sv,2p-11s1,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≤tN

4) 计算:${{z}_{j\beta }}=\underset{t=1}{\overset{N}{\mathop{\oplus }}}\,\left( \mathit{\boldsymbol{d}}_{jt}^{\beta }\left[ {{\delta }_{t}} \right]\cdot {{x}_{t}} \right)$(1≤β≤l)。

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

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

步骤5 用户收到p个响应向量zj(1≤jp,然后计算检索的l个数据${{x}_{{{i}_{\beta }}}}:{{x}_{{{i}_{\beta }}}}=\underset{j=1}{\overset{p}{\mathop{\oplus }}}\,{{z}_{j\beta }}\left( 1\le \beta \le l \right)$,即得到检索结果:xi1,xi2,…,xil

综上所述,点函数秘密共享可以在多项私有信息检索协议[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. )