Paper 2017/927

Near-Optimal Secret Sharing and Error Correcting Codes in AC0

Kuan Cheng, Yuval Ishai, and Xin Li


We study the question of minimizing the computational complexity of (robust) secret sharing schemes and error correcting codes. In standard instances of these objects, both encoding and decoding involve linear algebra, and thus cannot be implemented in the class AC0. The feasibility of non-trivial secret sharing schemes in AC0 was recently shown by Bogdanov et al. (Crypto 2016) and that of (locally) decoding errors in AC0 by Goldwasser et al. (STOC 2007). 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.

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

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2017
secret sharing
Contact author(s)
kcheng17 @ jhu edu
2018-01-05: last of 3 revisions
2017-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kuan Cheng and Yuval Ishai and Xin Li},
      title = {Near-Optimal Secret Sharing and Error Correcting Codes in AC0},
      howpublished = {Cryptology ePrint Archive, Paper 2017/927},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.