Collaborative Research: GCR: Towards a Physics-Inspired Approach to Computation on Encrypted Data

Harnessing the value of data into applications with great societal value raises significant security and privacy concerns that are likely to stifle progress and decrease the return-on-investment of an AI-powered market economy. The goal of this GCR proposal is to accelerate the development of trusted, low-overhead tools that enable computation directly on encrypted data such that, for example, confidential data can be shared with an untrusted party who can extract insights from the data without having access to the unencrypted data. Such a capability, which is currently unavailable for application to large scale problems, would have the broader impact of greatly increasing the public's trust in modern AI tools and create new opportunities for data-powered, socially responsible innovation. The success of this project hinges critically on the interplay and synergy of ideas and state-of-the-art techniques and methodologies from physics, mathematics, and computer science. The paradigm shift and the powerful practical tools proposed can be realized and implemented only by the integration of expertise and the strong interdisciplinary interactions stimulated and supported by this project. Apart from their significant practical implications, the novel convergent ideas driving this project are also likely to raise new questions and stimulate new ways of thinking and new directions of research in each of the disciplines: physics, mathematics, and computer science. This project brings together state of the art tools from theoretical physics, mathematics, and computer science to: (a) explore a novel paradigm for circuit obfuscation, a fundamental tool in modern cryptography; and (b) to establish the security and efficiency of a recently proposed scheme for computation on encrypted data, referred to as Encrypted Operator Computing (EOC). The conceptual elements that drive both the new approach to circuit obfuscation and the EOC scheme are inspired by the project team's experience with the fundamental physics of complex quantum and classical systems. In particular, the obfuscation of circuits is related to ``local thermalization” of circuits implemented through ``gate collisions,” a novel concept in the context of gate-based computational circuits, which the proposal connects with relators of group presentations in geometric group theory. The connection with geometric group theory provides a natural mathematical framework for formalizing the notion of ``circuit thermodynamics.” Moreover, the critical design elements of the EOC emerge from an exact mapping of reversible classical computation (via circuits of universal reversible classical gates) into the dynamics of strings of Pauli matrices in the space of Pauli strings, a formulation which highlights many useful parallels (as well as differences) between classical and quantum computation. In this context, the quality of encryption by classical ciphers can be characterized by tools that quantify scrambling of information, entropy production, and irreversibility and chaos in the space of Pauli strings, tools commonly used in modern quantum information science. The goal of this project is to scrutinize these physics-inspired ways of thinking with state-of-the-art tools of modern cryptography, mathematics, and statistical mechanics; and to leverage the proposed collaboration and strong multi-disciplinary expertise to establish the proposed paradigm for circuit obfuscation and the EOC scheme for classical computation on encrypted data as trusted practical cryptographic tools. 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.