Secret Sharing on Superconcentrator
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914354311462912 |
|---|---|
| author | Li, Yuan |
| author_facet | Li, Yuan |
| contents | We study the arithmetic circuit complexity of threshold secret sharing schemes by characterizing the graph-theoretic properties of arithmetic circuits that compute the shares. Using information inequalities, we prove that any unrestricted arithmetic circuit (with arbitrary gates and unbounded fan-in) computing the shares must satisfy superconcentrator-like connectivity properties. Specifically, when the inputs consist of the secret and $t-1$ random elements, and the outputs are the $n$ shares of a $(t, n)$-threshold secret sharing scheme, the circuit graph must be a $(t, n)$-concentrator; moreover, after removing the secret input, the remaining graph is a $(t-1, n)$-concentrator. Conversely, we show that any graph satisfying these properties can be transformed into a linear arithmetic circuit computing the shares of a threshold secret sharing scheme, assuming a sufficiently large field. As a consequence, we derive upper and lower bounds on the arithmetic circuit complexity of computing the shares in threshold secret sharing schemes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_04482 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Secret Sharing on Superconcentrator Li, Yuan Computational Complexity Cryptography and Security Information Theory Combinatorics We study the arithmetic circuit complexity of threshold secret sharing schemes by characterizing the graph-theoretic properties of arithmetic circuits that compute the shares. Using information inequalities, we prove that any unrestricted arithmetic circuit (with arbitrary gates and unbounded fan-in) computing the shares must satisfy superconcentrator-like connectivity properties. Specifically, when the inputs consist of the secret and $t-1$ random elements, and the outputs are the $n$ shares of a $(t, n)$-threshold secret sharing scheme, the circuit graph must be a $(t, n)$-concentrator; moreover, after removing the secret input, the remaining graph is a $(t-1, n)$-concentrator. Conversely, we show that any graph satisfying these properties can be transformed into a linear arithmetic circuit computing the shares of a threshold secret sharing scheme, assuming a sufficiently large field. As a consequence, we derive upper and lower bounds on the arithmetic circuit complexity of computing the shares in threshold secret sharing schemes. |
| title | Secret Sharing on Superconcentrator |
| topic | Computational Complexity Cryptography and Security Information Theory Combinatorics |
| url | https://arxiv.org/abs/2302.04482 |