The Distributed Multi-User Point Function

• URL: http://arxiv.org/abs/2501.10251v1
• Date: Fri, 17 Jan 2025 15:34:45 GMT
• Title: The Distributed Multi-User Point Function
• Abstract summary: We study the problem of information-theoretic distributed multi-user point function, involving a trusted master node, $N in mathbbN$ server nodes, and $Kin mathbbN$ users.<n>We propose a multi-user scheme that satisfies the correctness and information-theoretic privacy constraints, ensuring recovery for all point functions.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper, we study the problem of information-theoretic distributed multi-user point function, involving a trusted master node, $N \in \mathbb{N}$ server nodes, and $K\in \mathbb{N}$ users, where each user has access to the contents of a subset of the storages of server nodes. Each user is associated with an independent point function $f_{X_k,Z_k}: \{1,2,\hdots,T\} \rightarrow{GF(q^{m R_k})},T,mR_k \in \mathbb{N}$. Using these point functions, the trusted master node encodes and places functional shares $G_1,G_2,\hdots,G_N \in GF(q^{M}), M \in \mathbb{N}$ in the storage nodes such that each user can correctly recover its point function result from the response transmitted to itself and gains no information about the point functions of any other user, even with knowledge of all responses transmitted from its connected servers. For the first time, we propose a multi-user scheme that satisfies the correctness and information-theoretic privacy constraints, ensuring recovery for all point functions. We also characterize the inner and outer bounds on the capacity -- the maximum achievable rate defined as the size of the range of each point function $mR_k$ relative to the storage size of the servers $M$ -- of the distributed multi-user point function scheme by presenting a novel converse argument.

Related papers

• Secure Multi-User Linearly-Separable Distributed Computing [18.72935137242268]
  We show how a parallel treatment of users can yield large parallelization gains with relatively low computation and communication costs.<n>While this approach provides near-optimal performance, its linear nature has raised data secrecy concerns.<n>We here adopt an information-theoretic secrecy framework, seeking guarantees that each user can learn nothing more than its own requested function.
  arXiv  Detail & Related papers  (2026-02-02T18:59:10Z)
• Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits [17.82458125377762]
  Two parties compute an additive secret sharing of a tensor product of two vectors $mathbfx otimes mathbfy$.<n>We present a construction of OTE with optimal complexity from the standard learning with errors (LWE) problem.<n>We show how this new technical tool enables a host of cryptographic primitives, all with security reducible to LWE.
  arXiv  Detail & Related papers  (2025-08-13T10:03:03Z)
• Differential Privacy with Multiple Selections [52.5653572324012]
  We consider the setting where a user with sensitive features wishes to obtain a recommendation from a server in a differentially private fashion. We propose a multi-selection'' architecture where the server can send back multiple recommendations and the user chooses one that matches best with their private features.
  arXiv  Detail & Related papers  (2024-07-19T19:34:51Z)
• Universal Representation of Permutation-Invariant Functions on Vectors and Tensors [11.345796608258434]
  A main object of our study is multiset functions -- that is, permutation-invariant functions over inputs of varying sizes. Deep Sets, proposed by citezaheer 2017deep, provides a emphuniversal representation for continuous multiset functions on scalars via a sum-decomposable model. We prove that universal representation is guaranteed for continuous and discontinuous multiset functions though a latent space dimension of $O(ND)$.
  arXiv  Detail & Related papers  (2023-10-20T22:00:59Z)
• 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)
• Matching upper bounds on symmetric predicates in quantum communication complexity [0.0]
  We focus on the quantum communication complexity of functions of the form $f circ G = f(G)mathrmQCC_mathrmE(G)) when the parties are allowed to use shared entanglement. We show that the same statement holds emphwithout shared entanglement, which generalizes their result.
  arXiv  Detail & Related papers  (2023-01-01T08:30:35Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Decentralized Multi-Task Stochastic Optimization With Compressed Communications [22.31884634659446]
  The paper develops algorithms and obtains performance bounds for two different models of local information availability at the nodes. We show that deviation from the global minimum value and violations of the constraints are upper-bounded by $mathcalO(T-frac12)$ and $mathcalO(T-frac14)$.
  arXiv  Detail & Related papers  (2021-12-23T05:54:42Z)
• On minimal representations of shallow ReLU networks [0.0]
  We show that the minimal representation for $f$ uses either $n$, $n+1$ or $n+2$ neurons. In particular, where the input layer is one-dimensional, minimal representations always use at most $n+1$ neurons but in all higher dimensional settings there are functions for which $n+2$ neurons are needed.
  arXiv  Detail & Related papers  (2021-08-12T10:22:24Z)
• Neural networks with superexpressive activations and integer weights [91.3755431537592]
  An example of an activation function $sigma$ is given such that networks with activations $sigma, lfloorcdotrfloor$, integer weights and a fixed architecture is given. The range of integer weights required for $varepsilon$-approximation of H"older continuous functions is derived.
  arXiv  Detail & Related papers  (2021-05-20T17:29:08Z)
• Deep neural network approximation of analytic functions [91.3755431537592]
  entropy bound for the spaces of neural networks with piecewise linear activation functions. We derive an oracle inequality for the expected error of the considered penalized deep neural network estimators.
  arXiv  Detail & Related papers  (2021-04-05T18:02:04Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Neural Network Approximation: Three Hidden Layers Are Enough [4.468952886990851]
  A three-hidden-layer neural network with super approximation power is introduced. Network is built with the floor function ($lfloor xrfloor$), the exponential function ($2x$), the step function ($1_xgeq 0$), or their compositions as the activation function in each neuron.
  arXiv  Detail & Related papers  (2020-10-25T18:30:57Z)
• 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)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)

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.