Private Membership Aggregation

• URL: http://arxiv.org/abs/2309.03872v1
• Date: Thu, 7 Sep 2023 17:33:27 GMT
• Title: Private Membership Aggregation
• Authors: Mohamed Nomeir, Sajani Vithana, Sennur Ulukus,
• Abstract summary: We consider the problem of private membership aggregation (PMA) In PMA, a user counts the number of times a certain element is stored in a system of independent parties. We propose achievable schemes for each of the four variants of the problem based on the concept of cross-subspace alignment.
• Score: 32.97918488607827
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of private membership aggregation (PMA), in which a user counts the number of times a certain element is stored in a system of independent parties that store arbitrary sets of elements from a universal alphabet. The parties are not allowed to learn which element is being counted by the user. Further, neither the user nor the other parties are allowed to learn the stored elements of each party involved in the process. PMA is a generalization of the recently introduced problem of $K$ private set intersection ($K$-PSI). The $K$-PSI problem considers a set of $M$ parties storing arbitrary sets of elements, and a user who wants to determine if a certain element is repeated at least at $K$ parties out of the $M$ parties without learning which party has the required element and which party does not. To solve the general problem of PMA, we dissect it into four categories based on the privacy requirement and the collusions among databases/parties. We map these problems into equivalent private information retrieval (PIR) problems. We propose achievable schemes for each of the four variants of the problem based on the concept of cross-subspace alignment (CSA). The proposed schemes achieve \emph{linear} communication complexity as opposed to the state-of-the-art $K$-PSI scheme that requires \emph{exponential} complexity even though our PMA problems contain more security and privacy constraints.

Related papers

• Beyond Yao's Millionaires: Secure Multi-Party Computation of Non-Polynomial Functions [5.625796693054093]
  We present an unconditionally secure $N$-party comparison scheme based on Shamir secret sharing. Each party holds a private number and aims to ascertain the greatest number among the $N$ available private numbers without revealing its input.
  arXiv  Detail & Related papers  (2024-10-22T13:22:08Z)
• Differential Privacy on Trust Graphs [54.55190841518906]
  We study differential privacy (DP) in a multi-party setting where each party only trusts a (known) subset of the other parties with its data. We give a DP algorithm for aggregation with a much better privacy-utility trade-off than in the well-studied local model of DP.
  arXiv  Detail & Related papers  (2024-10-15T20:31:04Z)
• Privately Counting Partially Ordered Data [50.98561191019676]
  We consider differentially private counting when each data point consists of $d$ bits satisfying a partial order. Our main technical contribution is a problem-specific $K$-norm mechanism that runs in time $O(d2)$.
  arXiv  Detail & Related papers  (2024-10-09T13:43:35Z)
• Quantum Private Membership Aggregation [35.16231062731263]
  We consider the problem of private set membership aggregation of $N$ parties by using an entangled quantum state. We propose an encoding algorithm that maps the classical information into distinguishable quantum states, along with a decoding algorithm that exploits the distinguishability of the mapped states.
  arXiv  Detail & Related papers  (2024-01-29T18:32:19Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  We consider the example-scarce regime, where each user has only a few examples, and obtain the following results. For approximate-DP, we give a generic transformation of any item-level DP algorithm to a user-level DP algorithm. We present a simple technique for adapting the exponential mechanism [McSherry, Talwar FOCS 2007] to the user-level setting.
  arXiv  Detail & Related papers  (2023-09-21T21:51:55Z)
• Earn While You Reveal: Private Set Intersection that Rewards Participants [0.0]
  In Private Set Intersection protocols (PSIs), a non-empty result always reveals something about the private input sets of the parties. We propose a multi-party PSI, called "Anesidora", that rewards parties who contribute their private input sets to the protocol.
  arXiv  Detail & Related papers  (2023-01-10T10:22:55Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)
• Differentially Private Set Union [23.001440922454407]
  We study the basic operation of set union in the global model of differential privacy. In this problem, we are given a universe $U$ of items, possibly of infinite size, and a database $D$ of users. We want an ($epsilon$,$delta$)-differentially private algorithm which outputs a subset $S subset cup_i W_i$ such that the size of $S$ is as large as possible.
  arXiv  Detail & Related papers  (2020-02-22T18:33:14Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
  arXiv  Detail & Related papers  (2020-02-12T18:59:18Z)

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.