Foundations of classical and quantum verifiable computing
Lead Research Organisation:
University of Cambridge
Department Name: Computer Science and Technology
Abstract
Recent years have seen a vast surge in the volume and sensitivity of data that are being generated and collected, e.g., in genetic sequencing, distributed storage services, and graphs of social networks. The ubiquity and sheer size of modern data sets raise an urgent need to develop new techniques and methodologies for scalable computation.
At the same time, the rise of blockchain technology, which underlies deployed distributed systems such as Bitcoin and Ethereum, provides ample motivation for developing decentralised protocols that could go beyond challenging centralised financial control, and profoundly impact society by providing a foundation for real-world distributed systems that can be used for public benefit.
A key paradigm for meeting the challenges imposed by both of the aforementioned desiderata is that of verifiable computing. Here, the goal is to allow verification of computation that is performed by a third-party, in a scalable, secure, and privacy-preserving way. Moreover, with the advent of quantum computing on the horizon, it is imperative that the verification would also be post-quantum secure.
This proposal is focused on pushing the boundaries of classical and quantum verifiable computing and its real-world applications to delegation of computation to the cloud, as well as to blockchain technology. Its primary objective is to develop a wide arsenal of tools that would open new possibilities for meeting the challenges imposed by big data and the need for decentralised peer-to-peer systems.
The proposed approach is inherently interdisciplinary, involving fundamental concepts in cryptography, complexity theory, randomised algorithms, and quantum information, as well as relying on techniques from coding theory, combinatorics, and abstract algebra.
At the same time, the rise of blockchain technology, which underlies deployed distributed systems such as Bitcoin and Ethereum, provides ample motivation for developing decentralised protocols that could go beyond challenging centralised financial control, and profoundly impact society by providing a foundation for real-world distributed systems that can be used for public benefit.
A key paradigm for meeting the challenges imposed by both of the aforementioned desiderata is that of verifiable computing. Here, the goal is to allow verification of computation that is performed by a third-party, in a scalable, secure, and privacy-preserving way. Moreover, with the advent of quantum computing on the horizon, it is imperative that the verification would also be post-quantum secure.
This proposal is focused on pushing the boundaries of classical and quantum verifiable computing and its real-world applications to delegation of computation to the cloud, as well as to blockchain technology. Its primary objective is to develop a wide arsenal of tools that would open new possibilities for meeting the challenges imposed by big data and the need for decentralised peer-to-peer systems.
The proposed approach is inherently interdisciplinary, involving fundamental concepts in cryptography, complexity theory, randomised algorithms, and quantum information, as well as relying on techniques from coding theory, combinatorics, and abstract algebra.
Planned Impact
In recent years verifiable computing, the core of this research proposal, found a myriad of applications underlying the technical foundations of real-world technologies, including delegation of computation to the cloud, and decentralised systems such as blockchain technology and cryptocurrencies. Indeed, verifiable computing is a key ingredient in the future growth and evolution of blockchains and cloud computing, as advances in proof protocols can enhance the auditability and accountability of decentralised and outsourced computation, while obtaining key properties such as user privacy, post-quantum security, increased transaction throughput, off-chain computation, and transparent privacy.
The proposal outlines active engagement and close interaction with UK industry to obtain consistent feedback and disseminate ideas that would lead to an impact on UK society and industry. This would be facilitated via collaboration with the Warwick Manufacturing Group (WMG), which provides innovative solutions to industry, through research and knowledge transfer in engineering, manufacturing, and technology, as well as by Warwick's strong ties with the Alan Turing Institute, which would provide me with access to the top UK resources in data science, as well as a wide variety of opportunities to extend the impact of my work on UK industry. In addition, I propose to collaborate with the highly accomplished cryptocurrency company Zcash and the influential blockchain startup StarkWare Industries, towards establishing a practically-relevant theory.
The impact of developing the powerful methodologies of verifiable computing that are outlined in this proposal could go well beyond challenging centralised financial control (as decentralised systems such as Bitcoin, Zcash, and Ethereum have done in the last few years), and benefit UK society in many ways. More specifically, the purposed research aims to provide a foundation for real-world cloud computing and decentralised systems that can be used for public benefits such as preserving privacy, publicly-shared immutable ledgers for medical needs, decentralised validation of academic qualifications, and more.
The proposal outlines active engagement and close interaction with UK industry to obtain consistent feedback and disseminate ideas that would lead to an impact on UK society and industry. This would be facilitated via collaboration with the Warwick Manufacturing Group (WMG), which provides innovative solutions to industry, through research and knowledge transfer in engineering, manufacturing, and technology, as well as by Warwick's strong ties with the Alan Turing Institute, which would provide me with access to the top UK resources in data science, as well as a wide variety of opportunities to extend the impact of my work on UK industry. In addition, I propose to collaborate with the highly accomplished cryptocurrency company Zcash and the influential blockchain startup StarkWare Industries, towards establishing a practically-relevant theory.
The impact of developing the powerful methodologies of verifiable computing that are outlined in this proposal could go well beyond challenging centralised financial control (as decentralised systems such as Bitcoin, Zcash, and Ethereum have done in the last few years), and benefit UK society in many ways. More specifically, the purposed research aims to provide a foundation for real-world cloud computing and decentralised systems that can be used for public benefits such as preserving privacy, publicly-shared immutable ledgers for medical needs, decentralised validation of academic qualifications, and more.
Organisations
Related Projects
| Project Reference | Relationship | Related To | Start | End | Award Value |
|---|---|---|---|---|---|
| MR/S031545/1 | 01/02/2020 | 30/07/2023 | £891,646 | ||
| MR/S031545/2 | Transfer | MR/S031545/1 | 31/07/2023 | 29/09/2024 | £162,218 |
| Description | Resolving long-standing open problems in sublinear algorithms. In two recent papers, my work characterized the power of relaxed locally decodable codes, resolving a 16-year-old open problem posed by prominent leaders in the algorithms and complexity community. I was invited to give a plenary tutorial on the result at FOCS, which also covered my work that resolved three additional open problems. Resolving fundamental problems in quantum complexity theory. Prominent examples include: my work constructing the first zero-knowledge proofs that are secure in the presence of quantum-entangled adversaries, showing that spatial isolation implies zero knowledge even in a quantum world; achieving the first sublinear quantum algorithms for estimating the entropy of a quantum system; and resolving a textbook open problem in quantum property testing, showing its inherent connection to quantum communication. Connecting quantum machine learning and complexity theory. My work established the first general connection between the design of quantum algorithms and circuit lower bounds, explaining the hardness of quantum learning and providing a new promising approach to resolve key open problems in complexity theory via quantum algorithms. Quantum reductions via additive combinatorics and HDX. My research developed a new framework that utilizes deep mathematical tools from additive combinatorics, such as Sanders's quasi-polynomial Bogolyubov-Ruzsa lemma, to transform algorithms that are only correct on a small number of inputs into algorithms that are correct on all inputs. In a follow-up work, we extended the framework to yield such transformations for quantum algorithms for all linear problems, shedding light on a new connection between additive combinatorics and quantum mechanics. In another result, we showed a hypercontractivity theorem on High Dimensional Expanders (HDX), which was previously conjectured to be impossible. Pioneering new quantum and classical sublinear proof protocols. My research initiated the study of new sublinear verification protocols, which became standard models of computation, covered in textbooks and surveys, and taught in courses around the world. These protocols span many fields, including coding theory, property testing, streaming algorithms, distribution testing, communication complexity, data structures, and learning theory. |
| Exploitation Route | The outcomes provide new ways to capitalise on classical and quantum verifiable computing. |
| Sectors | Digital/Communication/Information Technologies (including Software) |