TL;DR
This paper establishes a fundamental equivalence: any computationally differentially private (CDP) protocol that can accurately estimate the inner product of two vectors implies the existence of Oblivious Transfer (OT), a powerful cryptographic primitive. This means that achieving even modest accuracy in private inner product computation is as hard as achieving OT, closing a significant gap in our understanding of private distributed computation.
What Problem Does This Paper Address?
In the realm of privacy-preserving data analysis, especially when data is distributed across multiple parties, ensuring individual privacy while enabling useful computations is a major challenge. Differential Privacy (DP) offers strong privacy guarantees, but in a distributed setting, achieving high accuracy for functions like the inner product is significantly harder than in a centralized model. While computational DP (CDP) offers more power by relying on cryptographic assumptions, it was unclear whether powerful primitives like Oblivious Transfer (OT) were strictly necessary for achieving good accuracy in distributed CDP protocols for non-Boolean functions like the inner product. Specifically, it was unknown if protocols with small additive error (e.g., $O(n^{1/6})$) could be constructed without relying on OT.
Methods
The core of this work is a reduction from CDP inner-product protocols to Oblivious Transfer. The authors construct a protocol that, given an accurate CDP inner-product protocol, can be used to build an Approximate Weak Erasure Channel (AWEC). This AWEC protocol is then shown to be convertible into a Weak Erasure Channel (WEC), which in turn can be amplified into a full Oblivious Transfer protocol. A key technical contribution is the proof that "erasures" in their construction are "hidden," meaning a party cannot tell if an erasure occurred without revealing private information. This involves a novel technical lemma (Lemma 2.3) that is crucial for the proof. The authors also leverage existing results on converting AWEC to WEC and WEC to OT.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Inner Product as a Cryptographic Primitive: The paper demonstrates that the inner product functionality, when computed under computational differential privacy with a certain accuracy, is as powerful as Oblivious Transfer. This elevates the inner product from a mere computational task to a primitive that can imply powerful cryptographic capabilities.
- The Power of "Hidden Erasures": A crucial technical insight is the construction of a protocol where "erasures" (a mechanism to obscure information) are hidden from one of the parties. This is achieved by carefully injecting noise and leveraging the properties of CDP.
- Bridging Accuracy Gaps: The work shows that for the inner product, achieving a relatively small additive error (like $O(n^{1/6})$) is equivalent to achieving OT. This implies that any CDP protocol for inner product with such accuracy must be using a primitive as strong as OT, effectively closing the gap between what's achievable with weaker primitives (like Key Agreement) and OT for this specific functionality.
- Conceptual Simplicity: Despite constructing a stronger primitive (OT) compared to prior work (which constructed Key Agreement), the authors note that their proof is conceptually simpler, partly due to the nature of the attacker model in OT versus Key Agreement.
Key Results
- Equivalence: The paper proves that any $(ε, δ)$-CDP two-party protocol that estimates the inner product over $\{-1,1\}^n \times \{-1,1\}^n$ up to an additive error of $O(n^{1/6})$ can be used to construct an Oblivious Transfer protocol.
- Implication: This result implies that without assuming the existence of OT, it's impossible to construct a CDP protocol for the inner product with a constant or even sub-polynomial additive error.
- Accuracy Regime: The result establishes an equivalence for protocols with additive error up to $O(n^{1/6})$, which is a significant improvement over previous results that only showed necessity for weaker primitives like Key Agreement.
Limitations and Future Work
- Accuracy Gap: While the paper closes the gap to OT for $O(n^{1/6})$ accuracy, it leaves open the question of whether OT is necessary for accuracy regimes between $O(n^{1/6})$ and $O(\sqrt{n})$.
- Generalization: The paper focuses on the inner product functionality. A major open challenge is to extend this understanding to characterize other CDP distributed computations and find more general conditions under which they imply powerful cryptographic primitives.
- Confidence Levels: The main result requires high confidence (0.999), while prior work on Key Agreement held for lower confidence regimes.
Summary updated