Cryptology ePrint Archive: Report 2021/802

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

Divesh Aggarwal and Eldon Chung and Maciej Obremski and João Ribeiro

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'.

Category / Keywords: foundations / Secret sharing, leakage-resilient secret sharing, non-malleable secret sharing, Randomness Extraction, Random-less reductions

Date: received 14 Jun 2021, last revised 11 Oct 2021

Contact author: dcsdiva at nus edu sg

Available format(s): PDF | BibTeX Citation

Note: Minor revisions

Version: 20211011:230044 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]