CryptoDB
On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2022 |
| Abstract: | Secret-sharing is one of the most fundamental primitives in cryptography, and has found several applications. All known constructions of secret sharing (with the exception of those with a pathological choice of parameters) require access to uniform randomness. However, in practice it is extremely challenging to generate a source of uniform randomness. This has led to a large body of research devoted to designing randomized algorithms and cryptographic primitives from imperfect sources of randomness. Motivated by this, Bosley and Dodis (TCC 2007) asked whether it is even possible to construct a $2$-out-of-$2$ secret sharing scheme without access to uniform randomness. In this work, we make significant progress towards answering this question. Namely, we resolve this question for secret sharing schemes with important additional properties: $1$-bit leakage-resilience and non-malleability. We prove that, for not too small secrets, it is impossible to construct any $2$-out-of-$2$ leakage-resilient or non-malleable secret sharing scheme without access to uniform randomness. Given that the problem of whether $2$-out-of-$2$ secret sharing requires uniform randomness has been open for more than a decade, it is reasonable to consider intermediate problems towards resolving the open question. In a spirit similar to NP-completeness, we also study how the existence of a $t$-out-of-$n$ secret sharing without access to uniform randomness is related to the existence of a $t'$-out-of-$n'$ secret sharing without access to uniform randomness for a different choice of the parameters $t,n,t',n'$. |
BibTeX
@inproceedings{tcc-2022-32516,
title={On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing},
publisher={Springer-Verlag},
author={Divesh Aggarwal and Eldon Chung and Maciej Obremski and João Ribeiro},
year=2022
}