Journal of Guangxi Normal University(Natural Science Edition) ›› 2020, Vol. 38 ›› Issue (3): 33-44.doi: 10.16088/j.issn.1001-6600.2020.03.005

Previous Articles     Next Articles

Private Information Retrieval Schemes with Erasure-correcting or Error-correcting Properties

GE Yifei1, ZHENG Yanbin2*   

  1. 1. School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China;
    2. Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin Guangxi 541004, China
  • Received:2019-10-09 Online:2020-05-25 Published:2020-06-11

Abstract: Private information retrieval (PIR) is a classic problem in theoretical computer science and cryptography. In recent years, new directions on PIR arise due to its connection with distributed storage systems. A distributed storage system containing N servers and storing a database of M files is studied. It is supposed that each file is stored independently via an (N,K)-MDS code. A PIR scheme allows a user to retrieve a specific file from the database privately and any T colluding servers cannot learn any information about the index of the retrieved file. A key problem is to analyze the PIR rate, which is the maximal number of bits privately retrieved per one downloaded bit. Optimal PIR schemes have been constructed in the classic model. In real life applications, the transmission of data suffers from erasures, noises, or even being intentionally tampered by a third party. Therefore, in this paper, PIR schemes with erasure-correcting and error-correcting properties are considered. Based on the PIR schemes in classic settings, additional coding strategies are used to bring in more redundancy among the queries and thus obtain PIR schemes suitable for erasure-correcting and error-correcting models. In addition, the PIR rates for these schemes are computed.

Key words: private information retrieval, distributed storage system, erasure-correcting property, error-correcting property

CLC Number: 

  • O236.2
[1] CHOR B, GOLDREICH O, KUSHILEVITZ E, et al. Private information retrieval[C]//Proceedings of the 36th Annual Symposium on Foundations of Computer Science(FOCS′95).Washington DC: IEEE Computer Society,1995: 41-50.
[2] CHOR B, KUZHILEVITZ E, GOLDREICH O, et al. Private information retrieval[J].Journal of the ACM,1998,45(6): 965-981.
[3] XU J, ZHANG Z. On sub-packetization and access number of capacity-achieving PIR schemes for MDS coded non-colluding servers[J]. Science China:Information Sciences, 2018,61(10): 100306.
[4] 蔡鹏飞, 王崇科, 李晓平. 基于通用单向累加器的车载自组织网络隐私保护撤销机制[J].计算机应用研究,2016,33(8): 2396-2401.
[5] 郭松矗, 崔杰. 面向车载自组网的高效位置隐私保护查询方案[J].计算机工程,2014,40(6): 99-103.
[6] DVIR Z, GOPI S. 2-server PIR with sub-polynomial communication[J].Journal of the ACM,2016, 63(4): 39.
[7] BEIMEL A, ISHAI Y, KUSHILEVITZ E, et al. Breaking the O(n1/(2k-1)) barrier for information-theoretic private information retrieval[C]//Proceedings of the Annual Symposium on Foundations of Computer Science(FOCS′02). Washington DC: IEEE Computer Society, 2002: 261-270.
[8] EFREMENKO K. 3-query locally decodable codes of subexponential length[J].SIAM Journal on Computing,2012,41(6): 1694-1703.
[9] YEKHANIN S. Private information retrieval[J].Communications of the ACM,2010,53(4): 68-73.
[10]YEKHANIN S. Towards 3-query locally decodable codes of subexponential length[J].Journal of the ACM,2008,55(1): 1.
[11]AUGOT D, LEVY-DIT-VEHEL F, SHIKFA A. A storage-efficient and robust private information retrieval scheme allowing few servers[C]//Lecture Notes in Computer Science Vol. 8813. Switzerland AG: Springer,2014: 222-239.
[12]BLACKBURN S, ETZION E, PATERSON M. PIR schemes with small download complexity and low storage requirements[EB/OL].(2018-12-04)[2019-10-09].https://arxiv.org/abs/1609.07027v4.
[13]CHAN T, HO S, YAMAMOTO H. Private information retrieval for coded storage[C]//2015 IEEE International Symposium on Information Theory. Piscataway, NJ: IEEE Press, 2015: 2842-2846.
[14]SHAH N B, RASHMI K V, RAMCHANDRAN K. One extra bit of download ensures perfectly private information retrieval[C]//2014 IEEE International Symposium on Information Theory. Piscataway, NJ: IEEE Press,2014: 856-860.
[15]SUN H, JAFAR S A. The capacity of private information retrieval[J].IEEE Transactions on Information Theory, 2017,63(7): 4075-4088.
[16]BANAWAN K, ULUKUS S. The capacity of private information retrieval from coded databases[EB/OL].(2016-09-26)[2019-10-09].https://arxiv.org/abs/1609.08138.
[17]FFEIJ-HOLLANTI R, GNILKE O, HOLLANTI C, et al. Private information retrieval from coded databases with colluding servers[EB/OL].(2017-08-16)[2019-10-09].https://arxiv.org/abs/1611.02062v3.
[18]SUN H, JAFAR S A. Private information retrieval from MDS coded data with colluding servers: settling a conjecture by Freij-Hollanti et al[EB/OL].(2017-01-30)[2019-10-09].https://arxiv.org/abs/1701.07807v2.
[19]SUN H, JAFAR S A. The capacity of robust private information retrieval with colluding databases[EB/OL].(2016-05-02)[2019-10-09].https://arxiv.org/abs/1605.00635.
[20]TAJEDDINE R, GNILKE O W, ROUAYHEB S E. Private information retrieval from MDS coded data in distributed storage systems[EB/OL].(2018-03-15)[2019-10-09].https://arxiv.org/abs/1602.01458v4.
[21]ZHANG Y, GE G. A general private information retrieval scheme for MDS coded databases with colluding servers[J].Designs, Codes and Cryptography, 2019, 87(11): 2611-2633.
[22]TAJEDDINE R, GNILKE O W, KARPUK D, et al. Private information retrieval schemes for coded data with arbitrary collusion patterns[EB/OL].(2016-09-26)[2019-10-09].https://arxiv.org/abs/1701.07636v3.
[23]TANDON R. The capacity of cache aided private information retrieval[EB/OL].(2017-06-21)[2019-10-09].https://arxiv.org/abs/1706.07035.
[24]KADHE S, GARCIA B, HEIDARZADEH A, et al. Private information retrieval with side information[EB/OL].(2017-09-01)[2019-10-09].https://arxiv.org/abs/1709.00112v1.
[25]TAJEDDINE R, ROUAYHEB S E. Robust private information retrieval on coded data[EB/OL].(2017-07-31)[2019-10-09].https://arxiv.org/abs/1707.09916v1.
[26]BABAWAN K, ULUKUS S. The capacity of private information retrieval from Byzantine and colluding databases[EB/OL].(2017-06-05)[2019-10-09].https://arxiv.org/abs/1706.01442.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] HUANG Yanping, WEI Yuming. Multiple Solutions of Multiple-points Boundary Value Problem for a Class of Fractional Differential Equation[J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(3): 41 -49 .
[2] ZHANG Tengyue,WENG Xiaoxiong. Reliability Estimation Model of Freeway Travel Time Based on Toll Data[J]. Journal of Guangxi Normal University(Natural Science Edition), 2016, 34(4): 70 -77 .
[3] YUAN Weiqiang, SONG Shuxiang, CHENG Yang, ZHANG Yonggan. Design of Ultra-Wideband Microstrip Bandpass Filter[J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(4): 32 -38 .
[4] YANG Yang, YU Huangsheng,WU Dianhua. Bound and Construction for Optimal (n,{3,4,5},(2,3,1),1,Q)-OOCs[J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(4): 58 -62 .
[5] LI Yonggang, QIN Lizhen, CHEN Disan, CHENG Minquan. A Special Kind of Combinatorial Batch Codes[J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(4): 63 -67 .
[6] PANG Yang,WEI Yuming,FENG Chunhua. Existence of Positive Solutions for a Class of Two-point BoundaryValue Problem of Fractional Differential Equations[J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(4): 68 -75 .
[7] XU Lun-hui, LIU Jing-ning, ZHU Qun-qiang, WANG Qing, XIE Yan, SUO Sheng-chao. Path Deviation Control of Automatic Guided Vehicle[J]. Journal of Guangxi Normal University(Natural Science Edition), 2015, 33(1): 1 -6 .
[8] KUANG Xian-yan, WU Yun, CAO Wei-hua, WU Yin-feng. Cellular Automata Simulation Model for Urban MixedNon-motor Vehicle Flow[J]. Journal of Guangxi Normal University(Natural Science Edition), 2015, 33(1): 7 -14 .
[9] XIAO Rui-jie, LIU Ye, XIU Xiao-ming, KONG Ling-jiang. State Transfer of Two Mechanical Oscillators in Coupled CavityOptomechanical System[J]. Journal of Guangxi Normal University(Natural Science Edition), 2015, 33(1): 15 -19 .
[10] HUANG Hui-qiong, QIN Yun-mei. Overtaking Model Based on Drivers’ Characteristics[J]. Journal of Guangxi Normal University(Natural Science Edition), 2015, 33(1): 20 -26 .