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

(1.西華大學(xué) 理學(xué)院，成都 610039； 2.西華大學(xué) 計(jì)算機(jī)與軟件工程學(xué)院，成都 610039)

(*通信作者電子郵箱yuan_dz34@163.com)

基于點(diǎn)函數(shù)秘密共享的私有信息檢索協(xié)議

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

(1.西華大學(xué) 理學(xué)院，成都 610039； 2.西華大學(xué) 計(jì)算機(jī)與軟件工程學(xué)院，成都 610039)

(*通信作者電子郵箱yuan_dz34@163.com)

針對(duì)私有信息檢索(PIR)中的隱私安全問(wèn)題，提出了一個(gè)基于點(diǎn)函數(shù)秘密共享的私有信息檢索協(xié)議。該協(xié)議將檢索的索引看成一個(gè)特殊的0- 1點(diǎn)函數(shù)，利用點(diǎn)函數(shù)秘密共享技術(shù)生成這個(gè)點(diǎn)函數(shù)的密鑰組，分別發(fā)送給p個(gè)服務(wù)器，根據(jù)p個(gè)服務(wù)器返回的響應(yīng)作異或運(yùn)算得到檢索結(jié)果。對(duì)協(xié)議進(jìn)行了正確性、安全性和效率分析,驗(yàn)證了這個(gè)協(xié)議是安全且高效的，并給出了一個(gè)具體實(shí)例來(lái)說(shuō)明該協(xié)議的有效性。最后介紹了將該協(xié)議推廣到多項(xiàng)私有信息檢索和基于關(guān)鍵字的私有信息檢索中的應(yīng)用情況。

點(diǎn)函數(shù);函數(shù)秘密共享;私有信息檢索;隱私安全;異或運(yùn)算

0 引言

私有信息檢索(Private Information Retrieval, PIR)[1]是指參與查詢的用戶與數(shù)據(jù)庫(kù)所有者在不泄露各自私有信息的情況下，完成對(duì)數(shù)據(jù)庫(kù)的查詢操作。PIR問(wèn)題作為安全多方計(jì)算[2]的一個(gè)重要的研究方向,在實(shí)際生活中，例如：多個(gè)公司之間的合作查詢、醫(yī)藥數(shù)據(jù)庫(kù)、專(zhuān)利數(shù)據(jù)庫(kù)及實(shí)時(shí)股票報(bào)價(jià)等對(duì)檢索隱私有較高要求的領(lǐng)域，有著很大的應(yīng)用空間[3-5]。

解決PIR問(wèn)題的一種最簡(jiǎn)單方法是數(shù)據(jù)庫(kù)所有者將整個(gè)數(shù)據(jù)庫(kù)中的文件全部發(fā)送給用戶，然后由用戶自己去完成檢索過(guò)程。這樣雖然可以保障用戶的隱私，但其通信開(kāi)銷(xiāo)太大，無(wú)法應(yīng)用到實(shí)際情況中；同時(shí)數(shù)據(jù)庫(kù)所有者也并不希望用戶得到數(shù)據(jù)庫(kù)中的所有文件；而且如果有一些數(shù)據(jù)沒(méi)有參與到用戶查詢中，數(shù)據(jù)庫(kù)所有者就可以推斷出用戶對(duì)這些數(shù)據(jù)不感興趣，從而泄露用戶的隱私。

1995年，Chor等[1]首次對(duì)PIR問(wèn)題進(jìn)行了形式化的定義，并提出了一個(gè)有效的解決方案，即通過(guò)多個(gè)互不通信的擁有相同數(shù)據(jù)庫(kù)副本的服務(wù)器共同協(xié)作完成查詢，而任何一個(gè)數(shù)據(jù)庫(kù)服務(wù)器的子集合作都不能獲得用戶的任何檢索信息。將這種通過(guò)多個(gè)數(shù)據(jù)庫(kù)副本實(shí)現(xiàn)的PIR的研究方法稱為信息論私有信息檢索(Information-theoretic Private Information Retrieval, IPIR)。隨后，文獻(xiàn)[6-10]相繼又提出了一些PIR協(xié)議。2002年,Yang等[11]將秘密共享技術(shù)應(yīng)用到私有信息檢索中，解決了數(shù)據(jù)庫(kù)所有者的惡意攻擊問(wèn)題。2008年，廖干才等[12]運(yùn)用秘密共享技術(shù)，構(gòu)造了單項(xiàng)和多項(xiàng)的PIR協(xié)議。PIR協(xié)議中，由于可能存在若干數(shù)據(jù)庫(kù)服務(wù)器互相串通，或發(fā)生崩潰無(wú)法返回正確查詢結(jié)果的情況，對(duì)此，文獻(xiàn)[11-14]等將秘密共享方法應(yīng)用到PIR問(wèn)題中，提出了能夠抵擋若干惡意服務(wù)器共謀、崩潰或返回錯(cuò)誤結(jié)果的魯棒性的PIR方法。

函數(shù)秘密共享(Function Secret Sharing, FSS)的概念最早是由De Santis等[15]于1994年出于分發(fā)一方的加密功能的目的而提出的，但由于其應(yīng)用的局限性，很少有關(guān)于它的研究。直到2015年，為了有效地實(shí)現(xiàn)安全搜索和更新分布式數(shù)據(jù)的目的，Boyle等[16]根據(jù)分布式點(diǎn)函數(shù)(Distributed Point Function, DPF)[17]對(duì)FSS進(jìn)行了介紹和研究，討論了DPF的兩個(gè)典型應(yīng)用場(chǎng)景：多服務(wù)器私有信息搜索的安全關(guān)鍵字檢索和增量式秘密共享，并基于異或運(yùn)算提出了一個(gè)點(diǎn)函數(shù)秘密共享(Point Function Secret Sharing, PFSS)方案；Komargodski等[18]也提到了函數(shù)秘密共享的概念。受此啟發(fā)，本文考慮將點(diǎn)函數(shù)秘密共享應(yīng)用到PIR問(wèn)題中。

本文針對(duì)PIR的隱私安全問(wèn)題，運(yùn)用點(diǎn)函數(shù)秘密共享方案構(gòu)造了一個(gè)新的私有信息檢索協(xié)議。在協(xié)議中，將檢索的索引看成一個(gè)點(diǎn)函數(shù)，利用點(diǎn)函數(shù)秘密共享技術(shù)生成這個(gè)點(diǎn)函數(shù)的密鑰組，分別發(fā)送給p個(gè)服務(wù)器，最后根據(jù)p個(gè)服務(wù)器返回的p個(gè)響應(yīng)作異或運(yùn)算得到檢索結(jié)果。但通過(guò)分析發(fā)現(xiàn)，對(duì)點(diǎn)函數(shù)fa,b:{0,1}n→{0,1}m,在m>1時(shí)，點(diǎn)函數(shù)秘密共享方案不能很好地構(gòu)造一個(gè)私有信息檢索協(xié)議，反而在m=1(即0- 1點(diǎn)函數(shù)秘密共享方案)時(shí)，能有效地構(gòu)造一個(gè)新的私有信息檢索協(xié)議，并且可以提高協(xié)議的通信和計(jì)算效率。為此，本文在用點(diǎn)函數(shù)秘密共享方案構(gòu)造新的私有信息檢索協(xié)議時(shí)，所用的點(diǎn)函數(shù)是一個(gè)特殊的0- 1點(diǎn)函數(shù)。本文主要工作如下：

1)基于點(diǎn)函數(shù)秘密共享提出一個(gè)新的私有信息檢索協(xié)議，并對(duì)協(xié)議進(jìn)行了正確性、安全性和效率的分析。

2)給出了協(xié)議的一個(gè)具體實(shí)例，便于對(duì)協(xié)議的理解。

3)將該協(xié)議推廣到多項(xiàng)私有信息檢索[12]和基于關(guān)鍵字的私有信息檢索[19]中，并簡(jiǎn)單描述了多項(xiàng)私有信息檢索協(xié)議的過(guò)程。

1 相關(guān)知識(shí)

1.1 點(diǎn)函數(shù)

定義1 點(diǎn)函數(shù)。對(duì)于a∈{0,1}n,b∈{0,1}m，點(diǎn)函數(shù)fa,b:{0,1}n→{0,1}m，滿足：fa,b(a)=b和fa,b(a′)=0m(a′≠a)。

定義2 0- 1點(diǎn)函數(shù)。對(duì)于a∈{0,1}n，0- 1點(diǎn)函數(shù)fa,1:{0,1}n→{0,1}，滿足：fa,1(a)=1和fa,1(a′)=0(a′≠a)。0- 1點(diǎn)函數(shù)是一種特殊的點(diǎn)函數(shù)。

1.2 函數(shù)秘密共享

定義3 函數(shù)秘密共享(FSS)[16]。令p∈N,T?[p]([p]表示{1,2,…,p}的所有子集)，函數(shù)群F的一個(gè)T-安全的函數(shù)秘密共享(FSS)方案有三個(gè)算法(Gen,Eval,Dec)，且滿足：

Gen(1λ,f)→(k1,k2,…,kp)：輸入安全參數(shù)1λ和共享的函數(shù)f∈F，通過(guò)密鑰生成算法輸出密鑰(k1,k2,…,kp)。

Eval(i,ki,x)→yi：輸入i∈[p]，x∈Df(其中Df為函數(shù)f的定義域)，通過(guò)響應(yīng)求值算法輸出第i個(gè)共享者的響應(yīng)。

Dec({yi}i∈T)→y：輸入合法的共享者集合T的響應(yīng){yi}i∈T，通過(guò)重建算法輸出對(duì)應(yīng)的值y。

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

1)正確性。對(duì)所有f∈F,x∈Df，滿足：y=f(x)。

2)安全性。考慮一個(gè)損壞的參與方集T?[p]的不可分辨性挑戰(zhàn)實(shí)驗(yàn)，即敵手首先選取f0,f1∈F,Df0=Df1；然后挑戰(zhàn)者選取樣本{0,1}→b,Gen(1λ,fb)→(k1,k2,…,kp)；對(duì)損壞參與者集T的密鑰，敵手輸出一個(gè)猜測(cè)A((ki)i∈T)→b′。在上述實(shí)驗(yàn)中，敵手猜測(cè)b的優(yōu)勢(shì)為Adv(1λ,A):=Pr[b=b′]-2-1。如果對(duì)于所有非均勻PPT的敵手A，都存在一個(gè)不可忽略的函數(shù)v,有Adv(1λ,A)≤v(λ)，則認(rèn)為方案(Gen,Eval,Dec)是T-安全。

1.3 點(diǎn)函數(shù)秘密共享方案

假設(shè)p表示共享者個(gè)數(shù)，fa,b:{0,1}n→{0,1}m表示共享的秘密點(diǎn)函數(shù)。令u=[2n/2·2(p-1)/2]和v=[2n/u]；G表示一個(gè)偽隨機(jī)生成器G：{0,1}λ→{0,1}mu；Op(Ep)表示每列1 bit的個(gè)數(shù)為奇數(shù)(偶數(shù))的p×2p-1維比特矩陣集；eδ表示一個(gè)長(zhǎng)度為2|δ|在位置δ為1和在其他位置都為0的向量。

具體的PFSS方案包括如下三個(gè)算法：

算法1 密鑰分發(fā)算法Gen(1λ,fa,b)→(k1,k2,…,kp)。

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

2)選取v個(gè)矩陣Aγ′(1≤γ′≤v)，滿足：Aγ∈Op和Aγ′∈Ep(γ′≠γ)。

3)隨機(jī)選擇v·2p-1個(gè)字符串: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發(fā)送給第j個(gè)共享者。

算法2 份額構(gòu)建算法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)計(jì)算：yj=dj[δ′]。

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

2 基于PFSS的PIR協(xié)議

本章首先介紹了私有信息檢索(PIR)的問(wèn)題，然后針對(duì)PIR的隱私安全問(wèn)題，結(jié)合點(diǎn)函數(shù)秘密共享技術(shù)，提出了一個(gè)基于點(diǎn)函數(shù)秘密共享的PIR協(xié)議，并分析了協(xié)議的正確性、安全性和效率。

2.1 PIR問(wèn)題描述

一般的PIR問(wèn)題的具體描述為：假設(shè)Alice是查詢者,Bob是數(shù)據(jù)庫(kù)擁有者,Bob存儲(chǔ)的數(shù)據(jù)用N個(gè)字符串X={x1,x2,…,xN}來(lái)表示,當(dāng)查詢者Alice想從Bob那里查詢索引為i∈{1,2,…,N}的數(shù)據(jù)xi,但又不希望Bob知道“i”的信息，而B(niǎo)ob也不想Alice知道除xi以外的數(shù)據(jù)庫(kù)信息，這樣的問(wèn)題就是PIR問(wèn)題。

2.2 基于點(diǎn)函數(shù)秘密共享的PIR協(xié)議

基于點(diǎn)函數(shù)秘密共享的PIR協(xié)議的描述如下：假設(shè)有p個(gè)服務(wù)器S1,S2,…,Sp,每個(gè)服務(wù)器都有一樣的N條數(shù)據(jù)記錄數(shù)據(jù)庫(kù)X={x1,x2,…,xN}(其中：xi∈{0,1}h表示第i條記錄，一般p?N)。用戶想在沒(méi)有泄露查詢索引i給服務(wù)器的任何嚴(yán)格子集情況下從X中查詢第i條記錄xi，就構(gòu)造一個(gè)特殊的0- 1點(diǎn)函數(shù)fi,1:{0,1}n→{0,1}(其中:n=「lb |N|?,符號(hào)「?表示N≤「N?

在協(xié)議中，由于0- 1點(diǎn)函數(shù)相當(dāng)于一般點(diǎn)函數(shù)中m=1時(shí)，因此，重新定義偽隨機(jī)生成器G為G：{0,1}λ→{0,1}u，而其他符號(hào)定義同上。協(xié)議的檢索階段執(zhí)行步驟如下所示：

輸入 索引i;

輸出xi。

步驟1 用戶通過(guò)算法Gen(1λ,fi,1)得到密鑰組(k1,k2,…,kp)。

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

2)選取v個(gè)p×2p-1維矩陣集Aγ′(1≤γ′≤v)，滿足：Aγ∈Op和Aγ′∈Ep(γ′≠γ)。

3)隨機(jī)選擇v·2p-1個(gè)字符串：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分別發(fā)送給服務(wù)器Sj(1≤j≤p)。

步驟3 服務(wù)器Sj通過(guò)算法Eval(j,kj,X)得到響應(yīng)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)得到響應(yīng)yj。

步驟4 將每個(gè)服務(wù)器Sj(1≤j≤p)利用步驟3計(jì)算所得的響應(yīng)yj發(fā)送給用戶。

2.3 協(xié)議的分析

2.3.1 正確性分析

定理1 按照上述PIR協(xié)議，如果用戶可以恢復(fù)出xi，則協(xié)議是正確的。

2.3.2 安全性分析

定理2 按照協(xié)議，一方面用戶能恢復(fù)出xi,且得不到其他數(shù)據(jù)信息，另一方面，數(shù)據(jù)庫(kù)服務(wù)器的任何嚴(yán)格子集不能夠得到檢索i的任何信息。

證明 因?yàn)閤t(t=1,2,…,i-1,i+1,…,N)都在檢索中相互抵消了，從而保證了用戶得不到xi外的其他數(shù)據(jù)信息，即協(xié)議能夠保證查詢者無(wú)法通過(guò)多次查詢獲取更多的信息；又因?yàn)樯厦纥c(diǎn)函數(shù)秘密共享技術(shù)的安全保證，因此數(shù)據(jù)庫(kù)服務(wù)器的任何嚴(yán)格子集不能夠得到0- 1點(diǎn)函數(shù)fi,1的任何信息，即得不到檢索i的任何信息。因此,該協(xié)議是安全的。

2.3.3 效率分析

對(duì)于協(xié)議的通信復(fù)雜度分析，因?yàn)樵谏鲜鯬IR協(xié)議中算法Gen輸出密鑰kj長(zhǎng)度包括σj的比特長(zhǎng)度v·λ·2p-1和向量集cw1,cw2,…,cw2p-1的比特長(zhǎng)度u·2p-1。所以協(xié)議的通信量為：O((λ+1)·2「lb |N|?/2·2(p-1)/2)。對(duì)于協(xié)議的計(jì)算復(fù)雜度分析，因?yàn)閰f(xié)議主要運(yùn)用到異或運(yùn)算，因此計(jì)算效率是較高的。

由于在將點(diǎn)函數(shù)秘密共享應(yīng)用到PIR問(wèn)題中時(shí)，本文用一個(gè)特殊的0- 1點(diǎn)函數(shù)代替一般點(diǎn)函數(shù)，而這樣不僅可以提高通信效率，還可以提高計(jì)算效率。因此，本文所提協(xié)議的效率是較高的。

3 協(xié)議的數(shù)據(jù)實(shí)例

為方便對(duì)于上述基于點(diǎn)函數(shù)秘密共享的PIR協(xié)議的理解，下面給出協(xié)議的一個(gè)小數(shù)據(jù)實(shí)例。

令λ=4,p=3,N=16,X={x1,x2,…,x16}，其中：xi∈{0,1}h表示第i條記錄。從而u=8,v=2，偽隨機(jī)發(fā)生器G：{0,1}4→{0,1}8。協(xié)議的具體執(zhí)行步驟如下所示：

輸入 索引i=11；

輸出xi。

步驟1 通過(guò)算法Gen(14,fi,1)得到密鑰組(k1,k2,k3)。

1)將i=11分解成γ=2,δ=4，其中“1010”、“1”和“010”分別表示i-1、γ-1和δ-1的二進(jìn)制式。

2)生成v=2個(gè)p×2p-1=3×4維矩陣A1∈O3,A2∈E3，具體如下：

3)隨機(jī)選取v·2p-1=2×4個(gè)字符串：s11,s12,s13,s14,s21,s22,s23,s24∈{0,1}λ。

5)令:

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

步驟2 3個(gè)服務(wù)器分別根據(jù)X通過(guò)算法Eval計(jì)算如下:

1)解析16個(gè)索引值為：(γ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)根據(jù)kj(j=1,2,3)，可以計(jì)算得到：

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))

其中：系數(shù)1≤t≤8。

步驟3 用戶根據(jù)3個(gè)服務(wù)器返回的響應(yīng)y1、y2、y3通過(guò)算法Dec計(jì)算y。

因?yàn)?

4 協(xié)議的推廣

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

輸出xi1,xi2,…,xil。

步驟1 用戶通過(guò)算法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分別發(fā)送給Sj(1≤j≤p)。

步驟3 服務(wù)器Sj通過(guò)算法Eval(j,kj,X)得到一個(gè)l維響應(yīng)向量zj=(zj1,zj2,…,zjl)(1≤j≤p)。

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

3)計(jì)算：

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

5)得到響應(yīng)向量zj=(zj1,zj2,…,zjl)。

步驟4 每個(gè)服務(wù)器將所得的響應(yīng)zj分別發(fā)送給用戶。

綜上所述，點(diǎn)函數(shù)秘密共享可以在多項(xiàng)私有信息檢索協(xié)議[12]和基于關(guān)鍵字的私有信息檢索協(xié)議[19]中有很好的應(yīng)用。

5 結(jié)語(yǔ)

本文針對(duì)私有信息檢索(PIR)中的隱私安全問(wèn)題，首次利用點(diǎn)函數(shù)秘密共享技術(shù)解決該問(wèn)題，提出了一個(gè)基于點(diǎn)函數(shù)秘密共享的私有信息檢索協(xié)議，在協(xié)議中將點(diǎn)函數(shù)定義為一個(gè)特殊的0- 1點(diǎn)函數(shù)以提高效率，然后通過(guò)效率分析驗(yàn)證該協(xié)議是高效的，并給出了一個(gè)具體實(shí)例驗(yàn)證該協(xié)議的有效性。最后簡(jiǎn)單介紹了將該協(xié)議推廣到多項(xiàng)私有信息檢索和基于關(guān)鍵字的私有信息檢索中的運(yùn)用情況。在以后的研究中，將提出更高效、安全的點(diǎn)函數(shù)秘密共享方案來(lái)解決PIR中的隱私安全問(wèn)題以及擴(kuò)展點(diǎn)函數(shù)秘密共享方案的新應(yīng)用。

)

[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] 廖干才，羅守山.一種基于秘密共享的對(duì)稱私有信息檢索協(xié)議[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] 俞志斌,周彥暉.基于關(guān)鍵字的云加密數(shù)據(jù)隱私保護(hù)檢索[J].計(jì)算機(jī)科學(xué),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。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(U1433130)；教育部春暉計(jì)劃項(xiàng)目(Z2014045)。

袁大曾(1992—)，女，四川達(dá)州人，碩士研究生，CCF會(huì)員，主要研究方向：安全協(xié)議、網(wǎng)絡(luò)安全、大數(shù)據(jù)； 何明星(1964—)，男，四川南江人，教授，博士，CCF會(huì)員，主要研究方向：現(xiàn)代密碼算法、安全協(xié)議、密鑰管理、電子商務(wù)/電子政務(wù)安全； 李虓(1972—)，男，四川達(dá)州人，副教授，博士，CCF會(huì)員，主要研究方向：信息安全、密碼學(xué)； 曾晟珂(1982—)，女，重慶人，副教授，博士，CCF會(huì)員，主要研究方向：信息安全、密碼學(xué)。

1001- 9081(2017)02- 0494- 05

10.11772/j.issn.1001- 9081.2017.02.0494

TP

A