Σ-private private information retrieval protocols

doi:10.7523/j.issn.2095-6134.2011.3.017

Abstract

Abstract:

We pose the definition of Σ-private private information retrieval (PIR) protocol,and then construct a Σ-private PIR protocol based on verifiable secret sharing(VSS)scheme on general access structure . We also construct an efficient robust Σ-private PIR protocol based on robust multiplication protocol and the database is also secure. The corresponding communication complexity is dependent on the size of the access structure and is efficient for minority of servers.

Key words: private information retrieval protocol, verifiable secret sharing scheme, general access structure

CLC Number:

TP309

ZHANG Zi-Kun, LV Ke-Wei. Σ-private private information retrieval protocols[J]. , 2011, 28(3): 389-397.

References

[1] Chor B, Goldreich O, Kushilevitz E, et al. Private information retrieval
[J]. J of the ACM, 1998, 45:965-981.

[2] Kushileviz E, Ostrovsky R. Replication is not needed: single-database computationally private information retrieval //Proc of the 38^th Annu IEEE Symp FOCS, 1997:364-373.

[3] Cachin C, Micali S, Stadler M. Computationally private information retrieval with polylogarithmic communication //Proc EUROCRYPT’99. 1999, 1592:402–414.

[4] Beaver D, Feigenbaum J. Hiding instances in multioracle queries //Proc of the 7^th Annu Symp on Theoretical Aspects of Computer Science. LNCS 415, Springer-Verlag, 1990:37-48.

[5] Beaver D, Feigenbaum J, Kilian J, et al. Locally Random reductions: improvements and applications
[J]. J of Cryptology, 1997, 10(1):17-36.

[6] Ambainis A. Upper bound on the communication complexity of private information retrieval //Proc of 24^th ICALP. LNCS 1256, Springer-Verlag, 1997: 401-407.

[7] Ishai Y, Kushilevitz E. Improved upper bounds on information-theoretic private information retrieval //Proc of the 31^st ACM Symp on the Theory of Computing. 1999:79-88.

[8] Beimel A, Ishai Y, Kushilevitz E, et al. Breaking the O(n^1/2k-1) barrier for information-theoretic private information retrieval //Proc of 43^rd Annu IEEE Symp. FOCS, 2002:261-270.

[9] Yekhanin S. New locally decodable codes and private information retrieval schemes . Electronic Colloquium on Computational Complexity (ECCC), 2006:127.

[10] Beimel A, Ishai Y. Information-theoretic private information retrieval: a unified construction //Proc of the 28^th International Colloquium on Automata, Languages and Programming. LNCS 2076, Springer-Verlag, 2001:912-926.

[11] Beimel A, Stahl Y. Robust information-theoretic private information retrieval //Third Conference on Security in Communication Networks. LNCS 2576, Springer-Verlag, 2002:326-341.

[12] Goldberg I. Improving the robustness of private information retrieval //Proc of 2007 IEEE Symposium on Security and Privacy. 2007: 131-145.

[13] Maurer U. Secure multi-party computation made simple //Proc of SCN`02. LNCS 2576, Springer-Verlag, 2003:14-28.

[1]	FAN Wei-Jie, WU Wen-Ling, ZHANG Lei. Differential fault analysis on HIGHT [J]. , 2012, (2): 271-276.
[2]	ZHANG En, CAI Yong-Quan. A verifiable rational secret sharing scheme based on the elliptic curve [J]. , 2011, 28(6): 806-810.
[3]	WEI Yun, XIONG Guo-Hua, ZHANG Xing-Kai, BAO Wan-Su. A strong blind signature scheme over the braid groups [J]. , 2011, 28(6): 826-831.
[4]	YANG Hui-Hui, ZHAO Xian-Feng. A modified method for storage and revoking of the AACS device keys [J]. , 2011, 28(5): 642-647.
[5]	LIU Shao-Hui, SUN Jian-Chao, YAO Hong-Xun. An improved image steganalysis method based on Markov chains for spread-spectrum data hiding [J]. , 2011, 28(5): 690-695.
[6]	ZHANG Lei, GUO Jian-Sheng. Best impossible differential cryptanalysis of 6-round ARIA [J]. , 2011, 28(2): 266-273.
[7]	HUANG Gui-Fang, HU Lei, LIN Dong-Dai. An efficient compiler from Σ-protocol to deniable zero knowledge in CRS model [J]. , 2010, 27(6): 831-837.
[8]	YUAN Chun-Yang, DENG Chen-Lei. Enforcement of Clark-Wilson model in combination of RBAC and TE models [J]. , 2010, 27(4): 538-546.
[9]	PAN Jia-Xin, MA Chang-She, WANG Li-Bin. Efficient and semantically secure password-based group key exchange protocol [J]. , 2010, 27(4): 547-555.
[10]	DING Zhi-Guo, ZHU Xue-Yong, LEI Ying-Ke. An RFID authentication protocol based on CDMA and anti-collision function [J]. , 2010, 27(3): 397-403.
[11]	ZHANG Hai-Bin, WU Chuan-Kun, WEI Ling-Bo. Key privacy in multi-recipient setting and shortened private broadcast encryption [J]. , 2010, 27(1): 90-106.
[12]	WANG Bi-Da, LIAN Yi-Feng. An efficiency evaluation methodology of DoS attack and defense mechanisms based on queueing theory [J]. , 2010, 27(1): 107-116.
[13]	TANG Qiang, JI Dong-Yao. Deniable problems in secret authentication [J]. , 2009, 26(6): 835-840.
[14]	LI Ming, WANG Kun-Peng. Cryptosystem based on elliptic curve over local ring Z／pZ [J]. , 2009, 26(5): 695-702.
[15]	SHEN Li-Hong, XU Zhen. Electronic cash based on trusted computing platform [J]. , 2009, 26(5): 712-719.