Beyond Yao's Millionaires: Secure Multi-Party Computation of Non-Polynomial Functions

• URL: http://arxiv.org/abs/2410.17000v1
• Date: Tue, 22 Oct 2024 13:22:08 GMT
• Title: Beyond Yao's Millionaires: Secure Multi-Party Computation of Non-Polynomial Functions
• Authors: Seyed Reza Hoseini Najarkolaei, Mohammad Mahdi Mojahedian, Mohammad Reza Aref,
• Abstract summary: 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.
• Score: 5.625796693054093
• License:
• Abstract: In this paper, we present an unconditionally secure $N$-party comparison scheme based on Shamir secret sharing, utilizing the binary representation of private inputs to determine the $\max$ without disclosing any private inputs or intermediate results. Specifically, each party holds a private number and aims to ascertain the greatest number among the $N$ available private numbers without revealing its input, assuming that there are at most $T < \frac{N}{2}$ honest-but-curious parties. The proposed scheme demonstrates a lower computational complexity compared to existing schemes that can only compare two secret numbers at a time. To the best of our knowledge, our scheme is the only information-theoretically secure method for comparing $N$ private numbers without revealing either the private inputs or any intermediate results. We demonstrate that by modifying the proposed scheme, we can compute other well-known non-polynomial functions of the inputs, including the minimum, median, and rank. Additionally, in the proposed scheme, before the final reveal phase, each party possesses a share of the result, enabling the nodes to compute any polynomial function of the comparison result. We also explore various applications of the proposed comparison scheme, including federated learning.

Related papers

• Privacy-Computation trade-offs in Private Repetition and Metaselection [28.11248357424981]
  A Private Repetition algorithm takes as input a differentially private algorithm with constant success probability and boosts it to one that succeeds with high probability. Existing algorithms for these tasks pay either a large overhead in privacy cost, or a large overhead in computational cost. This is in stark contrast with the non-private setting, where the failure probability falls exponentially in the computational overhead.
  arXiv  Detail & Related papers  (2024-10-22T18:33:02Z)
• 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)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
  We propose a general framework to evaluate the additional privacy cost incurred by non-private data-dependent pre-processing algorithms. Our framework establishes upper bounds on the overall privacy guarantees by utilising two new technical notions.
  arXiv  Detail & Related papers  (2024-03-19T17:54:49Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04: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)
• Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noise [7.767656876470667]
  We consider the problem of private distributed multi-party multiplication. It is well-established that Shamir secret-sharing coding strategies can enable perfect information-theoretic privacy in distributed computation.
  arXiv  Detail & Related papers  (2023-09-28T02:13:13Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• Optimal Accounting of Differential Privacy via Characteristic Function [25.78065563380023]
  We propose a unification of recent advances (Renyi DP, privacy profiles, $f$-DP and the PLD formalism) via the characteristic function ($phi$-function) of a certain worst-case'' privacy loss random variable. We show that our approach allows natural adaptive composition like Renyi DP, provides exactly tight privacy accounting like PLD, and can be (often losslessly) converted to privacy profile and $f$-DP.
  arXiv  Detail & Related papers  (2021-06-16T06:13:23Z)

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.