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

doi:10.19665/j.issn1001-2400.2021.06.026

Abstract

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

CLC Number:

TP391.3

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.

Figures/Tables 5

节点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$

References 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

Private information retrieval with low encoding/decoding complexity

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 29

Related Articles 4

Metrics

Comments

Recommended 10

[1]	YANG Yanbo,ZHANG Jiawei,MA Jianfeng. Method for using the blockchain to protect data privacy of IoV [J]. Journal of Xidian University, 2021, 48(3): 21-30.
[2]	ZHANG Lu,SUN Rong,LIU Jingwei. Cloned piggybacking framework for distributed storage [J]. Journal of Xidian University, 2020, 47(6): 139-147.
[3]	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+135.
[4]	ZHANG Wei1,2;MA Jian-feng2;YANG Xiao-yuan1. Reliability of distributed storage systems [J]. J4, 2009, 36(3): 480-485.