论文部分内容阅读
大数据时代,如何对海量数据有效存储和隐私检索是现在亟待解决的两个问题。因此,分布式存储(Distributed Storage,DS)和私有信息检索(Private Information Retrieval,PIR)的概念分别被提出。将网络编码技术应用于DS系统,不仅可以降低存储开销,还能有效降低修复损坏节点所消耗的带宽。但传统网络编码技术的编码、解码操作在大的有限域内进行,其能量消耗大,不适用于大规模数据存储、频繁数据读写等领域。因此,二进制的锯齿解码(Zigzag Decoding)被提出,它能够降低解码复杂度。本文是基于二进制锯齿解码,存储编码设计和PIR协议在分布式存储中的研究。(n,k)CP-BZD码是一种既拥有组合(Combination Property,CP)性质又可以在二元域进行锯齿解码的编码方式,它具有解码复杂度低和存储开销小等优点。但由于目前仅有针对n≤2k时的编码设计方案,存在一定的局限性。本文借鉴该编码思想,利用循环移位矩阵,提出n>2k时的编码方式,放宽了n的限制条件,使其可以满足任意的(n,k)参数。同时,作图并分析了 Inc-Diff码、Base-Shift码和CP-BZD码的存储开销,指出不同编码方式的优缺点。PIR是指用户在向数据库服务器提交查询请求时,在用户的查询信息不被泄漏的前提下完成整个查询操作。考虑各个存储节点互不串谋,本文基于锯齿解码,首先提出了(n,k)CP-BZD码DS系统上的低复杂度PIR协议。该协议分为两个阶段,分别为数据查询和下载阶段和数据解码阶段。在数据查询和下载阶段,用户生成一个随机向量和一个检索向量,将查询语句设置为两种,分别是随机向量U和随机向量与检索向量的组合U+ef,以此来保证隐私性。在数据解码阶段,利用锯齿解码,可以保持较低的计算复杂度。针对检索过程中,某些存储节点不响应的问题,本文对低复杂度PIR协议进行扩展,提出低复杂度的鲁棒性PIR协议。它能够在最多n-k-1个节点同时损坏的情况下,通过多轮查询下载,使用户仍然隐私的检索文件,并保持较低的计算复杂度。该协议还对所有损坏节点的情况进行了分析,包括无响应的节点仅为系统节点、无响应的节点仅为奇偶校验节点和无响应的节点同时包含系统节点和奇偶校验节点三种情况。同时,针对低复杂度的鲁棒性PIR协议通信成本过高的问题,本文又提出了低通信成本的鲁棒性PIR协议,它能够使一轮额外的查询数据弥补多个无响应节点损失的数据。最后对提出的三个PIR协议分别进行了隐私性、通信成本和复杂度的分析。综上,在存储方面,本文提出了n>2k时的(n,k)CP-BZD码,其能够在编码包个数m=n-k大的时候保持较小的存储开销。在检索方面,本文提出了三个PIR协议,分别是低复杂度的PIR协议,低复杂度的鲁棒性PIR协议和低通信成本的鲁棒性PIR协议。其在二进制利用锯齿解码,可以保持较低的计算复杂度。