A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866907784565489664 |
|---|---|
| author | Cheng, Qi Cao, Hongru Lin, Sian-Jheng Yu, Nenghai |
| author_facet | Cheng, Qi Cao, Hongru Lin, Sian-Jheng Yu, Nenghai |
| contents | The threshold secret sharing scheme allows the dealer to distribute the share to every participant such that the secret is correctly recovered from a certain amount of shares. The traditional $(k, n)$-threshold secret sharing scheme requests that the number of participants $n$ is known in advance. In contrast, the evolving secret sharing scheme allows that $n$ can be uncertain and even ever-growing. In this paper, we consider the evolving secret sharing scenario. Using the prefix codes and the properties of the polynomial ring, we propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $\ell$-bit secret over a polynomial ring, with correctness and perfect security. The proposed schemes establish the connection between prefix codes and the evolving schemes for $k\geq2$, and are also first evolving $k$-threshold secret sharing schemes by generalizing Shamir's scheme onto a polynomial ring. Specifically, the proposal also provides an unified mathematical decryption for prior evolving $2$-threshold secret sharing schemes. Besides, the analysis of the proposed schemes show that the size of the $t$-th share is $(k-1)(\ell_t-1)+\ell$ bits, where $\ell_t$ denotes the length of a binary prefix code of encoding integer $t$. In particular, when $δ$ code is chosen as the prefix code, the share size achieves $(k-1)\lfloor\lg t\rfloor+2(k-1)\lfloor\lg ({\lfloor\lg t\rfloor+1}) \rfloor+\ell$, which improves the prior best result $(k-1)\lg t+6k^4\ell\lg{\lg t}\cdot\lg{\lg {\lg t}}+ 7k^4\ell\lg k$, where $\lg$ denotes the binary logarithm. When $k=2$, the proposed scheme also achieves the minimal share size for single-bit secret, which is the same as the best known scheme. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_01144 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring Cheng, Qi Cao, Hongru Lin, Sian-Jheng Yu, Nenghai Information Theory Cryptography and Security The threshold secret sharing scheme allows the dealer to distribute the share to every participant such that the secret is correctly recovered from a certain amount of shares. The traditional $(k, n)$-threshold secret sharing scheme requests that the number of participants $n$ is known in advance. In contrast, the evolving secret sharing scheme allows that $n$ can be uncertain and even ever-growing. In this paper, we consider the evolving secret sharing scenario. Using the prefix codes and the properties of the polynomial ring, we propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $\ell$-bit secret over a polynomial ring, with correctness and perfect security. The proposed schemes establish the connection between prefix codes and the evolving schemes for $k\geq2$, and are also first evolving $k$-threshold secret sharing schemes by generalizing Shamir's scheme onto a polynomial ring. Specifically, the proposal also provides an unified mathematical decryption for prior evolving $2$-threshold secret sharing schemes. Besides, the analysis of the proposed schemes show that the size of the $t$-th share is $(k-1)(\ell_t-1)+\ell$ bits, where $\ell_t$ denotes the length of a binary prefix code of encoding integer $t$. In particular, when $δ$ code is chosen as the prefix code, the share size achieves $(k-1)\lfloor\lg t\rfloor+2(k-1)\lfloor\lg ({\lfloor\lg t\rfloor+1}) \rfloor+\ell$, which improves the prior best result $(k-1)\lg t+6k^4\ell\lg{\lg t}\cdot\lg{\lg {\lg t}}+ 7k^4\ell\lg k$, where $\lg$ denotes the binary logarithm. When $k=2$, the proposed scheme also achieves the minimal share size for single-bit secret, which is the same as the best known scheme. |
| title | A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring |
| topic | Information Theory Cryptography and Security |
| url | https://arxiv.org/abs/2402.01144 |