Foundations of classical and quantum verifiable computing
Lead Research Organisation:
University of Warwick
Department Name: Computer Science
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
- University of Warwick (Lead Research Organisation)
- UNIVERSITY OF OXFORD (Collaboration)
- Georgetown University (Collaboration)
- University of California, Berkeley (Collaboration)
- Sorbonne University (Collaboration)
- IBM (Collaboration)
- Birkbeck, University of London (Collaboration)
- Microsoft Research (Collaboration)
- University of Cambridge (Fellow)
Publications
Gur T
(2020)
An Entropy Lower Bound for Non-Malleable Extractors
in IEEE Transactions on Information Theory
Gur T
(2021)
An Exponential Separation Between MA and AM Proofs of Proximity
in computational complexity
Dall'Agnol M
(2021)
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
Goldreich O
(2021)
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
in Theoretical Computer Science
Gur T
(2021)
On the Power of Relaxed Local Decoding Algorithms
in SIAM Journal on Computing
Arunachalam S
(2022)
Quantum learning algorithms imply circuit lower bounds
Chiesa A
(2022)
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
in Journal of the ACM
Title | Local algorithm analysis |
Description | Developed a new methodology for construction and analysing the performance of local algorithms. |
Type Of Material | Improvements to research infrastructure |
Year Produced | 2020 |
Provided To Others? | Yes |
Impact | The new methodology led to several breakthrough papers and new algorithms. |
Title | New techniques for average-case complexity |
Description | Developed a new tool that allows for constructing worst-case to average-case reductions via additive combinatorics. |
Type Of Material | Improvements to research infrastructure |
Year Produced | 2022 |
Provided To Others? | Yes |
Impact | The technique led to several important results in complexity theory. |
URL | https://arxiv.org/pdf/2202.08996.pdf |
Description | Birkbeck |
Organisation | Birkbeck, University of London |
Country | United Kingdom |
Sector | Academic/University |
PI Contribution | Conducted research in algorithms and coding theory. |
Collaborator Contribution | Participated in all stages of the research. |
Impact | Two papers, published at the best international conference in algorithms. Resolving several long-standing open problems in coding theory and algorithm, including a major, 16-years old open problem in local decoding algorithms. |
Start Year | 2020 |
Description | CNRS |
Organisation | Sorbonne University |
Country | France |
Sector | Academic/University |
PI Contribution | Led a research team in a collaboration culminating in paper that appeared in QIP 2021, the top international conference in quantum information. |
Collaborator Contribution | Participation in all stages of the research. |
Impact | Research collaboration aimed at exploring the potential of quantum machine learning. We identified a key bottleneck towards obtaining quantum speedups for machine learning and laid out a plan for overcoming it. |
Start Year | 2020 |
Description | Georgetown |
Organisation | Georgetown University |
Country | United States |
Sector | Academic/University |
PI Contribution | Participated in all steps of the research. |
Collaborator Contribution | Participated in all steps of the research. |
Impact | We obtained a new methodology for boosting knowledge. The work was accepted to STOC, the top conference on the foundations of computer science. |
Start Year | 2021 |
Description | IBM T. J. Watson Research Center |
Organisation | IBM |
Department | IBM T. J. Watson Research Center, Yorktown Heights |
Country | United States |
Sector | Private |
PI Contribution | Led a research team in a collaboration culminating in paper that appeared in QIP 2021, the top international conference in quantum information. |
Collaborator Contribution | Participation in all stages of the research. |
Impact | Research collaboration aimed at exploring the potential of quantum machine learning. We identified a key bottleneck towards obtaining quantum speedups for machine learning and laid out a plan for overcoming it. |
Start Year | 2020 |
Description | Microsoft Quantum |
Organisation | Microsoft Research |
Country | Global |
Sector | Private |
PI Contribution | Led a research team in a collaboration culminating in paper that appeared in QIP 2021, the top international conference in quantum information. |
Collaborator Contribution | Participation in all stages of the research |
Impact | Research collaboration aimed at exploring the potential of quantum machine learning. We identified a key bottleneck towards obtaining quantum speedups for machine learning and laid out a plan for overcoming it. |
Start Year | 2020 |
Description | Oxford |
Organisation | University of Oxford |
Country | United Kingdom |
Sector | Academic/University |
PI Contribution | Led a research team in a collaboration culminating in the paper that appeared in TQC 2021, one of the top international conference in quantum information. |
Collaborator Contribution | Participated in all steps of the research |
Impact | We devised a new method of delegating quantum computation in a scalable way, and we resolved a long-standing textbook open problem. |
Start Year | 2021 |
Description | UC Berkeley |
Organisation | University of California, Berkeley |
Country | United States |
Sector | Academic/University |
PI Contribution | We resolved the key open problem of showing hypercontractivity on high dimensional expanders. |
Collaborator Contribution | Participation in all stages of the research |
Impact | The work was accepted to STOC, the top conference in theoretical computer science. |
Start Year | 2021 |
Description | Consulting to Quanta Magazine |
Form Of Engagement Activity | A press release, press conference or response to a media enquiry/interview |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Public/other audiences |
Results and Impact | Consulted for Quanta Magazine reporter Ben Brubaker on several articles. |
Year(s) Of Engagement Activity | 2022,2023 |
Description | Global talent campaign |
Form Of Engagement Activity | A press release, press conference or response to a media enquiry/interview |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Public/other audiences |
Results and Impact | Interviewed for a campaign aimed at attracting global talent to the UK. |
Year(s) Of Engagement Activity | 2022 |
Description | Quanta Magazine |
Form Of Engagement Activity | A press release, press conference or response to a media enquiry/interview |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Public/other audiences |
Results and Impact | Interviewed for a highly popular international magazine on science. |
Year(s) Of Engagement Activity | 2022 |
Description | STEM Challenges campaign |
Form Of Engagement Activity | A magazine, newsletter or online publication |
Part Of Official Scheme? | No |
Geographic Reach | National |
Primary Audience | Undergraduate students |
Results and Impact | A campaign aimed to attract young people to research in STEM subjects. |
Year(s) Of Engagement Activity | 2022 |