Quantum Advantage for Two-Party Differential Privacy

AI summary

Overview

Research area: Quantum information and privacy, specifically two-party differential privacy for the Hamming distance function, with comparisons against classical information-theoretic lower bounds.

Technical level: Advanced. The paper assumes familiarity with differential privacy (including pure and approximate variants, max-divergence and hockey-stick divergence), quantum states and CPTP maps, Stinespring dilations, Gram matrices, and classical communication-complexity lower bounds.

Scope: The paper constructs an information-theoretic quantum protocol for two-party Hamming distance that achieves constant expected error under Klauck's honest, nonpreemptive, message-preserving privacy model, separated against the classical Ω(√n) and Ω(√n/log n) lower bounds, and delineates exactly which adversarial models do and do not admit this advantage.

What This Paper Is About

Alice holds an n-bit string x and Bob holds an n-bit string y, and both must output the same estimate of the Hamming distance HD(x,y) without revealing their inputs to each other. Classically, information-theoretic privacy forces large error — Ω(√n) under pure differential privacy and Ω(√n/log n) under strong approximate differential privacy — while O(1) error is reachable only through computational assumptions. The paper asks whether this accuracy loss is inherent to information-theoretic privacy or merely an artifact of classical, copyable communication, and answers that it is model-dependent: under Klauck's exact message-preserving honesty condition, quantum communication restores O(1) error information-theoretically.

Key Contributions

1. A common-output distributed-noise functionality. Alice and Bob independently sample cyclic geometric noise shares A, B over ℤ_(4n+1) and release Z = HD(x,y) + A + B (mod 4n+1), which is pure ε-differentially private with expected error at most 2/sinh ε. Privacy and accuracy follow from geometric arguments and interval decoding.

2. A guarded coherent quantum round-trip protocol achieving pure ε-QDP. The protocol is pure ε-quantum differentially private for the complete terminal view of every Klauck-honest nonpreemptive observer, communicates 2n + 2 + O(log n) = O(n) qubits and bits, and has expected error below 2/sinh ε + γ for every γ > 0.

3. Exact hockey-stick calibration for approximate privacy. Rather than reusing the pure-DP noise parameter, the authors compute the exact quantum hockey-stick divergence of the finite cyclic geometric distribution and select a unique α_n*(ε,δ) > ε, giving (ε,δ)-QDP with error at most 2/sinh α_n* + γ, strictly below 2/sinh ε + γ.

4. Formalization of three view models and the boundary of the advantage. The paper defines the prescribed-channel (PC), Klauck-honest nonpreemptive (KHNP), and retention-robust (RR) views, shows PC admits an exact classical reversible realization, and gives a randomized-response baseline with error √n/(2 sinh(ε/2)) + 1/(2 sinh²(ε/2)) for the RR model.

Main Findings

• Same-model quantum–classical separation: Under Klauck's message-preserving model, the quantum protocol attains O(1) information-theoretic error (constant ε, arbitrarily small constant γ) versus Ω(√n) for any classical protocol in the same model. This matches the accuracy classical protocols obtain information-theoretically only via computationally secure function evaluation.

• Approximate privacy strictly improves utility: For δ = o(1/n), the quantum protocol retains O(1) error while the classical lower bound is Ω(√n/log n). The approximate-privacy protocol does not merely inherit the pure-privacy guarantee; the allowed δ-budget is converted into a more concentrated noise distribution.

• The mechanism is noncopyability plus equal-Gram rigidity: Exact preservation of a family of non-orthogonal pure messages with Gram entries ⟨ψ_i|ψ_j⟩ = κ > 0 forces any Klauck-honest observer's retained complementary state to be independent of the protected input. A classical observer can copy every message and retain the full transcript, which is why the classical lower bounds of McGregor et al. still apply to classical KHNP protocols.

• The guard moves approximation into utility, not privacy: Every encoded state contains a small input-independent fallback branch with probability κ = γ/(n+γ). On the guard branch both parties output a fixed fallback value whose error is at most n, contributing less than γ to expected error. The construction is exactly private for every positive κ, avoiding a trace-distance limit that would be insufficient for pure QDP (pure privacy requires support containment).

• The advantage is model-specific, not a lower-bound violation: In the prescribed-channel view, classical reversible computation already realizes the functionality exactly, so no meaningful separation exists there. In the retention-robust view, a receiver can measure the projector onto the data-dependent support of the first message and abort, distinguishing adjacent inputs; this attack is excluded from KHNP because that receiver cannot subsequently return the prescribed coherent state.

• Retention-robust bound: Randomized response with geometric output noise gives pure ε-QDP in the retention-robust class (hence also (ε,δ)-QDP for every δ ≥ 0) with error √n/(2 sinh(ε/2)) + 1/(2 sinh²(ε/2)), matching the accuracy guarantees of McGregor et al. Improvement in the approximate retention-robust case is stated as open.

• No extra cryptographic resources are used: The protocol requires no computational assumption, trusted setup, prior entanglement, bounded-storage assumption, or secure erasure.

Methodology in Plain English

The authors build the protocol in layers. First, they design an idealized functionality in which each party adds its own independent random noise to the distance before the value is combined, so neither party can strip out all the noise from its own view. The noise is drawn from a cyclic geometric distribution on a cycle of length 4n+1, chosen so that the valid distance range {0, …, n} sits far from its wraparound copies and a nearest-interval decoder works cleanly. The expected size of each noise share is at most 1/sinh α, which yields the 2/sinh α error bound; the factor of two comes from needing both shares in the same released value to protect both inputs.

Second, they make the protocol quantum. A naive encoding of a classical input into orthogonal states would let an observer read or copy the label without disturbing the outgoing message. Instead, Alice sends a superposition in which a dominant branch carries the data and a small branch is completely independent of the input, so distinct encoded states have a nonzero overlap κ. Bob coherently computes the noisy release and returns the entire prescribed pure state, with the input and returned families engineered to have exactly the same Gram matrix. A rigidity lemma then shows that any environment retained by an observer who returns the exact prescribed state must be independent of the input — the quantum analogue of "you cannot copy an unknown non-orthogonal state without disturbing it."

Third, for approximate privacy, they compute the hockey-stick divergence on the finite cycle in closed form rather than invoking generic composition or continuity bounds. The likelihood ratio between neighbouring shifts takes only the values 1, e^α, and e^(-α), the region where the ratio exceeds e^ε is exactly one half-cycle, and summing that excess mass gives an explicit formula that increases continuously and strictly from 0 at α = ε to 1 as α grows. Inverting it at budget δ yields α_n*(ε,δ) > ε, and because the rigidity argument is independent of α, the improved noise distribution lifts to the quantum protocol without spending any additional δ-budget.

Why This Matters

Impact on research. The paper reframes the accuracy gap identified by McGregor et al. as a question about the physical nature of communication rather than about information-theoretic privacy itself. It shows that the classical Ω(√n) and Ω(√n/log n) bounds are not inherited by quantum protocols under exact message preservation, while carefully demonstrating that they do survive for classical protocols in the same model and for quantum protocols against retention-capable adversaries. It thereby identifies non-copyability and coherent information flow as privacy resources, not just communication-complexity or key-distribution resources, and it gives a clean taxonomy of view models (PC, KHNP, RR) in which such claims can be stated precisely. It also connects to the line of work showing that accurate computationally differentially private protocols for Hamming distance imply key agreement, by exhibiting a route to comparable accuracy with no cryptographic assumption at all.

Potential real-world applications (directions implied by the problem, not reported experiments in the paper):

• Privacy-preserving similarity or record-linkage computation between two organizations that each hold private records and must agree on a shared statistic.
• Distributed analytics where no trusted curator exists, such as joint fraud or anomaly detection between institutions.
• Proximity and contact-matching computations where both sides must receive the same answer.
• Benchmarking or measurement collaborations in which two parties need a common noisy distance without a trusted intermediary.

Industry relevance. The result speaks to any setting where a trusted curator is unavailable and where classical secure computation is unattractive because it relies on computational assumptions, trusted setup, or key infrastructure. The paper is explicit that the guarantee holds under an idealized communication model permitting exact real-valued private randomness and arbitrary exact local unitaries, and that local computational complexity and finite-precision synthesis are not accounted for — so deployment claims would need those gaps closed.

Future Directions

• Retention-robust quantum accuracy: Whether quantum communication improves accuracy under fully retention-robust (all-CPTP) security is stated as open. The measurement-and-abort obstruction is formalized, and the approximate-privacy case for the retention-robust model is explicitly left open.

• Verification of quantum states in KHNP: Section VI is described as discussing the interpretation of the privacy models, the pure-versus-approximate distinction, and the possibility of verifying quantum states in the KHNP model.

• Closing the implementation gap: The analysis assumes exact real-valued randomness and arbitrary exact local unitaries, leaving local computational complexity, finite-precision synthesis of the guarded states, and the robustness of the equal-Gram rigidity argument under realistic imperfections unaddressed.

• Extending beyond Hamming distance: The paper treats Hamming distance specifically; whether the guarded-round-trip and equal-Gram technique yields analogous separations for other natural sensitivity-one statistics is not reported.

Target Audience

Researchers in quantum information and theoretical cryptography working on privacy models, quantum differential privacy, and two-party computation; theoretical computer scientists familiar with the McGregor et al. lower bounds who want to know how they interact with quantum communication; and advanced graduate students who already know differential privacy and the basics of quantum states, CPTP maps, and Stinespring dilations. Readers seeking practical protocols or empirical evaluations will not find them here, since the work is purely theoretical and explicitly idealized.

Authors’ 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.