More is Merrier: Relax the Non-Collusion Assumption in Multi-Server PIR

More is Merrier: Relax the Non-Collusion Assumption in Multi-Server PIR

Speakers: Tiantian Gong, PhD Student, Purdue University; Ryan Henry; Alexandros Psomas; Aniket Kate

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=i7aVA8gmFPY

Overview

This talk, "More is Merrier: Relax the Non-Collusion Assumption in Multi-Server PIR," presented by Tiantian Gong, delves into a critical security challenge within Private Information Retrieval (PIR) schemes, specifically those utilizing multiple servers. PIR allows a client to retrieve an item from a database without the server(s) learning which item was requested. While multi-server PIR offers significant efficiency benefits over single-server approaches, these advantages traditionally come at the cost of a strong non-collusion assumption – specifically, that the servers will not conspire to reveal the client's query.

The core contribution of this research is a novel mechanism designed to relax this stringent non-collusion assumption, replacing it with a more practical rationality assumption. Instead of presuming servers are unconditionally honest, the proposed system assumes servers act to maximize their own utility, whether they are rational or outright malicious. By introducing a game-theoretic framework with carefully designed rewards, penalties, and verification procedures, the work demonstrates how to incentivize servers against collusion, even when they possess undetectable communication channels. This research is pivotal for enhancing the real-world applicability and robustness of efficient multi-server PIR protocols in environments where trust cannot be absolute.

Background

▶ Watch: Introduction to "More is Merrier" and Talk Agenda (0:00)

Private Information Retrieval (PIR) is a fundamental cryptographic primitive enabling a client to query a database hosted by one or more servers without revealing the queried index to the servers. The most trivial PIR scheme involves the server sending the entire database to the client, which is secure but highly inefficient. To achieve practical efficiency, researchers have explored various approaches, with multi-server PIR emerging as a particularly promising avenue.

Multi-server PIR schemes typically involve a client querying K out of L available servers. A common variant, 1-private PIR, ensures that no single server can learn the client's query. The efficiency of multi-server PIR, especially 1-private schemes, is often highlighted in terms of communication complexity and computation complexity. Information-theoretic multi-server PIR can achieve significantly better communication overhead compared to single-server solutions, which must transmit the entire database. While single-server computational PIR can theoretically reach polylogarithmic computation complexity, concrete implementations of multi-server solutions often outperform them in practice by avoiding expensive public-key operations.

However, this efficiency comes with a critical caveat: the non-collusion assumption. Specifically, for 1-private PIR, it is assumed that no two parties will collude, as two colluding servers could potentially learn the client's query. This assumption is increasingly problematic in modern distributed systems, where servers may belong to different entities but could still find ways to collude through various unobserved or undetectable communication channels. Simply dismissing the entire family of efficient multi-server PIR constructions due to this strong assumption is not constructive. Instead, this work asks a more proactive question: can this assumption be relaxed?

The proposed solution shifts the paradigm from a strict non-collusion model to a rationality assumption. In this model, servers are either rational (acting to maximize their utility) or malicious (behaving arbitrarily). The mechanism does not attempt to prevent collusion channels but rather designs an economic game that disincentivizes servers from using them. The focus is on the outcome of collusion – whether any party has learned non-trivial information about the index or the retrieved entry – and designing incentives such that the non-collusion outcome is preferred by rational servers in equilibrium.

Key Findings

▶ Watch: Multi-Server PIR Efficiency vs. Strong Non-Collusion Assumption (2:00)

The central finding of this research is that the strong non-collusion assumption in multi-server PIR can be effectively relaxed to a more realistic rationality assumption through a carefully designed game-theoretic mechanism. This mechanism, implemented on a public bulletin board, induces a game among servers where reporting successful collusion (and thus revealing the colluding parties) becomes individually advantageous for the reporting server, while colluding without reporting leads to significant penalties.

Key findings and contributions include:

1. Mechanism Design for Disincentivizing Collusion: The talk introduces a multi-stage mechanism that functions as an algorithm on a public bulletin board. This mechanism specifies winner selection rules (who gets what) and payment rules (who pays what), designed to induce a non-collusion outcome.
2. Addressing Practical Collusion Scenarios: The work differentiates between verified collusion (where outputs from a collusion protocol can be checked for validity) and blind collusion (where forged inputs can make outputs appear legitimate). The primary focus is on verified collusion, though blind collusion is also discussed as potentially easier to tackle.
3. Mitigating Arbitrary Private Knowledge and Client Collusion: To prevent servers from claiming prior knowledge or clients from framing servers, the mechanism incorporates Omega random competing queries generated by the client and requires client and server commitments to query and answer strings, respectively. A service fee charged to the client further disincentivizes client-side framing.
4. Rigorous Game-Theoretic Analysis: The mechanism’s parameters (reward R, penalty P, service fee) are rigorously derived using solution concepts like subgame perfect equilibrium (for verified collusion) and sequential equilibrium (for blind collusion) to guarantee a non-collusion outcome in a single round. The analysis reveals that the reward R can be zero, and the service fee only needs to be positive.
5. Handling Infinite Repetition: The challenging problem of infinite repetitions, where the Folk Theorem suggests multiple equilibria (including collusion), is addressed. Solutions include significantly increasing the total number of servers L far beyond the queried servers K (making repeated interactions between any two servers rare), providing a sufficiently large positive reward R for reporting, and periodically replacing players.
6. Incorporating Byzantine Parties: The mechanism is extended to handle the presence of Byzantine parties (servers that can behave arbitrarily). This involves considering worst-case scenarios for rational servers and, crucially, employing zero-knowledge proofs (ZKPs) for report verification. ZKPs allow rational servers to collaboratively prove the correctness or triviality of a reported function without revealing the underlying secret, thus preventing malicious framing by Byzantine parties.
7. Practicality and Implementation: The proposed mechanism is shown to have reasonable communication and computation overhead. It was implemented as a smart contract on Ethereum, demonstrating its practical feasibility and the potential for real-world deployment on blockchain platforms.

Technical Deep Dive

▶ Watch: Relaxing to Rationality: The Core Mechanism Idea (3:40)

The core of this work lies in designing a robust mechanism that alters the game-theoretic incentives of servers in a multi-server PIR setting. The standard multi-server PIR model involves a client querying an index X from a database held by L servers. For each query, the client selects K servers uniformly at random to participate. The privacy parameter T implies that up to T parties cannot learn extra information about the index. The focus here is on 1-private PIR, where T = 1, meaning even two colluding servers could compromise privacy.

The proposed mechanism, let's call it M, operates on a public bulletin board accessible to all parties. It aims to achieve a non-collusion outcome in equilibrium by making it strategically disadvantageous for servers to collude.

Initial Mechanism M0 and its Evolution:

1. Basic M0:

• Knows a secret value V (upper bound of the worth of any secret).
• Winner Selection Rule: If server S1 tells the mechanism the correct secret, S1 is the winner; others are "colluders."
• Payment Rule: Winner S1 receives a reward R > 0. Colluders pay a penalty P such that P > V. S1 also pays a penalty if it reports a wrong secret.
• Intuition: S1 is incentivized to report collusion to get R and avoid P. Others are disincentivized from learning the secret due to P.

1. Addressing M0's Flaws:

• How to tell if collusion was successful?
• Verified Collusion: If the original PIR protocol makes it computationally hard to forge query/answer strings, servers can verify if the output of a collusion protocol is garbage or legitimate. This is the primary focus.
• Blind Collusion: If forging is easy, servers can't tell from outputs alone. Counter-intuitively, this might be easier to handle as servers are already making it hard for themselves.
• S1 helping others learn the secret?
• Democratize Winner Selection: Any server can become the winner by reporting the correct secret first. This shifts the incentive: servers want to escape the penalty, not just get a reward. Consequently, R can be zero.
• Arbitrary Private Knowledge?
• Client generates Omega random competing queries. For an original query X, the client also samples XR (a random index). Query strings for both X and XR are generated, permuted, and sent to servers.
• The winning server must report the secret AND its corresponding input used to generate it. This distinguishes learning via collusion from prior knowledge.

Refined Mechanism with Verification and Client Mitigation:

To rigorously verify reports and prevent client-side framing, additional routines are integrated into the PIR protocol:

1. Commitment Phase:

• Client generates query strings for X and XR.
• Client commits to these query strings and sends the permuted commitments to the public bulletin board (mechanism).
• Client reveals / de-commits information to the K queried servers, allowing them to retrieve the actual query strings.
• Servers compute answer strings and commit to these answer strings, sending their commitments to the bulletin board.
• Servers reveal their answer commitments to the client, who performs reconstruction.

1. Report Verification Procedure:

• If a server reports a collusion (i.e., reports a learned secret F(X) and its input), the mechanism initiates a verification phase.
• A proof collection time window Δ is set. During Δ, servers must reveal (de-commit) their corresponding commitments to the mechanism.
• The mechanism, having access to all commitments and now the de-committed data, can perform computations on plaintext to verify the correctness of the reported secret and the input.
• Any server failing to reveal commitments during Δ is treated as a colluder and penalized. This procedure does not leak the secret if a non-collusion outcome is achieved in equilibrium.

1. Client Collusion Mitigation:

• To prevent a malicious client from intentionally framing servers (e.g., by fabricating reports), the mechanism charges service fees from the client. A sufficiently large service fee disincentivizes such behavior.

Game-Theoretic Parameterization for Non-Collusion:

The mechanism models the interaction as a sequential game with three stages:

1. Servers decide whether to collude or not.
2. Colluding servers decide whether to input correct information into their collusion protocol.
3. Colluding servers decide whether to report learned information to the mechanism.

The goal is to achieve a non-collusion outcome in equilibrium. For verified collusion, the concept of subgame perfect equilibrium is used. For blind collusion, sequential equilibrium is applied. The analysis yields two key inequalities that must hold for the non-collusion outcome:

• Utility_Report > Utility_NoReport (incentive to report if collusion occurs)
• Utility_NonCollude > Utility_ColludeAndNotReport (incentive not to collude in the first place)

These inequalities show that:

• The reward R for reporting can indeed be zero (servers are incentivized by avoiding penalty P).
• The service fee needs only to be positive to deter client framing.
• Practical parameters satisfying these conditions always exist.

Handling Infinite Repetition and Byzantine Parties:

1. Infinite Repetition: The Folk Theorem states that in infinitely repeated games, any individually rational payoff can be sustained in a subgame perfect equilibrium, including collusion. To combat this:

• Increase L (total servers) significantly beyond K (queried servers): If any two servers are queried together with low probability, their "long-term relationship" for collusion is weakened. The parameter space for R expands with increasing L, meaning a smaller R is needed.
• Increase R (reward): A positive reward R incentivizes servers to participate in the mechanism (reporting) rather than maintaining long-term collusion with "strangers."
• Periodic Player Replacement: This reduces infinite games to finite ones, simplifying the equilibrium analysis.

1. Byzantine Parties: If some servers are Byzantine (arbitrarily malicious), the commitment-revealing verification procedure is insufficient, as Byzantine parties could submit fake reports, forcing honest parties to reveal commitments and potentially compromising the secret.

• The solution resorts to Zero-Knowledge Proofs (ZKPs). When a server reports a learned secret F(X) and its input, other participating servers collaboratively compute an inequality proof using a ZKP protocol. This proof verifies:
• Their inputs are correct with respect to their commitments.
• The function F was actually computed.
• The output F(X) is not a value committed in the report (if F(X) is trivial).
• ZKPs allow verification without revealing the secret itself, thus protecting honest parties from malicious framing by Byzantine actors.

Overhead and Implementation:

The mechanism introduces minimal overhead:

• Communication Overhead: Client and servers send one additional commitment message to the public bulletin board.
• Computation Overhead: Servers need to compute answer strings for Omega random component queries.

The mechanism was implemented as a smart contract on Ethereum. The authors consider the associated gas costs for both "normal service functions" (during regular PIR execution) and "collusion resolution functions" (only run if a report is made) to be reasonable, demonstrating the practicality of the approach.

Demo / Proof of Concept

▶ Watch: Detailing the Simple Mechanism (m0) and its Rules (5:30)

The practical feasibility of the proposed mechanism was demonstrated through an implementation as a smart contract on Ethereum. This serves as a tangible proof of concept, showing how the game-theoretic incentives and verification procedures can be codified and executed on a decentralized, public ledger.

The Ethereum smart contract would encapsulate the logic for:

• Receiving and storing client commitments to query strings.
• Receiving and storing server commitments to answer strings.
• Handling collusion reports from servers.
• Initiating the Δ time window for commitment revelations.
• Performing the plaintext verification computations based on revealed commitments.
• Managing the reward R, penalty P, and service fee payments.
• Potentially coordinating the collaborative ZKP protocols for Byzantine-resilient verification.

The authors assessed the computation and communication overhead incurred by this implementation. They concluded that these costs were "reasonable." This assessment likely involved analyzing the gas costs associated with contract deployments, state changes, and function calls on the Ethereum network. The distinction was made between "normal service functions," which run during every PIR execution, and "collusion resolution functions," which are only invoked if a server actually reports a collusion. This implies that the additional overhead is primarily incurred only in the event of a detected or reported collusion, making the base PIR operation still efficient.

While a live demonstration was not detailed in the transcript, the mention of a working Ethereum smart contract implementation strongly suggests a successful proof of concept, validating the theoretical framework with a practical application.

Defensive Implications

▶ Watch: Key Unresolved Challenges with the Simple Mechanism (6:30)

This research offers crucial insights and actionable strategies for defenders, system architects, and developers working with privacy-preserving technologies, particularly multi-server PIR.

1. Re-evaluate Trust Assumptions: Defenders should critically re-evaluate the non-collusion assumptions in their existing or planned multi-server PIR deployments. Relying solely on the assumption that servers will not collude, especially across different administrative domains or in environments with undetectable communication channels, is a significant security risk. This work provides a concrete framework for moving from a naive honesty assumption to a more robust rationality assumption.
2. Incorporate Game-Theoretic Incentives: For systems where full trust in all servers is impractical, defenders should consider integrating economic or game-theoretic mechanisms to disincentivize collusion. The proposed system of rewards (R), penalties (P), and service fees, managed by a public mechanism (e.g., a smart contract), can transform the strategic landscape, making collusion individually disadvantageous for rational actors.
3. Leverage Public Bulletin Boards/Blockchains: The use of a public bulletin board (like a blockchain) is central to the mechanism's integrity. It provides a transparent, immutable, and auditable record of commitments, reports, and verification outcomes. Defenders should explore blockchain or similar decentralized ledger technologies as a foundational layer for such anti-collusion mechanisms.
4. Implement Commitment-Based Verification: The client and servers committing to their query and answer strings, respectively, before interaction, provides a robust basis for post-collusion-report verification. This commitment-revealing procedure, coupled with a time window (Δ), allows the mechanism to verify reports without compromising the secret in a non-collusion equilibrium.
5. Prepare for Byzantine Adversaries: In high-stakes environments where some servers might be completely malicious (Byzantine), simple commitment-revealing protocols are insufficient. Defenders must be ready to deploy more advanced cryptographic primitives like Zero-Knowledge Proofs (ZKPs) for report verification. ZKPs enable collaborating servers to prove the correctness of a reported function or the triviality of a learned secret without revealing any sensitive information, thus protecting honest parties from malicious framing.
6. Consider L >> K Architectures: When designing multi-server PIR systems, increasing the total pool of available servers (L) far beyond the number of servers actually queried (K) can significantly enhance security against collusion in repeated interactions. This strategy reduces the probability of any two specific servers being queried together repeatedly, thereby weakening the basis for long-term collusive agreements.
7. Client-Side Fee Structures: To prevent clients from malicious framing or participating in collusion, charging a service fee should be considered. This economic disincentive aligns client behavior with the overall security goals of the system.
8. Future-Proofing for Privacy-Preserving Computations: The principles outlined in this talk, particularly the relaxation of non-collusion assumptions through game theory and advanced cryptography, are not limited to PIR. Defenders should recognize that these techniques are broadly applicable to other privacy-preserving computation protocols that rely on similar multi-party trust assumptions, such as secure multi-party computation (MPC), secret sharing schemes, distributed key generation, and time-release encryption.

Key Takeaways

• Multi-server Private Information Retrieval (PIR) offers significant efficiency benefits but traditionally relies on a strong, often unrealistic, non-collusion assumption among servers.
• This research proposes a novel game-theoretic mechanism that relaxes the non-collusion assumption to a more practical rationality assumption, incentivizing servers not to collude through rewards, penalties, and verification.
• The mechanism employs commitments from clients and servers to query and answer strings, respectively, enabling robust verification of collusion reports on a public bulletin board (e.g., a blockchain).
• To address the complexities of infinite repetitions and the Folk Theorem, strategies such as significantly increasing the total number of servers (L >> K), offering positive rewards for reporting, and periodically replacing players are proposed.
• For environments with Byzantine parties, the mechanism integrates Zero-Knowledge Proofs (ZKPs) for collaborative report verification, ensuring privacy and preventing malicious framing without revealing the underlying secret.
• The system was implemented as a smart contract on Ethereum, demonstrating its practical feasibility and acceptable overhead for both normal operation and collusion resolution.
• The principles of relaxing non-collusion assumptions through economic incentives and advanced cryptography are broadly applicable to other privacy-preserving computation protocols involving multiple parties.

About the Speaker(s)

Tiantian Gong is a PhD student at Purdue University, where he works under the guidance of Dr. Aniket Kate. His research interests evidently lie in the intersection of privacy-preserving technologies and game theory, specifically focusing on strengthening the security and practicality of cryptographic primitives like Private Information Retrieval in multi-party settings. This work represents a significant contribution to the field by addressing fundamental trust assumptions in distributed systems.

The research is a joint effort with Ryan Henry, Alexandros Psomas, and his advisor Aniket Kate, indicating a collaborative approach from experienced researchers in cryptography and theoretical computer science.