TL;DR
This paper introduces a new, more realistic definition of quantum zero-knowledge that accounts for the limited quantum memory of near-term quantum devices. They show that achieving this "space-bounded" zero-knowledge is possible for certain types of verifiers (logarithmic space) but impossible for more powerful verifiers (super-logarithmic space) in a fully black-box setting.
What Problem Does This Paper Address?
Zero-knowledge proofs are a cornerstone of modern cryptography, allowing a prover to convince a verifier of a statement's truth without revealing any extra information. The traditional definition of quantum zero-knowledge (QZK) allows a simulator to perfectly mimic the verifier's view, but it doesn't restrict the simulator's computational resources, particularly its quantum memory. This is problematic for near-term quantum computers, which have limited qubit capacity. The authors argue that the existing QZK definition is too permissive and not practical for these emerging devices. They aim to bridge this gap by proposing a fine-grained definition that considers the quantum memory used by both the verifier and the simulator.
Methods
The core of this work lies in defining and analyzing a new notion called (s, f)-space-bounded quantum zero-knowledge. This definition requires that a malicious verifier using s qubits of quantum memory can be simulated by a quantum polynomial-time algorithm using at most f(s) qubits. They explore three variations of this notion:
- Fully Black Box QZK: The simulator has oracle access to the verifier's circuit.
- Black Box QZK: The simulator has oracle access to the purified version of the verifier's circuit (a standard technique in QZK).
- Non Black Box QZK: The simulator can depend arbitrarily on the verifier's code.
The paper then establishes feasibility and impossibility results for these notions, particularly focusing on the fully black-box setting. Key techniques include:
- Rewinding: A standard technique in QZK proofs, adapted to the quantum setting.
- State Recovery: Strategies to recover previous states of the verifier, dealing with the no-cloning theorem.
- Subspace States: Utilizing specific quantum states with properties of unclonability and efficient testing, crucial for their impossibility proof.
- Hybrid Arguments: A common proof technique in cryptography to show computational indistinguishability between different distributions.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The practical constraint of quantum memory: The paper highlights that the theoretical definition of QZK doesn't align with the practical limitations of current and near-term quantum hardware. This motivates the need for resource-aware definitions.
- Logarithmic space verifiers are feasible: The authors demonstrate that achieving space-bounded QZK is possible for verifiers with only logarithmic quantum space, assuming the existence of post-quantum one-way functions. This is a positive result for certain practical scenarios.
- Super-logarithmic space verifiers pose a challenge: For verifiers with more substantial quantum memory (super-logarithmic space), they prove that fully black-box QZK is impossible. This is a significant negative result, suggesting that achieving QZK in this setting might require non-black-box simulation techniques or different assumptions.
- The role of purification: The paper points out that the standard "purification" technique used in QZK proofs can significantly increase the quantum memory required by the simulator, making it incompatible with space-bounded definitions.
Key Results
- Feasibility for Logarithmic Space Verifiers: They construct constant-round, fully black-box (s, f)-space-bounded QZK protocols for NP, where s = O(log λ) and f(s) = 2s, based on post-quantum one-way functions.
- Impossibility for Super-Logarithmic Space Verifiers: Assuming post-quantum one-way functions, they show that fully black-box (s, f)-space-bounded QZK protocols for languages outside BQP do not exist when s = ω(log λ).
Limitations and Future Work
- Focus on Quantum Memory: The paper primarily focuses on the quantum memory resource. Future work could explore other resource constraints, such as circuit depth or gate complexity.
- Non-Black-Box QZK: The paper leaves the feasibility of non-black-box (s, f)-space-bounded QZK for polynomial f as an open problem. This is a promising direction, as non-black-box models often allow for stronger results.
- NISQ-Safe Definitions: The authors suggest exploring new definitions of zero-knowledge protocols that are secure against weaker quantum adversaries, potentially tailored for Noisy Intermediate-Scale Quantum (NISQ) devices. This could involve considering fixed gate sets or architectures.
- Other Cryptographic Protocols: The paper proposes extending their space-bounded simulation notions to other cryptographic primitives like quantum oblivious transfer and quantum secure computation.
Summary updated