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.