Private information retrieval protocol based on point function secret sharing

doi:10.11772/j.issn.1001-9081.2017.02.0494

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (2): 494-498.DOI: 10.11772/j.issn.1001-9081.2017.02.0494

Previous Articles Next Articles

Private information retrieval protocol based on point function secret sharing

YUAN Dazeng^1,2, HE Mingxing², LI Xiao¹, ZENG Shengke²

1. School of Science, Xihua University, Chengdu Sichuan 610039, China;
2. School of Computer and Software Engineering, Xihua University, Chengdu Sichuan 610039, China

Received:2016-08-10 Revised:2016-09-09 Online:2017-02-10 Published:2017-02-11
Supported by:
This work is partially supported by the National Natural Science Foundation of China (U1433130), the Ministry Basic Research Program (Chunhui Program) of China (Z2014045).

基于点函数秘密共享的私有信息检索协议

袁大曾^1,2, 何明星², 李虓¹, 曾晟珂²

1. 西华大学理学院, 成都 610039;
2. 西华大学计算机与软件工程学院, 成都 610039

通讯作者: 袁大曾,yuan_dz34@163.com
作者简介:袁大曾(1992-),女,四川达州人,硕士研究生,CCF会员,主要研究方向:安全协议、网络安全、大数据;何明星(1964-),男,四川南江人,教授,博士,CCF会员,主要研究方向:现代密码算法、安全协议、密钥管理、电子商务/电子政务安全;李虓(1972-),男,四川达州人,副教授,博士,CCF会员,主要研究方向:信息安全、密码学;曾晟珂(1982-),女,重庆人,副教授,博士,CCF会员,主要研究方向:信息安全、密码学。
基金资助:
国家自然科学基金资助项目（U1433130）；教育部春晖计划项目（Z2014045）。

Abstract

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

摘要： 针对私有信息检索（PIR）中的隐私安全问题，提出了一个基于点函数秘密共享的私有信息检索协议。该协议将检索的索引看成一个特殊的0-1点函数，利用点函数秘密共享技术生成这个点函数的密钥组，分别发送给p个服务器，根据p个服务器返回的响应作异或运算得到检索结果。对协议进行了正确性、安全性和效率分析，验证了这个协议是安全且高效的，并给出了一个具体实例来说明该协议的有效性。最后介绍了将该协议推广到多项私有信息检索和基于关键字的私有信息检索中的应用情况。

关键词: 点函数, 函数秘密共享, 私有信息检索, 隐私安全, 异或运算

CLC Number:

TP309.2

YUAN Dazeng, HE Mingxing, LI Xiao, ZENG Shengke. Private information retrieval protocol based on point function secret sharing[J]. Journal of Computer Applications, 2017, 37(2): 494-498.

袁大曾, 何明星, 李虓, 曾晟珂. 基于点函数秘密共享的私有信息检索协议[J]. 计算机应用, 2017, 37(2): 494-498.

References

[1] CHOR B, KUSHILEVITZ E, GOLDREICH O, et al. Private information retrieval[J]. Journal of the ACM, 1998, 45(6):965-981.
[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.
[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.)

Private information retrieval protocol based on point function secret sharing

基于点函数秘密共享的私有信息检索协议

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics