Communication Efficient Secret Sharing With Small Share Size

Abstract

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 ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\triangle $ </tex-math></inline-formula> -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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">decoding delay</i> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\triangle $ </tex-math></inline-formula> -universal cases, whereas each secret and share of our schemes are a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">single</i> element of a finite field <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{q^{e}}$ </tex-math></inline-formula> , and each participant of an authorized subset provides a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">single</i> element of a same subfield of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{q^{e}}$ </tex-math></inline-formula> 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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">smaller</i> share sizes than other existing works, which are realized by using a smaller sub-packetization <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$e$ </tex-math></inline-formula> and a smaller base field <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula> . Indeed, the sub-packetizations of our schemes are <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">minimum</i> for given <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula> among balanced CESS schemes. In addition, when our constructions are used to generate communication efficient <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,r)$ </tex-math></inline-formula> threshold schemes, we derive a generalized Shamir’s scheme that universally achieves optimal decoding bandwidth and optimal information rate for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">the first time</i> , where the restriction on the number of available participants is removed.