New Results in Share Conversion, with Applications to Evolving Access Structures

Ben David, Tamar; Narayanan, Varun; Nissenbaum, Olga; Paskin-Cherniavsky, Anat

doi:10.4230/LIPIcs.ITC.2025.11

New Results in Share Conversion, with Applications to Evolving Access Structures

Tamar Ben David

Ariel University, Israel Varun Narayanan

University of California, Los Angeles, CA, USA Olga Nissenbaum

Ariel University, Israel Anat Paskin-Cherniavsky

Ariel University, Israel

Abstract

We say there is a share conversion from a secret-sharing scheme $\Pi$ to another scheme $\Pi^{\prime}$ implementing the same access structure if each party can locally apply a deterministic function to their share to transform any valid secret-sharing under $\Pi$ to a valid (but not necessarily random) secret-sharing under $\Pi^{\prime}$ of the same secret. If such a conversion exists, we say that $\Pi\geq\Pi^{\prime}$ . This notion was introduced by Cramer et al. (TCC’05), where they particularly proved that for any access structure, any linear secret-sharing scheme over a given field $\mathbb{F}$ , has a conversion from a CNF scheme, and is convertible to a DNF scheme.

In this work, we initiate a systematic study of convertability between secret-sharing schemes, and present a number of results with implications to the understanding of the convertibility landscape.

$\blacksquare$

In the context of linear schemes, we present two key theorems providing necessary conditions for convertibility, proved using linear-algebraic tools. It has several implications, such as the fact that Shamir secret-sharing scheme can be neither maximal or minimal. Another implication of it is that a scheme may be minimal if its share complexity is at least as high as that of DNF.
$\blacksquare$

Our second key result is a necessary condition for convertibility to CNF from a broad class of (not necessarily linear) schemes. This result is proved via information-theoretic techniques and implies non-maximality for schemes with share complexity smaller than that of CNF.

We also provide a condition which is both necessary and sufficient for the existence of a share conversion to some linear scheme. The condition is stated as a system of linear equations, such that a conversion exists if and only if a solution to the linear system exists. We note that the impossibility results for linear schemes may be viewed as identifying a subset of contradicting equations in the system.

Another contribution of our paper, is in defining and studying share conversion for evolving secret-sharing schemes. In such a schemes, recently introduced by Komargodski et al. (IEEE ToIT’18), the number of parties is not bounded apriori, and every party receives a share as it arrives, which never changes in the sequel. Our impossibility results have implications to the evolving setting as well. Interestingly, unlike in the standard setting, there is no maximum or minimum in a broad class of evolving schemes, even without any restriction on the share size.

Finally, we show that, generally, there is no conversion between additive schemes over different fields, even from CNF to DNF! However by relaxing from perfect to statistical security, it may be possible to convert, and exemplify this for $(n,n)$ -threshold access structures.

Keywords and phrases:

secret sharing, linear secret sharing, evolving access structures, share conversion, feasibility

Copyright and License:

2012 ACM Subject Classification:

Security and privacy

\rightarrow

Information-theoretic techniques ; Security and privacy

\rightarrow

Mathematical foundations of cryptography

Editor:

Niv Gilboa

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Secret-sharing is a fundamental notion in cryptography. A secret-sharing scheme enables a dealer to distribute a secret among a set of parties so that any pre-specified subset of qualified parties can recover the secret while any other subset of parties remains oblivious to the secret. The monotone class of subsets of qualified parties constitutes the access structure realized by the secret-sharing scheme.

Secret-sharing is a building block for realizing several complex cryptographic tasks. Certain such tasks may require additional properties in the secret-sharing scheme – for instance, succinctness of the shares, or homomorphism and other algebraic properties. This suggests use cases where a protocol requires secret-sharing according to one scheme during one stage, and according to another scheme during another. This motivated non-interactive conversion between secret-sharing schemes, which was formalized in [9] by Cramer, Damgard, and Ishai as share conversion.

We say there is a share conversion from a secret-sharing scheme $\Pi$ to another scheme $\Pi^{\prime}$ implementing the same access structure $\Gamma$ if each party can locally apply a deterministic function to their share to transform any valid secret-sharing under $\Pi$ to a valid (but not necessarily random) secret-sharing of the same secret under $\Pi^{\prime}$ . In full generality, share conversion may be defined from $\Pi$ to $\Pi^{\prime}$ which implement different access structures $\Gamma\supseteq\Gamma^{\prime}$ , respectively. Moreover the secret under $\Pi^{\prime}$ after the transformation can be a pre-specified function of the secret under $\Pi$ before transformation. In this work, we focus on the natural case where $\Gamma=\Gamma^{\prime}$ and the above-mentioned function is identity.

In the sequel, we will say $\Pi\geq\Pi^{\prime}$ if there is a share conversion from $\Pi$ to $\Pi^{\prime}$ . This induces a partial ordering over secret-sharing schemes realizing any access structure $\Gamma$ . Many important insights into the partial order $\geq$ of convertability for linear secret-sharing schemes over a finite field were provided in [9]. Among other results, they proved that, for any access structure $\Gamma$ and finite filed $\mathbb{F}$ , CNF-based secret-sharing scheme $CNF_{\Gamma,\mathbb{F}}$ is maximal, and DNF-based secret-sharing scheme $DNF_{\Gamma,\mathbb{F}}$ is minimal among the set of all linear secret-sharing schemes for $\Gamma$ over $\mathbb{F}$ . I.e., $CNF_{\Gamma,\mathbb{F}}\geq\Pi\geq DNF_{\Gamma,\mathbb{F}}$ for any linear secret-sharing scheme $\Pi$ . Note, however, that the existence of additional minimal and maximal schemes is not ruled out in [9]. For certain access structures, specifically (2,3)-threshold, they demonstrated that certain linear schemes like Shamir secret-sharing scheme in not maximal, as it is not convertible to CNF. They also show that a limited class of linear secret-sharing schemes – the so called replicated schemes, that are similar in structure to CNF in the sense that the secret is defined as the sum of random elements, and every party gets a subset of them as it’s share, are not maximal for $(k,n)$ -threshold access structures unless they have share complexity as high as that of CNF (see Section 3.3 in [9]).

In this paper, we initiate a systematic study of convertibility between secret-sharing schemes, and obtain new results in several directions:

$\blacksquare$

We develop new and easily checkable necessary conditions for share conversion between linear schemes implementing a given access structure. These necessary conditions are in the form of linear algebraic constraints on the monotone span program (MSP) corresponding to the linear schemes. Using these conditions, we are able to get a clearer view of the partial order induced by convertibility over the linear schemes.
$\blacksquare$

We develop a necessary and sufficient condition for a conversion between the linear schemes $\Pi,\Pi^{\prime}$ in form of a linear system decided by the MSP of $\Pi$ and $\Pi^{\prime}$ which has a solution if and only if $\Pi\geq\Pi^{\prime}$ .
$\blacksquare$

Next, we address the broader problem of share conversions involving potentially non-linear secret-sharing schemes. To this end, we introduce the notion of non-degenerate secret-sharing schemes and establish a necessary condition for converting shares from general (potentially non-linear) schemes to non-degenerate ones. This condition has implications for share conversion to CNF and Shamir secret-sharing schemes, which are both non-degenerate.
$\blacksquare$

We apply our results to develop necessary conditions for conversion to the well-studied schemes, such as CNF, DNF, and Shamir secret-sharing schemes.
$\blacksquare$

The necessary conditions we develop also bear consequences for secret-sharing schemes for evolving setting, i.e. where the number of parties is not bounded, and the party gets it’s share when appears. We show that, for several interesting evolving access structures, there is no maximal or minimal scheme.
$\blacksquare$

We also initiate the study of share conversion between different fields. We show that, in a general case, there is no conversion between linear schemes over two different fields. To circumvent this, we propose a general approach of bounding the randomness domain in a source scheme. We build a leaky additive scheme over ${\mathbb{Z}}_{p}$ allowing conversion into ${\mathbb{Z}}_{q}$ . As it’s possible to see from our example, the proposed approach could result in a privacy leakage, which is often tolerable if small.

1.1 Overview of Our Results

In this section, we provide a brief exposition of our results, which we formally describe and prove in the subsequent sections.

Necessary conditions for conversion between linear schemes.

A linear secret-sharing scheme $\Pi$ over a field $\mathbb{F}$ implementing access structure $\Gamma$ over $n$ parties is characterized by a monotone span program described as a triple $(\mathbb{F},M,\rho)$ , where $M$ is a matrix over $\mathbb{F}$ of dimension $m\times k$ and $\rho:[m]\rightarrow[n]$ defines the set of $M$ ’s rows corresponding to a certain party [16].

To share a secret $s\in\mathbb{F}$ , the dealer samples a vector $\mathbf{r}\in\mathbb{F}^{k}$ such that its first coordinate is $s$ , and computes $\mathbf{v}=M\cdot{\mathbf{r}}$ . Then, the $i$ ’th share in $\Pi$ is $\mathsf{sh}_{i}=\mathbf{v}[\rho^{(-1)}(i)]$ , which is the sub-vector containing entries in the coordinates $\rho^{-1}(i)$ . A qualified set of parties $T$ can recover the secret using a reconstruction function $\alpha\in\mathbb{F}^{|\rho^{-1}(T)|}$ such that

\left({\alpha}\right)^{\mathsf{T}}\cdot\mathbf{v}_{T}=\left({\alpha}\right)^{% \mathsf{T}}\cdot M_{T}\cdot\mathbf{r}=\mathbf{r}[1]=s.

Here, $\mathbf{v}_{T}=\mathbf{v}[\rho^{-1}(T)]$ and $M_{T}=M[\rho^{-1}(T),\cdot]$ , i.e., the rows of $M$ corresponding to the coordinates $\rho^{-1}(T)$ (under some pre-specified ordering).

One of the key tools in our paper is a necessary condition for conversion between a pair of linear schemes. Informally, it states that conversion is impossible, if the schemes satisfy certain linear-algebraic conditions.

Theorem 1 (Necessary condition for conversion between linear schemes – Informal).

There is no share conversion from a linear secret-sharing scheme described by MSP $({\mathbb{F}},M\in\mathbb{F}^{m\times k},\rho)$ to another linear scheme $({\mathbb{F}},M^{\prime}\in\mathbb{F}^{m^{\prime}\times k^{\prime}},\rho^{% \prime})$ both realizing $\Gamma$ , if there are sets of parties $T$ , $T^{*}$ and party $h\notin T\cup T^{*}$ such that $T\cup h\in\Gamma$ , and no strict subsets of $T\cup h$ is qualified, and, when $\alpha$ and $\alpha^{\prime}$ are reconstruction functions for $T\cup h$ in $M$ and $M^{\prime}$ , respectively,

1.

$\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}\cdot M^{\prime}_{h}\in\mathrm{% Rowspan}(M^{\prime}_{T^{*}})$ .
2.

$\left({\alpha_{h}}\right)^{\mathsf{T}}\cdot M_{h}\notin\left.\left(\mathrm{% Rowspan}(M_{T})\cap\mathrm{Rowspan}(M_{h})\right)+\left(\mathrm{Rowspan}(M_{T^% {*}})\cap\mathrm{Rowspan}(M_{h})\right)\right.$ .

This theorem is formally stated as Theorem 27 in the technical section. We demonstrate the power of this seemingly abstract necessary condition by providing a concrete application to well studied secret-sharing schemes, and its application to share conversions for evolving access structures.

We exploit the fact that the share conversion function is local and the secret is preserved during the share conversion. We can reach a contradiction if it is possible to produce a pair of fooling instances of sharing under the source scheme that result in shares after conversion that do not respect the dependencies present among the shares in the target distribution. This proof is a vast generalization of the proof of a result in [9] that showed that in $(2,3)$ -Shamir is not convertible to CNF, so that it applies to conversion between any pair of linear schemes. Specifically, it follows that any Shamir secret-sharing scheme is not convertible to CNF.

In Theorem 30 we prove a different type of necessary condition for convertibility between linear schemes. As a corollary from Theorem 1 and Theorem 30, we prove that $D N F$ is not convertible to any linear scheme with lower share complexity. In particular, it is not convertible to Shamir, which proves the non-minimality of the latter.

Both Theorem 30 and Theorem 1 are based on a key technical result – Lemma 25, which involves a single minterm $T$ , while the theorems refer to at least 2 minterms to establish a conversion does not exist. We believe it is a useful conceptual simplification towards understanding convertability.

Convertibility characterization for linear schemes.

We devise a characterization of convertibility between linear schemes by solvability of a certain system of linear equations $\mathcal{L}_{\Pi,\Pi^{\prime}}$ which we provide in Section 5.

Theorem 2 (Theorem 35, informal).

There is a conversion from a linear scheme $\Pi$ to a linear scheme $\Pi^{\prime}$ realizing the same access structure over the same field if and only if the linear system $\mathcal{L}_{\Pi,\Pi^{\prime}}$ has a solution.

A solution of the system encodes a conversion in a straightforward (although redundant) way. The high level idea is to solve for variables $X_{{\mathbf{r}},i,j}$ , where $X_{{\mathbf{r}},i,j}$ represents the $j$ ’th share of $p_{i}$ , when converting from a sharing based on randomness ${\mathbf{r}}$ in $\Pi$ (as is sometimes useful, here ${\mathbf{r}}$ is assumed to include $s$ ). We note that the impossibility in Theorem 1 may be viewed as identifying a subset of contradicting equations, so that a solution does not exist.

Share conversion from non-linear schemes.

In a prior work [9], CNF was proved to be maximal among linear schemes over the same field. In this work, we prove new necessary conditions for share conversion from general (potentially non-linear) schemes to CNF secret-sharing.

For this, we introduce the notion of non-degenerate secret-sharing schemes. A secret-sharing scheme $\Pi$ is non-degenerate if any sub-scheme of $\Pi$ is equivalent to $\Pi$ . Here, a secret-sharing scheme $\Pi^{\prime}$ is a sub-scheme of $\Pi$ if the secret domains of both schemes are identical, and every valid secret-sharing under $\Pi^{\prime}$ is also a valid secret-sharing under $\Pi$ . A formal definition of non-degenerate secret-sharing schemes is provided in Definition 36.

To drive down this subtle notion, we will demonstrate that a 2-out-of-3 DNF secret-sharing scheme for secret domain $\{0,1\}$ is not non-degenerate. In 2-out-of-3 DNF secret-sharing of a secret $s\in\{0,1\}$ , the shares of the 3 parties are $(r_{1,2},s\oplus r_{3,1}),(s\oplus r_{1,2},r_{2,3})$ and $(s\oplus r_{2,3},r_{3,1})$ , respectively, where $r_{1,2},r_{2,3}$ and $r_{3,1}$ are uniform and independent bits. Consider a modified secret-sharing scheme in which the secret $s$ is shared among the three parties exactly as in 2-out-of-3 DNF secret-sharing except that $r_{1,2},r_{2,3}$ and $r_{3,1}$ are uniform and only pairwise independent bits. It is easy to see that the latter is a 2-out-of-3 secret-sharing which is also a sub-scheme of the former. However, they are not clearly not equivalent: the former uses more randomness; hence, 2-out-of-3 DNF is not non-degenerate.

On the other hand, CNF secret-sharing scheme for arbitrary access structures over a group $\mathbb{G}$ for secret domain $\mathbb{G}$ , and Shamir secret-sharing scheme are non-degenerate as established in Lemma 38 and Lemma 39, respectively. Lemma 38 is proved by considering the correlation of the shares induced by picking a secret $s\in\mathbb{G}$ at random and secret-sharing it using any secret-sharing scheme $\Pi$ that is a sub-scheme of the given CNF scheme. Appealing to correctness and privacy of $\Pi$ , an information theoretic argument is used to show that the entropy of each share in this correlation is the same as that in the correlation obtained by secret-sharing a random secret $s$ using the CNF scheme. Since the secret domain is the same as the group over which CNF is defined, this further implies in a straightforward way that $\Pi$ coincides with the CNF scheme, establishing its non-degeneracy.

By appealing to non-degeneracy of CNF, and using standard entropy lower bounds, we show that share conversion to CNF scheme is possible only if the share size under the source scheme is at least as large as that in the CNF scheme. The following result is formally stated in Theorem 40.

Theorem 3 (Extended maximality of CNF).

Let $\Pi$ be a secret-sharing scheme realizing an $n$ -party access structure $\Gamma$ with secret domain $\mathbb{G}$ – a finite group. There is a share conversion from $\Pi$ to CNF over $\mathbb{G}$ realizing $\Gamma$ only if, for each $i\in[n]$ , size of the share $i$ in $\Pi$ is at least $\log|\mathbb{G}|\cdot|\{F\in\mathcal{F}\text{ s.t. }i\notin F\}|$ , where $\mathcal{F}$ is the set of all maximal forbidden sets associated with $\Gamma$ .

We note that Theorem 1 also implies results of non-maximality by impossibility of conversion to CNF for certain linear schemes $\Pi$ with low share complexity. These results are mostly subsumed by Theorem 3, both because it does not restrict $\Pi$ to be linear, and in terms of share size.

Share conversion for evolving secret-sharing.

Komargodski et al. [17] defined evolving secret-sharing schemes where the unbounded number of parties arriving one after another, obtain their shares of secret. The previously qualified sets remain qualified, and shares of parties are not refreshed as new parties come, but each newcomer is provided a (potentially) progressively larger share. An evolving access structure is an infinite monotone class of qualified subsets of $\mathbb{N}$ .

We initiate a study of share conversion for evolving secret-sharing, starting with formal extension of the notion of share conversion, MSP and linearity to the evolving setting. Then, we apply the theory we develop for proving impossibility of share conversion in the standard setting to the evolving setting. In particular, some of our results apply to evolving linear secret-sharing schemes, which have been previously considered in the literature, but never explicitly defined.

We address the problem of maximal and minimal secret-sharing schemes for evolving access structures, and show that for several broad classes of evolving schemes there is no maximal and minimal scheme. In Theorem 46 we formally state and prove the following result.

Theorem 4 (No evolving maximal scheme – Informal).

For any non-trivial evolving access structure, there exists no maximal secret-sharing scheme for one-bit secrets.

By a non-trivial evolving access structure (See Definition 45), we mean one that does not devolve into a finite secret-sharing scheme among the first $n$ parties (for some $n$ ) with the remaining parties either being not part of the qualified set or are required to simply receive the secret.

In the other direction, we obtain a slightly weaker result, showing there is no minimal linear scheme for certain access structures. This is formally stated and proved as Theorem 44.

Theorem 5 (No evolving minimal scheme – Informal).

For a certain broad class of evolving access structures $\Gamma$ , and for the finite field $\mathbb{F}_{2}$ , there is no minimal linear evolving scheme for any $\Gamma$ in the class.

Conversion between different fields.

The bit simultaneously shared in two different fields, is called dBit, and is an important primitive for many applications, such as [2, 6, 8, 12, 13, 19, 20, 24]. There exist bit share conversion protocols, here we point out only few of them, such as proposed in [6, 7, 10]. It is natural to raise the question if such a conversion can be done locally.

Generalizing our impossibility result for linear schemes over the same field, we prove the inconvertibility of the maximal $C N F$ scheme over ${\mathbb{Z}}_{p}$ to any other linear scheme over ${\mathbb{Z}}_{q}$ for primes $p\neq q$ with the same secret domain $\left\{{0,1}\right\}$ .

We complement this result with a relaxed form of conversion between additive schemes for certain pairs of distinct primes for 1-bit shares. The relaxation allows for a privacy leakage (over the scheme randomness). It may be interesting to further explore share conversions with a small correctness errors. These may suffice for many applications, while potentially extending the set of convertible secret sharing scheme pairs (denote $\Pi\geq_{\epsilon}\Pi^{\prime}$ ).

1.2 Future work

Our work leaves several fascinating questions open. The main question is to obtain a simpler characterization of convertibility between linear schemes. As a first step, identify pairs of linear schemes $\Pi,\Pi^{\prime}$ over the same field where $\Pi$ is not convertible to $\Pi^{\prime}$ , which is not implied by Theorem 27 or Theorem 30. It may be particularly interesting to find a different type of conflicting requirements in the linear system in Section 5, thereby better understanding the easier linear case, which was also studied in the original paper on share conversion [9]. Another concrete question is to characterize the minimal and maximal schemes for various access structures (in other words, those convertible to CNF, or from DNF). As the linear systems introduced in Section 5 work also for non-linear source schemes, it could be also interesting to explore convertibility from such schemes to linear ones. This would require new techniques not based on theorems as above, that both rely on linearity of $\Pi$ as well.

In evolving setting, proving impossibility results is potentially easier. In our context, it could be interesting to understand whether minimal and/or maximal schemes exist for access structures for which we have not resolved this question.

Finally, it is interesting to find new non-trivial examples of conversions which are possible. As an extension, it is interesting to study the direction of converting from a modified subset of a scheme $\Pi$ where part of the randomness is removed, as we do for a modified version of additive over $\mathbb{Z}_{p}$ to $\mathbb{Z}_{q}$ , and the incurred privacy losses. The motivation here is that some properties of the original $\Pi$ may be preserved by such a transformation, which may suffice for certain applications.

2 Prior Work

Share conversion.

Cramer et al. [9] first defined share conversion for secret-sharing schemes as a way for converting shares of a secret in one scheme into shares of the same secret in a different scheme using only local computation and no communication between parties. Referring to a conversion between schemes realizing the same access structure and defined over the same field, they showed that CNF can be converted to any linear scheme, and any linear scheme can be converted to DNF. Furthermore, they put forward an application of share conversion to improving efficiency of multiparty computation (MPC). Beimel et al. [5] use generalized share conversion including non-identity relation between secrets from $(2,3)$ CNF to $(3,3)$ additive secret-sharing over different groups to $3$ -party private information retrieval (PIR). In fact, they observe that certain share conversions are implicit in state-of-the-art $3$ -party PIR constructions from the literature, and devise another conversions along these lines that induces an improved PIR construction. They also put forward certain impossibility results for certain PIR induced conversions. The following papers [21, 22] show additional positive results for potential conversions for $3$ -party schemes from the PIR-induced family.

Evolving secret-sharing.

Komargodski et al. [17] defined evolving secret-sharing schemes for a case that the number of parties is unbounded, parties are only added as they arrive one after the other, and previously qualified sets remain qualified. They constructed the following evolving linear secret-sharing schemes: (1) a scheme for every evolving access structure, such that, the share size of the $t^{\text{th}}$ party is $2^{t-1}$ ; (2) a $k$ -threshold schemes in which the size of the share of party $p_{t}$ is $O(k\log t)$ ; (3) an undirected st-connectivity schemes in which the share of each party is a bit.

A natural generalization of an evolving threshold access structure is to allow the threshold to depend on the index of the arriving party. Komargodski and Paskin-Cherniavsky [18] showed that any dynamic-threshold access can be realized with an evolving linear secret-sharing scheme in which the size of the share of party $p_{t}$ is $O(t^{4}\cdot\log t)$ . Infinite decision trees were used in [17, 18] to construct evolving secret-sharing schemes. Alon et al. [1] define formally this model. They showed how to construct evolving secret-sharing schemes for generalized infinite decision trees. We use this construction in our work.

Peter in [23] defined evolving conditional disclosure of secrets (CDS), where the number of parties is unbounded, and parties arrive sequentially. Each party holds a private input, and when arrives, it sends a random message to a referee. In turn, at any stage of the protocol, the referee should be able to reconstruct a secret string, held by all the parties, from the messages it gets, if and only if the inputs of the parties that arrived satisfy some condition.

3 Preliminaries

In this section, we present the necessary notation and formal definitions of secret-sharing schemes and evolving secret-sharing schemes.

Notation.

For $n\in{\mathbb{N}}$ by $[n]$ we denote the set $\{1,2,\ldots,n\}$ . We denote by $\log$ the logarithmic function with base $2$ . Vectors are denoted by bold letters (e.g., $\mathbf{r}$ ). For matrices $M$ , $M^{\prime}$ with the same number of columns we denote by $[M;M^{\prime}]$ the concatenation of matrix $M^{\prime}$ below $M$ . For matrices $M$ , $M^{\prime}$ with the same number of rows, $[M|M^{\prime}]$ is the concatenation of $M^{\prime}$ to the right for $M$ . By $\mathrm{Rowspan}(M)$ we denote the set of all vectors spanned by rows of $M$ .

For a set of parties $\mathcal{P}=\{p_{1},\ldots,p_{n}\}$ , when it is clear from the context, we often abuse notation replacing parties by their indexes from $[n]$ . When we refer to a subset of parties $\left\{p_{i_{1}},p_{i_{2}},\ldots,p_{i_{t}}\right\}$ , we assume that $i_{1}<i_{2}<\cdots<i_{t}$ .

We will need the following well known fact in linear algebra.

Fact 6.

Let ${\mathbb{F}}$ be a field, and $A\in{\mathbb{F}}^{n\times k}$ , $\mathbf{v}\in{\mathbb{F}}^{1\times k}$ such that $\mathbf{v}\notin\mathrm{Rowspan}(A)$ . Then there exists a solution $\mathbf{r}$ to the linear system $[\mathbf{v}|A]\mathbf{r}=(1,0,\ldots,0)$ .

Finally, we sometimes abuse notation, and use a linear subspace $L={\mathbb{F}}^{k}$ as a matrix consisting of some basis of $L$ as its rows, without explicitly stating so.

3.1 Secret-Sharing

We start by defining (perfect) secret-sharing schemes for a finite set of parties.

Definition 7 (Access Structures).

Let $\mathcal{P}=\left\{p_{1},\ldots,p_{n}\right\}$ be a set of parties. A collection $\Gamma\subseteq 2^{\left\{p_{1},\ldots,p_{n}\right\}}$ is monotone if $B\in\Gamma$ and $B\subseteq C$ imply that $C\in\Gamma$ . An access structure $\Gamma\subseteq 2^{\left\{p_{1},\ldots,p_{n}\right\}}$ is a monotone collection of non-empty sets. Sets in $\Gamma$ are called authorized, and sets not in $\Gamma$ are called unauthorized. We will represent an $n$ -party access structure by a function $f:\{0,1\}^{n}\rightarrow\{0,1\}$ , where an input (i.e., a string) $\sigma=(\sigma_{1},\sigma_{2},\ldots,\sigma_{n})\in\{0,1\}^{n}$ represents the set $A_{\sigma}=\{p_{i}:i\in[n],\sigma_{i}=1\}$ , and $f(\sigma)=1$ if and only if $A\in\Gamma$ . We will also call $f$ an access structure.

In a monotone access structure, the set $A\in\Gamma$ is called a minterm if there is no $B\subset A$ such that $B\in\Gamma$ . The set $A\notin\Gamma$ is called a maxterm if for all $p_{i}\notin A$ it holds that $A\cup\{p_{i}\}\in\Gamma$ .

The most basic and well-known access structure is the threshold access structure:

Definition 8 (Threshold Access Structures).

Let $1\leq k\leq n$ . A $k$ -out-of- $n$ threshold access structure $\Gamma$ over a set of parties $\mathcal{P}=\left\{p_{1},\ldots,p_{n}\right\}$ is the access structure containing all subsets of size at least $k$ , that is, $\Gamma=\{A\subseteq P:|A|\geq k\}$ .

A secret-sharing scheme defines a way to distribute shares to parties. Such a scheme is said to realize an access structure $\Gamma$ if the shares held by any authorized set of parties (i.e., a set in the access structure) can be used to reconstruct the secret, and the shares held by any unauthorized set of parties reveal nothing about the secret. The formal definition follows.

Definition 9 (Secret-Sharing Schemes).

A secret-sharing scheme $\Pi$ over a set of parties $\mathcal{P}=\left\{p_{1},\ldots,p_{n}\right\}$ with domain of secrets $S$ and domain of random strings $R$ is a mapping from $S\times R$ to a set of $n$ -tuples $S_{1}\times S_{2}\times\cdots\times S_{n}$ (the set $S_{j}$ is called the domain of shares of $p_{j}$ ). A dealer distributes a secret $s\in S$ according to $\Pi$ by first sampling a random string $r\in R$ with uniform distribution, computing a vector of shares $\Pi(s;r)=\left(\mathsf{sh}_{1},\ldots,\mathsf{sh}_{n}\right)$ , and privately communicating each share $\mathsf{sh}_{j}$ to party $p_{j}$ . For a set $A\subseteq\left\{p_{1},\ldots,p_{n}\right\}$ , we denote $\Pi_{A}(s;r)$ as the restriction of $\Pi(s;r)$ to its A-entries (i.e., the shares of the parties in $A$ ).

A secret-sharing scheme $\Pi$ with domain of secrets $S$ realizes an access structure $\Gamma$ if the following two requirements hold:

Correctness.: The secret $s$ can be reconstructed by any authorized set of parties. That is, for any authorized set $B=\{p_{i_{1}},\ldots,p_{i_{|B|}}\}\in\Gamma$ , there exists a reconstruction function $\operatorname{Recon}_{B}:S_{i_{1}}\times\cdots\times S_{i_{|B|}}\rightarrow S$ such that for every secret $s\in S$ and every random string $r\in R$ , it holds that $\operatorname{Recon}_{B}\left(\Pi_{B}(s;r)\right)=s$ .
Security.: Every unauthorized set cannot learn anything about the secret from its shares. Formally, for any set $T\notin\Gamma$ , every two secrets $s_{1},s_{2}\in S$ , and every possible vector of shares $\left\langle\mathsf{sh}_{j}\right\rangle_{p_{j}\in T}$ , $\Pr\left[\Pi_{T}(s_{1};r)=\left\langle\mathsf{sh}_{j}\right\rangle_{p_{j}\in T% }\right]=\Pr\left[\Pi_{T}(s_{2};r)=\left\langle\mathsf{sh}_{j}\right\rangle_{p% _{j}\in T}\right],$ where the probability is over the choice of $r$ from $R$ with uniform distribution.

The size of the share of party $p_{j}$ is defined as $\log\left|S_{j}\right|$ and the size of the shares of $\Pi$ as $\max_{1\leq j\leq n}\log|S_{j}|$ . The total share size of $\Pi$ is defined as $\sum_{j=1}^{n}\log|S_{j}|$ .

Next we give some widely known secret-sharing schemes.

Definition 10 (Additive Secret-Sharing Scheme [15]).

In the additive secret-sharing scheme $ADD_{{\mathbb{F}},n}$ over ${\mathbb{F}}$ , shares $\mathsf{sh}_{1},...,\mathsf{sh}_{n}$ are sampled uniformly at random from ${\mathbb{F}}$ on the condition that $s=\sum_{i=1}^{n}\mathsf{sh}_{i}$ , and $\Gamma=\{\mathcal{P}\}$ .

Definition 11 (Shamir Secret-Sharing Scheme [25]).

In the $(n,k)$ -Shamir secret-sharing scheme over ${\mathbb{F}}$ realizing $k$ -out-of- $n$ threshold access structure $\Gamma$ , the dealer sets a polynomial $p(x)=s+r_{1}x+\dots+r_{k-1}x^{k-1}$ by uniformly random sampling of $r_{j}\leftarrow{\mathbb{F}}$ for $j\in[k-1]$ . The share of $p_{i}$ for $i\in[n]$ is set as $\mathsf{sh}_{i}=p(i)$ .

The properties of Shamir’s scheme over $\mathbb{F}_{2^{m}}$ for an appropriate $m\in{\mathbb{N}}$ are summarized in the next theorem.

Theorem 12 (Shamir [25]).

For every $n\in{\mathbb{N}}$ , and $k\in[n]$ , there is a secret-sharing scheme for secrets of size $\ell$ (i.e., the domain of secrets is $S=\{0,1\}^{\ell}$ ) realizing the $k$ -out-of- $n$ threshold access structure, in which the share size is $\max\{\ell,\lceil\log(n+1)\rceil\}$ . Moreover, the shares of the scheme are elements of the field $\mathbb{F}_{2^{\ell+\log n}}$ .

Next two schemes realize any monotone access structure. A replicated secret-sharing scheme [14] is also known as a CNF secret-sharing scheme [15].

Definition 13 (Replicated Secret-Sharing Schemes [14]).

Let $\Gamma\subseteq 2^{[n]}$ be a (monotone) access structure, and let $\mathcal{T}$ is the set of all maxterms of $\Gamma$ . The CNF secret-sharing schemes for $\Gamma$ over ${\mathbb{F}}$ , denoted $CNF_{\Gamma,{\mathbb{F}}}$ , proceeds as follows. A secret $s\in S$ is shared in $ADD_{{\mathbb{F}},|\mathcal{T}|}$ , where each share $r_{T}$ is labelled by a different set $T\in\mathcal{T}$ . Then, the dealer distributes to each party $p_{j}$ all shares $r_{T}$ such that $j\notin T$ , that is, $\mathsf{sh}_{j}=(r_{T})_{j\notin T}$ . For correctness, since $\Gamma$ is monotone, a qualified set $Q\in\Gamma$ cannot be contained in any unqualified set, hence, members of $Q$ jointly view all shares $r_{T}$ and can thus reconstruct the secret $s$ . For privacy, the parties of every maxterm $T\in\mathcal{T}$ jointly miss exactly one additive share $r_{T}$ , hence parties of any unqualified set miss at least one share.

Definition 14 (DNF Secret-Sharing Scheme [15]).

In DNF secret-sharing schemes, denoted $DNF_{\Gamma,{\mathbb{F}}}$ , the secret $s$ is additively shared between the parties of each minterm, where each additive sharing uses independent randomness.

More secret-sharing schemes can be defined using the notion of a monotone span program (MSP). We bring the definition of MSP below.

Definition 15 (Monotone Span Program [16]).

A monotone span program is a triple $\mathcal{M}=(\mathbb{F},M,\rho)$ , where $\mathbb{F}$ is a field, $M$ is an $m\times k$ matrix over $\mathbb{F}$ , and a mapping $\rho:[m]\rightarrow[n]$ labels each row of $M$ by a party’s index. The size of $\mathcal{M}$ is the number of rows of $M$ (i.e., $m$ ).

Next we give some notation which simplifies addressing to sets and operations of MSP. Let $M\in{\mathbb{F}}^{m\times k}$ be a matrix, and $A\subseteq[m]$ . We denote by $M[A,\cdot]$ the $|A|\times k$ dimensional submatrix that restricts $M$ to the rows labeled by $i\in A$ . Hence, for an MSP $({\mathbb{F}},M\in{\mathbb{F}}^{m\times k},\rho)$ describing an $n$ -party linear secret-sharing scheme, and $h\in[n]$ , $M[\rho^{-1}(h),\cdot]$ denotes the submatrix induced by rows of $M$ corresponding to shares of party $h$ . For any $S\subseteq[n]$ , for brevity, we will refer to $M[\rho^{-1}(S),\cdot]$ by $M_{S}$ , and when $S=\{h\}$ for some $h\in[n]$ , we will further simplify the notation by referring to $M_{\{h\}}$ as $M_{h}$ . Similarly, for a column vector $\alpha\in{\mathbb{F}}^{m}$ , and set $A\subseteq[m]$ , we denote by $\alpha[A]$ the sub-vector of $\alpha$ labeled by $i\in A$ , and for the subset of parties $S\subseteq[n]$ we let $\alpha_{S}=\alpha[\rho^{-1}(S)]$ , and $\alpha_{\{h\}}=\alpha_{h}$ .

Definition 16 (Access structure accepted by MSP [16]).

We say that MSP $\mathcal{M}$ accepts $B\subseteq[n]$ if the rows of $M_{B}$ span the vector $\mathbf{e}_{\mathbf{1}}=(1,0,\ldots,0)$ , called a target vector.¹¹1In [16] it is proven that one could define MPS’s with any target vector $\epsilon\neq\mathbf{0}$ , rather than $\mathbf{e}_{1}$ , resulting in the same matrix size and labeling. We say that $\mathcal{M}$ accepts an access structure $\Gamma$ if $\mathcal{M}$ accepts a set $B$ if and only if $B\in\Gamma$ .

A monotone span program implies a so called linear secret-sharing scheme for an access structure containing all the sets accepted by the program. Essentially, a dealer gives each party the rows of matrix $M$ assigned to it, multiplied by the randomness vector.

Claim 17 ([4]).

Let $\mathcal{M}=(\mathbb{F},M,\rho)$ be a MSP accepting an access structure $\Gamma$ , where $\mathbb{F}$ is a finite field and for every $j\in[n]$ there are $a_{j}$ rows of $M$ labeled by $p_{j}$ . Then, there is a linear secret-sharing scheme realizing $\Gamma$ for $S=\mathbb{F}$ such that the share of party $p_{j}$ is a vector in $\mathbb{F}^{a_{j}}$ with the information equal to $\max_{1\leq j\leq n}a_{j}$ .

3.2 Evolving Secret-Sharing Schemes

In an evolving secret-sharing scheme, defined by [17], the number of parties is unbounded. Parties arrive one after the other; when a party $p_{t}$ arrives the dealer gives it a share. The dealer cannot update the share later and does not know how many parties will arrive after party $p_{t}$ . Thus, we measure the share size of $p_{t}$ as a function of $t$ . We start by defining an evolving access structure, which specifies the authorized sets. The number of parties in an evolving access structure is infinite, however every authorized set is finite.

Definition 18 (Evolving Access Structures).

Let $\mathcal{P}=\left\{p_{i}\right\}_{i\in{\mathbb{N}}}$ be an infinite set of parties. A collection of finite sets $\Gamma\subseteq 2^{\mathcal{P}}$ is an evolving access structure if for every $t\in{\mathbb{N}}$ the collections $\Gamma^{t}\triangleq\Gamma\cap 2^{\{p_{1},\dots,p_{t}\}}$ is an access structure as defined in Definition 7. We will represent an access structure by a function $f:\{0,1\}^{*}\rightarrow\{0,1\}$ , where an input (i.e., a string) $\sigma=(\sigma_{1},\sigma_{2},\ldots,\sigma_{n})\in\{0,1\}^{n}$ represents the set $A_{\sigma}=\{p_{i}:i\in[n],\sigma_{i}=1\}$ ,²²2In particular, the same set has infinitely many representations by inputs of various lengths, using sufficiently many trailing zeros. and $f(\sigma)=1$ if and only if $A_{\sigma}\in\Gamma$ . We will also call $f$ an evolving access structure.

Definition 19 (Evolving Secret-Sharing Schemes).

Let $S$ be a domain of secrets, where $|S|\geq 2$ , and $\left\{R_{t}\right\}_{t\in{\mathbb{N}}},\left\{S_{t}\right\}_{t\in{\mathbb{N}}}$ be two sequences of finite sets. An evolving secret-sharing scheme with domain of secrets $S$ is a sequence of mappings $\Pi=\left\{\Pi^{t}\right\}_{t\in{\mathbb{N}}}$ , where for every $t\in{\mathbb{N}}$ , $\Pi^{t}$ is a mapping $\Pi^{t}:S\times R_{1}\times\cdots\times R_{t}\rightarrow S_{t}$ (which returns the share $\mathsf{sh}_{t}$ of $p_{t}$ ).

An evolving secret-sharing scheme $\Pi=\left\{\Pi^{t}\right\}_{t\in{\mathbb{N}}}$ realizes an evolving access structure $\Gamma$ if for every $t\in{\mathbb{N}}$ the secret-sharing scheme $\Pi_{t}\left(s;r_{1},\ldots,r_{t}\right)$ $\triangleq\left\langle\Pi^{1}\left(s;r_{1}\right),\ldots,\Pi^{t}\left(s;r_{1},% \ldots,r_{t}\right)\right\rangle$ (i.e., the shares of the first $t$ parties) is a secret-sharing scheme realizing $\Gamma^{t}$ according to Def. 9.

By default, the domain of secrets of an evolving scheme is $\{0,1\}$ . Known results show that every evolving access structure can be realized by an evolving secret-sharing scheme.

Definition 20 (Evolving Threshold Access Structures).

Let $k\in{\mathbb{N}}$ . The evolving $k$ -threshold access structure is the evolving access structure $\Gamma$ , where $\Gamma^{t}$ is the $k$ -out-of-t threshold access structure.

Komargodski et al. [17] showed that any evolving threshold access structure can be realized by an efficient evolving secret-sharing scheme.

Theorem 21 ([17]).

For every $k\in{\mathbb{N}}$ , there is a secret-sharing scheme realizing the evolving $k$ -threshold access structure such that the share size of party $p_{t}$ is $(k-1)\cdot\log{t}+\operatorname{poly}(k)\cdot o(\log{t})$ .

More evolving asses structures are defined by such structures as undirected st-connectivity graphs (st-connectivity), infinite decision trees (IDT), and generalized infinite decision trees (GIDT) [1]. Komargodski et al. [17] showed that every undirected st-connectivity access structure can be realized by an evolving secret-sharing scheme in which the share of each party is a bit. Infinite decision trees were used in [17, 18] to construct evolving secret-sharing schemes. Alon et al. [1] showed how to construct secret-sharing schemes for IDT and GIDT. For definitions and constructions we refer to the full version [11].

3.3 Share Conversion

Cramer et al. [9] defined the notion of a share conversion as a local mapping from the shares a secret over one scheme into shares over another scheme, maintaining the secret value. We next include a formal definition of share conversion.³³3In [9], they in fact give a slightly more general definition.

Definition 22 (Share Conversion).

Let $\Pi,\Pi^{\prime}$ be two secret-sharing schemes over the same secret-domain $S$ for $n$ parties realizing the same access structure. We say that $\Pi$ is locally convertible to $\Pi^{\prime}$ if there exist functions $g_{1},\ldots,g_{n}$ such that the following holds. If $(\mathsf{sh}_{1},\ldots,\mathsf{sh}_{n})$ are valid shares of a secret $s$ in $\Pi$ (i.e., $\Pr[\Pi(s;\mathbf{r})=(\mathsf{sh}_{1},\ldots,\mathsf{sh}_{n})]>0$ ), then $(g_{1}(\mathsf{sh}_{1}),\ldots,g_{n}(\mathsf{sh}_{n}))$ are valid shares of the same secret $s$ in $\Pi^{\prime}$ . We denote by $g$ the concatenation of all $g_{i}$ , namely $g(\mathsf{sh}_{1},\ldots,\mathsf{sh}_{n})=(g_{1}(\mathsf{sh}_{1}),\ldots,g_{n}% (\mathsf{sh}_{n}))$ , and refer to $g$ as a conversion function.

We next extend the definition of share conversion to the evolving setting.

Definition 23 (Evolving Share Conversion).

Let $\Pi,\Pi^{\prime}$ be two evolving secret-sharing schemes over the same secret-domain $S$ realizing an access structure $\Gamma$ . We say that $\Pi$ is locally convertible to $\Pi^{\prime}$ if there exists a sequence of functions $g_{1},g_{2},g_{3},\ldots$ such that the following holds. For every $t\geq 1$ , if $(\mathsf{sh}_{1},\ldots,\mathsf{sh}_{t})$ are valid shares of a secret $s$ in $\Pi$ (i.e., $\exists\mathbf{r}\in R_{1}\times\ldots\times R_{t}$ such that $\Pi(s;\mathbf{r})=(\mathsf{sh}_{1},\ldots,\mathsf{sh}_{t})$ ), then $(g_{1}(\mathsf{sh}_{1}),\ldots,g_{t}(\mathsf{sh}_{t}))$ are valid shares of the same secret $s$ in $\Pi^{\prime}$ . We denote by $g$ the concatenation of all $g_{i}$ , namely $g(\mathsf{sh}_{1},\mathsf{sh}_{2},\ldots)=(g_{1}(\mathsf{sh}_{1}),g_{2}(% \mathsf{sh}_{2}),\ldots)$ , and refer to $g$ as a conversion function.

If the secret-sharing scheme $\Pi$ is convertible to $\Pi^{\prime}$ , we say that $\Pi\geq\Pi^{\prime}$ . This defines a partial ordering over secret-sharing schemes. Next, we show that changing a target vector preserves much of the MSP structure, while being convertible to the original scheme.

Claim 24.

Let $\Pi=({\mathbb{F}},M\in\mathbb{F}^{m\times k},\rho)$ is a linear scheme for an access structure $\Gamma$ with the target vector $\mathbf{\epsilon}\in{\mathbb{F}}^{m}\setminus\mathbf{0}$ . Then for any target vector $\mathbf{\epsilon}^{\prime}\in{\mathbb{F}}^{m}\setminus\mathbf{0}$ , there exists a linear scheme $\Pi^{\prime}=({\mathbb{F}},M^{\prime}\in{\mathbb{F}}^{m\times k},\rho)$ for $\Gamma$ , convertible to $\Pi$ .

The proof is simply by observing the identity conversion works. See [11] for a full proof.

In linear (MSP-based) schemes, it is convenient to consider a secret $s$ as part of the randomness vector $\mathbf{r}$ , being its first coordinate. Sometimes, $s$ is defined by ${\mathbf{r}}$ in a different manner, which results in a different than $\mathbf{e}_{1}$ target vector in MSP. For example, in CNF with $\mathbf{1}$ target, as used in [9], the secret is the sum of all elements in ${\mathbf{r}}$ . Thus, we will sometimes consider conversions to a scheme $\Pi^{\prime}$ with a certain target vector, and implicitly rely on the implied conversion to $\Pi^{\prime}$ with a different target vector.

4 Impossibility results for linear Share Conversion

Our impossibility results for linear schemes presented in this section follow from the lemma stated below.

Lemma 25.

Let $\Pi,\Pi^{\prime}$ denote linear secret-sharing schemes realizing $\Gamma$ and specified by MSPs $({\mathbb{F}},M\in{\mathbb{F}}^{m\times k},\rho)$ , $({\mathbb{F}},M^{\prime}\in{\mathbb{F}}^{m^{\prime}\times k^{\prime}},\rho^{% \prime})$ . Let $T\cup\{h\}$ denote a minterm in $\Gamma$ for $T\subseteq[n],h\in[n]$ , and let $\alpha_{T\cup h}$ , $\alpha^{\prime}_{T\cup h}$ be its reconstruction functions for $\Pi$ and $\Pi^{\prime}$ , respectively. Let $L=\mathrm{Rowspan}(M_{T})\cap\mathrm{Rowspan}(M_{h})$ , and $B$ denote a basis for $L$ . Suppose $g$ is some share conversion from $\Pi$ to $\Pi^{\prime}$ . Then $\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}g_{h}(M_{h}{\mathbf{r}})=\left(% {\alpha_{h}}\right)^{\mathsf{T}}M_{h}{\mathbf{r}}+c(B{\mathbf{r}})$ for some function $c$ , where ${\mathbf{r}}$ is a randomness vector for $\Pi$ . ⁴⁴4Note that even if $L=\{\mathbf{0}\}$ , we are free to pick the constant $c(\mathbf{0})$ , which depends only on $\alpha$ in this case.

$\blacktriangleright$ Remark 26.

The lemma gives us a high level clue as to why CNF is high up in the convertibility (partial) order for linear schemes of a given access structure, while DNF is so low. In DNF, for every party $h$ , and every minterm $T\cup\{h\}$ , it is easy to see that the resulting $L=\{\mathbf{0}\}$ . This way, there is “little freedom” in converting determining the converted (sub)share for $h$ (this is formally proved in Theorem 31). On the other hand, in CNF, for a given $h$ and minterm $T\cup\{h\}$ , $dim(L)$ is typically large – equal to the number of maxterms $H$ where $H\cap(T\cup\{h\})\subset T$ . This allows for more freedom at choosing the conversion function.

Proof of Lemma 25.

First observe that since $T\cup\{h\}$ is a minterm, $\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}\notin\mathrm{Rowspan}(M_{T})$ , and hence $\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}\notin L$ . Also, by definition, $B\subseteq\mathrm{Rowspan}(M_{h})$ . Note that $\{\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}\}\cup B$ may not constitute a basis of the rows of $M_{h}$ , it which case, it is complemented by adding a set of appropriate linear combinations of an appropriate set $X$ of rows in $M_{h}$ . Let $M^{-}_{T}$ denote a subset of $M_{T}$ ’s rows constituting a basis of $\mathrm{Rowspan}(M_{T})$ . By choice of $B$ , for any scalar $a$ and vector $\mathbf{v}$ (of the right dimension) there exists randomness ${\mathbf{r}}$ (one or more) such that $M^{-}_{T}{\mathbf{r}}=\mathbf{v}$ , $\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}{\mathbf{r}}=a$ . Note that $B{\mathbf{r}}$ is determined by $\mathbf{v}$ (and is otherwise independent of ${\mathbf{r}}$ ). In the sequel, for (an implicit or explicit) randomness vector ${\mathbf{r}}$ , we let $\mathbf{v}$ , $a$ denote the share portions as above induced by it. As $\alpha^{\prime}$ is a reconstruction function, and by locality of $g$ and linearity of $\Pi^{\prime}$ , $\forall{\mathbf{r}}$ it holds that

\left.\left({\alpha^{\prime}_{T\cup h}}\right)^{\mathsf{T}}g_{{T\cup h}}(M_{T% \cup h}{\mathbf{r}})=\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}g_{h}(M_{h% }{\mathbf{r}})+\left({\alpha^{\prime}_{T}}\right)^{\mathsf{T}}g_{T}(\mathbf{v}% )=s\right.

(1)

By Equation (1), and the definition of $\alpha$ we have that

\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}g_{h}(M_{h}{\mathbf{r}})=s-% \left({\alpha^{\prime}_{T}}\right)^{\mathsf{T}}g_{T}(M_{T}{\mathbf{r}})=\left(% {\alpha_{h}}\right)^{\mathsf{T}}M_{h}{\mathbf{r}}+\left({\alpha_{T}}\right)^{% \mathsf{T}}M_{T}{\mathbf{r}}-\left({\alpha^{\prime}_{T}}\right)^{\mathsf{T}}g_% {T}(M_{T}{\mathbf{r}}),

(2)

where the first term equals to $a$ by definition, and the rest is some function of only $\mathbf{v}$ . We denote $\left({\alpha_{T}}\right)^{\mathsf{T}}M_{T}{\mathbf{r}}-\left({\alpha^{\prime}% _{T}}\right)^{\mathsf{T}}g_{T}(M_{T}{\mathbf{r}})$ by $f(\mathbf{v})$ . From locality of $g$ , $f(\mathbf{v})$ in fact depends only on $B{\mathbf{r}}$ . To see this, denote $span(M^{-}_{T})=span(B)\oplus span(B^{-}_{T})$ (direct sum of linear subspaces) for an independent set of vectors $B^{-}_{T}\subseteq\mathrm{Rowspan}(M_{T})$ complementing $B$ into a basis. Using the fact that $B$ is a basis of $\mathrm{Rowspan}(M_{h})\cap\mathrm{Rowspan}(M_{T})$ , it is easy to show that $B^{-}_{T}$ with $span(B_{T}^{-})\cap\mathrm{Rowspan}(M_{h})=\{\mathbf{0}\}$ indeed exists.

The observation follows by locality, since $g_{h}$ has no information on $span(B^{-}_{T}){\mathbf{r}}$ (given $B{\mathbf{r}}$ that it knows). Also, $\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}g_{h}(M_{h}{\mathbf{r}})$ may not depend on $X{\mathbf{r}}$ , as $span(X)\cap\mathrm{Rowspan}(M_{T})=\{\bf{0}\}$ , as then it would not be a (deterministic) function of $\mathbf{v}$ .⁵⁵5Note that the above does not imply that $g_{h}(M_{h}{\mathbf{r}})$ does not depend on $X{\mathbf{r}}$ , but rather that it is of the form $g^{\prime}_{h}(B{\mathbf{r}},a)+g^{\prime\prime}_{h}(X{\mathbf{r}})$ , where $g^{\prime\prime}_{h}(X{\mathbf{r}})=(g^{\prime\prime}_{h,1}(X{\mathbf{r}}),% \ldots,g^{\prime\prime}_{h,\ell}(X{\mathbf{r}}))$ is a vector of functions in the formal variables $X[1]{\mathbf{r}},\ldots,X[\ell]{\mathbf{r}}$ , such that $\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}g^{\prime\prime}_{h}(X{\mathbf{% r}})=0$ . Similarly, it implicitly follows that the vector $g_{T}(M_{T}{\mathbf{r}})=g_{T}(B{\mathbf{r}},B^{-}_{T}{\mathbf{r}})$ , of functions is such that $\left({\alpha^{\prime}_{T}}\right)^{\mathsf{T}}g^{\prime\prime}_{T}(B^{-}_{T}{% \mathbf{r}})$ is a formal function of $B{\mathbf{r}}$ only. That is in Fourier basis in the variables $y_{1}=B[1]{\mathbf{r}},\ldots,y_{|B|}=B[|B|]{\mathbf{r}},\ldots,y_{i}=B^{-}_{T% }[i-|B|]{\mathbf{r}},\ldots,y_{k}$ , it does not contain minterms of the form $\prod_{j\in A}y_{j}$ where $A\setminus[|B|]$ is not empty. This also poses a certain restriction of $g_{T}$ which can possibly exploited by future work. Thus, we have

\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}g_{h}(M_{h}{\mathbf{r}})=a+c(B{% \mathbf{r}})

(3)

for some function $c$ , as required. $\hfill\blacktriangleleft$

Next we state two corollaries defining necessary conditions for convertability between linear schemes $\Pi,\Pi^{\prime}$ (as sufficient conditions for non-convertability).

The following theorem is in a sense a generalization of the Claim in Section 3.3 in [9] of non-convertability from Shamir to CNF for $(2,3)$ -threshold access structures.

Theorem 27.

Let $\Gamma$ be an access structure on $n$ parties. Let $\Pi$ and $\Pi^{\prime}$ be linear secret-sharing schemes realizing $\Gamma$ and specified by MSP $({\mathbb{F}},M\in{\mathbb{F}}^{m\times k},\rho)$ and $({\mathbb{F}},M^{\prime}\in\mathbb{F}^{m^{\prime}\times k^{\prime}},\rho^{% \prime})$ , respectively. Then, $\Pi$ has no share conversion to $\Pi^{\prime}$ if there exist $h\in[n]$ , $\emptyset\neq T\subseteq[n]\setminus\{h\}$ such that $T\cup\{h\}$ is a minterm of $\Gamma$ with the reconstruction functions $\alpha$ and $\alpha^{\prime}$ in $\Pi$ and $\Pi^{\prime}$ resp., and $\emptyset\neq T^{*}\subseteq[n]\setminus\{h\}$ that satisfy the following conditions:

1.

$\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}\cdot M^{\prime}_{h}\in\mathrm{% Rowspan}(M^{\prime}_{T^{*}})$ .
2.

$\left({\alpha_{h}}\right)^{\mathsf{T}}\cdot M_{h}\notin\left(\mathrm{Rowspan}(% M_{T})\cap\mathrm{Rowspan}(M_{h})\right)+\left.\left(\mathrm{Rowspan}(M_{T^{*}% })\cap\mathrm{Rowspan}(M_{h})\right)\right.$ .⁶⁶6Recall that $U+V=\{u+v|u\in U,v\in V\}$ .

Proof.

Let us assume for contradiction a conversion $g$ exists, and denote $L=\mathrm{Rowspan}(M_{T})\cap\mathrm{Rowspan}(M_{h})$ and $L^{*}=\mathrm{Rowspan}(M_{T^{*}})\cap\mathrm{Rowspan}(M_{h})$ . We first show that there exist randomness vectors ${\mathbf{r}}_{1}$ , ${\mathbf{r}}_{2}$ such that:

1.

$(L+\mathrm{Rowspan}(M_{T^{*}})){\mathbf{r}}_{1}=(L+\mathrm{Rowspan}(M_{T^{*}})% ){\mathbf{r}}_{2}=\mathbf{0}$ .
2.

$\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}{\mathbf{r}}_{1}\neq\left({\alpha_{% h}}\right)^{\mathsf{T}}M_{h}{\mathbf{r}}_{2}$ .

Fix ${\mathbf{r}}_{1}=\bf{0}$ . Then, $(L+\mathrm{Rowspan}(M_{T^{*}})){\mathbf{r}}_{1}=\mathbf{0}$ and $\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}{\mathbf{r}}_{1}=0$ . Next, let us show that ${\mathbf{r}}_{2}$ as required exists. We claim $\mathrm{Rowspan}(M_{h})\cap(L+L^{*})=\mathrm{Rowspan}(M_{h})\cap(L+\mathrm{% Rowspan}(M_{T^{*}})).$

Clearly, former is contained in the latter. For the other direction, consider $x\in\mathrm{Rowspan}(M_{h})\cap(L+\mathrm{Rowspan}(M_{T^{*}}))$ . Since $L$ is a subspace of $M_{h}$ , it suffices to show that if $x\in L+y$ such that $y\in\mathrm{Rowspan}(M_{T^{*}})$ , then $y\in\mathrm{Rowspan}(M_{T^{*}})\cap\mathrm{Rowspan}(M_{h})=L^{*}$ . Indeed, if $y\in\mathrm{Rowspan}(M_{T^{*}})\setminus\mathrm{Rowspan}(M_{h})$ , then $y+z\notin\mathrm{Rowspan}(M_{h})$ for all $z\in L$ , which contradicts the fact $x\in\mathrm{Rowspan}(M_{h})$ ; the claim follows.

By this claim and condition 2 of the Theorem, $\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}\notin L+\mathrm{Rowspan}(M_{T^{*}})$ since $\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}\in\mathrm{Rowspan}(M_{h})$ . Therefore, there exists ${\mathbf{r}}_{2}$ such that $(L+\mathrm{Rowspan}(M_{T^{*}})){\mathbf{r}}_{2}=\mathbf{0}$ and $\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}{\mathbf{r}}_{2}=1(\neq 0)$ , by Fact 6.

By Lemma 25 applied to $h, T$ , when $B$ is the basis for $L$ , we have

\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}g_{h}(M_{h}{\mathbf{r}}_{1})% \neq\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}g_{h}(M_{h}{\mathbf{r}}_{2}),

(4)

since $B{\mathbf{r}}_{1}=B{\mathbf{r}}_{2}(=\mathbf{0})$ and $\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}{\mathbf{r}}_{1}\neq\left({\alpha_{% h}}\right)^{\mathsf{T}}M_{h}{\mathbf{r}}_{2}$ . On the other hand, by locality, $g_{T^{*}}(M_{T^{*}}{\mathbf{r}}_{1})=g_{T^{*}}(M_{T^{*}}{\mathbf{r}}_{2})=g_{T% ^{*}}(\bf{0})$ , and thus

g_{T^{*}}(M_{T^{*}}{\mathbf{r}}_{1})=g_{T^{*}}(M_{T^{*}}{\mathbf{r}}_{2}).

(5)

By condition 1 of the theorem, there exists $\mathbf{u}$ such that $\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}M^{\prime}_{h}=\left({\mathbf{u% }}\right)^{\mathsf{T}}M^{\prime}_{T^{*}}$ . Further, by definition of $g$ , there exists randomness vectors ${\mathbf{r}}^{\prime}_{1},{\mathbf{r}}^{\prime}_{2}$ for $\Pi^{\prime}$ such that $g(M{\mathbf{r}}_{i})=M^{\prime}{\mathbf{r}}^{\prime}_{i}$ for $i=1,2$ . Hence,

	$\displaystyle\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}g_{h}(M_{h}{% \mathbf{r}}_{1})$	$\displaystyle=\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}M^{\prime}_{h}{% \mathbf{r}}^{\prime}_{1}=\left({\mathbf{u}}\right)^{\mathsf{T}}M^{\prime}_{T^{% }}{\mathbf{r}}^{\prime}_{1}=\left({\mathbf{u}}\right)^{\mathsf{T}}g_{T^{}}(M% _{T^{*}}{\mathbf{r}}_{1})$
		$\displaystyle=\left({\mathbf{u}}\right)^{\mathsf{T}}g_{T^{}}(M_{T^{}}{% \mathbf{r}}_{2})=\left({\mathbf{u}}\right)^{\mathsf{T}}M^{\prime}_{T^{*}}{% \mathbf{r}}^{\prime}_{2}=\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}M^{% \prime}_{h}{\mathbf{r}}^{\prime}_{2}=\left({\alpha^{\prime}_{h}}\right)^{% \mathsf{T}}g_{h}(M_{h}{\mathbf{r}}_{2}).$

The first equality in the second line uses Equation (5). We conclude our proof since the above sequence of equations contradicts Equation (4). $\hfill\blacktriangleleft$

The following corollary from Theorem 27 provides necessary conditions for $\Pi_{\Gamma}\leq CNF_{\Gamma}$ that are easy to check. These conditions involve only $\Gamma$ , and the share size of a single party.

Corollary 28.

Let $\Gamma$ denote an access structure on $n$ parties, such that there exists a party $h$ and two minterms $T_{1}$ , $T_{2}$ of size $\geq 2$ each, such that $h\in T_{1}$ , $h\in T_{2}$ , $(T_{1}\cup T_{2})\setminus\{h\}$ is qualified. Let $\Pi=({\mathbb{F}},M\in{\mathbb{F}}^{m\times k},\rho)$ be a linear scheme for $\Gamma$ , and $M_{h}$ consists of a single row. Then $\Pi$ is not convertible to $\Pi^{\prime}=CNF_{\Gamma,\mathbb{F}}$ .

In the proof we apply Theorem 27 to $\Pi,\Pi^{\prime}$ , with $T=T_{1}\setminus\{h\}$ , $T^{*}=T_{2}\setminus\{h\}$ . See [11] for details.

$\blacktriangleright$ Remark 29.

From Corollary 28 it follows directly that Shamir secret-sharing scheme is not convertible to CNF, and hence is not maximal. Indeed, any party can be viewed as $h$ , as it obtains a single field element as its share. The condition on the access structure automatically holds for threshold structures.

The following theorem exploits a different property implied by convertability than the previous theorem.

Theorem 30.

Let $\Gamma$ be an access structure on $n$ parties. Let $\Pi,\Pi^{\prime}$ be linear secret-sharing schemes specified for $\Gamma$ by MSP $({\mathbb{F}},M\in\mathbb{F}^{m\times k},\rho)$ and $({\mathbb{F}},M^{\prime}\in\mathbb{F}^{m^{\prime}\times k^{\prime}},\rho^{% \prime})$ , respectively. Let $h\in[n]$ denote a party, and let $\mathcal{T}^{h}=\{T_{1},\ldots,T_{v_{h}}\}$ denote minterms each of which is of size $\geq 2$ , and contains $h$ . Let $\{\alpha^{T_{i}}\}_{i\in[v_{h}]}$ denote a set of reconstruction functions for sets $T_{1},\ldots,T_{v_{h}}$ in $\Pi$ respectively. Similarly, $\{{\alpha^{\prime}}^{T_{i}}\}_{i\in[v_{h}]}$ denotes a set of reconstruction functions for $T_{1},\ldots,T_{v_{h}}$ in $\Pi^{\prime}$ . Assume the following conditions hold:

1.

$A=\{\alpha^{T_{i}}_{h}\}_{i\in[v_{h}]}$ constitutes a set of $v_{h}$ linearly independent vectors.
2.

$A^{\prime}=\{\alpha^{\prime T_{i}}_{h}\}_{i\in[v_{h}]}$ constitutes a (multi)set of vectors with $rank(span(A^{\prime}))<v_{h}$ .
3.

$span(\{\alpha^{\intercal}M_{h}|\alpha\in A\})\cap\sum_{i\in[v_{h}]}(\mathrm{% Rowspan}(M_{T_{i}\setminus{h}})\cap\mathrm{Rowspan}(M_{h}))=\{\mathbf{0}\}$ .

Then $\Pi$ has no share conversion to $\Pi^{\prime}$ .

Proof.

Assume for contradiction that a conversion $g$ exists. Fix some party $h\in[n]$ as guaranteed to exist by the theorem. Consider the matrix $Rec^{h}=[\left({\alpha^{T_{1}}_{h}}\right)^{\mathsf{T}}M_{h};\ldots;\left({% \alpha^{T_{v_{h}}}_{h}}\right)^{\mathsf{T}}M_{h}]$ . For each $i\in[v_{h}]$ , let $L_{i}=\mathrm{Rowspan}(M_{T_{i}\setminus{h}})\cap\mathrm{Rowspan}(M_{h})$ . By condition 1, it is of rank $v_{h}$ . Therefore, there exists a set $R^{h}=\{{\mathbf{r}}^{1},\ldots,{\mathbf{r}}^{|{\mathbb{F}}|^{v_{h}}}\}$ of randomness values such that

1.

$\{Rec^{h}{\mathbf{r}}^{j}\}_{j\in[|{\mathbb{F}}|^{v_{h}}]}$ goes over all distinct vectors in ${\mathbb{F}}^{v_{h}}$ .
2.

For every $j\in|{\mathbb{F}}|^{v_{h}},i\in[v_{h}]$ , $L_{i}{\mathbf{r}}^{j}=\mathbf{0}$ .

Such a set $R^{h}$ exists, by combining conditions 1 and 3 in the Theorem. Now, let us consider the matrix $Rec^{\prime h}=[\left({{\alpha^{\prime}}^{T_{1}}_{h}}\right)^{\mathsf{T}}M_{h}% ;\ldots;\left({{\alpha^{\prime}}^{T_{v_{h}}}_{h}}\right)^{\mathsf{T}}M_{h}]$ , and let ${R^{\prime}}^{h}=\{{{\mathbf{r}}^{\prime}}^{1},\ldots,{{\mathbf{r}}^{\prime}}^% {|{\mathbb{F}}|^{v_{h}}}\}$ denote the set of effective randomness vectors induced by the conversion $g$ (that is $M^{\prime}{{\mathbf{r}}^{\prime}}^{j}=g(M{\mathbf{r}}^{j})$ ). By condition 2 in the Theorem, $rank(Rec^{\prime h})<v_{h}$ . Therefore, $span(\{Rec^{\prime h}{{\mathbf{r}}^{\prime}}^{j}\}_{j\in|{\mathbb{F}}|^{v_{h}}})$ is of dimension at most $v_{h}-1$ , and thus contains at most $|{\mathbb{F}}|^{v_{h}-1}$ distinct values. However, by Lemma 25, for every $i\in[v_{h}],j\in[|{\mathbb{F}}|^{v_{h}}]$ we have

{Rec^{\prime}}^{h}[i]{{\mathbf{r}}^{\prime}}^{j}=Rec^{h}[i]{\mathbf{r}}^{j}+c^% {i}(\mathbf{0})

That is, $c^{j}(\mathbf{0})$ is some constant, independent of ${\mathbf{r}}^{j}$ . Therefore,

{R^{\prime}}^{h}{{\mathbf{r}}^{\prime}}^{j}=R^{h}[j]{\mathbf{r}}^{j}+\mathbf{c}

where $\mathbf{c}$ is a constant vector. Going over all values of $j$ , on the RHS we obtain a permutation of the set ${\mathbb{F}}^{v_{h}}$ , but on the LHS, we only get a subset of at most $|{\mathbb{F}}|^{v_{h}-1}$ (constituting a linear subspace) – a contradiction. $\hfill\blacktriangleleft$

The above theorem implies that DNF can only be converted to linear schemes of size at least that of the DNF. More precisely:

Theorem 31.

Let $\Gamma$ be an access structure over $n>1$ parties, and ${\mathbb{F}}$ be a finite field. For simplicity, assume $\Gamma$ has no redundant parties. Let $\Pi^{\prime}$ be a linear secret-sharing scheme specified by MSP $\mathcal{M}^{\prime}=({\mathbb{F}},M^{\prime}\in\mathbb{F}^{m^{\prime}\times k% ^{\prime}},\rho^{\prime})$ for $\Gamma$ . If $\mathcal{M}=DNF_{\Gamma,{\mathbb{F}}}=({\mathbb{F}},M\in\mathbb{F}^{m\times k}% ,\rho)$ is convertible to $\Pi^{\prime}$ , then ⁷⁷7In fact, the number of rows assigned to each party is at least as large as in DNF.

m^{\prime}\geq\sum_{T:T\text{ is a minterm of }\Gamma}|T|.

Proof.

Consider some $h\in[n]$ that belongs to some minterm $T$ of size at least 2. Let $\mathcal{T}^{h}=\{T_{i}\text{ is a minterm}||T_{i}|\geq 2,h\in T_{i}\}$ , and denote $v_{h}=|\mathcal{T}^{h}|$ . The (unique, in case of DNF) reconstruction function projection set $A=\{\alpha^{T_{i}}_{h}\}$ are all linearly independent by construction of DNF. Namely, each selects a single row in $M_{h}$ , and $\left({\alpha^{T_{i}}_{h}}\right)^{\mathsf{T}}M_{h}$ is either of the form $r_{i,h}$ or of the form $s-\sum_{k\in T_{i}\setminus{h}}r_{i,k}$ , where $r_{i,j}$ is a random element used by the DNF in the additive sub-scheme for minterm $T_{i}$ and party $j$ .

For a fixed $k\in[v_{h}]$ , by structure of DNF, we have $\mathrm{Rowspan}(M_{T_{k}\setminus{h}})\cap\mathrm{Rowspan}(M_{h})=\mathbf{0}$ . Therefore, $\sum_{k\in[v_{h}]}\left(\mathrm{Rowspan}(M_{T_{k}\setminus{h}})\cap\mathrm{% Rowspan}(M_{h})\right)=\{\mathbf{0}\}$ . Thus, $A$ satisfies conditions 1 and 3 of Theorem 30 relative to $\mathcal{T}^{h}$ .

It follows from Theorem 30 that $A^{\prime}$ is of dimension $\geq v_{h}$ . Thus, the matrix $A^{\prime}M^{\prime}_{h}$ (where $A^{\prime}$ is treated as a matrix constructed from the vectors of $A^{\prime}$ as rows) also has dimension at least $v_{h}$ . This implies $M^{\prime}_{h}$ itself is of rank at least $v_{h}$ , which in turn lower bounds its number of rows.

Parties that constitute a singleton minterm, contribute at least 1 to $rank(M^{\prime}_{h})$ , as the party contained in the minterm is not redundant. Going over all parties $h$ , the result follows by changing the order of summation, obtaining.

m^{\prime}\geq\sum_{h}\sum_{T:T\text{ is a minterm},h\in T}1=\sum_{T:T\text{ % is a minterm}}|T|

(6)

$\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 32.

Theorem 31, in fact, states that DNF is not convertible to any linear scheme with lower share complexity, in particular, in the Shamir secret sharing scheme. The non-minimality of Shamir follows.

$\blacktriangleright$ Remark 33.

In fact, the above theorem can be fairly easily generalized to $\Pi$ where $span(\{\alpha^{\intercal}M_{h}|\alpha\in A\})\cap\sum_{i\in[v_{h}]}(\mathrm{% Rowspan}(M_{T_{i}\setminus{h}})\cap\mathrm{Rowspan}(M_{h}))=U$ for some $h$ has a “relatively small” dimension $u$ . Then, we can prove $dim(span(A))-u$ lower bounds $rank(M^{\prime}_{h})$ if $\Pi\leq\Pi^{\prime}$ . That is, the smaller $u$ relatively to $dim(span(A))$ is, the higher the share complexity of party $h$ in $\Pi^{\prime}$ must be.

5 A characterization of convertability between linear schemes

Let $\Gamma$ be an access structure on $n$ parties. Let $\Pi,\Pi^{\prime}$ be linear secret-sharing schemes specified by MSPs $({\mathbb{F}},M\in\mathbb{F}^{m\times k},\rho)$ and $({\mathbb{F}},M^{\prime}\in\mathbb{F}^{m^{\prime}\times k^{\prime}},\rho^{% \prime})$ , respectively, realizing $\Gamma$ . We devise a characterization of convertibility from $\Pi$ to $\Pi^{\prime}$ by solvability of a certain system of linear equations. Essentially, every solution of the system represents a conversion function $g$ . Namely, for every randomness vector from $\Pi$ , it defines converted shares for $\Pi^{\prime}$ .

The linear system $\mathcal{L}_{\Pi,\Pi^{\prime}}$ .

For each randomness vector $\mathbf{r}\in\mathbb{F}^{m}$ we define a variable $X^{(\mathbf{r})}\in\mathbb{F}^{m^{\prime}}$ , that assumes a value for the purported sharing under $M^{\prime}$ induced by the share conversion of $M\cdot\mathbf{r}$ . The constraints we define are as follows.

$\blacksquare$

Locality. For every $i\in[n]$ and $\mathbf{r},\mathbf{r}^{\prime}\in\mathbb{F}^{m}$ such that $M_{i}\cdot\mathbf{r}=M_{i}\cdot\mathbf{r}^{\prime}$ , add the constraint:

$X^{(\mathbf{r})}_{i}=X^{(\mathbf{r}^{\prime})}_{i}.$
$\blacksquare$

Consistency. Let $A\subseteq[m^{\prime}]$ be a subset of rows of $M^{\prime}$ which form a basis of $\mathrm{Rowspan}(M^{\prime})$ . Since $M^{\prime}[A,\cdot]$ is a basis of $\mathrm{Rowspan}(M^{\prime})$ , there exists a (unique) matrix $H\in\mathbb{F}^{m^{\prime},|A|}$ such that $H\cdot M^{\prime}[A,\cdot]=M^{\prime}$ . For every $\mathbf{r}\in\mathbb{F}^{m}$ , we add the constraint

$H\cdot X^{(\mathbf{r})}[A]=X^{(\mathbf{r})}.$
$\blacksquare$

Correctness. For each minterm $T\subset[n]$ of $\Gamma$ do the following: let ${\alpha^{\prime}}^{T}\in\mathbb{F}^{|(\rho^{\prime})^{-1}(T)|}$ be a smallest reconstruction vector for $T$ under some arbitrary ordering of $\mathbb{F}^{|(\rho^{\prime})^{-1}(T)|}$ ). For every $s\in\mathbb{F}$ , and every $\mathbf{r}$ such that $\mathbf{r}[1]=s$ , add the constraint

$\left({{\alpha^{\prime}}^{T}}\right)^{\mathsf{T}}\cdot X^{(\mathbf{r})}_{T}=s.$

$\blacktriangleright$ Remark 34.

The characterization may be easily extended to non-linear $\Pi$ with $S=\mathbb{F}$ , keeping the system linear.

Theorem 35.

Let $\Gamma$ be an access structure on $n$ parties. Let $\Pi$ , $\Pi^{\prime}$ be linear secret-sharing schemes specified by MSPs $({\mathbb{F}},M\in\mathbb{F}^{m\times k},\rho)$ and $({\mathbb{F}},M^{\prime}\in\mathbb{F}^{m^{\prime}\times k^{\prime}},\rho^{% \prime})$ , respectively, realizing $\Gamma$ . Then, $\Pi$ is convertible to $\Pi^{\prime}$ if and only if the linear system $\mathcal{L}_{\Pi,\Pi^{\prime}}$ is solvable.

Proof.

Both directions essentially follow from the fact that the solution set to $\mathcal{L}_{\Pi,\Pi^{\prime}}$ exactly corresponds to the set of conversions from $\Pi$ to $\Pi^{\prime}$ . See [11] for a formal proof. $\hfill\blacktriangleleft$ Theorems 27 and 30 may be viewed as a result of an inconsistency in the characterization equations. In Theorem 27, the inconsistent subset of equations supported only on $X^{({\mathbf{r}}^{1})},X^{({\mathbf{r}}^{2})}$ for a pair ${\mathbf{r}}_{1},{\mathbf{r}}_{2}$ as chosen in the proof, and the inconsistency involves a potentially large set of ${\mathbf{r}}^{j}$ ’s, already. Lemma 25 relies on equations of all three types to derive its conclusion.

Future work.

We believe that there exist additional types of “inconsistencies” in the linear equations in the characterization that may result in proving non-existence of a conversion from between pairs of linear schemes $\Pi$ to $\Pi^{\prime}$ , and it is an interesting open question to list all possible types of inconsistencies, and thereby make the above characterization easier to apply. Most importantly, we wish to understand when conversions between linear schemes do exist. Another interesting open question on convertability between pairs of linear schemes is understanding whether it is helpful to have non-linear conversion functions $g$ .

6 Impossibility of conversion to CNF for general schemes

In this section, we introduce the class of non-degenerate secret-sharing schemes, which includes CNF and Shamir schemes, and, using properties of non-degenerate schemes, we prove a necessary condition of convertibility to CNF from any (not necessarily linear) scheme.

Definition 36.

Let $\Pi$ be a secret-sharing scheme with secret domain $S$ and randomness domain $R$ realizing an access structure $\Gamma$ . $\Pi$ is non-degenerate if the following holds: If $\Pi^{\prime}$ is a secret-sharing scheme with secret domain $S$ and randomness domain $R^{\prime}$ realizing $\Gamma$ such that, for all $s\in S,r^{\prime}\in R^{\prime}$ , there exists $r\in R$ such that $\Pi^{\prime}(s;r^{\prime})=\Pi(s;r)$ , then

\displaystyle\left(\Pi^{\prime}(s;r^{\prime})\middle|r^{\prime}\leftarrow R^{% \prime}\right)\equiv\left(\Pi(s;r)\middle|r\leftarrow R\right),\forall s\in S.

(7)

Suppose $\Pi$ is a non-degenerate secret-sharing scheme. If a secret-sharing scheme $\Pi^{\prime}$ is locally convertible to $\Pi$ , then the secret-sharing scheme induced by the applying the share conversion function to $\Pi^{\prime}$ coincides with $\Pi$ .

Proposition 37.

Let $\Pi$ be a non-degenerate secret-sharing scheme with secret domain $S$ and randomness domain $R$ realizing access structure $\Gamma$ over $n$ parties. Suppose $\Pi^{\prime}$ be a secret-sharing scheme with the same secret domain and access structure and randomness domain $R^{\prime}$ that admits share conversion to $\Pi$ using a share conversion function $g=(g_{1},\ldots,g_{n})$ . Then, for all $s\in S$ ,

\displaystyle\left(g(\Pi^{\prime}(s;r^{\prime}))\middle|r^{\prime}\leftarrow R% ^{\prime}\right)\equiv\left(\Pi(s;r)\middle|r\leftarrow R\right).

(8)

Proof.

Consider the secret-sharing scheme in which $s\in S$ is secret shared as $(\mathsf{sh}_{1},\ldots,\mathsf{sh}_{n})=g(\Pi^{\prime}(s,r^{\prime}))$ where $r^{\prime}\leftarrow R^{\prime}$ . Since $g$ is a share conversion function that converts $\Pi^{\prime}$ to $\Pi$ , this induces secret-sharing scheme with secret domain $S$ realizing the access structure $\Gamma$ . Further, for each $s\in S$ and $r^{\prime}\in R^{\prime}$ , $g(\Pi^{\prime}(s;r^{\prime}))=\Pi(s;r)$ for some $r\in R$ . The proposition now follows from the fact that $\Pi$ is a non-degenerate secret-sharing scheme (See Definition 36). $\hfill\blacktriangleleft$ We establish that CNF and Shamir secret sharing schemes are non-degenerate. The proofs of these claims follow the outline sketched in Section 1.1; their formal proofs are deferred to the full version.

Lemma 38.

For any finite group $\mathbb{G}$ , and access structure $\Gamma$ over $n$ parties, the CNF secret-sharing scheme for secrets in $\mathbb{G}$ realizing $\Gamma$ is non-degenerate.

Lemma 39.

For any finite field $\mathbb{F}$ such that $|\mathbb{F}|>n$ , and $1\leq t\leq n$ , a $t$ -private $n$ -party Shamir secret-sharing scheme over $\mathbb{F}$ is non-degenerate.

We exploit the non-degeneracy of CNF secret sharing to establish lower bound on share size in any (potentially non-linear) secret sharing schemes that admit share conversion to CNF secret sharing.

Theorem 40.

Let $\Pi$ be a secret-sharing scheme with secret domain $\mathbb{G}$ and randomness domain $R$ realizing an $n$ -party access structure $\Gamma$ . There is a share conversion from $\Pi$ to CNF secret-sharing over $\mathbb{G}$ realizing $\Gamma$ only if, for each $i\in[n]$ , size of the share $i$ in $\Pi$ is at least $\log|\mathbb{G}|\cdot|\{F\in\mathcal{F}\text{ s.t. }i\notin F\}|$ , where $\mathcal{F}$ is the set of all maximal forbidden sets associated with $\Gamma$ .

Proof.

By Lemma 38, the CNF secret-sharing scheme is non-degenerate. Let $g=(g_{1},\ldots,g_{n})$ be the share conversion function that induces the share conversion from $\Pi$ to the CNF secret-sharing scheme. By Proposition 37, for any $s\in\mathbb{G}$ , when $r\leftarrow R$ , $g(\Pi(s;r))$ is identically distributed as CNF secret-sharing of $s$ . Hence, $g_{i}(\Pi(s;r))$ corresponds to the share of party $i$ in CNF secret-sharing: $\{\gamma_{F}:F\in\mathcal{F},i\notin F\}$ where $\gamma_{F}$ is uniformly chosen from $\mathbb{G}$ for each $F\in\mathcal{F}$ subject to $\sum_{F}\gamma_{F}=s$ . Theorem follows immediately from this observation. $\hfill\blacktriangleleft$

7 Results for Evolving Linear Secret-Sharing Schemes

In this section, we extend the notion of Monotone Span Programs and the induced notion of a linear secret-sharing scheme to the evolving setting. We then apply our impossibility results obtained is Sections 4 and 6 for the finite case to study the convertibility hierarchy in this setting.

Monotone span programs [16] were used to construct linear secret-sharing schemes in [4]. In this section, we extend Definition 15 to define infinite monotone span programs and cast a few constructions from the literature as instances of this notion. We define the product of an infinite matrix $K\in\mathbb{F}^{[n]\times\mathbb{N}^{+}}$ by a finite vector $\mathbf{r}\in\mathbb{F}^{[m]}$ as $K^{\prime}{\mathbf{r}}$ , where $K^{\prime}$ is obtained by keeping the first $m$ columns of $K$ . We will typically use such products for matrices where all but the first $m$ columns are 0. Generalizing this notion to the evolving setting, we dub IMSP, requires some care. Roughly, in an IMSP $M(\mathbb{F},M,\rho)$ $|\rho^{-1}(i)|$ is finite for all $i$ , every row, as well as the target vector (typically $\mathbf{e}_{1}=(1,0,\ldots,0)$ ) have finitely many non-0 elements. See [11] for a formal definition. ⁸⁸8We use a “working definition” of linear evolving secret-sharing schemes specified by an IMSP, which is a natural extension of the finite case. An arguably more intuitive definition requires that all shares are linear combinations of the $r_{i}$ ’s and $s$ (over a field $\mathbb{F}$ ) without the restriction on reconstruction. Beimel has demonstrated in [3] that linear schemes imply MSPs of similar share complexity, so the definitions are equivalent. We do not demonstrate such a result in this paper, but it would be useful to demonstrate in future work on the theory of linear evolving schemes.

In the following theorem, we generalize the MSP-based linear secret-sharing schemes to the evolving setting, essentially giving each party the linear combinations of a randomness vector (that also defines the secret $s$ ), as specified by the IMSP. As in the finite case, every finite subset $A\subseteq\mathbb{N}^{+}$ either reconstructs the secret, or learns nothing about it.

Theorem 41.

Let $\mathcal{M}=(\mathbb{F},M,\rho)$ be an IMSP accepting an access structure $\Gamma$ . Then, Construction 42 instantiated with $\mathcal{M}$ implements $\Gamma$ .

Construction 42.

Consider an IMSP $\mathcal{M}(\mathbb{F},M,\rho)$ .

$\blacksquare$

INPUT: a secret $s\in\mathbb{F}$ .

We determine $r_{0}=s$ and define $\mathbf{r}=\left(s,r_{1},r_{2}\ldots\right)$ .
$\blacksquare$
SHARE: To generate $\mathsf{sh}_{i}$ the dealer does the following:
1. 1.
  
  Gets as input $(s,\mathsf{sh}_{1},\ldots,\mathsf{sh}_{i-1})$ , that is, a secret $s$ and the shares of parties $p_{1},\ldots,p_{i-1}$ . For convenience, we assume it in fact receives the set of $r_{1},\ldots,r_{j}$ ’s sampled so far, for $j=max(C_{[i-1]})$ . It samples random independent elements $r_{j+1},\ldots,r_{j+d}\in\mathbb{F}$ for $j+d=max(C_{[i]})$ .
2. 2.
  
  Set $\mathsf{sh}_{i}=M_{i}\mathbf{r}$ , where $\mathbf{r}$ is the prefix of $\mathbf{r}$ sampled so far.
$\blacksquare$

RECON: Let $\alpha$ denote the (finite) reconstruction vector such that $\alpha^{T}M_{B}=\mathbf{e_{1}}$ . Return $<\alpha,\Pi(B)>$ .

The proof of this theorem is deferred to the main version [11] and re-interprets the construction of [1] as an IMSP based scheme. We define evolving linear secret-sharing schemes as the set of schemes so specified by an IMSP.

For constructions for the evolving threshold, and for the evolving undirected $s t$ -connectivity access structures families as instances of IMSP, we refer the reader to the full version [11].

Theorem 43.

Let $\Gamma$ denote an evolving access structure. Then GIDT [1, Construction 3.9] for $S={\mathbb{F}}_{2}$ and $\Gamma$ instantiated so that edge predicates are implemented by linear schemes over ${\mathbb{F}}_{2}$ is (evolving) linear.

The proof immediately follows from observing the GIDT [1] given as Construction 3.9.

The following theorem states that for a large class of evolving access structures there is no minimal linear evolving secret-sharing scheme. This proof follows from Theorem 27 applied to any specific evolving scheme and a tailor crafted GIDT scheme [1, Construction 3.9], and is deferred to the full version [11].

Theorem 44.

Consider an evolving access structure $\Gamma$ such that there exists $\tilde{h}\in[n]$ , and an infinite collection of minterms $A=\{T_{i}\}_{i\in\mathbb{N}}$ where $\tilde{h}\in T_{i}$ for all $i\in\mathbb{N}$ . Then, for any linear scheme $\tilde{\Pi}$ specified by $M$ over $\mathbb{F}_{2}$ , there exists an evolving linear scheme $\tilde{\Pi^{\prime}}$ specified by $M^{\prime}$ over $\mathbb{F}_{2}$ for $\Gamma$ , such that $\tilde{\Pi}^{\prime}$ is not convertible to $\tilde{\Pi}$ .

Next, using results obtained in Section 6, we prove the absence of a maximal evolving scheme in a wide class of evolving secret-sharing schemes, even not necessarily linear.

Definition 45 (Trivial Evolving Access Structures).

An evolving access structure $\Gamma$ is said to be trivial if there exists $N\in\mathbb{N}$ such that, for all $n>N$ , $\{n\}\in\Gamma$ or for all finite set $A$ , $A\in\Gamma$ only if $A\setminus\{n\}\in\Gamma$ .

Theorem 46.

Any non-trivial evolving access structure $\Gamma$ and finite field $\mathbb{F}$ has no maximal evolving secret-sharing scheme over $\mathbb{F}$ .

Proof.

We will need the following technical claim on evolving access structures (see [11] for a proof).

Claim 47.

If $\Gamma$ is nontrivial, then for any $k\in\mathbb{N}$ , there exists $n\in\mathbb{N}$ such that $|\{F\in\mathcal{F}_{n}:1\notin F\}|\geq k$ , where $\mathcal{F}_{n}$ is the set of max-terms of $\Gamma_{n}$ .

Now, let $\Pi$ be a purported maximal secret-sharing scheme for one bit secrets realizing the access structure $\Gamma$ . Let $|\mathsf{sh}_{1}|$ be the share size of the share assigned to party $1$ by $\Pi$ . By the above claim, there exists $n$ such that, when $\mathcal{F}_{n}$ is the set of max-terms of $\Gamma_{n}$ , $|\{F\in\mathcal{F}_{n}:1\notin F\}|>|\mathsf{sh}_{1}|$ . Consider the GIDT-based construction $\Pi^{\prime}$ for $\Gamma$ of [1] with the first generation consisting of $n$ parties, and a CNF implementation of $\Gamma_{n}$ , in the edge going from the root to a leaf. By Theorem 40, $\Pi$ does not have a share conversion to $\Pi^{\prime}$ since the size of share $i$ is less than $|\{F\in\mathcal{F}_{n}:1\notin F\}|>|\mathsf{sh}_{1}|$ . $\hfill\blacktriangleleft$

8 Extensions and applications

Above, we considered secret-share conversion for schemes defined over the same field. It this section, we discover the possibility to perform share conversion between schemes over different fields. We show that the most of our impossibility results is applicable to the case when the source and target schemes are defined over the fields of the same characteristic, and when characteristics are different, the conversion is not possible for many access structures.

8.1 Extending impossibility results to schemes over different fields of the same characteristics

In this section, we extend our impossibility results following from Theorem 27 to secret sharing schemes defined over distinct fields of the same characteristic. For this, we slightly restate Lemma 25 and Theorem 27 such that $\Pi$ and $\Pi^{\prime}$ are two secret sharing schemes defined over ${\mathbb{F}}$ and ${\mathbb{F}}^{\prime}$ , respectively, which are the extension fields of ${\mathbb{F}}_{p}$ .

Observation 48.

Lemma 25 holds for secret-sharing schemes $\Pi$ defined by MSP $({\mathbb{F}},M\in{\mathbb{F}}^{m\times k},\rho)$ and $\Pi^{\prime}$ defined by MSP $({\mathbb{F}}^{\prime},M^{\prime}\in{\mathbb{F}}^{\prime m^{\prime}\times k^{% \prime}},\rho^{\prime})$ with the secret domain ${\mathbb{F}}_{p}$ , where ${\mathbb{F}}$ and ${\mathbb{F}}^{\prime}$ are extension fields of ${\mathbb{F}}_{p}$ for prime $p$ .

Proof.

The proof is the same as the proof of Lemma 25, with the difference that (1) holds over ${\mathbb{F}}^{\prime}$ , Equation 2 is over ${\mathbb{F}}^{*}$ which is the extension field for both ${\mathbb{F}}$ and ${\mathbb{F}}^{\prime}$ , and Equation 3 is over ${\mathbb{F}}^{\prime}$ (where function $c$ is over ${\mathbb{F}}^{*}$ with the output in ${\mathbb{F}}^{\prime}$ ). $\hfill\blacktriangleleft$

Observation 49.

Theorem 27 holds for secret-sharing schemes $\Pi$ defined by MSP $({\mathbb{F}},M\in{\mathbb{F}}^{m\times k},\rho)$ and $\Pi^{\prime}$ defined by MSP $({\mathbb{F}}^{\prime},M^{\prime}\in{\mathbb{F}}^{\prime m^{\prime}\times k^{% \prime}},\rho^{\prime})$ with the secret domain ${\mathbb{F}}_{p}$ , where ${\mathbb{F}}$ and ${\mathbb{F}}^{\prime}$ are extension fields of ${\mathbb{F}}_{p}$ for prime $p$ .

Proof.

The proof of this observation is the same as the proof of Theorem 27, where all the equations before (4) are over ${\mathbb{F}}$ . To obtain Equation (4), we apply Theorem 27 under Observation 48 which facilitates the transition to the field ${\mathbb{F}}^{\prime}$ . Equations (4), (5), and all the following proof are constructed over ${\mathbb{F}}^{\prime}$ . $\hfill\blacktriangleleft$

We rely on the above observation to extend our impossibility result in Corollary 28 for conversion from certain linear schemes to CNF. In the observation below, both source and target schemes work for sharing secrets in the larger domains $\mathbb{F}$ , $\mathbb{F}^{\prime}$ , but are used only to share secrets in the base field $\mathbb{F}_{p}$ . Any such scheme may be viewed as a scheme over the smaller field $S$ , where each party, including $h$ receives several field elements, which correspond to operations over $\mathbb{F}_{p}$ . Shamir over a large extension field of $\mathbb{F}_{p}$ is one example of such a scheme.

Observation 50.

Corollary 28 holds for secret-sharing schemes $\Pi$ defined by MSP $({\mathbb{F}},M\in{\mathbb{F}}^{m\times k},\rho)$ and $\Pi^{\prime}=CNF_{\Gamma,{\mathbb{F}}^{\prime}}$ with the secret domain ${\mathbb{F}}_{p}$ , where ${\mathbb{F}}$ and ${\mathbb{F}}^{\prime}$ are extension fields of ${\mathbb{F}}_{p}$ for prime $p$ .

Proof.

The proof of this observation is the same as the proof of Corollary 28, where Theorem 27 is applied under Observation 48. $\hfill\blacktriangleleft$ The above result is not subsumed by Theorem 40, as it allows $\mathbb{F}$ to be much larger than $\mathbb{F}^{\prime}$ .

8.2 Negative result for the inter-field conversion

It is often useful in applications to perform share conversion between schemes over different fields of different characteristic. A natural choice of a secret domain for such a conversion is $\{0,1\}$ , as these values belong to all finite fields. Furthermore, these values can be viewed as bits, which is the most useful setting for most MPC protocols. In this section, we show that a local conversion, in general, is not possible (even from CNF) for many access structures. However, below we show a specially tailored leaky secret-sharing scheme over field ${\mathbb{Z}}_{p}$ which allows local conversion to a different field ${\mathbb{Z}}_{q}$ for $q<n/2$ for $(n,n)$ -threshold.

Next, we observe that for all pairs $p\neq q$ , and many access structures $\Gamma$ , one can not convert from $CNF_{\Gamma,{\mathbb{F}}_{p}}$ to $\Pi_{\Gamma,{\mathbb{F}}_{q}}$ , where $\Pi_{\Gamma,{\mathbb{F}}_{q}}$ is any linear scheme over $q$ for that share. More precisely, we have

Theorem 51.

Let $\Gamma$ denote an access structure for $n>1$ parties, such that for all maxterms $B_{1},B_{2}$ , $B_{1}\cup B_{2}=[n]$ .⁹⁹9For instance, the $(\lceil n/2\rceil+1,n)$ -threshold access structure. Let $p\neq q$ be primes, and $CNF_{\Gamma,{\mathbb{F}}_{p}}$ and $\Pi_{\Gamma,{\mathbb{F}}_{q}}$ linear schemes for $\Gamma$ over $\mathbb{F}_{p},\mathbb{F}_{q}$ respectively. Then $CNF_{\Gamma,{\mathbb{F}}_{p}}$ is not convertible to $\Pi_{\Gamma,{\mathbb{F}}_{q}}$ for secret domain $S=\{0,1\}$ (that is, we do not care how other secrets are converted).

The theorem follows almost immediately from a variant of Lemma 25 for different fields $p, q$ which we provide below (see full version [11] for a proof).

Claim 52.

Let $\Pi=(\mathbb{F}_{p},M\in\mathbb{F}^{m\times\ell}_{p},\rho)$ , $\Pi^{\prime}=(\mathbb{F}_{q},M^{\prime}\in\mathbb{F}^{m^{\prime}\times\ell^{% \prime}}_{q},\rho^{\prime})$ for a pair of primes $p\neq q$ , and let $T\cup\{h\}$ denote a minterm of $\Gamma$ . Let $\alpha_{T\cup h},\alpha^{\prime}_{T\cup h}$ be reconstruction functions for $T\cup\{h\}$ in $\Pi$ and $\Pi^{\prime}$ respectively. Assume $L=\mathrm{Rowspan}(M_{T})\cap\mathrm{Rowspan}(M_{h})=\{\mathbf{0}\}$ . Then for every conversion scheme $g$ from $\Pi$ to $\Pi^{\prime}$ there exists a sequence ${\mathbf{r}}_{1},\ldots,{\mathbf{r}}_{i},\ldots\in\mathbb{Z}^{\ell}$ and constant $c\in\mathbb{Z}$ such that (1) $\left({\alpha^{\prime}_{h}}\right)^{\mathsf{T}}g_{h}(M_{h}{\mathbf{r}}_{i}\mod p% )\equiv i+c\ (\text{mod }q)$ ; (2) $\left({\alpha_{h}}\right)^{\mathsf{T}}M_{h}{\mathbf{r}}_{i}\equiv i\ (\text{% mod }p)$ for all $i\in\mathbb{N}^{+}$ , and (3) $\langle{\mathbf{r}}_{i},\mathbf{e}_{1}\rangle\text{ mod }p\in\{0,1\}$ . We conclude that such a $g$ does not exist if $p\neq q$ .

Proof of Theorem 51.

Finally, the theorem follows from Claim 52 by observing that for $n>2$ , in $CNF_{\Gamma,{\mathbb{F}}_{p}}$ each party $p_{i}$ gets a subset of independent random vectors over ${\mathbb{F}}_{p}$ , namely ${\mathbf{r}}_{T}$ of each maxterm $T$ such that $i\notin T$ . The sets of ${\mathbf{r}}_{H}$ ’s that $h$ holds, vs those $T$ holds. Assume the contrary – that $h\notin H$ and $T\cap H=\emptyset$ . In that case $i\notin T\cup H$ , contradicting the assumptions that $T\cup H=[n]$ (as $T, H$ are maxterms). This implies that for $CNF_{\Gamma,{\mathbb{F}}_{p}}$ , $L=\{\mathbf{0}\}$ , so the conditions of Claim 52 are indeed satisfied by $\Pi=CNF_{\Gamma,{\mathbb{F}}_{p}}$ and $\Pi^{\prime}=\Pi_{\Gamma,{\mathbb{F}}_{q}}$ . $\hfill\blacktriangleleft$

8.3 The specially tailored additive secret-sharing scheme allowing inter-field conversion

Next, we build the secret-sharing scheme over the field ${\mathbb{Z}}_{p}$ , and define the conversion function to the field ${\mathbb{Z}}_{q}$ . The scheme implies some restrictions on the randomness of the dealer, and also is not perfectly secure. However it’s existence raises a question if there are statistical secure secret-sharing schemes allowing an inter-field conversion, and how small the leakage could be. The other question is about the possibility to convert the original additive scheme over ${\mathbb{F}}_{p}$ to a perfectly private scheme over ${\mathbb{F}}_{q}$ , by using the entire randomness domain of the former. This way, privacy of the converted scheme automatically holds by locality of the conversion scheme. Correctness is the only measure that suffers, with some small probability. This way, we are talking about a conversion scheme between the same pair of perfect schemes $\Pi,\Pi^{\prime}$ , while the conversion scheme itself is statistically correct.

The $𝒏$ -party additive convertible scheme $ADD_{p\to q}$ .

Parameters:

$p\neq q$ are primes such that $q<n/2$ .

Sharing algorithm:

(1)

the dealer for each $i\in[n]$ samples $r_{i}\leftarrow{\mathbb{Z}}_{p}$ .
(2)

If $\sum_{i=1}^{n}r_{i}=kpq+s$ , where $s\in\left\{{0,1}\right\}$ for some $k$ then output $\mathsf{sh}_{i}:=r_{i}$ and terminate. Otherwise go to Step 1.

Conversion function:

Each $p_{i}$ computes $\mathsf{sh}^{\prime}_{i}=\mathsf{sh}_{i}\mod q$ .

This scheme is correct by construction, with polynomial computational complexity, and statistical leakage less or equal to $p_{leak}=\frac{1}{p}+o\left(\frac{1}{p^{2}n}\right)$ (see the full version [11]).

The convertible additive scheme is the basic case for creating the convertible CNF and DNF schemes. However, even directly it could have several applications, similar to applications of dBits. For more details, we refer to the full version [11]. We leave the existence of practical inter-field convertible secret-sharing schemes with the statistical, or even computational security, as the open question for the future research.

References

[1] Bar Alon, Amos Beimel, Tamar Ben David, Eran Omri, and Anat Paskin-Cherniavsky. New upper bounds for evolving secret sharing via infinite branching programs. Cryptology ePrint Archive, Paper 2024/419, 2024. URL: https://eprint.iacr.org/2024/419.
[2] Abdelrahaman Aly, Emmanuela Orsini, Dragos Rotaru, Nigel P Smart, and Tim Wood. Zaphod: Efficiently combining LSSS and garbled circuits in SCALE. In Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 33–44, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3338469.3358943.
[3] A. Beimel. Secure schemes for secret sharing and key distribution. Phd thesis, 1996.
[4] Amos Beimel. Secret-sharing schemes: A survey. In Yeow Meng Chee, Zhenbo Guo, San Ling, Fengjing Shao, Yuansheng Tang, Huaxiong Wang, and Chaoping Xing, editors, Coding and Cryptology, pages 11–46, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. doi:10.1007/978-3-642-20901-7_2.
[5] Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Ilan Orlov. Share conversion and private information retrieval. In Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012, Proceedings of the Annual IEEE Conference on Computational Complexity, pages 258–268, September 2012. IEEE Computer Society Technical Committee on Mathematical Foundations of Computing ; Conference date: 26-06-2012 Through 29-06-2012. doi:10.1109/CCC.2012.23.
[6] Aner Ben-Efraim. On multiparty garbling of arithmetic circuits. In Advances in Cryptology–ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part III 24, pages 3–33, Cham, 2018. Springer, Springer International Publishing. doi:10.1007/978-3-030-03332-3_1.
[7] Aner Ben-Efraim, Lior Breitman, Jonathan Bronshtein, Olga Nissenbaum, and Eran Omri. MYao: Multiparty “Yao” garbled circuits with row reduction, half gates, and efficient online computation. Cryptology ePrint Archive, 2024. URL: https://eprint.iacr.org/2024/1430.
[8] Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J Wu. Exploring crypto dark matter: New simple PRF candidates and their applications. In Theory of Cryptography Conference, pages 699–729, Cham, 2018. Springer, Springer International Publishing. doi:10.1007/978-3-030-03810-6_25.
[9] Ronald Cramer, Ivan Damgård, and Yuval Ishai. Share conversion, pseudorandom secret-sharing and applications to secure computation. In Joe Kilian, editor, Theory of Cryptography, pages 342–362, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007/978-3-540-30576-7_19.
[10] Ivan Damgard and Rune Thorbek. Efficient conversion of secret-shared values between different fields. Cryptology ePrint Archive, 2008. URL: https://eprint.iacr.org/2008/221.
[11] Tamar Ben David, Varun Narayanan, Olga Nissenbaum, and Anat Paskin-Cherniavsky. New results in share conversion, with applications to evolving access structures. Cryptology ePrint Archive, 2024. URL: https://eprint.iacr.org/2024/1781.
[12] Itai Dinur, Steven Goldfeder, Tzipora Halevi, Yuval Ishai, Mahimna Kelkar, Vivek Sharma, and Greg Zaverucha. MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications. In Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part IV 41, pages 517–547, Cham, 2021. Springer, Springer International Publishing. doi:10.1007/978-3-030-84259-8_18.
[13] Daniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri, and Peter Scholl. Improved primitives for MPC over mixed arithmetic-binary circuits. In Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II 40, pages 823–852, Cham, 2020. Springer, Springer International Publishing. doi:10.1007/978-3-030-56880-1_29.
[14] Niv Gilboa and Yuval Ishai. Compressing cryptographic resources. In Advances in Cryptology - CRYPTO ’99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings, volume 1666 of Lecture Notes in Computer Science, pages 591–608. Springer, 1999. doi:10.1007/3-540-48405-1_37.
[15] Mitsuru Ito, Akira Saito, and Takao Nishizeki. Secret sharing scheme realizing general access structure. Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 72(9):56–64, 1989.
[16] Mauricio Karchmer and Avi Wigderson. On span programs. [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 102–111, 1993. doi:10.1109/SCT.1993.336536.
[17] Ilan Komargodski, Moni Naor, and Eylon Yogev. How to share a secret, infinitely. IEEE Trans. Inf. Theory, 64(6):4179–4190, 2018. doi:10.1109/TIT.2017.2779121.
[18] Ilan Komargodski and Anat Paskin-Cherniavsky. Evolving secret sharing: Dynamic thresholds and robustness. In Yael Kalai and Leonid Reyzin, editors, Theory of Cryptography, pages 379–393, Cham, 2017. Springer International Publishing. doi:10.1007/978-3-319-70503-3_12.
[19] Eleftheria Makri, Dragos Rotaru, Frederik Vercauteren, and Sameer Wagh. Rabbit: Efficient comparison for secure multi-party computation. In International Conference on Financial Cryptography and Data Security, pages 249–270, Berlin, Heidelberg, 2021. Springer, Springer Berlin Heidelberg. doi:10.1007/978-3-662-64322-8_12.
[20] Eleftheria Makri and Tim Wood. Full-threshold actively-secure multiparty arithmetic circuit garbling. In Progress in Cryptology–LATINCRYPT 2021: 7th International Conference on Cryptology and Information Security in Latin America, Bogotá, Colombia, October 6–8, 2021, Proceedings 7, pages 407–430, Cham, 2021. Springer, Springer International Publishing. doi:10.1007/978-3-030-88238-9_20.
[21] Anat Paskin-Cherniavsky and Olga Nissenbaum. New bounds and a generalizati-on for share conversion for 3-server PIR. Entropy, 24(4), 2022. doi:10.3390/e24040497.
[22] Anat Paskin-Cherniavsky and Leora Schmerler. On share conversions for private information retrieval. Entropy, 21(9), 2019. doi:10.3390/e21090826.
[23] Naty Peter. Evolving conditional disclosure secrets. In Information Security: 26th International Conference, ISC 2023, Groningen, The Netherlands, November 15–17, 2023, Proceedings, pages 327–347, Berlin, Heidelberg, 2023. Springer-Verlag. doi:10.1007/978-3-031-49187-0_17.
[24] Dragos Rotaru and Tim Wood. Marbled circuits: Mixing arithmetic and boolean circuits with active security. In International Conference on Cryptology in India, pages 227–249, Cham, 2019. Springer International Publishing. doi:10.1007/978-3-030-35423-7_12.
[25] Adi Shamir. How to share a secret. In Communications of the ACM, 22, pages 612–613, 1979. doi:10.1145/359168.359176.

[bib.bib1] [1] Bar Alon, Amos Beimel, Tamar Ben David, Eran Omri, and Anat Paskin-Cherniavsky. New upper bounds for evolving secret sharing via infinite branching programs. Cryptology ePrint Archive, Paper 2024/419, 2024. URL: https://eprint.iacr.org/2024/419.

[bib.bib2] [2] Abdelrahaman Aly, Emmanuela Orsini, Dragos Rotaru, Nigel P Smart, and Tim Wood. Zaphod: Efficiently combining LSSS and garbled circuits in SCALE. In Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 33–44, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3338469.3358943.

[bib.bib3] [3] A. Beimel. Secure schemes for secret sharing and key distribution. Phd thesis, 1996.

[bib.bib4] [4] Amos Beimel. Secret-sharing schemes: A survey. In Yeow Meng Chee, Zhenbo Guo, San Ling, Fengjing Shao, Yuansheng Tang, Huaxiong Wang, and Chaoping Xing, editors, Coding and Cryptology, pages 11–46, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. doi:10.1007/978-3-642-20901-7_2.

[bib.bib5] [5] Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Ilan Orlov. Share conversion and private information retrieval. In Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012, Proceedings of the Annual IEEE Conference on Computational Complexity, pages 258–268, September 2012. IEEE Computer Society Technical Committee on Mathematical Foundations of Computing ; Conference date: 26-06-2012 Through 29-06-2012. doi:10.1109/CCC.2012.23.

[bib.bib6] [6] Aner Ben-Efraim. On multiparty garbling of arithmetic circuits. In Advances in Cryptology–ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part III 24, pages 3–33, Cham, 2018. Springer, Springer International Publishing. doi:10.1007/978-3-030-03332-3_1.

[bib.bib7] [7] Aner Ben-Efraim, Lior Breitman, Jonathan Bronshtein, Olga Nissenbaum, and Eran Omri. MYao: Multiparty “Yao” garbled circuits with row reduction, half gates, and efficient online computation. Cryptology ePrint Archive, 2024. URL: https://eprint.iacr.org/2024/1430.

[bib.bib8] [8] Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J Wu. Exploring crypto dark matter: New simple PRF candidates and their applications. In Theory of Cryptography Conference, pages 699–729, Cham, 2018. Springer, Springer International Publishing. doi:10.1007/978-3-030-03810-6_25.

[bib.bib9] [9] Ronald Cramer, Ivan Damgård, and Yuval Ishai. Share conversion, pseudorandom secret-sharing and applications to secure computation. In Joe Kilian, editor, Theory of Cryptography, pages 342–362, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007/978-3-540-30576-7_19.

[bib.bib10] [10] Ivan Damgard and Rune Thorbek. Efficient conversion of secret-shared values between different fields. Cryptology ePrint Archive, 2008. URL: https://eprint.iacr.org/2008/221.

[bib.bib11] [11] Tamar Ben David, Varun Narayanan, Olga Nissenbaum, and Anat Paskin-Cherniavsky. New results in share conversion, with applications to evolving access structures. Cryptology ePrint Archive, 2024. URL: https://eprint.iacr.org/2024/1781.

[bib.bib12] [12] Itai Dinur, Steven Goldfeder, Tzipora Halevi, Yuval Ishai, Mahimna Kelkar, Vivek Sharma, and Greg Zaverucha. MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications. In Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part IV 41, pages 517–547, Cham, 2021. Springer, Springer International Publishing. doi:10.1007/978-3-030-84259-8_18.

[bib.bib13] [13] Daniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri, and Peter Scholl. Improved primitives for MPC over mixed arithmetic-binary circuits. In Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II 40, pages 823–852, Cham, 2020. Springer, Springer International Publishing. doi:10.1007/978-3-030-56880-1_29.

[bib.bib14] [14] Niv Gilboa and Yuval Ishai. Compressing cryptographic resources. In Advances in Cryptology - CRYPTO ’99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings, volume 1666 of Lecture Notes in Computer Science, pages 591–608. Springer, 1999. doi:10.1007/3-540-48405-1_37.

[bib.bib15] [15] Mitsuru Ito, Akira Saito, and Takao Nishizeki. Secret sharing scheme realizing general access structure. Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 72(9):56–64, 1989.

[bib.bib16] [16] Mauricio Karchmer and Avi Wigderson. On span programs. [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 102–111, 1993. doi:10.1109/SCT.1993.336536.

[bib.bib17] [17] Ilan Komargodski, Moni Naor, and Eylon Yogev. How to share a secret, infinitely. IEEE Trans. Inf. Theory, 64(6):4179–4190, 2018. doi:10.1109/TIT.2017.2779121.

[bib.bib18] [18] Ilan Komargodski and Anat Paskin-Cherniavsky. Evolving secret sharing: Dynamic thresholds and robustness. In Yael Kalai and Leonid Reyzin, editors, Theory of Cryptography, pages 379–393, Cham, 2017. Springer International Publishing. doi:10.1007/978-3-319-70503-3_12.

[bib.bib19] [19] Eleftheria Makri, Dragos Rotaru, Frederik Vercauteren, and Sameer Wagh. Rabbit: Efficient comparison for secure multi-party computation. In International Conference on Financial Cryptography and Data Security, pages 249–270, Berlin, Heidelberg, 2021. Springer, Springer Berlin Heidelberg. doi:10.1007/978-3-662-64322-8_12.

[bib.bib20] [20] Eleftheria Makri and Tim Wood. Full-threshold actively-secure multiparty arithmetic circuit garbling. In Progress in Cryptology–LATINCRYPT 2021: 7th International Conference on Cryptology and Information Security in Latin America, Bogotá, Colombia, October 6–8, 2021, Proceedings 7, pages 407–430, Cham, 2021. Springer, Springer International Publishing. doi:10.1007/978-3-030-88238-9_20.

[bib.bib21] [21] Anat Paskin-Cherniavsky and Olga Nissenbaum. New bounds and a generalizati-on for share conversion for 3-server PIR. Entropy, 24(4), 2022. doi:10.3390/e24040497.

[bib.bib22] [22] Anat Paskin-Cherniavsky and Leora Schmerler. On share conversions for private information retrieval. Entropy, 21(9), 2019. doi:10.3390/e21090826.

[bib.bib23] [23] Naty Peter. Evolving conditional disclosure secrets. In Information Security: 26th International Conference, ISC 2023, Groningen, The Netherlands, November 15–17, 2023, Proceedings, pages 327–347, Berlin, Heidelberg, 2023. Springer-Verlag. doi:10.1007/978-3-031-49187-0_17.

[bib.bib24] [24] Dragos Rotaru and Tim Wood. Marbled circuits: Mixing arithmetic and boolean circuits with active security. In International Conference on Cryptology in India, pages 227–249, Cham, 2019. Springer International Publishing. doi:10.1007/978-3-030-35423-7_12.

[bib.bib25] [25] Adi Shamir. How to share a secret. In Communications of the ACM, 22, pages 612–613, 1979. doi:10.1145/359168.359176.

New Results in Share Conversion, with Applications to Evolving Access Structures

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

1.1 Overview of Our Results

Necessary conditions for conversion between linear schemes.

Theorem 1 (Necessary condition for conversion between linear schemes – Informal).

Convertibility characterization for linear schemes.

Theorem 2 (Theorem 35, informal).

Share conversion from non-linear schemes.

Theorem 3 (Extended maximality of CNF).

Share conversion for evolving secret-sharing.

Theorem 4 (No evolving maximal scheme – Informal).

Theorem 5 (No evolving minimal scheme – Informal).

Conversion between different fields.

1.2 Future work

2 Prior Work

Share conversion.

Evolving secret-sharing.

3 Preliminaries

Notation.

Fact 6.

3.1 Secret-Sharing

Definition 7 (Access Structures).

Definition 8 (Threshold Access Structures).

Definition 9 (Secret-Sharing Schemes).

Definition 10 (Additive Secret-Sharing Scheme [15]).

Definition 11 (Shamir Secret-Sharing Scheme [25]).

Theorem 12 (Shamir [25]).

Definition 13 (Replicated Secret-Sharing Schemes [14]).

Definition 14 (DNF Secret-Sharing Scheme [15]).

Definition 15 (Monotone Span Program [16]).

Definition 16 (Access structure accepted by MSP [16]).

Claim 17 ([4]).

3.2 Evolving Secret-Sharing Schemes

Definition 18 (Evolving Access Structures).

Definition 19 (Evolving Secret-Sharing Schemes).

Definition 20 (Evolving Threshold Access Structures).

Theorem 21 ([17]).

3.3 Share Conversion

Definition 22 (Share Conversion).

Definition 23 (Evolving Share Conversion).

Claim 24.

4 Impossibility results for linear Share Conversion

Lemma 25.

▶ Remark 26.

Proof of Lemma 25.

Theorem 27.

Proof.

Corollary 28.

▶ Remark 29.

Theorem 30.

Proof.

Theorem 31.

Proof.

▶ Remark 32.

▶ Remark 33.

5 A characterization of convertability between linear schemes

The linear system 𝓛𝚷,𝚷′.

▶ Remark 34.

Theorem 35.

Proof.

Future work.

6 Impossibility of conversion to CNF for general schemes

Definition 36.

Proposition 37.

Proof.

Lemma 38.

Lemma 39.

Theorem 40.

Proof.

7 Results for Evolving Linear Secret-Sharing Schemes

Theorem 41.

$\blacktriangleright$ Remark 26.

$\blacktriangleright$ Remark 29.

$\blacktriangleright$ Remark 32.

$\blacktriangleright$ Remark 33.

The linear system $\mathcal{L}_{\Pi,\Pi^{\prime}}$ .

$\blacktriangleright$ Remark 34.

The $𝒏$ -party additive convertible scheme $ADD_{p\to q}$ .