Near-Optimal Secret Sharing and Error Correcting Codes in \(\mathsf {AC}^0\)
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 th
- PDF / 505,282 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 23 Downloads / 184 Views
Department of Computer Science, Johns Hopkins University, Baltimore, USA [email protected],[email protected] 2 Department of Computer Science, Technion, Haifa, Israel [email protected] 3 UCLA, Los Angeles, USA
Abstract. 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.
1
Introduction
The motivation for this paper comes from two different sources. The first is the general theme of improving performance at the price of allowing some small probability of error or failure. This is evident throughout computer science. For example, randomized algorithms tend to be much more efficient than their deterministic counterparts. In cryptography and coding theory, randomization with small failure probability can often be used to amplify security or improve efficiency. This is arguably a good tradeoff in practice. The second source of motivation is the goal of minimizing the computational complexity of cryptographic primitives and related combinatorial objects. For example, a line of work on the parallel complexity of cryptography [2,3,16,18,29] A full version of this paper appears in [13]. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 424–458, 2017. https://doi.org/10.1007/978-3-319-70503-3_14
Near-Optimal Secret Sharing and Error Correcting Codes in AC0
425
successfully constructed one way functions and other cryptographic primitives in the complexity class NC0 based on different kinds of assumptions, including very standard cryptographic assumptions. Works along this line have found several unexpected applications, most recently in the context of general-purpose obfuscation [24]. The study of low-complexity cryptography is also motivated by the goal of obtaining stronger negative results. For instance, low-complexity pseudo-random functions imply
Data Loading...
