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

• URL: http://arxiv.org/abs/2201.07740v6
• Date: Mon, 08 Sep 2025 01:13:36 GMT
• Title: More is Merrier: Relax the Non-Collusion Assumption in Multi-Server PIR
• Authors: Tiantian Gong, Ryan Henry, Alexandros Psomas, Aniket Kate,
• Abstract summary: A long line of research on secure computation has confirmed that anything that can be computed, can be computed securely using a set of non-colluding parties.<n>However, it remains highly susceptible to covert, undetectable collusion among computing parties.<n>This work stems from an observation that if the number of available computing parties is much higher than the number of parties required to perform a secure computation task, collusion attempts in privacy-preserving computations could be deterred.
• Score: 61.13962963550403
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: A long line of research on secure computation has confirmed that anything that can be computed, can be computed securely using a set of non-colluding parties. Indeed, this non-collusion assumption makes a number of problems solvable, as well as reduces overheads and bypasses computational hardness results, and it is pervasive across different privacy-enhancing technologies. However, it remains highly susceptible to covert, undetectable collusion among computing parties. This work stems from an observation that if the number of available computing parties is much higher than the number of parties required to perform a secure computation task, collusion attempts in privacy-preserving computations could be deterred. We focus on the prominent privacy-preserving computation task of multi-server $1$-private information retrieval (PIR) that inherently assumes no pair-wise collusion. For PIR application scenarios, such as those for blockchain light clients, where the available servers can be plentiful, a single server's deviating action is not tremendously beneficial to itself. We can make deviations undesired via small amounts of rewards and penalties, thus significantly raising the bar for collusion resistance. We design and implement a collusion mitigation mechanism on a public bulletin board with payment execution functions, considering only rational and malicious parties with no honest non-colluding servers. Privacy protection is offered for an extended period after the query executions.

Related papers

• Your Privacy Depends on Others: Collusion Vulnerabilities in Individual Differential Privacy [50.66105844449181]
  Individual Differential Privacy (iDP) promises users control over their privacy, but this promise can be broken in practice.<n>We reveal a previously overlooked vulnerability in sampling-based iDP mechanisms.<n>We propose $(varepsilon_i,_i,overline)$-iDP a privacy contract that uses $$-divergences to provide users with a hard upper bound on their excess vulnerability.
  arXiv  Detail & Related papers  (2026-01-19T10:26:12Z)
• Cascade: Token-Sharded Private LLM Inference [31.561665382764076]
  We propose a new multi-party inference protocol, Cascade, that avoids punitive costs by leveraging sharding in the sequence dimension to maintain privacy.<n>We demonstrate that Cascade is resistant to a generalization of a recent attack that is highly effective against other statistical privacy schemes.
  arXiv  Detail & Related papers  (2025-07-07T17:37:16Z)
• SVIP: Towards Verifiable Inference of Open-source Large Language Models [33.910670775972335]
  We introduce SVIP, a secret-based verifiable Large Language Models inference protocol.<n>Our protocol requires the computing provider to return both the generated text and processed hidden representations from LLMs.<n>SVIP achieves false negative rates below 5% and false positive rates below 3%, while requiring less than 0.01 seconds per prompt query for verification.
  arXiv  Detail & Related papers  (2024-10-29T17:52:45Z)
• On the Necessity of Collaboration for Online Model Selection with Decentralized Data [53.244188985271606]
  We consider online model selection with decentralized data over $M$ clients, and study the necessity of collaboration among clients. Our results show (i) collaboration is unnecessary in the absence of computational constraints on clients; (ii) collaboration is necessary if the computational cost on each client is limited to $o(K)$, where $K$ is the number of candidate hypothesis spaces.
  arXiv  Detail & Related papers  (2024-04-15T06:32:28Z)
• Having your Privacy Cake and Eating it Too: Platform-supported Auditing of Social Media Algorithms for Public Interest [70.02478301291264]
  Social media platforms curate access to information and opportunities, and so play a critical role in shaping public discourse. Prior studies have used black-box methods to show that these algorithms can lead to biased or discriminatory outcomes. We propose a new method for platform-supported auditing that can meet the goals of the proposed legislation.
  arXiv  Detail & Related papers  (2022-07-18T17:32:35Z)
• Should All Proposals be Treated Equally in Object Detection? [110.27485090952385]
  The complexity-precision trade-off of an object detector is a critical problem for resource constrained vision tasks. It is hypothesized that improved detection efficiency requires a paradigm shift, towards the unequal processing of proposals. This results in better utilization of available computational budget, enabling higher accuracy for the same FLOPS.
  arXiv  Detail & Related papers  (2022-07-07T18:26:32Z)
• THE-X: Privacy-Preserving Transformer Inference with Homomorphic Encryption [112.02441503951297]
  Privacy-preserving inference of transformer models is on the demand of cloud service users. We introduce $textitTHE-X$, an approximation approach for transformers, which enables privacy-preserving inference of pre-trained models.
  arXiv  Detail & Related papers  (2022-06-01T03:49:18Z)
• Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation [32.004283989604154]
  We present a protocol for vector summation that verifies that the Euclidean norm of each contribution is approximately bounded. Unlike SMC algorithms that inevitably cast integers to elements of a large finite field, our algorithms work over integers/reals, which may allow for additional efficiencies.
  arXiv  Detail & Related papers  (2022-02-22T02:06:42Z)
• ABG: A Multi-Party Mixed Protocol Framework for Privacy-Preserving Cooperative Learning [13.212198032364363]
  We propose a privacy-preserving multi-party cooperative learning system, which allows different data owners to cooperate in machine learning. We also design specific privacy-preserving computation protocols for some typical machine learning methods such as logistic regression and neural networks. The experiments indicate that ABG$n$ has excellent performance, especially in the network environment with low latency.
  arXiv  Detail & Related papers  (2022-02-07T03:57:57Z)
• Secure Summation via Subset Sums: A New Primitive for Privacy-Preserving Distributed Machine Learning [15.275126264550943]
  Summation is an important primitive for computing means, counts or mini-batch gradients. In many cases, the data is privacy-sensitive and cannot be collected on a central server. Existing solutions for distributed summation with computational privacy guarantees make trust or connection assumptions that might not be fulfilled in real world settings. We propose Secure Summation via Subset Sums (S5), a method for distributed summation that works in the presence of a malicious server and only two honest clients.
  arXiv  Detail & Related papers  (2019-06-27T23:27:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.