Quantum communication improves private two-party distance estimates with low error
Quantum Advantage for Two-Party Differential Privacy
Cryptography and SecurityInformation Theory
Summary
Estimating how different two private inputs are without revealing them is a common problem in privacy. The authors show quantum communication can do this with much less error than classical methods when both parties must agree on an estimate. They find a quantum protocol that achieves constant error regardless of input size, which is a big improvement over classical privacy limits. This means quantum methods may offer stronger privacy guarantees without sacrificing accuracy.
What this means in practice
- •For cryptography engineers: Design two-party private protocols that achieve low error using quantum communication for sensitive input distance computations.
- •For quantum network developers: Develop secure two-party communication systems leveraging quantum privacy to improve accuracy in shared data computations.
A theory result. No direct application yet.
Authors
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.