Quantum Advantage for Two-Party Differential Privacy
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 Ω(√n) error under pure differential privacy and Ω(√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 ε quantum differential privacy (QDP) and expected error at most 2/(sinh ε)+γ, for every γ>0. For approximate (ε, δ) QDP, an exact hockey-stick divergence calculation yields strictly smaller error, while preserving the O(1)-versus-Ω(√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.
Related
BibTeX
@misc{alabi2026quantum,
title = {{Quantum Advantage for Two-Party Differential Privacy}},
author = {Daniel Alabi and Emil T. Khabiboulline},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02113},
eprint = {2610.02113},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02113},
}
RIS
TY - UNPB
TI - Quantum Advantage for Two-Party Differential Privacy
AU - Daniel Alabi
AU - Emil T. Khabiboulline
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02113
UR - https://arxiv.org/abs/2610.02113
AB - 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 Ω(√n) error under pure differential privacy and Ω(√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 ε quantum differential privacy (QDP) and expected error at most 2/(sinh ε)+γ, for every γ>0. For approximate (ε, δ) QDP, an exact hockey-stick divergence calculation yields strictly smaller error, while preserving the O(1)-versus-Ω(√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.
ER -