具有低编解码复杂度的私有信息检索

doi:10.19665/j.issn1001-2400.2021.06.026

摘要/Abstract

摘要：

目前的私有信息检索方法大都是基于线性组合运算的,这些方法具有较高的计算复杂度。针对这一问题,提出一种基于CP-BZD码的私有信息检索方案。其中,Combination Property具有组合性质,Binary Zigzag Decoding是二进制锯齿解码。在(n,k) CP-BZD系统中,k个原始数据包被编码为n大于等于k个编码数据包,n个编码数据包中的任意k个可以解码得到原始的k个数据包,且该解码可由二进制锯齿解码算法实现。用户想要从分布式存储系统中下载单个文件,系统中存储的多个文件是以CP-BZD编码方式存储在节点上的,且系统中不存在互相串谋的节点。该方案的运算是基于二进制的移位加运算,计算复杂度显著低于基于线性组合的乘除法和矩阵求逆操作。该方案适用于任意的(n,k)系统,并且计算复杂度和通信成本都相对较低,在私有信息检索中具有较大的研究和应用价值。

关键词: 分布式存储, 私有信息检索, CP-BZD码, 锯齿解码

Abstract:

Most of current private information retrieval methods are based on linear combination operations,and these methods have a high computational complexity.To solve this problem,this paper proposes a private information retrieval scheme based on CP-BZD (combination property,binary zigzag decoding) code and zigzag decoding.In the (n,k) CP-BZD system,k original source packets are encoded into n≥k packets,where arbitrary k packets are able to recover the original k source packets,and the decoding can use the zigzag decoding algorithm.The user wants to download a file from the distributed storage system.The file is encoded by CP-BZD code and stored on the node.There are no nodes colluding with each other in the system.The operation of the proposed scheme is based on the binary shift and addition operation,whose computational complexity is lower than that of linear multiplication and matrix inversion.The communication cost has reached the lowest threshold proposed in the existing papers.This scheme is suitable for an arbitrary (n,k) system,and the computational complexity and communication cost are low.The scheme is of great significance in private information retrieval.

Key words: distributed storage, private information retrieval, CP-BZD code, zigzag decode

中图分类号:

TP391.3

代明军,李晓凤,邓海燕,陈彬. 具有低编解码复杂度的私有信息检索[J]. 西安电子科技大学学报, 2021, 48(6): 212-220.

DAI Mingjun,LI Xiaofeng,DENG Haiyan,CHEN Bin. Private information retrieval with low encoding/decoding complexity[J]. Journal of Xidian University, 2021, 48(6): 212-220.

图/表 5

图1

表1

文件存储模型"

节点1	节点2	…	节点k	节点k+1	…	节点n
$s 111$	$s 121$	…	$s 1 k 1$	$z τ 1,1 s 111 + z τ 1,2 s 121 + … + z τ 1, k s 1 k 1$	…	$z τ α, 1 s 111 + z τ α, 2 s 121 + … + z τ α, k s 1 k 1$
?	?		?	?		?
$s α 1 1$	$s α 2 1$	…	$s αk 1$	$z τ 1,1 s α 1 1 + z τ 1,2 s α 2 1 + … + z τ 1, k s αk 1$	…	$z τ α, 1 s α 1 1 + z τ α, 2 s α 2 1 + … + z τ α, k s αk 1$
?	?		?	?		?
$s 11 m$	$s 12 m$	…	$s 1 k m$	$z τ 1,1 s 11 m + z τ 1,2 s 12 m + … + z τ 1, k s 1 k m$	…	$z τ α, 1 s 11 m + z τ α, 2 s 12 m + … + z τ α, k s 1 k m$
?	?		?	?		?
$s α 1 m$	$s α 2 m$	…	$s αk m$	$z τ 1,1 s α 1 m + z τ 1,2 s α 2 m + … + z τ 1, k s αk m$	…	$z τ α, 1 s α 1 m + z τ α, 2 s α 2 m + … + z τ α, k s αk m$

表1

图2

图3

图4

参考文献 29

[1]	CHOR B, GOLDREICH O, KUSHILEVITZ E, et al. Private Information Retrieval[C]// Proceedings of IEEE 36th Annual Foundations of Computer Science.Piscataway:IEEE, 1995:41-45.
[2]	CHOR B, KUSHILEVITZ E, GOLDREICH O, et al. Private Information Retrieval[J]. Journal of the ACM, 1998, 45(6):965-981. doi: 10.1145/293347.293350
[3]	HEZAVEH M, ADAMS C. A PIR Scheme to Improve the Computation Cost on the Client Side of Smartphone Applications[C]// 2018 IEEE Canadian Conference on Electrical Computer Engineering.Piscataway,IEEE, 2018:1-4.
[4]	TAN Z, WANG C, ZHOU M, et al. Private Information Retrieval in Vehicular Location Based Services[C]// 2018 IEEE 4th World Forum on Internet of Things.Piscataway:IEEE, 2018:56-61.
[5]	MANE S B, SAWANT S T, SINHA P K. Using Private Information Retrieval Protocol for an E-Commerce Application[C]// Proceedings of the CUBE International Information Technology Conference.New York:ACM, 2012:659-663.
[6]	BANAWAN K, ULUKUS S. The Capacity of Private Information Retrieval From Coded Databases[J]. IEEE Transactions on Information Theory, 2018, 64(3):1945-1956. doi: 10.1109/TIT.2018.2791994
[7]	TIAN C, SUN H, CHEN J. Capacity-Achieving Private Information Retrieval Codes With Optimal Message Size and Upload Cost[J]. IEEE Transactions on Information Theory, 2019, 65(11):7613-7627. doi: 10.1109/TIT.18
[8]	FANTI G, RAMCHANDRAN K. Efficient Private Information Retrieval Over Unsynchronized Databases[J]. IEEE Journal of Selected Topics in Signal Processing, 2015, 9(7):1229-1239. doi: 10.1109/JSTSP.2015.2432740
[9]	SUN H, JAFAR S A. The Capacity of Symmetric Private Information Retrieval[J]. IEEE Transactions on Information Theory, 2019, 65(1):322-329. doi: 10.1109/TIT.2018.2848977
[10]	WANG Q, SUN H, SKOGLUND M. The Capacity of Private Information Retrieval With Eavesdroppers[J]. IEEE Transactions on Information Theory, 2019, 65(5):3198-3214. doi: 10.1109/TIT.18
[11]	AUGOT D, LEVY-DIT-VEHEL F, SHIKFA A. A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers[C]// 13rd International Conference on Cryptology and Network Security.Heidelberg:Springer, 2014:222-239.
[12]	ZHANG Y, GE G. A General Private Information Retrieval Scheme for MDS Coded Databases with Colluding Servers[EB/OL]. [2020-07-30]. https://link.springer.com/article/10.1007/s10623-019-00640-x .
[13]	HOU H X, HAN Y S, LEE P P C. Two Classes of Binary MDS Array Codes with Asymptotically Optimal Repair for Any Single Column[J/OL]. [2020-07-28].DOI: 10.1109/TCOMM.2020.3020060. doi: 10.1109/TCOMM.2020.3020060
[14]	TAJEDDINE R, GNILKE O W, KARPUK D, et al. Private Information Retrieval From Coded Storage Systems With Colluding,Byzantine,and Unresponsive Servers[J]. IEEE Transactions on Information Theory, 2019, 65(6):3898-3906. doi: 10.1109/TIT.18
[15]	LI J, KARPUK D, HOLLANTI C. Towards Practical Private Information Retrieval From MDS Array Codes[J]. IEEE Transactions on Communications, 2020, 68(6):3415-3425. doi: 10.1109/TCOMM.26
[16]	WANG Q, SKOGLUND M. Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Non-Colluding and Colluding Servers[J/OL]. [2020-08-02].DOI: 10.1109/TIT.2019.2903206. doi: 10.1109/TIT.2019.2903206
[17]	TAJEDDINE R, GNILKE O W, ElROUAYHEB S. Private Information Retrieval From MDS Coded Data in Distributed Storage Systems[J]. IEEE Transactions on Information Theory, 2018, 64(11):7081-7093. doi: 10.1109/TIT.2018.2815607
[18]	TAJEDDINE R, GNILKE O W, KARPUK D, et al. Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns[EB/OL]. [2020-08-02]. http://arXiv preprint arXiv:1701.07636.
[19]	SUNG C W, GONG X. A ZigZag-Decodable Code with the MDS Property for Distributed Storage Systems[C]// Proceedings IEEE International Symposium Information Theory.Piscataway:IEEE, 2013: 341C345.
[20]	郝晓慧, 车书玲, 张欣瑜. LRC码最小距离限的深入分析[J]. 西安电子科技大学学报, 2018, 45(5):75-79.
	HAO Xiaohui, CHE Shuling, ZHANG Xinyu. In-Depth Analysis of Bounds on the Minimum Distance of LRCs[J]. Journal of Xidian University, 2018, 45(5):75-79.
[21]	SATHIAMOORTHY M, ASTERIS M, PAPAILIOPOULOS D, et al. XORing Elephants:Novel Erasure Codes for Big Data[C/OL]. [2020-07-30].DOI: 10.14778/2535573.2488339. doi: 10.14778/2535573.2488339
[22]	康海燕, XIONG Li. 面向大数据的个性化检索中用户匿名化方法[J]. 西安电子科技大学学报, 2014, 41(5):148-154.
	KANG Haiyan, XIONG Li. Enhancing User Privacy for Personalized Web Search in Big Data[J]. Journal of Xidian University, 2014, 41(5):148-154.
[23]	GRISSA M, YAVUZ A A, HAMDAOUI B. Location Privacy in Cognitive Radios With Multi-Server Private Information Retrieval[J]. IEEE Transactions on Cognitive Communications and Networking, 2019, 5(4):949-962. doi: 10.1109/TCCN.6687307
[24]	JOONAS P, CAMILLA H, OLAV T. Device To-Device Data Storage for Mobile Cellular Systems[C]// Proceedings of IEEE Globecom Workshops.Piscataway:IEEE, 2013:671-676.
[25]	GONG B, CHENG P, CHEN Z, et al. Spatio temporal Compressive Network Coding for Energy-Efficient Distributed Data Storage in Wireless Sensor Networks[J]. IEEE Communications Letters, 2015, 19(5):803-806. doi: 10.1109/LCOMM.2015.2401008
[26]	HOU H X, HAN Y S, SHUM K W, et al. A Unified Form of EVENODD and RDP Codes and Their Efficient Decoding[J]. IEEE Transactions on Communications, 2018, 66(11):5053-5066. doi: 10.1109/TCOMM.2018.2859956
[27]	DAI M J, LU S S, ZHANG N, et al. Error Correction CP-BZD Storage Codes for Content Delivery in Drive-Thru Internet[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(11):4869-4882. doi: 10.1109/TITS.6979
[28]	HOU H X, LEE P P C, HAN Y S. Zigzag-Decodable Reconstruction Codes With Asymptotically Optimal Repair for All Nodes[J]. IEEE Transactions on Communications, 2020, 68(10):5999-6011. doi: 10.1109/TCOMM.26
[29]	DAI M J, SUNG C W, WANG H, et al. A New Zigzag-Decodable Code with Efficient Repair in Wireless Distributed Storage[J]. IEEE Transactions on Mobile Computing, 2017, 16(5):1218-1230. doi: 10.1109/TMC.2016.2591537