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

CIF：小型：用于通信和可验证存储的超高效代码

• 批准号: 1910659
• 负责人: Elena Grigorescu
• 金额: $ 49.92万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910659&HistoricalAwards=false
• 关键词: CIF; Small; Ultra; Efficient; Codes

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.

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

项目成果

The Parallel Reversible Pebbling Game: Analyzing the Post-quantum Security of iMHFs

并行可逆卵石游戏：分析 iMHF 的后量子安全性

• 发表时间: 2022
• 期刊: Theory of Cryptography Conference (TCC 2022
• 作者: Blocki, Jeremiah;Holman, Blake;Lee, Seunghoon
• 通讯作者: Lee, Seunghoon

Hardness of Maximum Likelihood Learning of DPPs

• DOI: 10.48550/arxiv.2205.12377
• 发表时间: 2022-05
• 期刊: Electron. Colloquium Comput. Complex.
• 作者: Elena Grigorescu;Brendan Juba;K. Wimmer;Ning Xie

Locally Decodable/Correctable Codes for Insertions and Deletions

用于插入和删除的本地可解码/可纠正代码

• DOI: 10.4230/lipics.fsttcs.2020.16
• 发表时间: 2020
• 期刊: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
• 作者: Block, A;Blocki, J;Grigorescu, E;Kulkarni, S;Zhu, M.
• 通讯作者: Zhu, M.

Online Directed Spanners and Steiner Forests

在线指导扳手和斯坦纳森林

• DOI: 10.4230/lipics.approx/random.2021.5
• 发表时间: 2021
• 期刊: and Combinatorial Optimization. Algorithms and Techniques
• 作者: Elena Grigorescu;Young-San Lin;Kent Quanrud
• 通讯作者: Kent Quanrud

Relaxed Locally Correctable Codes in Computationally Bounded Channels

计算有界通道中的宽松局部可校正码

• DOI: 10.1109/tit.2021.3076396
• 发表时间: 2021
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Blocki, Jeremiah;Gandikota, Venkata;Grigorescu, Elena;Zhou, Samson
• 通讯作者: Zhou, Samson