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

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

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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

1 相關(guān)知識

1.1 點函數(shù)

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

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

1.2 函數(shù)秘密共享

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

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

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

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

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

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

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

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

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

具體的PFSS方案包括如下三個算法：

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

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

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

3)隨機(jī)選擇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發(fā)送給第j個共享者。

算法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)計算：yj=dj[δ′]。

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

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

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

2.1 PIR問題描述

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

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

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

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

輸入 索引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)隨機(jī)選擇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分別發(fā)送給服務(wù)器Sj(1≤j≤p)。

步驟3 服務(wù)器Sj通過算法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 將每個服務(wù)器Sj(1≤j≤p)利用步驟3計算所得的響應(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ù)庫服務(wù)器的任何嚴(yán)格子集不能夠得到檢索i的任何信息。

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

2.3.3 效率分析

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

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

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

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

令λ=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 通過算法Gen(14,fi,1)得到密鑰組(k1,k2,k3)。

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

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

3)隨機(jī)選取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個服務(wù)器分別根據(jù)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)根據(jù)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))

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

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

因為:

4 協(xié)議的推廣

輸入 索引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分別發(fā)送給Sj(1≤j≤p)。

步驟3 服務(wù)器Sj通過算法Eval(j,kj,X)得到一個l維響應(yīng)向量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)得到響應(yīng)向量zj=(zj1,zj2,…,zjl)。

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

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

5 結(jié)語

本文針對私有信息檢索(PIR)中的隱私安全問題，首次利用點函數(shù)秘密共享技術(shù)解決該問題，提出了一個基于點函數(shù)秘密共享的私有信息檢索協(xié)議，在協(xié)議中將點函數(shù)定義為一個特殊的0- 1點函數(shù)以提高效率，然后通過效率分析驗證該協(xié)議是高效的，并給出了一個具體實例驗證該協(xié)議的有效性。最后簡單介紹了將該協(xié)議推廣到多項私有信息檢索和基于關(guān)鍵字的私有信息檢索中的運用情況。在以后的研究中，將提出更高效、安全的點函數(shù)秘密共享方案來解決PIR中的隱私安全問題以及擴(kuò)展點函數(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] 廖干才，羅守山.一種基于秘密共享的對稱私有信息檢索協(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ī)科學(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。 基金項目:國家自然科學(xué)基金資助項目(U1433130)；教育部春暉計劃項目(Z2014045)。

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

1001- 9081(2017)02- 0494- 05

10.11772/j.issn.1001- 9081.2017.02.0494

TP

A