Communication Efficient Secret Sharing with Small Share Size

Communication efficient secret sharing (CESS) schemes are a class of threshold schemes that aim to minimize the so-called decoding bandwidth, namely the necessary amount of communication between a combiner who wants to reconstruct the secret and the available participants storing shares of the secret. Previous works proved that the decoding bandwidth had a tight lower bound related to the number of available participants. Some threshold schemes that achieved the lower bound (optimal decoding bandwidth) and optimal information rate were constructed for a given number (non-universal case) or multiple distinct number (Δ-universal case) of available participants. However, all those CESS schemes have large share sizes. Moreover, they have a common feature that each secret and share are a vector with multiple coordinates, which results in the decoding delay since the combiner must reconstruct a part of coordinates of the secret at first, and these recovered coordinates will be used to reconstruct another part of coordinates of the secret. In this work, we describe a new construction for CESS schemes of non-universal and Δ-universal cases, whereas each secret and share of our schemes are a single element of a finite field Fqe, and each participant of an authorized subset provides a single element of a same subfield of Fqe to the combiner to reconstruct the secret. We find that the CESS schemes of this type, termed balanced CESS schemes, have an inevitable restriction on the number of available participants, but our schemes has no decoding delay. Furthermore, our schemes have smaller share sizes than other existing works, which are realized by using a smaller sub-packetization e and a smaller base field Fq. Indeed, the sub-packetizations of our schemes are minimum for given Fq among balanced CESS schemes. In addition, when our constructions are used to generate communication efficient (n, r) threshold schemes, we derive a generalized Shamir’s scheme that universally achieves optimal decoding bandwidth and optimal information rate for the first time, where the restriction on the number of available participants is removed.