arXiv:2610.02113
Quantum Advantage for Two-Party Differential Privacy
Daniel Alabi, Emil T. Khabiboulline
Abstract
We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length $n$, information-theoretic protocols require $Ω(\sqrt{n})$ error under pure differential privacy and $Ω(\sqrt{n}/\log n)$ error under strong approximate differential privacy, whereas computational security permits $O(1)$ error. In Klauck's honest, nonpreemptive, message-preserving model, we give an $O(n)$-communication quantum protocol with pure $\varepsilon$ quantum differential privacy (QDP) and expected error at most $\frac{2}{\sinh \varepsilon}+γ$, for every $γ>0$. For approximate $(\varepsilon, δ)$ QDP, an exact hockey-stick divergence calculation yields strictly smaller error, while preserving the $O(1)$-versus-$Ω(\sqrt{n}/\log n)$ separation for $δ=o(1/n)$. Thus, quantum communication achieves $O(1)$ information-theoretic error, matching the accuracy available classically only under computational assumptions. The main construction uses a guarded coherent round trip and an equal-Gram rigidity principle that prevents an honest player from retaining input-dependent complementary information. We separate this model from weaker prescribed-channel privacy, which already admits an exact classical realization, and from fully retention-robust security, against which measurement-and-abort attacks remain possible. Therefore, we identify preservation of non-orthogonal quantum messages as a resource for privacy.
AI Summary
The paper asks whether quantum communication can overcome classical information-theoretic accuracy limits for two-party differentially private Hamming-distance estimation, with both parties required to produce the same output. It studies privacy of terminal views under Klauck-honest nonpreemptive (KHNP) strategies: observers may retain private systems but must preserve every prescribed outgoing message exactly and complete the protocol. For inputs of length $n$, it constructs a pure $\varepsilon$-quantum-DP protocol using $O(n)$ communication and achieving expected absolute error below $2/\sinh\varepsilon+\gamma$ for any $\gamma>0$. For suitable constant privacy parameters, this contrasts with classical KHNP lower bounds of $\Omega(\sqrt n)$ under pure privacy and $\Omega(\sqrt n/\log n)$ under strong approximate privacy, with $\delta=o(1/n)$. The construction combines independent cyclic-geometric noise shares with a coherent round trip. A small input-independent guard makes all input encodings nonorthogonal. Equality of the incoming and prescribed outgoing Gram matrices forces an exactly message-preserving observer’s retained complementary state to be input-independent. Privacy then follows by postprocessing an ideal noisy-release functionality. An exact finite-cycle hockey-stick-divergence calculation calibrates a larger noise parameter $\alpha_n^\star>\varepsilon$, giving the approximate-privacy error bound $2/\sinh\alpha_n^\star+\gamma$. The separation depends on exact message preservation, classical inputs and private random tapes, and idealized exact local operations. The protocol fails against measurement-and-abort attacks and provides neither malicious nor simulation-based security. Weaker prescribed-channel privacy already permits an exact classical realization. For arbitrary retention-capable adversaries, the paper supplies a classical $O(\sqrt n)$-error baseline; a quantum accuracy advantage remains open.
using GPT 5.6 Sol, the authors optimized the noise mechanism to obtain a more accurate approximate DP protocol.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 15 + 7 pages, 2 figures. Also on ePrint