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.