Beyond Yao's Millionaires: Secure Multi-Party Computation of Non-Polynomial Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917812596899840 |
|---|---|
| author | Najarkolaei, Seyed Reza Hoseini Mojahedian, Mohammad Mahdi Aref, Mohammad Reza |
| author_facet | Najarkolaei, Seyed Reza Hoseini Mojahedian, Mohammad Mahdi Aref, Mohammad Reza |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_17000 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Beyond Yao's Millionaires: Secure Multi-Party Computation of Non-Polynomial Functions Najarkolaei, Seyed Reza Hoseini Mojahedian, Mohammad Mahdi Aref, Mohammad Reza Cryptography and Security Information Theory 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. |
| title | Beyond Yao's Millionaires: Secure Multi-Party Computation of Non-Polynomial Functions |
| topic | Cryptography and Security Information Theory |
| url | https://arxiv.org/abs/2410.17000 |