Time-Delayed Publicly Verifiable Quantum Computation for Classical Verifiers DOI: XXXXXXX.XXXXXXX Conference: Conference on Computer and Communications Security; November 15–19, 2026; The Hague, The Netherlands ISBN: 978-1-4503-XXXX-X/18/06 CCS: Security and privacy Cryptography CCS: Security and privacy Security services
Ameer Mohammed, Aydin Abadi, Jaffer Mahdi · 2026
Read Time-Delayed Publicly Verifiable Quantum Computation for Classical Verifiers DOI: XXXXXXX.XXXXXXX Conference: Conference on Computer and Communications Security; November 15–19, 2026; The Hague, The Netherlands ISBN: 978-1-4503-XXXX-X/18/06 CCS: Security and privacy Cryptography CCS: Security and privacy Security services by Ameer Mohammed, Aydin Abadi, Jaffer Mahdi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23516.txt.
Introduction
Mohammed, Abadi, and Mahdi tackle delegation of quantum computation to an untrusted server that a classical user, and anyone else, must be able to check. Instead of demanding instant public verification, they delay release of the verification key until the work and its proof are certainly done. Time-lock puzzles turn a two-round private scheme into a practical non-interactive public one under standard post-quantum assumptions.
Catalog record
| CREATOR | Ameer Mohammed, Aydin Abadi, Jaffer Mahdi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75253 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.23516
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Time-Delayed Publicly Verifiable Quantum Computation for Classical Verifiers DOI: XXXXXXX.XXXXXXX Conference: Conference on Computer and Communications Security; November 15–19, 2026; The Hague, The Netherlands ISBN: 978-1-4503-XXXX-X/18/06 CCS: Security and privacy Cryptography CCS: Security and privacy Security services Ameer Mohammed, Aydin Abadi, Jaffer Mahdi Abstract . Publicly verifiable delegation is a well-known problem involving a user who wishes to outsource a resource-intensive computational task to a more powerful but potentially untrusted server such that any other party is able to efficiently check the veracity of the computation’s result. This problem has been extensively studied in the classical domain where the user and server are both non-quantum machines. However, the problem becomes more challenging when the classical user wants to delegate a quantum circuit to a single prover with quantum-computing capabilities. Previous solutions have resorted to using impractical or non-standard cryptographic solutions (e.g. indistinguishability obfuscation) to achieve this requirement. In this work, we relax the requirement to have time-delayed publicly verifiable proofs, where the verification key is made known to the public only when the computation (and its proof) are guaranteed to have been completed. We propose a practical non-interactive scheme leveraging commitment schemes and time-lock puzzles, which can be efficiently realized through well-established and standard post-quantum assumptions. The main idea of our technique lies in using time-lock puzzles to compile a 2-round privately verifiable scheme into a non-interactive publicly verifiable scheme with timestamped proofs, outsourcing not only the quantum computation but the puzzle solving as well. Security is proven in the quantum random oracle model with a common reference string (CRS). \DeclareSourcemap \maps [datatype=bibtex, overwrite] \map \step [fieldsource=url, match= \regexp \x 5F, replace= \regexp \x 5F] 1. Introduction An important problem when outsourcing a client’s computation to a more capable server is ensuring that the result that is computed and returned by the server is correct and efficiently verifiable by the client. In particular, the verification complexity should be much lower than that required to run the actual computation. This problem has been well studied when the server and client are both non-quantum machines, and, in fact, can be realized through the use of succinct arguments for \mathbf{NP} 61 ; 74 . With quantum computing on the horizon and likely to be offered initially as a pay-per-use service by major companies, it is vital to prepare for a scenario where users with classical computers want to delegate complex computations to powerful quantum servers and efficiently verify the results produced by the servers– a task now known in the literature as Classical Verification of Quantum Computation (CVQC). In the breakthrough work of Mahadev 67 , it was demonstrated that such a scheme does indeed exist assuming the post-quantum hardness of Learning With Errors (LWE). This was further extended 28 ; 11 to add succinctness, in which the verifier’s time complexity is \operatorname{poly}(\log T) where T is the time to execute the delegated quantum computation. In addition, while the original protocol consisted of 4 rounds of communication, this was reduced to 2 rounds or less (1 round with setup) while still preserving negligible soundness through parallel repetition 28 ; 7 ; 11 . More relevant to this work, some applications demand public verifiability , an additional property allowing anyone (not just the delegator) to verify the result of the computation. The usual desired setting of publicly verifiable non-interactive verifiable computation involves a prover who wishes to publish a single-message proof convincing any verifier that C(x)=y for some program or circuit C over input x . To avoid triviality in the fully classical setting, the proof needs to be relatively “short” such that verification is faster than re-executing C(x) and checking the result, otherwise the verifier has no need to delegate and can instead perform the computation itself. The proof size requirement, while preferred, is not highly prioritized when the prover is quantum, as C is not necessarily efficiently computable by the verifier. The standard go-to approach to solve this problem is by using succinct non-interactive arguments (SNARGs) for \mathbf{NP} (or even \mathbf{P} ), which can be realized from LWE 29 . However, our delegated computation is quantum, and thus one needs a SNARG for \mathbf{BQP} for this approach to work. The work of Bartusek and Malavolta 13 provides one means to achieve this goal, and, in fact, they obtain SNARGs for \mathbf{QMA} , the quantum analogue of \mathbf{NP} , (and hence \mathbf{BQP} ) which would imply publicly verifiable CVQC. Their results rely on quantum null-iO, which is derived from non-standard cryptographic primitives, e.g., VBB obfuscation. In contrast, our goal is to prioritize practicality over theoretical feasibility, and therefore, we wish to avoid such strong assumptions. Ideally, we would like to base the scheme on falsifiable assumptions 79 ; 39 , which are those that can be tested in a security game against an efficient challenger. Examples include one-way functions, trapdoor permutations, DDH, and LWE. Notably, indistinguishability obfuscation is not falsifiable 52 . Roughly speaking, such assumptions are often preferred, as they can be efficiently proven/refuted and therefore instill more confidence when used as building blocks for more advanced schemes. The very recent related work of Bartusek et al. 10 comes close to achieving this by showing a publicly verifiable CVQC that is based on LWE but they do so under the classical oracle model 12 , which idealizes the notion of obfuscation for classical circuits and can be heuristically instantiated with iO. 1.1. Our Result We seek to make progress toward addressing the following question: Does a publicly verifiable delegation protocol for quantum computation with a classical verifier exist under falsifiable assumptions in the random oracle model? We answer the question affirmatively with a minor adjustment to the standard publicly verifiable computation setting. Unlike standard publicly verifiable computation, where the verification key is available from the outset, our scheme delays the release of this capability. Specifically, public verifiability is enabled only after a time delay \Delta , where \Delta>O(T) , and only for proofs generated before time \Delta . Until that point in time, the scheme operates in a privately verifiable mode. Theorem 1.1 (informal). Under the post-quantum LWE assumption, there exists a non-interactive time-delayed publicly verifiable CVQC protocol for problems in BQP with computational soundness in the common reference string (CRS) and quantum random oracle model (QROM). A scheme in the common reference string (CRS) model, as opposed to the plain model, would allow all parties to have access to a string that was honestly generated by some trusted setup algorithm. We note that the CRS is not uniformly random but is deliberately structured, so we cannot simply replace the need for a CRS with an output of the random oracle. Our technique of employing time-lock puzzles to render a CVQC protocol publicly verifiable is also of independent interest. To the best of our knowledge, this is the first instance in which time-lock puzzles are used to transform a designated-verifier verifiable quantum computation scheme into a publicly verifiable one. We expect that this technique can be generalized to compile any privately verifiable computation scheme into a time-delayed, publicly verifiable one, even in the classical (non-quantum) setting. However, since standard publicly verifiable delegation schemes based on falsifiable assumptions already exist in the classical