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

Purdue University, West Lafayette IN

Investigators

Abstract

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.