⚛️ quantum physics

A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs

This paper demonstrates a quantum advantage in secure two-party computations by presenting protocols that achieve communication complexity independent of the output length under standard quantum assumptions, whereas classical cryptography is proven to require communication linear in the output size.

Original authors: Jiayu Zhang

Published 2026-10-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiayu Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of secure computing, two parties often need to solve a problem together without revealing their private secrets to one another. Imagine two millionaires who want to know who is richer without telling the other their exact bank balance. This is the essence of secure computation, a field dedicated to letting people collaborate on data while keeping that data hidden. For decades, researchers have built complex systems to make this possible, but they hit a stubborn wall when the answer to the problem is very long. If the result of a calculation is a massive file, the amount of information the two parties must exchange to keep the process secure grows just as large as that file. In the classical world of standard computers, this is an unavoidable cost; to get a secure answer, you must pay the price of sending the entire answer back and forth.

This limitation has long been considered a fundamental law of classical cryptography. However, a new study by Jiayu Zhang at the Zhongguancun Laboratory suggests that the rules change when we introduce the strange properties of quantum mechanics. The researcher has designed a new type of protocol that allows two parties to perform these secure calculations with long answers, yet the amount of information they need to send to each other depends only on the size of the question, not the size of the answer. This work demonstrates a genuine quantum advantage, proving that tasks once thought impossible in the classical realm can be achieved more efficiently using quantum tools.

The core of this discovery lies in a specific challenge called secure function sampling. In this scenario, one party, the client, wants to pick a random secret number and have the other party, the server, calculate a result based on that number. The catch is that the server must learn the result, but nothing else about the secret number, even if the server attempts to deviate from the protocol. In a classical setting, if the result is a huge string of data, the server must receive that entire string to verify the calculation, creating a communication bottleneck. The paper proves that no classical method can bypass this bottleneck without sacrificing security. If a classical protocol tries to send less information than the size of the result, a clever attacker could eventually figure out the secret number or forge the result.

To break this barrier, the researcher turned to quantum cryptography, specifically using a concept known as remote state preparation with verifiability. In this quantum approach, the client does not simply send a number; instead, they send a delicate quantum state that encodes the secret. The server performs the calculation on this quantum state. The brilliance of the method is that the server can only extract the final result if they follow the rules perfectly. If the server tries to hold onto extra information about the secret number to deviate later, the laws of quantum mechanics ensure that their attempt to measure or store that extra data will disturb the system in a detectable way. The client can run a series of checks to verify that the server did not peek. If the server passes these checks, the client knows the server only has the result and nothing more.

The paper details a step-by-step construction of this protocol. It begins with a simplified version where the client sends a superposition of two possible secret numbers. The server processes this superposition and returns part of the state. The client then performs a test to ensure the server did not store the original numbers. If the server is honest, the test passes, and the client learns which number was chosen while the server learns the result. The researcher then refined this into a robust, full-scale protocol that works for any efficient function, not just simple examples. This protocol relies on the existence of mathematical structures called collapsing hash functions, which are believed to be secure even against future quantum computers. The result is a system where the communication cost remains small and fixed, regardless of how massive the output data becomes.

Building on this foundation, the researcher extended the idea to general secure two-party computations, where both parties have private inputs and both want to learn the result of a joint calculation. By combining the new sampling method with existing techniques like garbled circuits, the paper shows how to create a complete system for secure collaboration. In one version, the parties can use quantum channels to send the necessary states. In another, more practical version, the researcher shows how to achieve the same result using only classical communication channels, provided they have access to specific quantum-resistant cryptographic tools. This classical-channel version is particularly significant because it means the efficiency gains do not require a fully functional quantum internet, only that the participants have local quantum capabilities and use standard communication lines.

The work stands as a rigorous proof that quantum mechanics offers a distinct advantage in reducing communication overhead for secure computing. The researcher did not merely suggest this was possible; they provided a concrete protocol and a mathematical proof that classical methods cannot achieve the same efficiency without compromising security. The study assumes the existence of certain cryptographic primitives, such as collapsing hash functions, which are widely believed to be secure. Under these assumptions, the paper establishes that the communication complexity can be made independent of the output length, a feat that is strictly impossible in the classical world. This finding opens a new path for designing efficient, secure systems for the future, where the size of the data being protected no longer dictates the cost of protecting it.

Technical Summary: A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs

1. Problem Statement

The paper addresses a fundamental limitation in classical cryptography regarding secure two-party computations (2PC) and secure function sampling (SFS) when the output length ( $m$ ) is significantly larger than the input length ( $n$ ).

In classical secure computation, protocols based on Fully Homomorphic Encryption (FHE) and succinct arguments typically achieve a communication complexity of $O(n + m)$ . While this is efficient relative to the time complexity of evaluating the function, it remains linearly dependent on the output size $m$ . The author notes that classical impossibility results (specifically adapting techniques from [30]) prove that achieving communication complexity independent of $m$ is impossible in the malicious setting for classical protocols, even with approximate security.

The core research question is: Can quantum cryptography reduce the communication complexity of secure computations with long outputs to be independent of the output length $m$ ?

2. Methodology and Technical Approach

The author proposes a series of quantum cryptographic protocols that achieve communication complexity polynomial in the input length $n$ and the security parameter, but independent of the output length $m$ . The methodology relies on viewing the problem through the lens of Remote State Preparation with Verifiability (RSPV) and utilizing specific quantum primitives.

2.1 Core Primitive: Secure Function Sampling (SFS)

The author first defines and solve the Secure Function Sampling (SFS) problem.

Goal: A client samples a random input $x \in \{0, 1\}^n$ and sends $f(x)$ to a server. The server learns $f(x)$ , but learns nothing more about $x$ (even if malicious), and the client learns nothing about the server's internal state.
Quantum Strategy: The protocol is constructed as a variant of RSPV.
- Toy Protocol: The client sends a superposition state $\frac{1}{\sqrt{2}}(|x_0\rangle + |x_1\rangle)$ to the server. The server evaluates $f$ to get $\frac{1}{\sqrt{2}}(|x_0\rangle|f(x_0)\rangle + |x_1\rangle|f(x_1)\rangle)$ and returns the input register. The client measures to collapse the state.
- Security Mechanism: To prevent a malicious server from storing $x$ , the protocol employs Hadamard basis tests. The client challenges the server to measure in the Hadamard basis. The author proves that if a server passes these tests with high probability, its state must be "basis-phase correspondence" form, meaning it cannot hold information about $x$ beyond what is implied by $f(x)$ .
- Forward-Succinctness: The initial construction reduces client-to-server communication to be succinct ( $O(n)$ ).
- Full Succinctness: To reduce server-to-client communication (which is initially long), the author employs a compiler based on succinct arguments of knowledge and collapsing hash functions. This allows the server to prove it holds a valid witness for the relation without revealing the long output directly, effectively "deleting" the long communication.

2.2 Generalization to Secure Two-Party Computation (2PC)

Building on the SFS protocol, the author constructs protocols for general 2PC where both parties have private inputs and outputs.

Secure Function Value Preparation (SFVP): They first adapt SFS to allow the client to choose the input $x$ (rather than having it sampled). This is achieved using Yao's garbled circuits. The client uses SFS to sample the "circuit encoding" (garbled circuit) and then sends the "input encoding" classically.
Malicious Client Security: To ensure security against a malicious client (who might send arbitrary inputs), the author introduces SFVP2. This protocol combines:
- Statistically-binding commitments.
- Collapsing hash functions.
- Succinct Zero-Knowledge Arguments of Knowledge (succinct-ZK-AoK).
- A "cut-and-choose" amplification technique to ensure the client holds a valid committed input.
Full 2PC Protocol: The final protocol involves:
1. A 2PC step to generate shared randomness and commitments.
2. Alice and Bob using SFVP2 to exchange garbled circuits for each other's functions.
3. Decryption to obtain outputs.
Classical-Channel Variant: The author further constructs a protocol using only classical channels. This replaces the quantum communication steps (sending superposition states) with existing RSPV protocols for specific state families (BB84 states and superposition states), assuming the existence of Noisy Trapdoor Claw-Free Functions (NTCF).

2.3 Assumptions

The protocols rely on the following cryptographic assumptions:

Collapsing Hash Functions: A quantum generalization of collision-resistant hash functions (e.g., implied by LWE or the Quantum Random Oracle Model).
Noisy Trapdoor Claw-Free Functions (NTCF): Used specifically for the classical-channel variant to enable RSPV without quantum communication.
One-Way Functions: Implied by collapsing hash functions, used for Yao's garbled circuits and commitments.

3. Key Contributions and Results

3.1 Quantum Advantage in Communication Complexity

The paper establishes a quantum advantage in the communication complexity of secure computations with long outputs.

Theorem 1.2 (Informal): Assuming collapsing hash functions, there exists a quantum protocol for SFS with communication complexity $poly(n, 1/\epsilon)$ , independent of the output length $m$ .
Theorem 1.3 & 1.4 (Informal): Similar succinct protocols exist for general 2PC, both with quantum communication and with classical communication (assuming NTCF).
Classical Impossibility: The paper proves (Theorem 1.1) that under the assumption of one-way functions, no classical protocol can achieve SFS with communication complexity independent of $m$ in the malicious setting. This confirms the quantum advantage is not merely a matter of better classical algorithms but a fundamental separation.

3.2 Protocol Constructions

SFS Protocol: A fully succinct protocol for secure function sampling with approximate security.
SFVP and SFVP2: Protocols for preparing secure function values where the input is client-chosen, secured against both malicious servers and malicious clients.
General 2PC Protocol: A succinct communication protocol for general secure two-party computation.
Classical-Channel 2PC: A protocol achieving the same succinctness using only classical communication, leveraging RSPV and NTCF.

3.3 Technical Innovations

Adaptation of RSPV Framework: The author adapts the framework from [57] to handle the specific constraints of SFS, introducing new "forms" of states (basis-honest, basis-phase correspondence) to prove soundness.
Succinct Testing for Two-Party Relations: A new primitive (a variant of the compiler in [8]) that allows a client to verify a server's claim about a relation $R(x, w)$ where $x$ is initially private, using succinct communication.
Amplification Techniques: Using sequential repetition and cut-and-choose to amplify approximate security (preRSPV) to full security (RSPV/SFS).

4. Significance and Claims

The paper claims to discover a new type of quantum advantage in cryptography. Unlike previous advantages (e.g., QKD, unclonability, or CVQC) which often focus on information-theoretic security or verification, this work demonstrates that quantum mechanics allows for communication efficiency in secure computation that is fundamentally unattainable classically.

Breaking the Output-Length Barrier: The primary significance is overcoming the "output-length dependency" in classical secure computation. In the classical world, achieving security against malicious adversaries requires paying a communication cost proportional to the output size. The quantum protocols presented bypass this, making the communication cost depend only on the input size and security parameters.
Approximate Security: The author explicitly states that their protocols achieve approximate security (with error tolerance $\epsilon$ ). They acknowledge that achieving negligible security loss remains an open problem and that their results are currently limited to approximate security.
Practicality: The paper does not claim immediate practicality. It notes that the protocols rely on assumptions like collapsing hash functions and NTCF, and the computational overhead of quantum operations is not analyzed in depth. The focus is on theoretical feasibility and the existence of a quantum advantage.

5. Limitations and Open Problems

The author modestly outlines several limitations and open questions:

Approximate vs. Negligible Security: The current constructions only achieve approximate security. Overcoming this to achieve negligible security loss is an open challenge.
Assumptions: The protocols rely on specific quantum assumptions (Collapsing Hash Functions, NTCF). Weakening these to post-quantum one-way functions or extending the problem to quantum circuits are open directions.
Communication Lower Bounds: The author notes that for insecure protocols, communication can be smaller than the input length. They question whether secure protocols can approach the communication complexity of the function itself ( $O(CC(f))$ ) without the security overhead.
Practical Implementation: The paper does not propose experimental implementations, focusing instead on theoretical construction and proof of concept.

In summary, this work provides a theoretical framework demonstrating that quantum cryptography can fundamentally alter the communication complexity landscape of secure computation, specifically enabling succinct protocols for functions with long outputs where classical cryptography is provably limited.