Preliminaries

Denote \lbrack n\rbrack ≝ \left\{ 1,\ldots,n \right\}. Denote f\left( \mathcal{S} \right) ≝ \left\{ f(x)|x \in \mathcal{S} \right\}, disambiguated by context. Given a bilinear map \circ :U \times V \rightarrow W we naturally extend it to U^{n} \times V^{n} \rightarrow W^{n} by applying it element wise. Given a vector \mathbf{x} \in \mathcal{S}^{n} and a subset of the indices \mathcal{I} \subseteq \lbrack n\rbrack. We write the x_{\mathcal{I}} \in \mathcal{S}^{|\mathcal{I}|} to be the vector containing only elements at those indices. Similarly define \pi_{\mathcal{I}}:\mathcal{S}^{n} \rightarrow \mathcal{S}^{|\mathcal{I}|} to be the projection map x \mapsto x_{\mathcal{I}}. Rings are assumed finite, unital and commutative unless state otherwise.

Given an bilinear map b:A \times B \rightarrow C we define a bilinear map \hat{b}:A^{n} \times B^{n} \rightarrow C^{n} to be the coordinate wise application of b so that z = \hat{b}(x,y) is given by z_{i} = b\left( x_{i},y_{i} \right) in the coordinate basis.

Linear Secret Sharing

A linear secret sharing scheme is a method to store a secret value from a space Z over a number of parties by handing each a secret share from a space U. We adapt the definitions from (Cascudo et al. 2018), (Abspoel et al. 2020):

Given an R-LSSS \mathcal{S}, denote with \lbrack z\rbrack_{\mathcal{S}} for z \in Z the set of preimages \left\{ c \in C~|~\psi(c) = z \right\} of \psi. A valid sharing of a secret z \in \mathcal{Z} is given by a uniform random sampling c\overset{\ \$}{\leftarrow}\lbrack z\rbrack_{\mathcal{S}} where each party i is assigned share c_{i}. The purpose of a secret sharing scheme is that qualified subsets of shares reconstruct the secret, while smaller privacy subsets reveal nothing of the secret.

Informally, a subset of parties \mathcal{A} \subseteq \lbrack n\rbrack is a reconstructing set if the assigned subset of shares c_{\mathcal{A}} corresponds to a unique secret z \in Z for any sharing c \in C. We can formalize this by observing that share selection map \pi_{\mathcal{A}} is a linear map wich ‘forgets” the subspace \ker\pi_{\mathcal{A}}|_{C}. If this is contained in the subspace \ker\psi ignored by reconstruction, then the secret is unique.

Similarly, a subset of parties \mathcal{A} \subseteq \lbrack n\rbrack is a privacy set if for any sharing c \in C, the shares c_{\mathcal{A}} reveal no information about the secret. This is taken in the information-theoretic sense; given knowledge of a prior distribution of the secret learning c_{\mathcal{A}} does not change the posterior distribution. As \pi_{\mathcal{A}} and \psi are both linear, it is sufficient to require that c_{\mathcal{A}} is compatible with every value of z.

We also introduce a notion of efficiency, the rate

Intuitively, the information ratio is the total storage size of the secret shares as a multiple of the size of the secrets. It is bounded by requirements on reconstruction and privacy. Notably there are schemes with |Z| > |U|, e.g. vector secret sharing.

From this lemma follows that given an R-LSSSs for Z, we can construct an LSSS with secret space Z^{n} for any n.

Arithmetic Secret Sharing

Take operations over \lbrack x\rbrack to mean the direct image of the operation on the input sets, e.g. \lbrack a\rbrack + \lbrack b\rbrack ≝ \left\{ x + y|x \in \lbrack a\rbrack,y \in \lbrack b\rbrack \right\}. From the linearity of \psi it follows that \lbrack a\rbrack + \lbrack b\rbrack = \lbrack a + b\rbrack and also c \cdot \lbrack a\rbrack = \lbrack c \cdot a\rbrack. To support arbitrary computation over secrets we also need multiplicative operations. Equipping the secret space Z with multiplication turns it into an R-algebra and allows us to define secret sharing schemes that support this algebra.

Note that since C_{\mathcal{S}} is an R-module and {\hat{\circ}}_{U} is a bilinear map, it follows that C_{\mathcal{T}} an R-module.

This allows us to write

\lbrack a\rbrack_{\mathcal{S}} \circ_{U}\lbrack b\rbrack_{\mathcal{S}} = \left\lbrack a \circ_{Z}b \right\rbrack_{\mathcal{T}}.

TODO: Lemma for ASSS.

TODO: Direct product of two LSSSs/ASSSs, i.e. concatenation.

Shamir Secret Sharing

Lenstra constant

Galois Rings

The rings of practical interested are {\mathbb{Z}}_{2^{k}} as these allow for efficient binary implementations. For sake of completeness we generalize this to {\mathbb{Z}}_{p^{k}} for any prime p. (From {\mathbb{Z}}_{p^{k}} it can be generalized to arbitrary {\mathbb{Z}}_{m} by applying the Chinese Remainder Theorem, which we will not persue.)

For small p using {\mathbb{Z}}_{p^{k}} directly is often problematic as the ring does not have sufficient structure. This is commonly solved using Galois rings, an extension of {\mathbb{Z}}_{p^{k}} much like a Galois extension to a field. As in finite fields, all extension of the same degree are isomorphic allowing the following definition:

In particular {\operatorname{GR}(p^{k},1)} \simeq {\mathbb{Z}}_{p^{k}} and {\operatorname{GR}(p^{1},d)} \simeq {\mathbb{F}}_{p^{d}}, hence Galois Rings simultaneously generalize over rings {\mathbb{Z}}_{p^{k}} and fields {\mathbb{F}}_{p^{d}} preserving much of their structure. See (Wan 2012) for a full treatment and proofs of the following theorems:

The ideals form a descending chain (1) \supset (p) \supset \left( p^{2} \right) \supset \cdots \supset \left( p^{k - 1} \right) \supset (0) with (p) the unique maximal ideal, thus \operatorname{GR}(p^{k},d) is a local ring with residue field {\operatorname{GR}(p^{k},d)}/(p) \simeq {\mathbb{F}}_{p^{d}}. Denote with \overline{\square}:{\operatorname{GR}(p^{k},d)} \rightarrow {\mathbb{F}}_{p^{d}} the homomorphism given by \overline{x} \mapsto x\operatorname{mod}\,(p).

An important tool in Galois rings is Hensel lifting, see hensel-lift.

References