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
- Computing Voting Rules with Elicited Incomplete Votes [12.981755656269097]
We study voting rules that are computable by querying voters about $t m$ candidates.
For scoring rules that are computable with limited-sized queries, we give parameterized upper and lower bounds on the number of such queries.
While there is no gap between our bounds for deterministic algorithms, identifying the exact query complexity for randomized algorithms is a challenging open problem.
arXiv Detail & Related papers (2024-02-16T22:17:01Z) - 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) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
We propose an algorithm that minimizes the regret over the horizon of time $T$.
The proposed algorithm is applicable to domains such as recommendation systems and transportation.
arXiv Detail & Related papers (2023-01-31T03:49:00Z) - 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) - The Minority Matters: A Diversity-Promoting Collaborative Metric
Learning Algorithm [154.47590401735323]
Collaborative Metric Learning (CML) has recently emerged as a popular method in recommendation systems.
This paper focuses on a challenging scenario where a user has multiple categories of interests.
We propose a novel method called textitDiversity-Promoting Collaborative Metric Learning (DPCML)
arXiv Detail & Related papers (2022-09-30T08:02:18Z) - Single-Server Private Linear Transformation: The Joint Privacy Case [10.072633952908456]
This paper introduces the problem of Private Linear Transformation (PLT) which generalizes the problems of private information retrieval and private linear computation.
The problem includes one or more remote server(s) storing (identical copies of) $K$ messages and a user who wants to compute $L$ independent linear combinations of a $D$-subset of messages.
arXiv Detail & Related papers (2021-06-09T17:09:22Z) - 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.