CIF: Small: Ultra-Efficient Codes for Communication and Verifiable Storage

该项目的目标是开发超高效的编码方案，以满足分析和处理大量数据的迫切需求带来的现代通信和存储需求。编码方案是保护数据不受损坏和丢失的一种手段。编码方案的一个理想特征是局部性，即能够通过仅访问大数据集的一小部分来快速恢复数据段的特性。其他需要的特性包括可验证性，它允许验证数据是否正确存储，以及隐私和安全，它确保用户的数据不被滥用。研究成果在分布式云存储中得到了应用。本研究建立的通信方案可用于实际部署，以保证传输消息的安全性。此外，该项目旨在让本科生参与研究，并开发课程材料，向幼儿介绍编码理论和密码学的基本概念，从而扩大对计算机的参与。这项研究将通过在研讨会、研讨会和会议上的陈述广泛传播，并将纳入普渡大学的本科生和研究生课程。该研究项目将集中在概率多项式时间信道、顺序有界信道和功率有界信道中的局部码的研究。它还将研究特定于分布式数据的本地擦除编码方案，并开发新的密码原语以保护隐私和确保数据的稳健存储。研究的具体成果将包括：(1)抽象与存储和通信相关的真实世界数据的模型；(2)在这些模型中提供超高效算法；(3)纳入隐私和安全考虑；以及(4)开发新的分析技术，将整合和推进数学和理论计算机科学的不同领域，包括编码理论、次线性算法、密码学和隐私。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The goal of this project is to develop ultra-efficient coding schemes for modern communication and storage requirements brought forth by the pressing need to analyze and work with large amounts of data. A coding scheme is a means of protecting data from damage and loss. A desirable feature of coding schemes is locality, namely the property of being able to quickly recover a segment of the data by accessing only a tiny portion of a large data set. Other desirable properties include verifiability, which allows verification that data is properly stored, and privacy and security, which ensure that users' data is not misused. The outcomes of the research find application in distributed cloud storage. The communication schemes built in this research may be used in real-world deployment to ensure security of the transmitted message. Furthermore, the project aims to broaden participation in computing by involving undergraduate students in research, and by developing course material to introduce young children to basic concepts in coding theory and cryptography. The research will be broadly disseminated through presentations in workshops, seminars and conferences, and will be integrated in undergraduate and graduate courses at Purdue University. The research project will focus on the study of local codes in probabilistic polynomial time channels, sequentially bounded channels, and power-bounded channels. It will also study local erasure coding schemes specific to distributed data, and develop novel cryptographic primitives to protect privacy and ensure robust storage of data. Specific outcomes of the research will include: (1) abstracting models that capture real-world data relevant to storage and communication; (2) providing ultra-efficient algorithms in these models; (3) incorporating privacy and security considerations; and (4) developing novel analysis techniques that will integrate and advance diverse areas of mathematics and theoretical computer science including coding theory, sublinear algorithms, cryptography and privacy.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.