Research On Private Information Retrieval And Coding Design In Distributed Storage

In the era of big data,there are two problems that need to be solved urgently,namely,effective storage and privacy retrieval for massive data.Therefore,the concepts of distributed storage(DS)system and private information retrieval(PIR)have been proposed,respectively.Applying network coding technology to the DS system not only reduces storage overhead,but also effectively reduces the bandwidth consumed by repairing damaged nodes.However,the encoding and decoding operations of the traditional network coding technology are carried out in a large finite field,it has high energy consumption and is not suitable for large-scale data storage,frequent data reading and writing,and so on.Therefore,binary zigzag decoding has been proposed,which can reduce the decoding complexity.This paper is based on zigzag decoding technology in the binary field,research on storage coding design and PIR protocol in distributed storage.(n,k)CP-BZD(Combination Property-Binary Zigzag Decodable)code is a coding method that has both combination property and zigzag decoding in the binary field,it has the advantages of low decoding complexity and low storage overhead.However,due to the current coding design for n ? 2k,there are certain limitations.This paper draws on this coding idea and using a cyclic shift matrix,the coding mode of n>2k is proposed.The constraint condition of n is relaxed,so it can satisfy any parameter of(n,k).At the same time,we draw and analyze the storage overhead of Inc-Diff code,Base-Shift code and CP-BZD code,and point out the advantages and disadvantages of different coding methods.Private information retrieval means that when the user submits a query request to the database server,the user can retrieving a file without revealing any information about which file is being retrieved.Consider that each storage nodes does not colluding,this paper proposes a low complexity PIR protocol in a distributed storage system based on(n,k)CP-BZD code,which can using zigzag decoding.This protocol consists of two stages,including the data request and download stage and the data decoding stage.In data request and download stage,the user generates a random vector and a retrieval vector.We set the query to two types to ensure privacy,which are random vector U and combination of a random vector and a retrieval vector U+ef.In data decoding stage,we can use zigzag decoding to keep the low computational complexity.In view of the problem that some storage nodes do not respond during the retrieval process,this paper extends the low complexity PIR protocol and proposes a low complexity robust PIR protocol.It can guarantee that the user still can retrieve files privately through multiple rounds of queries and download even if these n-k-1 nodes are damaged together,and it also has low computational complexity.This paper also analyzes all damages of storage nodes,including all unresponsive nodes are systematic nodes,all unresponsive nodes are parity nodes and the unresponsive nodes contain both systematic nodes and parity nodes.At the same time,in view of the problem that communication cost of low complexity robust PIR protocol is too high,this paper proposes a low communication cost robust PIR protocol,which can make a round of additional query data to make up for the loss data by multiple unresponsive nodes.Finally,this paper analyzes the performance of three PIR protocols,including privacy,communication cost and complexity.In summary,in terms of storage,this paper proposes a(n,k)CP-BZD code for n>2k,which have low storage overhead when the number of encoded packets m=n-k is large.In terms of retrieval,this paper proposes three PIR protocols,namely low complexity PIR protocol,low complexity robust PIR protocol and low communication cost robust PIR protocol.It uses zigzag decoding in the binary field and has low computational complexity.