In this paper, we show that by allowing some slight relaxation such as a small error probability, we can construct much better secret sharing schemes and error correcting codes in the class AC0. In some cases, our parameters are close to optimal and would be impossible to achieve without the relaxation. Our results significantly improve previous constructions in various parameters.
Our constructions combine several ingredients in pseudorandomness and combinatorics in an innovative way. Specifically, we develop a general technique to simultaneously amplify security threshold and reduce alphabet size, using a two-level concatenation of protocols together with a random permutation. We demonstrate the broader usefulness of this technique by applying it in the context of a variant of secure broadcast.
Category / Keywords: secret sharing Original Publication (with minor differences): IACR-TCC-2017 Date: received 22 Sep 2017, last revised 4 Jan 2018 Contact author: kcheng17 at jhu edu Available format(s): PDF | BibTeX Citation Note: Some minor edits, including some references about previous work and some descriptions in the application part. Also note that the paper was published in TCC 2017 Version: 20180105:010130 (All versions of this report) Short URL: ia.cr/2017/927 Discussion forum: Show discussion | Start new discussion