Collaborative Research: SaTC: CORE: Medium: New Constructions for Garbled Computation

安全多方计算（MPC）是密码学的一个庞大且不断增长的子领域，它使相互不信任的各方能够共同评估其私有数据上的函数。MPC的一个令人兴奋的承诺是能够编写这样的函数作为通用程序，然后安全地评估它们。这将使非加密专家能够自动增强具有强大安全属性的普通软件。实现这一目标的工具已被证明是难以捉摸的，由于MPC内部有效执行普通程序的障碍。关键的障碍是有效地处理随机存取存储器（RAM）。RAM在计算中无处不在，但RAM的有效MPC处理是众所周知的顽固挑战。 该项目将显著改善MPC对RAM的处理，从而实现更高效的通用MPC工具。乱码RAM（GRAM）是一个强大的MPC原语，它消除了MPC对RAM访问程序的交互性（从而消除了昂贵的延迟）。 最新的可再生能源技术克服了几个长期存在的障碍，可再生能源的效率和恢复的希望显着进一步改善。研究人员将抓住这个机会，探索和实施新的生物技术。该项目的范围很广，包括提高密码学效率，将密码学引入更丰富的环境，理解密码学的理论和实践局限性，改进构建高效密码学所需的密码学假设，以及实现软件原型。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Secure multi-party computation (MPC) is a large and growing subfield of cryptography that enables mutually untrusting parties to jointly evaluate functions on their private data. One exciting promise of MPC is the ability to write such functions as general programs and then evaluate them securely. This would enable even non-crypto-specialists to automatically augment ordinary software with powerful security properties. Tools for achieving this goal have proven elusive, due to barriers to efficiently executing ordinary programs inside MPC. The critical barrier is in efficiently handling random access memory (RAM). RAM is ubiquitous in computing, but efficient MPC handling of RAM is well known as a stubborn challenge. This project will significantly improve MPC handling of RAM, thus enabling far more efficient general-purpose MPC tools.Garbled RAM (GRAM) is a powerful MPC primitive that removes interactivity (and hence costly latency) from MPC of programs with RAM accesses. Recent GRAM techniques overcame several long-standing obstacles to GRAM efficiency and restored hope for significant further improvement. The investigators will seize the opportunity, and will explore and implement novel GRAM techniques. The project’s scope is broad, and includes improving GRAM efficiency, bringing GRAM to richer settings, understanding GRAM’s theoretical and practical limitations, improving the cryptographic assumptions needed to construct efficient GRAM, and implementing software prototypes.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.