广西师范大学学报（自然科学版） ›› 2020, Vol. 38 ›› Issue (3): 33-44.doi: 10.16088/j.issn.1001-6600.2020.03.005

• • 上一篇    下一篇

带有纠删或纠错性质的隐私保护信息检索方案

葛奕飞1, 郑彦斌2*   

  1. 1.桂林电子科技大学数学与计算科学学院, 广西桂林541004;
    2.桂林电子科技大学广西密码学与信息安全重点实验室,广西桂林541004
  • 收稿日期:2019-10-09 出版日期:2020-05-25 发布日期:2020-06-11
  • 通讯作者: * 郑彦斌(1983—),男,河北邢台人,桂林电子科技大学副研究员,博士。E-mail: zhengyanbin@guet.edu.cn
  • 基金资助:
    广西科技计划(桂科AD18281065)

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

PDF (PC)

170

摘要： 隐私保护信息检索(private information retrieval,PIR)是理论计算机科学和密码学领域中的经典问题之一。近年来,此问题与分布式存储系统相结合,产生了新的研究方向。考虑一个由N个服务器组成的分布式存储系统,以一定的编码方式存储了由M个文件组成的数据库,每个文件经由一个(N,K)-MDS码独立存储。PIR方案可以保障用户在数据库中检索某个文件时,任意T个可合谋的服务器无法得知所检索文件指标的任何信息。PIR方案的主要指标是PIR码率,即所检索文件的大小与总下载量的比值的最大值。在这一经典模型下已有最优PIR方案。在实际应用中,数据的传输必然面临着数据丢失、噪声甚至人为篡改等干扰。因此,本文考虑带有纠删纠错性质的PIR方案。在无纠删纠错性质的PIR方案的基础上,通过引入额外的编码方法对用户问询加以适当的冗余,得到了适用于纠删纠错模型的PIR方案,并精确计算出其PIR码率。

关键词: 隐私保护信息检索, 分布式存储系统, 纠删性质, 纠错性质

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

中图分类号: 

  • 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] 黄燕萍, 韦煜明. 一类分数阶微分方程多点边值问题的多解性[J]. 广西师范大学学报（自然科学版）, 2018, 36(3): 41 -49 .
[2] 张腾月,翁小雄. 基于收费数据的高速公路行程时间可靠性估计模型[J]. 广西师范大学学报（自然科学版）, 2016, 34(4): 70 -77 .
[3] 袁伟强,宋树祥,程 洋,张勇敢. 超宽带微带带通滤波器的设计[J]. 广西师范大学学报（自然科学版）, 2017, 35(4): 32 -38 .
[4] 杨 杨,余黄生,吴佃华. 最优(n,{3,4,5},(2,3,1),1,Q)光正交码的界与构造[J]. 广西师范大学学报（自然科学版）, 2017, 35(4): 58 -62 .
[5] 李勇刚，秦丽珍，陈迪三，程民权. 一类特殊的组合批处理码[J]. 广西师范大学学报（自然科学版）, 2017, 35(4): 63 -67 .
[6] 庞 杨,韦煜明,冯春华. 一类分数阶微分方程两点边值问题正解的存在性[J]. 广西师范大学学报（自然科学版）, 2017, 35(4): 68 -75 .
[7] 许伦辉, 刘景柠, 朱群强, 王晴, 谢岩, 索圣超. 自动引导车路径偏差的控制研究[J]. 广西师范大学学报（自然科学版）, 2015, 33(1): 1 -6 .
[8] 邝先验, 吴赟, 曹韦华, 吴银凤. 城市混合非机动车流的元胞自动机仿真模型[J]. 广西师范大学学报（自然科学版）, 2015, 33(1): 7 -14 .
[9] 肖瑞杰, 刘野, 修晓明, 孔令江. 耦合腔光机械系统中两个机械振子的态交换[J]. 广西师范大学学报（自然科学版）, 2015, 33(1): 15 -19 .
[10] 黄慧琼, 覃运梅. 考虑驾驶员性格特性的超车模型研究[J]. 广西师范大学学报（自然科学版）, 2015, 33(1): 20 -26 .
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发