Limits of Practical Sublinear Secure Computation

Elette Boyle, Yuval Ishai, Antigoni Polychroniadou

TL;DR

This paper introduces a formal framework to distinguish between "practical" and "impractical" sublinear-communication secure computation protocols for big data. It shows that while some natural problems admit efficient protocols, slight variations of these problems are provably "PIR-hard," meaning they inherently require significant computational cost, akin to the difficulty of NP-complete problems. The authors also introduce "semi-PIR," a relaxed notion of privacy, to capture intermediate hardness and demonstrate its implications for understanding the limits of secure computation.

What Problem Does This Paper Address?

In the age of big data, securely computing on massive datasets is crucial. Ideally, secure computation protocols should have sublinear communication complexity, meaning the amount of data exchanged between parties grows slower than the total input size. While fully homomorphic encryption (FHE) offers a general solution, it's computationally too expensive for practical use on large datasets. Weaker forms of encryption, like "somewhat homomorphic encryption" or single-server private information retrieval (PIR), also face significant computational bottlenecks, particularly on the server side.

However, a line of research has shown that for certain specific problems (like finding medians or shortest paths), efficient sublinear-communication protocols do exist, requiring minimal computational overhead. This raises a fundamental question: are these efficient protocols a general phenomenon, or are they exceptions? Can we systematically identify problems that are inherently "hard" to compute securely with sublinear communication, even with advanced cryptographic tools? This paper tackles this by developing a framework to classify problems based on their inherent difficulty for secure computation.

Methods

The core of this paper is the introduction of a framework for classifying secure computation problems based on their "PIR-hardness." PIR (Private Information Retrieval) is a fundamental problem where a client wants to retrieve an item from a database without revealing which item they're interested in. The authors define PIR-hardness for a functionality: if a secure protocol for that functionality implies a non-trivial PIR protocol on a large database, it's considered PIR-hard. This is analogous to how NP-completeness signifies inherent computational difficulty.

Key techniques include:

  • PIR-Hardness Framework: Defining PIR-hardness to establish a barrier on the local computational cost of secure protocols. This means that if a problem is PIR-hard, any sublinear-communication secure protocol for it will likely involve significant, non-amortizable computation.
  • Combinatorial Problem Variants: Analyzing specific combinatorial problems (like median, convex hull, shortest paths, set cover) and showing that while their standard versions might have "easy" protocols, slight variations (e.g., one-sided output) become PIR-hard.
  • Semi-PIR: Introducing a new, relaxed notion of privacy called "semi-PIR." In semi-PIR, the server can learn the client's query index only if the retrieved data has a specific value (e.g., 0). This allows for "intermediate hardness" classification and helps separate problems that are not fully PIR-hard but still challenging.
  • VC-Dimension Connection: For one-sided functionalities, the paper draws a connection between PIR-hardness and the VC-dimension of the function class, providing a combinatorial tool for proving hardness.
  • Reductions: Employing reductions to prove hardness. For example, showing that if a problem can be used to solve PIR efficiently, then that problem is PIR-hard. They also show reductions from PIR to semi-PIR and vice-versa to understand their relative strengths.
  • Local Compressibility: Identifying a property called "local compressibility" that allows for efficient, "easy" sublinear protocols for certain problems, even for their variants.

Datasets

Not discussed in the paper. The paper focuses on theoretical hardness results for abstract functionalities rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "PIR-hard" Barrier: The most significant insight is the formalization of "PIR-hardness" as a benchmark for inherent computational difficulty in sublinear secure computation. This provides a principled way to identify problems that are fundamentally hard to solve efficiently, even with advanced cryptography.
  • Subtle Variations Lead to Hardness: A surprising finding is how minor changes to seemingly simple problems (like switching from two-sided to one-sided output) can dramatically increase their computational hardness, making them PIR-hard. This highlights the sensitivity of secure computation complexity to problem formulation.
  • Semi-PIR as an Intermediate Step: The introduction of "semi-PIR" is crucial. It bridges the gap between problems that are "easy" (like standard PIR) and those that are "PIR-hard." This allows for a more nuanced understanding of problem complexity and suggests that some problems might be solvable with a slightly relaxed privacy model.
  • VC-Dimension as a Proof Tool: The connection between VC-dimension and PIR-hardness for one-sided functions offers a powerful combinatorial tool for proving hardness results, moving beyond purely cryptographic reductions.
  • Practical Implications: The framework helps guide researchers and practitioners by identifying which types of problems are likely to remain computationally expensive for secure computation, even with future algorithmic improvements in areas like FHE or PIR.

Key Results

  • PIR-Hardness Results: Several natural combinatorial problems, including one-sided variants of Median, Convex Hull, Single-Source Shortest Distance, and Approximate Set Cover, are proven to be PIR-hard. This implies that efficient sublinear-communication secure protocols for these specific variants are unlikely to exist without significant computational overhead.
  • Semi-PIR Hardness Results: A range of two-sided functionalities, such as Two-Sided Single Source Single Destination Shortest Path, Two-Sided Closest Destination Problem, and Two-Sided Nearest Neighbor Problem, are shown to be semi-PIR-hard. This means they require a relaxed privacy model (semi-PIR) for efficient secure computation.
  • Separation of Semi-PIR and PIR: The paper demonstrates that semi-PIR does not imply PIR in a strong sense, and certain problems are semi-PIR-hard but not PIR-hard. This suggests that semi-PIR captures a distinct level of complexity.
  • Local Compressibility: The paper identifies "local compressibility" as a property that allows for efficient, "easy" sublinear protocols for problems like Minimum Spanning Tree and certain Median Predicates, even for their variants.

Limitations and Future Work

  • VC-Dimension for Two-Sided Functions: While VC-dimension is effective for one-sided functions, the paper notes that the situation for two-sided functionalities is less understood, especially when outputs are not very short. A natural analogue of VC-dimension for two-sided functions is an open problem.
  • Multi-Party and Asymmetric Functionalities: The framework is primarily developed for two-party computation. Extending it to multi-party settings or functionalities where parties receive different outputs is a direction for future work.
  • Malicious Security: The current analysis focuses on semi-honest adversaries. Extending the framework to security against malicious adversaries is another important open question.
  • Semi-PIR to PIR Reductions: The paper shows that strong semi-PIR implies weak PIR, but the reduction is complex and uses non-trivial machinery (locally decodable codes) and multiple rounds. It's an open question whether a simpler or more direct reduction exists, or if ruling out such a reduction would imply a breakthrough in complexity theory.
  • Identifying "Easy" Problems: The framework identifies "hard" problems, but problems that escape these hardness notions are not necessarily easy. Identifying natural candidate problems that are "easy" despite not fitting the current framework and refining the hardness notions to capture them is an area for future research.

Summary updated

Abstract

Secure computations on big data call for protocols that have sublinear communication complexity in the input length. While fully homomorphic encryption (FHE) provides a general solution to the problem, employing it on a large scale is currently quite far from being practical. This is also the case for secure computation tasks that reduce to weaker forms of FHE such as “somewhat homomorphic encryption” or single-server private information retrieval (PIR). Quite unexpectedly, Aggarwal, Mishra, and Pinkas (Eurocrypt 2004), Brickell and Shmatikov (Asiacrypt 2005), and Shelat and Venkitasubramaniam (Asiacrypt 2015) have shown that in several natural instances of secure computation on big data, there are practical sublinear communication protocols that only require sublinear local computation and minimize the use of expensive public-key operations. This raises the question of whether similar protocols exist for other natural problems. In this paper we put forward a framework for separating “practical” sublinear protocols from “impractical” ones, and establish a methodology for identifying “provably hard” big-data problems that do not admit practical protocols. This is akin to the use of NP-completeness to separate hard algorithmic problems from easy ones. We show that while the previous protocols of Aggarwal et al., Brickell and Shmatikov, and Shelat and Venkitasubramaniam are indeed classified as being “practical” in this framework, slight variations of the problems they solve and other natural computational problems on big data are hard. Our negative results are established by showing that the problem at hand is “PIR-hard” in the sense that any secure protocol for the problem implies PIR on a large database. This imposes a barrier on the local computational cost of secure protocols for the problem. We also identify a new natural relaxation of PIR that we call semi-PIR, which is useful for establishing “intermediate hardness” of several practically motivated secure computation tasks. We show that semi-PIR implies slightly sublinear PIR via an adaptive black-box reduction and that ruling out a stronger black-box reduction would imply a major breakthrough in complexity theory. We also establish information-theoretic separations between semi-PIR and PIR, showing that some problems that we prove to be semi-PIR-hard are not PIR-hard.
BibTeX
@article{boyle2018limits,
  author = {Elette Boyle and Yuval Ishai and Antigoni Polychroniadou},
  title = {{Limits of Practical Sublinear Secure Computation}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
}

Loading related content...

Figure