SaTC: CORE: Medium: Collaborative: Rethinking Access Pattern Privacy: From Theory to Practice

SaTC：核心：媒介：协作：重新思考访问模式隐私：从理论到实践

• 批准号: 2128519
• 负责人: Elaine Shi
• 金额: $ 64.03万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-02-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2128519&HistoricalAwards=false
• 关键词: SaTC; CORE; Medium; Collaborative; Rethinking

When a program accesses data stored in memory, disk, or on a remote server, its access patterns can leak information about its secret inputs and data. There has been decades of work that investigated how to prevent programs from leaking any information by making their access patterns "oblivious", i.e., independent from their execution. This project is motivated by the significant overhead that past techniques incur. The project introduces and investigates new relaxed notions of access pattern obliviousness, and discovers new algorithms that achieve these notions with a significantly reduced overhead. The project includes training of Ph.D. students and postdoctoral researchers, and mentoring activities focused on high school, undergraduate, and graduate students. This project rethinks the definition of access pattern privacy, and considers (but not limited to) a new notion called "differential obliviousness". In analogy with differential privacy, differential obliviosness requires that the access patterns resulting from executing a program on similar inputs should be hard to distinguish. The project establishes theoretical understanding, including new lower and upper bounds, of the extent to which various notions of obliviosness impact the performance of programs. The investigators also explore the practical performance of new privacy-preserving algorithms in cloud outsourcing and database scenarios. The project develops open-source libraries for the new, differentially oblivious algorithms and data structures.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.

当程序访问存储在内存、磁盘或远程服务器上的数据时，其访问模式可能会泄露有关其秘密输入和数据的信息。几十年来，人们一直致力于研究如何通过使程序的访问模式“不被察觉”（即独立于其执行）来防止程序泄露任何信息。该项目的动机是过去的技术所产生的巨大开销。该项目引入并研究了访问模式遗忘的新宽松概念，并发现了以显着减少开销实现这些概念的新算法。该项目包括博士培训。学生和博士后研究人员，以及针对高中生、本科生和研究生的指导活动。该项目重新思考访问模式隐私的定义，并考虑（但不限于）一个称为“差异遗忘”的新概念。与差异隐私类似，差异遗忘性要求在相似输入上执行程序所产生的访问模式应该难以区分。该项目建立了对各种遗忘概念对程序性能影响程度的理论理解，包括新的下限和上限。研究人员还探索了新的隐私保护算法在云外包和数据库场景中的实际表现。该项目为新的、差异明显的算法和数据结构开发开源库。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Differentially Oblivious Database Joins: Overcoming the Worst-Case Curse of Fully Oblivious Algorithms

差异不经意的数据库连接：克服完全不经意算法的最坏情况诅咒

• 发表时间: 2021
• 期刊: ITCS
• 作者: Chu, Shumo;Zhuo, Dangyang;Shi, Elaine;Chan, T-H. Hubert
• 通讯作者: Chan, T-H. Hubert