Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noise
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912191262752768 |
|---|---|
| author | Cadambe, Viveck R. Devulapalli, Ateet Jeong, Haewon Calmon, Flavio P. |
| author_facet | Cadambe, Viveck R. Devulapalli, Ateet Jeong, Haewon Calmon, Flavio P. |
| contents | 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 via the celebrated algorithm of Ben Or, Goldwasser and Wigderson (the "BGW algorithm"). However, perfect privacy and accuracy require an honest majority, that is, $N \geq 2t+1$ compute nodes are required to ensure privacy against any $t$ colluding adversarial nodes. By allowing for some controlled amount of information leakage and approximate multiplication instead of exact multiplication, we study coding schemes for the setting where the number of honest nodes can be a minority, that is $N< 2t+1.$ We develop a tight characterization privacy-accuracy trade-off for cases where $N < 2t+1$ by measuring information leakage using {differential} privacy instead of perfect privacy, and using the mean squared error metric for accuracy. A novel technical aspect is an intricately layered noise distribution that merges ideas from differential privacy and Shamir secret-sharing at different layers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_16105 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noise Cadambe, Viveck R. Devulapalli, Ateet Jeong, Haewon Calmon, Flavio P. Information Theory Cryptography and Security Distributed, Parallel, and Cluster Computing Machine Learning 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 via the celebrated algorithm of Ben Or, Goldwasser and Wigderson (the "BGW algorithm"). However, perfect privacy and accuracy require an honest majority, that is, $N \geq 2t+1$ compute nodes are required to ensure privacy against any $t$ colluding adversarial nodes. By allowing for some controlled amount of information leakage and approximate multiplication instead of exact multiplication, we study coding schemes for the setting where the number of honest nodes can be a minority, that is $N< 2t+1.$ We develop a tight characterization privacy-accuracy trade-off for cases where $N < 2t+1$ by measuring information leakage using {differential} privacy instead of perfect privacy, and using the mean squared error metric for accuracy. A novel technical aspect is an intricately layered noise distribution that merges ideas from differential privacy and Shamir secret-sharing at different layers. |
| title | Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noise |
| topic | Information Theory Cryptography and Security Distributed, Parallel, and Cluster Computing Machine Learning |
| url | https://arxiv.org/abs/2309.16105 |