Foundations of classical and quantum verifiable computing

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.

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.