Differentially Private Secure Multiplication with Erasures and Adversaries
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918238586142720 |
|---|---|
| author | Hu, Haoyang Cadambe, Viveck R. |
| author_facet | Hu, Haoyang Cadambe, Viveck R. |
| contents | We consider a private distributed multiplication problem involving N computation nodes and T colluding nodes. Shamir's secret sharing algorithm provides perfect information-theoretic privacy, while requiring an honest majority, i.e., N \ge 2T + 1. Recent work has investigated approximate computation and characterized privacy-accuracy trade-offs for the honest minority setting N \le 2T for real-valued data, quantifying privacy leakage via the differential privacy (DP) framework and accuracy via the mean squared error. However, it does not incorporate the error correction capabilities of Shamir's secret-sharing algorithm. This paper develops a new polynomial-based coding scheme for secure multiplication with an honest minority, and characterizes its achievable privacy-utility tradeoff, showing that the tradeoff can approach the converse bound as closely as desired. Unlike previous schemes, the proposed scheme inherits the capability of the Reed-Solomon (RS) code to tolerate erasures and adversaries. We utilize a modified Berlekamp-Welch algorithm over the real number field to detect adversarial nodes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21178 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Differentially Private Secure Multiplication with Erasures and Adversaries Hu, Haoyang Cadambe, Viveck R. Information Theory We consider a private distributed multiplication problem involving N computation nodes and T colluding nodes. Shamir's secret sharing algorithm provides perfect information-theoretic privacy, while requiring an honest majority, i.e., N \ge 2T + 1. Recent work has investigated approximate computation and characterized privacy-accuracy trade-offs for the honest minority setting N \le 2T for real-valued data, quantifying privacy leakage via the differential privacy (DP) framework and accuracy via the mean squared error. However, it does not incorporate the error correction capabilities of Shamir's secret-sharing algorithm. This paper develops a new polynomial-based coding scheme for secure multiplication with an honest minority, and characterizes its achievable privacy-utility tradeoff, showing that the tradeoff can approach the converse bound as closely as desired. Unlike previous schemes, the proposed scheme inherits the capability of the Reed-Solomon (RS) code to tolerate erasures and adversaries. We utilize a modified Berlekamp-Welch algorithm over the real number field to detect adversarial nodes. |
| title | Differentially Private Secure Multiplication with Erasures and Adversaries |
| topic | Information Theory |
| url | https://arxiv.org/abs/2504.21178 |