CS Paper Radar

Zero Knowledge Proofs in Quantum Networks

Tuhin Paul, Srijani Das, Manasi Patra, Ramij Rahaman

cs.CR quant-phcs.SImath-ph ·submitted 2026-09-28 14:58 UTC · v1

Abstract

Zero-knowledge proofs (ZKPs) enable the verification of a statement without revealing any information beyond its validity and constitute a fundamental primitive in cryptography and information theory. However, existing constructions rely on computational assumptions and are predominantly confined to bipartite settings, leaving their information-theoretic realization in bipartite or network scenarios largely unexplored. Here we develop a framework for zero-knowledge verification based on the indistinguishability of quantum states under operational constraints. Exploiting the fundamental limitations imposed by local operations, we show that a verifier is inherently restricted from extracting information about the underlying state while retaining the ability to verify correctness. We construct explicit protocols for multiparty quantum networks that achieve information-theoretic security, ensuring that no subset of collaborating parties can gain knowledge beyond the validity of the statement, independent of their joint computational power.

Comment
18 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Secure Information Flow in Quantum Programs

cs.CR quant-phcs.PL ·2026-11-10 ·Zhicheng Zhang, Mingsheng Ying, Lirong Xia
theory similarity 0.71
Abstract · 61 pages, 13 figures

Information-flow security aims to prevent the leakage of confidential information through program execution. This problem becomes fundamentally subtler for quantum programs, because their states may involve superposition and entanglement, and their executions may involve intricate interactions between classical and quantum variables. This paper develops semantic foundations and verification methods for secure information flow in quantum programs. We formulate two notions of information-flow security. The first is a noninterference-based definition that naturally generalizes its classical counterpart. The second is a simulation-based definition that explicitly models an attacker, providing a clear operational interpretation of security. We prove that these two notions are equivalent. To verify the information-flow security of quantum programs, we develop a proof framework based on quantum Hoare logic. A key challenge is that the standard self-composition technique, which expresses information-flow security in Hoare logic by composing a program with a renamed copy of itself, fails in the quantum setting due to an obstruction analogous to the no-cloning theorem. To overcome this challenge, we introduce self-conjugation, a novel technique that leverages the deferred measurement principle and properties of unitary operations. We demonstrate our framework on examples drawn from the quantum one-time pad, quantum error correction, and anonymous entanglement generation.

0.18

Reducing Provers in Distributed Quantum Verification

cs.DC quant-ph ·2026-11-09 ·Alex Della Schiava, Atsuya Hasegawa, François Le Gall, Harumichi Nishimura
similarity 0.69
Abstract · 22 pages (including references), 4 figures. Submitted to SIROCCO 2027

In the distributed quantum Merlin-Arthur ($\mathsf{dQMA}$) model introduced by Fraigniaud, Le Gall, Nishimura, and Paz (ITCS 2021), a network of quantum computers verifies a global property with the aid of a quantum proof supplied by an untrusted prover. While the nodes are computationally unbounded, the challenge is to limit proof size and the communication required for verification. In this paper, we consider the model of Hasegawa, Kundu, and Nishimura (PODC 2024), where the proof must be unentangled across nodes, and define its extension to $k$ unentangled provers, denoted by $\mathsf{dQMAS}(k)$. In this setting, we investigate the proof size per node and the communication costs of reducing the number of provers. Our first result reduces the number of provers from $k$ to two, doubling the proof size without additional communication. Moreover, with four additional rounds, we can reduce the number of provers from $k$ to one, using at most three times the original local proof size plus a logarithmic term in the number of nodes. Finally, we establish amplification for perfectly complete protocols. In this regime, a single prover suffices with a constant-factor overhead in our reductions, yielding $\mathsf{dQMAS} = \mathsf{dQMAS}(k)$.

0.21

Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

cs.CC quant-phcs.CR ·2026-10-27 ·Atul Mantri
theory similarity 0.67
Abstract

It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.

0.30

EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity

cs.CR quant-ph ·2026-09-10 ·Atul Mantri
similarity 0.67
Abstract

EFI pairs (Brakerski, Canetti, and Qian, ITCS 2023) and one-way puzzles (Khurana and Tomer, STOC 2024) are the leading candidates for the minimal assumption of quantum cryptography. The first are efficiently preparable quantum states, statistically far yet computationally indistinguishable; the second are classical puzzles, easy to sample and hard to solve. One-way puzzles imply EFI pairs, and whether the converse holds is open. We construct a single classical oracle relative to which one-way puzzles do not exist, even with an unbounded verifier, while an EFI pair survives every distinguisher that queries the oracle classically throughout and holds advice about it, making its one superposition query at the end. The oracle answers every question about the output probabilities of quantum samplers, which removes the puzzles, and hides a Haar-random half-dimensional subspace. To prove security we reduce it to communication complexity. An adversary whose knowledge of the subspace arrives as classical query answers can be simulated inside a two-party protocol against the party holding it, so it does no better than the best classical protocol for Vector-in-Subspace (Klartag and Regev, STOC 2011), whatever the oracle computes. That argument does not cover the superposition query, which we bound instead using tools from random matrix theory. The same attack gives a classical simulation of any quantum party in a classical-message protocol with no entanglement shared in advance, so relative to the oracle there is no proof of quantumness either. Quantum polynomial time therefore offers no advantage on any task with classical inputs and outputs, while the two quantum states stay indistinguishable. We state conjectures on removing the restriction on superposition queries.

0.42

From Claws to Conferences: Device-Independent Key Agreement Beyond Non-Signaling

cs.CR quant-ph ·2026-11-03 ·Suvradip Chakraborty
theory similarity 0.67
Abstract

Device-independent conference key agreement (DI-CKA) allows a group of users to establish a common secret key without trusting the internal operation of their quantum devices. Existing DI-CKA protocols derive their security from multipartite Bell tests and therefore require the device components not to communicate during each round. We present, to the best of our knowledge, the first DI-CKA protocol that removes this non-signaling assumption: all interfaces and their mutual communication are treated as one untrusted device, which only has to be quantum polynomial-time while the protocol runs. Assuming that the Learning With Errors (LWE) problem is hard for quantum algorithms with quantum advice during the execution, we prove finite-size security against coherent attacks, in which the device may keep quantum memory and correlate and adapt its behavior across rounds. For two parties the protocol is a computational DI-QKD protocol with an explicit finite-size proof against coherent attacks. Technically, we lift the claw state underlying the classical-verifier test of Brakerski et al.\ (FOCS 2018) to multipartite entanglement, obtaining a \emph{GHZ-correlated claw state}. %that is prepared with one coherent claw-free function evaluation and $N-1$ CNOT gates. We then introduce the \emph{collective adaptive hardcore bit}, a multiparty generalization of the adaptive hardcore bit of Brakerski et al.\ and show that it follows from the original property by a tight reduction. Combined with Jordan's lemma, an entropic uncertainty relation, and entropy accumulation, this certifies smooth min-entropy of the key against an external quantum adversary. Our protocol achieves \emph{everlasting security}: LWE needs to hold only during the execution, because the final key is statistically secure and its secrecy persists even if LWE is broken after the protocol ends.

0.29

Secure Quantum Handshakes: Quantum Network Verification Via Simon's Algorithm

cs.NI quant-ph ·2026-10-08 ·Reece Robertson, Sejal Patil, Sebastian Deffner
similarity 0.66
Abstract

Quantum networking represents the future of secure communication, enabling fundamentally new capabilities through quantum information exchange. However, these networks require secure, high-fidelity quantum communication channels, and they require every participating node to be a genuine quantum device. Currently, there is no reliable method to verify whether clients entering a quantum network truly possess quantum computational capability and are connecting over robust channels. In this work, we introduce a client-validation protocol that functions as a proof-of-quantum-capability handshake. Our protocol secures a quantum network against classical spoofers, noisy quantum computers, and genuine quantum devices connecting with the network over noisy or insecure channels. We validate the efficacy of this protocol through numerical simulations under erasure, dephasing, and depolarizing noise models.

0.10

A Post-Quantum Interactive Hashing Theorem

cs.CR quant-ph ·2026-11-04 ·Céline Chevalier, Laurent Holin, Quoc-Huy Vu
theoryhot direction similarity 0.66
Abstract

Interactive hashing, introduced by Ostrovsky, Venkatesan, and Yung [OVY93], is a building block in many cryptographic protocols, including perfectly hiding commitments from one-way permutations [NOVY92]. Its multi-output generalization is a key ingredient in constructions of statistical zero-knowledge arguments for NP and statistically hiding commitments from arbitrary one-way functions [NOV06,HR07]. In this note, we give a post-quantum security proof for this multi-output interactive hashing protocol with arbitrary relations.

0.21

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

cs.CR quant-ph ·2026-09-30 ·Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček, Yunchao Liu
similarity 0.66
Abstract

We construct protocols for classically verifiable quantum advantage and classical verification of $\mathsf{BQP}$ computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of $\mathsf{BQP}\neq\mathsf{BPP}$, we construct a two-message quantum-advantage protocol that is efficiently and publicly verifiable. Our result can be viewed as a rigorous cryptographic foundation for the heuristic quantum advantage proposals based on \emph{peaked random circuit sampling} of Aaronson and Zhang (arXiv:2404.14493). We also construct two simple protocols for classically verifying arbitrary $\mathsf{BQP}$ computations. The first protocol is privately verifiable and assumes only the existence of qiO. This gives a rare example of a nontrivial cryptographic application of (quantum) iO that does not make additional computational hardness assumptions. The second protocol additionally assumes post-quantum one-way functions and is \emph{publicly verifiable}. To our knowledge, this is the first publicly verifiable protocol for classical verification of $\mathsf{BQP}$ computations under computational assumptions in the standard model. As qiO is the basis for our results, we propose an approach to constructing qiO by adapting the local-mixing framework of Canetti--Chamon--Mucciolo--Ruckenstein.

0.26