分布式存储编码和保密信息提取研究

Distributed storage and private information retrieval (PIR for short) respectively deal with the problems arising from the processes of storing and accessing big data. These two subjects are very similar and closely connected. In this project, through analogies between coding for distributed storage and PIR schemes, we deeply dig into the relations between them and propose several new research problems that have both important theoretical value and practical value. More specifically, we focus on several basic parameters, including sub-packetization, field size, disk reads, and storage overhead. We try to determine the optimal values of these parameters and find out the tradeoff between them. Our research on these parameters is applicable to all models about distributed storage and PIR, and also closely related to the storage efficiency, the access efficiency and the implementation efficiency of practical use. During our research, we develop some new methods, including measuring information entropy by matrix rank, simulating PIR by distributed storage with blind repair, and drawing the information flow graph for PIR models. Some breakthrough in theoretical study of the two subjects can be expected in this project.

分布式存储是海量数据的主要存储方式，保密信息提取（简称PIR, Private Information Retrieval）是密码学中的经典问题，二者分别对应了分布式环境下海量数据的存和取两个重要过程，具有极强的相似性和相关性。本项目通过深度发掘分布式存储编码和PIR方案之间内在的联系，将它们的研究内容和研究方法相互贯通，互为利用，进而提出若干兼具理论价值和应用价值的新课题。具体来说，项目重点研究分布式存储编码和PIR方案的几个基本参数，即分包数、有限域规模、读取量、和存储量，研究它们的最优值及彼此间的影响。这些研究对相关编码理论具有重要的推动作用，也是所有模型不可或缺的理论支撑。同时，它们与实际系统的存储效率、访问效率，实现效率息息相关，具有非常基本的应用价值。在研究中，我们发展了以矩阵秩度量信息熵，以盲修复模拟保密提取，建立PIR信息流图等全新的思路和方法，预计将取得一些突破性进展。

分布式存储编码是大规模数据存储系统的重要理论基础，保密信息提取（PIR）是密码学中的经典问题，而基于分布式存储的PIR在隐私保护中有重要应用。本项目抓住分布式存储编码和保密信息提取二者之间的联系，充分利用编码和信息论等数学方法，取得一系列重要研究成果，圆满完成各项预定的研究目标。具体从三个方面总结项目的研究成果。.1..保密信息提取。首次提出达到容量的PIR方案的最优分包数问题，并完全确定了基于重写存储的抗合谋PIR和基于MDS码存储的无合谋PIR方案的最优分包数；进一步，将达到容量和最优分包数的线性PIR方案的有限域规模降低常数因子，再降低到指数级开方级别，并最终在二元域上对非平凡参数构造出最优PIR方案。.2..合作再生码和局部修复码。完整刻画了标量MSCR码（最小存储合作再生码）的存在性和构造方案；设计了第一个实现最优读取的全参数MSCR码，分包数较前人减小一个指数因子；改进前人关于Reed-Solomon码合作修复两到三个失效节点的方案，去掉有限域特征的限制，并将交互轮数降为一轮；证明了局部修复码的堆球界，给出优于C-M界的参数估计。.3..机架感知再生码。首次给出最小带宽机架感知再生码（MBRR码）的全参数显式构造；改进前人的最小存储机架感知再生码（MSRR码）构造，将分包数的指数降低一个常数因子；提出可容忍多个失效节点的机架感知再生码（MET-RRC）模型，并显式地构造了所有参数情形下标量的MET-MSRR码和MET-MBRR码。..项目的研究成果不仅在编码和信息安全领域具有重要的理论价值，而且在数据存储和隐私保护方面也有非常实用的应用前景。此外，项目在人才培养，合作交流方面也做出了重要的工作，取得了较好的社会效益。