Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions
SPINI, Gabriele
Institut de Mathématiques de Bordeaux [IMB]
Mathematisch Instituut Universiteit Leiden
Centrum voor Wiskunde en Informatica [CWI]
Institut de Mathématiques de Bordeaux [IMB]
Mathematisch Instituut Universiteit Leiden
Centrum voor Wiskunde en Informatica [CWI]
CRAMER, Ronald
Mathematisch Instituut Universiteit Leiden
Centrum voor Wiskunde en Informatica [CWI]
Leer más >
Mathematisch Instituut Universiteit Leiden
Centrum voor Wiskunde en Informatica [CWI]
SPINI, Gabriele
Institut de Mathématiques de Bordeaux [IMB]
Mathematisch Instituut Universiteit Leiden
Centrum voor Wiskunde en Informatica [CWI]
Institut de Mathématiques de Bordeaux [IMB]
Mathematisch Instituut Universiteit Leiden
Centrum voor Wiskunde en Informatica [CWI]
CRAMER, Ronald
Mathematisch Instituut Universiteit Leiden
Centrum voor Wiskunde en Informatica [CWI]
< Leer menos
Mathematisch Instituut Universiteit Leiden
Centrum voor Wiskunde en Informatica [CWI]
Idioma
en
Communication dans un congrès
Este ítem está publicado en
Advances in Cryptology -- EUROCRYPT 2015, Advances in Cryptology -- EUROCRYPT 2015, Advances in Cryptology -- EUROCRYPT 2015, 2015-04-26, Sofia. 2015-04-14, vol. 9057, n° XVIII, p. 313-336
Springer
Resumen en inglés
We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that ...Leer más >
We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that the privacy property of the resulting secret sharing scheme essentially becomes independent of the code we use, only depending on its rate. This allows us to fully harness the algorithmic properties of recent code constructions such as efficient encoding and decoding or efficient list-decoding. Choosing the error correcting codes and universal hash functions involved carefully, we obtain solutions to the following open problems: - A linear near-threshold secret sharing scheme with both linear time sharing and reconstruction algorithms and large secrets (i.e. secrets of size $\Omega(n)$). Thus, the computational overhead per shared bit in this scheme is *constant*. - An efficiently reconstructible robust secret sharing scheme for $n/3 \leq t < (1 - \epsilon) \cdot n/2$ corrupted players (for any constant $\epsilon > 0$) with shares of optimal size $O(1 + \lambda / n)$ and secrets of size $\Omega(n + \lambda)$, where $\lambda$ is the security parameter.< Leer menos
Palabras clave en inglés
Linear Secret Sharing Schemes
Linear Time Sharing
Robust Secret Sharing
Orígen
Importado de HalCentros de investigación