pipette
ENEnglish

The Price of Privacy: Randomness Complexity of Graph-Based Multi-Secret Sharing

Piotr Marszalik

PreprintCódigo disponible

En palabras de los autores

We study the randomness required to share possibly correlated secret bits among parties connected by a graph. A dealer places shares on the edges so that each party can recover its own secret from its incident shares and learn nothing about the others beyond what its own secret reveals. Anilkumar et al. completely determined the minimum randomness required for three binary secrets. We extend this study to four secrets and obtain results for arbitrary numbers of secrets on general graphs. For four parties on a complete graph, we determine the minimum number of random states for every set of permitted secret combinations: the possible values are one, two, three and four. We also characterize when one random bit suffices on an arbitrary graph.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 12 pages, 4 figures, including an appendix with proofs. Code: https://github.com/pjmarszalik/price-of-privacy-code