Paper 2021/802

On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing

Divesh Aggarwal, National University of Singapore
Eldon Chung, National University of Singapore
Maciej Obremski, National University of Singapore
João Ribeiro, Carnegie Mellon University
Abstract

Secret-sharing is one of the most basic and oldest primitives in cryptography, introduced by Shamir and Blakely in the 70s. It allows to strike a meaningful balance between availability and confidentiality of secret information. It has a host of applications most notably in threshold cryptography and multi-party computation. All known constructions of secret sharing (with the exception of those with a pathological choice of parameters) require access to uniform randomness. 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, 15 years ago, Bosley and Dodis asked whether it is even possible to build 2-out-of-2 secret sharing without access to uniform randomness. In this work, we make progress towards resolving this question. We answer this question for secret sharing schemes with important additional properties, i.e., either leakage-resilience or non-malleability. We prove that, unfortunately, for not too small secrets, it is impossible to construct any of 2-out-of-2 leakage-resilient secret sharing or 2-out-of-2 non-malleable secret sharing without access to uniform randomness. Given that the problem whether 2-out-of-2 secret sharing requires uniform randomness has been open for a long time, it is reasonable to consider intermediate problems towards resolving the open question. In a spirit similar to NP-completeness, we 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'.

Note: Minor revisions. Added Funding Acknowledgements. Added sub-section about computational setting.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2022
Keywords
Secret sharing leakage-resilient secret sharing non-malleable secret sharing Randomness Extraction Random-less reductions
Contact author(s)
dcsdiva @ nus edu sg
History
2022-09-19: last of 2 revisions
2021-06-14: received
See all versions
Short URL
https://ia.cr/2021/802
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/802,
      author = {Divesh Aggarwal and Eldon Chung and Maciej Obremski and João Ribeiro},
      title = {On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2021/802},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/802}},
      url = {https://eprint.iacr.org/2021/802}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.