1 Introduction

Evolving secret-sharing schemes, introduced by Komargodski, Naor, and Yogev [11], are a secret-sharing scheme in which the dealer does not know the number of parties that will participate and has no upper bound on their number. The parties arrive one after the other and when a party arrives the dealer gives it a share; the dealer cannot update this share when other parties arrive. The motivation for studying such schemes is that updates can be the very costly (e.g., the Y2K problem). On the other hand, if the system designer would take cautious upper bound on the number of parties, then the scheme will not be efficient (specifically, if a small number of parties participate).

Komargodski, Naor and Yogev [11] constructed evolving k-threshold secret-sharing schemes for any constant k (where any k parties can reconstruct the secret). The size of the share of the i-th party in their scheme is \(O(k \log i)\). Komargodski and Paskin-Cherniavsky [12] constructed evolving dynamic a-threshold secret-sharing schemes (for every \(0< a <1\)), where any set of parties whose maximum party is the i-th party and contains at least ai parties (i.e., the set contains an a-fraction of the firtst i parties) can reconstruct the secret; any set such that all its prefixes are not an a-fraction of the parties should not get any information on the secret. The length of the share of the i-th party in their scheme is \(O(i^4 \log i)\). As the number of parties is unbounded, this share size can be quite large.

We consider a relaxation of evolving a-threshold secret-sharing schemes motivated by ramp secret-sharing schemes. Ramp secret-sharing schemes were first presented by Blakley and Meadows [2], and were used to construct efficient secure multiparty computation (MPC) protocols, starting in the work of Franklin and Yung [8]. We consider evolving (a, b)-ramp secret-sharing schemes (where \(0<b< a <1\)), in which any set of parties whose maximum party is the i-th party and contains at least ai parties can reconstruct the secret, however we only require that any set such that all its prefixes are not a b-fraction of the parties should not get any information on the secret. For all constants \(0<b< a <1\), we construct an evolving (a, b)-ramp secret-sharing scheme where the length of the share of the i-th party is O(1). Thus, we show that evolving ramp secret-sharing schemes offer a big improvement compared to the known constructions of evolving \(a\cdot i\)-threshold secret-sharing schemes. We note that all our schemes are linear.

Our Technique. We demonstrate the basic idea of our schemes by describing a simple construction of an evolving (1/2,1/8)-ramp secret-sharing scheme. Following [11], we partition the parties to sets, called generations, according to the order they arrive. The first generation contains the first two parties, the second generation contains the next \(2^2\) parties, and so on, where the g-th generation contains \(2^g\) parties. When the first party of the g-th generation arrives, the dealer prepares shares of a \(2^g/4\)-out-of-\(2^g\) threshold secret-sharing scheme (e.g., Shamir’s scheme [14]); when a party in generation g arrives the dealer gives it a share of this scheme. On one hand, if a set whose maximum party is the i-th party contains at least i/2 parties, then in some generation it contains at least 1/4 of the parties (even if it ends at the beginning of a generation), thus it can reconstruct the secret. On the other hand, if a set can reconstruct the secret from the shares of some generation g, then it contains at least 1/4 of the parties in that generation, hence it contains at least 1/8 of the parties that have arrived until the end of the generation.

Using a more complicated analysis, we show how to construct evolving (1/2,b)-ramp secret-sharing schemes with small share size for every \( b < 1/6\) by sharing the secret using one threshold secret-sharing scheme in each generation (with an appropriate threshold). To construct evolving (a, b)-ramp secret-sharing schemes for every constants \(0< b< a<1\), we need to share the secret more than once in each generation. However, we share the secret only O(1) times in each generation, resulting in a scheme in which the share size of the i-th party is \(O(\log i)\) (where \(O(\log i)\) is the share size in the threshold secret-sharing scheme). To reduce the share size to O(1), we use (non-evolving) ramp secret-sharing schemes of Chen et al. [6] instead of the threshold secret-sharing schemes. As Chen et al. only provide an existential proof of their ramp schemes with share size O(1), we only obtain that there exist evolving (a, b)-ramp secret-sharing schemes with share size O(1). In contrast, our evolving (a, b)-ramp secret-sharing schemes with share size \(O(\log i)\) for party \(p_i\) are explicit.

1.1 Previous Works

Secret-sharing schemes were introduced by Shamir [14] and Blakley [1] for threshold access structures, and by Ito, Saito, and Nishizeki for the general case [9]. Shamir’s [14] and Blakley’s [1] constructions are efficient both in the size of the shares and in the computation required for sharing and reconstruction. The size of the share in Shamir’s scheme for sharing an \(\ell \)-bits secret among n parties is \(\max \{ \ell , \log n \}\). Blakley’s scheme requires larger share size, but it can be optimized by using finite fields to get a scheme that is equivalent to Shamir’s scheme. Kilian and Nisan [10] proved a \(\log (n-k+2)\) lower bound on the share size for sharing a 1-bit secret for the k-out-of-n threshold access structure. This lower bound implies that \(\varOmega (\log n)\) bits are necessary when k is not too close to n. Bogdanov, Guo, and Komargodski [3] proved that the lower bound of \(\varOmega (\log n)\) bits applies to any secret-sharing scheme realizing k-out-of-n threshold access structures for every \(1< k < n\). When \(k=1\) or \(k=n\), schemes with share size of 1 are known.

Ramp secret-sharing schemes are a generalization of threshold secret-sharing schemes that allow for a gap between the privacy and reconstruction thresholds. Ramp secret-sharing schemes were first presented by Blakley and Meadows [2], and were used to construct efficient secure multiparty computation (MPC) protocols, starting in the work of Franklin and Yung [8]. Ramp schemes have found numerous other applications in cryptography, including broadcast encryption [15] and error decodable secret sharing [13]. Cascudo, Cramer, and Xing [5] proved lower bounds on the share size in ramp secret-sharing schemes: If every set of size at least an can reconstruct the secret while every set of size at most bn cannot learn any information on the secret, then the length of the shares is at least \(\log ((1-b)/(a-b))\). Bogdanov et al. [3] showed that for all \(0<b<a<1\), in any ramp secret sharing the length of the shares is at least \(\log (a/(a-b))\). On the positive side, Chen et al. [6] proved that for every \(\epsilon >0\) there is a ramp secret-sharing scheme with share size O(1) in which every set of size at least \((1/2+\epsilon )n\) can reconstruct the secret while every set of size at most \((1/2-\epsilon )n\) cannot learn any information on the secret.

Evolving Secret-Sharing Schemes. Evolving secret-sharing schemes were introduced by Komargodski, Naor, and Yogev [11]. They showed that for every evolving access structure there is a secret-sharing scheme that realizes it in which the share size of party i is \(2^{i-1}\) (even if the dealer does not know the access structure in advance). The main result of their work is providing schemes for evolving threshold access structures. They showed a scheme for the evolving 2-threshold access structure where the share size of party i is \(\log i + O(\log \log i)\). Furthermore, they proved a matching lower bound on the share size in any evolving secret-sharing scheme realizing the evolving 2-threshold access structure, that is, their scheme is almost optimal. They generalized the scheme for the evolving 2-threshold access structure to a scheme for the evolving k-threshold access structure for any constant \(k \in {\mathbb {N}}\). In their scheme, the size of the share of the i-th party is \((k-1)\log i + O(\log \log i)\).

Komargodski and Paskin-Cherniavsky [12] considered evolving \(\alpha (i)\)-threshold access structures, where a set A is authorized if for some \(p_i \in A\) the set A contains at least \(\alpha (i)\) parties from the set \(\{p_1,\dots ,p_i\}\). For example, for the function \(\alpha (i)=i/2\) this is the evolving \(1/2\cdot i\)-threshold access structure. For every monotone function \(\alpha :{\mathbb {N}}\rightarrow {\mathbb {N}}\), they constructed an evolving secret-sharing scheme realizing the evolving \(\alpha (i)\)-threshold access structure in which the share size of the i-th party is \(O(i^4 \log i)\). Furthermore, they showed how to transform any evolving secret-sharing scheme to a robust schme, where a shared secret can be recovered even if some parties hand-in incorrect shares.

Cachin [4] and Csirmaz and Tardos [7] considered online secret sharing, which is similar to evolving secret-sharing schemes. As in evolving secret-sharing scheme, in on-line secret-sharing, parties can enroll in any time after the initialization, and the number of parties is unbounded. However, in the works on online secret-sharing, the number of authorized sets a party can join is bounded.

2 Preliminaries

In this section we present formal definitions of secret-sharing schemes and evolving secret-sharing schemes.

Notations. We denote the logarithmic function with base 2 by \(\log \). We use the notation [n] to denote the set \(\{1,2, \dots , n \}\). When we refer to a set of parties \(A=\{p_{i_1}, p_{i_2},\dots , p_{i_t} \}\), we assume that \(i_1<i_2<\cdots < i_t\).

2.1 Secret-Sharing Schemes

We next present the definition of secret-sharing schemes.

Definition 2.1

(Access structures). Let \({\mathcal {P}}={\{p_1,\dots ,p_n\}}\) be a set of parties. A collection \(\varGamma \subseteq 2^{\{p_1,\dots ,p_n\}}\) is monotone if \(B \in \varGamma \) and \(B \subseteq C\) imply that \(C \in \varGamma \). An access structure \(\varGamma = (\varGamma _{\mathrm {YES}},\varGamma _{\mathrm {NO}})\) is a pair of collections of sets such that \(\varGamma _{\mathrm {YES}}, \varGamma _{\mathrm {NO}}\subseteq 2^{\{p_1,\dots ,p_n\}}\), the collections \(\varGamma _{\mathrm {YES}}\) and \(2^{\{p_1,\dots ,p_n\}}\setminus \varGamma _{\mathrm {NO}}\) are monotone, and \(\varGamma _{\mathrm {YES}} \cap \varGamma _{\mathrm {NO}} = \emptyset \). Sets in \(\varGamma _{\mathrm {YES}}\) are called authorized, and sets in \(\varGamma _{\mathrm {NO}}\) are called unauthorized. The access structure is called an incomplete access structure if there is a subset of parties \(A \subseteq {\mathcal {P}}\) such that \(A \not \in \varGamma _{\mathrm {YES}} \cup \varGamma _{\mathrm {NO}}\). Otherwise, it is called a complete access structure.

Definition 2.2

(Secret-sharing schemes). A secret-sharing \(\varSigma ={\langle \varPi ,\mu \rangle }\) over a set of parties \({\mathcal {P}}=\{p_1,\dots ,p_n\}\) with domain of secrets K is a pair, where \(\mu \) is a probability distribution on some finite set R called the set of random strings and \(\varPi \) is a mapping from \(K\times R\) to a set of n-tuples \(K_1\times K_2 \times \dots \times K_{n}\) (the set \(K_j\) is called the domain of shares of \(p_j\)). A dealer distributes a secret \(k\in K\) according to \(\varSigma \) by first sampling a random string \(r \in R\) according to \(\mu \), computing a vector of shares \(\varPi (k,r)=(s_1,\ldots ,s_{n})\), and privately communicating each share \(s_j\) to party \(p_j\). For a set \(A \subseteq {\{p_1,\dots ,p_n\}}\), we denote \(\varPi _A(k,r)\) as the restriction of \(\varPi (k,r)\) to its A-entries (i.e., the shares of the parties in A). The size of the secret is defined as \(\log |K|\) and the size of the share of party \(p_j\) is defined as \(\log |K_j|\).

A secret-sharing scheme \({\langle \varPi ,\mu \rangle }\) with domain of secrets K realizes an access structure \(\varGamma = (\varGamma _{\mathrm {YES}}, \varGamma _{\mathrm {NO}})\) if the following two requirements hold:

Correctness. The secret k can be reconstructed by any authorized set of parties. That is, for any set \(B=\{p_{i_1},\dots ,p_{i_{|B|}}\} \in \varGamma _{\mathrm {YES}}\), there exists a reconstruction function \(\mathrm{Recon}_B : K_{i_1} \times \cdots \times K_{i_{|B|}} \rightarrow K\) such that for every secret \(k\in K\) and every random string \(r \in R\), \( \mathrm{Recon}_B\Big (\varPi _B(k,r)\Big )=k. \)

Security. Every unauthorized set cannot learn anything about the secret from its shares. Formally, for any set \(T \in \varGamma _{\mathrm {NO}}\), every two secrets \(a,b \in K\), and every possible vector of shares \({\langle s_j \rangle }_{p_j\in T}\), \( \Pr [ \, \varPi _T(a,r) = {\langle s_j \rangle }_{p_j\in T} \, ] = \Pr [ \, \varPi _T(b,r) = {\langle s_j \rangle }_{p_j\in T} \, ], \) where the probability is over the choice of r from R at random according to \(\mu \).

Remark 2.3

For sets of parties \(A \in 2^{{\mathcal {P}}}\) such that \(A \not \in \varGamma _{\mathrm {YES}} \cup \varGamma _{\mathrm {NO}}\) there are no requirements, i.e., they might be able to reconstruct the secret, they may have some partial information on the secret, or they may have no information on the secret.

Definition 2.4

(Threshold access structures). Let \(1\le k\le n\). A k-out-of-n threshold access structure \(\varGamma \) over a set of parties \({\mathcal {P}}=\{p_1,\dots ,p_n\}\) is the complete access structure accepting all subsets of size at least k, that is, \(\varGamma _{\mathrm {YES}} = \{A\subseteq {\mathcal {P}}: |A|\ge k \}\) and \(\varGamma _{\mathrm {NO}} = \{ A\subseteq {\mathcal {P}}: |A|< k \}\).

The well known scheme of Shamir [14] for the k-out-of-n threshold access structure (based on polynomial interpolation) satisfies the following.

Claim 2.5

(Shamir [14]). For every \(n \in N\) and \(1\le k\le n\), there is a secret-sharing scheme for secrets of length m realizing the k-out-of-n threshold access structure in which the share size is \(\ell \), where \(\ell = \max \{m, {\left\lceil \log (n+1) \right\rceil }\}\).

Definition 2.6

(Ramp secret-sharing schemes [2]). Let \(0\le b \le a \le 1\). An (a, b)-ramp access structure over a set of parties \({\mathcal {P}}={\{p_1,\dots ,p_n\}}\) is the incomplete access structure \(\varGamma ^n_{a,b} = (\varGamma _{\mathrm {YES}},\varGamma _{\mathrm {NO}})\), where \(\varGamma _{\mathrm {YES}} = \{A \subseteq {\mathcal {P}}: |A| \ge an \}\) and \(\varGamma _{\mathrm {NO}} = \{A \subseteq {\mathcal {P}}: |A| < bn \}\). An (a, b)-ramp scheme with n parties is a secret-sharing scheme realizing \(\varGamma ^n_{a,b}\).

Chen et al. [6] showed the existence of ramp secret-sharing schemes with share size O(1).

Claim 2.7

(Chen et al. [6]). For every constant \(0< \epsilon <1/2\) there are integers \(\ell \) and \(n_0\) such that for every \(n \ge n_0\) there is a \((1/2+\epsilon ,1/2-\epsilon )\)-ramp secret-sharing scheme with n parties and share size \(\ell \).

2.2 Secret Sharing for Evolving Access Structures

We proceed with the definition of an evolving access structure, introduced in [11].

Definition 2.8

(Evolving access structures). Let \({\mathcal {P}}=\{p_i\}_{i \in {\mathbb {N}}}\) be an infinite set of parties. An evolving access structure \(\varGamma =(\varGamma _{\mathrm {YES}},\varGamma _{\mathrm {NO}})\) is a pair of collections of sets \(\varGamma _{\mathrm {YES}},\varGamma _{\mathrm {NO}} \subset 2^{{\mathcal {P}}}\), where each set in \(\varGamma _{\mathrm {YES}}\cup \varGamma _{\mathrm {NO}}\) is finite and for every \(t \in {\mathbb {N}}\) the collections \(\varGamma ^t\triangleq (\varGamma _{\mathrm {YES}}\cap 2^{\{p_1,\dots ,p_t\}},\varGamma _{\mathrm {NO}}\cap 2^{\{p_1,\dots ,p_t\}})\) is an access structure as defined in Definition 2.1.

Definition 2.9

(Evolving secret-sharing schemes). Let \(\varGamma \) be an evolving access structure, K be a domain of secrets, where \(|K| \ge 2\), and \(\{R^t\}_{t \in {\mathbb {N}}},\{K^t\}_{t \in {\mathbb {N}}}\) be two sequences of finite sets. An evolving secret-sharing scheme with domain of secrets K is a pair \(\varSigma ={\langle \{\varPi ^t\}_{t \in {\mathbb {N}}},\{\mu ^t\}_{t \in {\mathbb {N}}} \rangle }\), where, for every \(t \in {\mathbb {N}}\), \(\mu ^t\) is a probability distribution on \(R_t\) and \(\varPi ^t\) is a mapping \(\varPi ^t:K\times R_1\times \cdots \times R_t\rightarrow K_{t}\) (this mapping returns the share of \(p_j\)).

An evolving secret-sharing scheme \(\varSigma ={\langle \{\varPi ^t\}_{t \in {\mathbb {N}}},\{\mu ^t\}_{t \in {\mathbb {N}}} \rangle }\) realizes \(\varGamma \) if for every \(t\in {\mathbb {N}}\) the secret-sharing scheme \({\langle \mu ^1\times \cdots \times \mu ^t,\varPi _t \rangle }\), where \(\varPi _t(k,(r_1,\dots ,r_k)) ={\langle \varPi ^1(k,r_1), \dots ,\varPi ^t(k,r_1,\dots ,r_t) \rangle },\) is a secret-sharing scheme realizing \(\varGamma ^t\) according to Definition 2.2.

Definition 2.10

(Evolving threshold access structures [11]). For every \(k \in {\mathbb {N}}\), the evolving k-threshold access structure is the evolving access structure \(\varGamma \), where \(\varGamma ^t\) is the k-out-of-t threshold access structure.

Definition 2.11

(\(\alpha (t)\)-threshold access structures [12]). Let \(\alpha : {\mathbb {N}}\rightarrow {\mathbb {N}}\) be a monotone function. The \(\alpha (t)\)-threshold access structure is the evolving access structure \(\varGamma \), where \(\varGamma ^t\) is the \(\alpha (t)\)-out-of-t threshold access structure.

Similar to the above definition of the \(\alpha (t)\)-threshold access structure, we define the evolving ramp access structure as follows.

Definition 2.12

(Evolving ramp access structures). For every \(0 \le b < a \le 1\), the evolving (a, b)-ramp incomplete access structure is the evolving incomplete access structure \(\varGamma _{a,b}\), where \(\varGamma ^t_{a,b}\) is the (a, b)-ramp access structure.

Let \(A = \{p_{i_1}, p_{i_2},\dots , p_{i_t} \}\). Notice that the set A is authorized in \(\varGamma _{a,b}\) if \(a \cdot i_j < j\) for some \(1 \le j \le t\). Furthermore, the set A is unauthorized in \(\varGamma _{a,b}\) if \(b \cdot i_j \ge j\) for every \(1 \le j \le t\). There are no requirements on sets where \(j < a\cdot i_j\) for every j and \(b\cdot i_j < j\) for at least one j.

We next prove two lemmas that are used to prove the security and correctness of the schemes we construct in this paper.

Lemma 2.13

Assume that we share a secret s using a k-out-of-n secret-sharing scheme among the parties \(p_{\ell +1},\dots ,p_{\ell +t}\) and

$$\begin{aligned} k\ge & {} b \left( {\ell +t} \right) . \end{aligned}$$
(1)

If a set \(A=\{p_{i_1}, p_{i_2},\dots , p_{i_t} \}\), where \(i_t \le \ell +t\), can learn information on the secret then \(|A| \ge b \cdot i_t\), i.e., A is not unauthorized in \(\varGamma _{a,b}\).

Proof

If A can learn information on the secret, by the security of the threshold secret-sharing scheme, it must contain at least k parties from the parties \(p_{\ell +1},p_{\ell +2},\dots ,p_{\ell +n}\). Since \(i_t \le \ell +t\) parties, by (1), \(|A| \ge k \ge b (\ell +t) \ge b \cdot i_t.\) This implies that A contains at least a fraction b of the parties \(p_{1},p_{\ell +2},\dots ,p_{i_t}\), i.e., A is not unauthorized in \(\varGamma _{a,b}\). \(\square \)

The above lemma remains true if we replace the k-out-of-n secret-sharing scheme with any secret-sharing scheme in which each set of size \(k-1\) has no information on the secret.

Lemma 2.14

Let \(A=\{p_{i_1}, p_{i_2},\dots , p_{i_t} \}\) be a minimal authorized set in \(\varGamma _{a,b}\) for \(a<1\). If for some \( j < i_t\) there are at most D parties in \(A \cap \{p_1,\dots ,p_j\}\), then \(i_t \cdot a \ge \frac{a}{1-a} (j-D).\)

Proof

We first give an upper bound on the size of A, \(|A| = |A \cap \{p_1,\dots ,p_j\}|+|A \cap \{p_{j+1},\dots ,p_{i_t}\}| \le D +i_t -j.\) Since A is a minimal authorized set, the number of parties in A is at least \(i_t \cdot a\), hence, \( D+ i_t - j \ge i_t \cdot a\), and the lemma follows. \(\square \)

3 Two Warmup Evolving Ramp Schemes

3.1 A Simple Scheme Realizing \(\varGamma _{1/2,1/8}\)

As a warm up, we start with a secret-sharing scheme realizing \(\varGamma _{1/2,1/8}\). We partition the parties into sets, called generations; the size of generation g is \(2^g\), that is, generation g contains the parties \(p_{2^g-1},\dots ,p_{2^{g+1}-2}\). We define the scheme \(\varPi ^0\) as follows.

figure a

Remark 3.1

In the above scheme and in the rest of the paper, when we instruct the dealer to share the secret among the parties in generation g, we mean that when the first party of generation g arrives, the dealer shares the secret using Shamir’s threshold scheme; when the i-th party in generation g arrives, the dealer gives it the i-th share of the scheme. Since we use Shamir’s scheme, the dealer does not need to prepare all shares of Shamir’s scheme in advance; instead it samples the appropriate polynomial Q; when the i-th party in generation g arrives, the dealer gives it the share Q(i).

In order to prove the correctness of \(\varPi ^0\), it suffices to prove that a minimal authorized set of parties A, that is, a set that contains the majority of the parties that have arrived, can reconstruct the secret. Let \(A=\{p_{i_1}, p_{i_2},\dots , p_{i_t} \}\) be a minimal authorized set; in particular \(t\ge i_t/2\). Let g be the generation of party \(p_{i_t}\). Then, \(i_t \ge 2^g - 1\) and

$$\begin{aligned} |A|\ge & {} {\left\lceil \frac{i_t}{2} \right\rceil } \ge \left\lceil \frac{2^g-1}{2} \right\rceil = 2^{g-1}. \end{aligned}$$
(2)

There are two cases:

  1. 1.

    For some \(j < g\) the number of parties in A from generation j is at least \(\frac{1}{4}\cdot 2^{j}\). In this case A can reconstruct the secret using the shares of generation j.

  2. 2.

    For each \(j < g\), there are less than \(\frac{1}{4}\cdot 2^{j}\) parties from generation j. Thus, the number of parties in A from generations \(1,\dots ,g-1\) is less than \(\sum _{j=1}^{g-1} \frac{1}{4} \cdot 2^j = (2^g-2)/4\). Thus, by (2), the number of parties in A from generation g is at least \(|A| - (2^g-2)/4 \ge 2^{g-1} - (2^g-2)/4 > 2^{g}/4\), so the parties in A from generation g can reconstruct the secret using the shares of generation g.

Next we prove the security of the scheme. We show that if the parties in A can learn some information on the secret, then there is a prefix of A that contains at least a 1/8 fraction of the parties, i.e., the set A is not unauthorized. As the dealer shares the secret independently in each generation, if a set A can learn some information on the secret, then it can learn information on the secret from the shares of some generation g. In generation g, the secret is shared by a \(\frac{2^g}{4}\)-out-of-\(2^g\) secret-sharing scheme among the parties \(p_{2^g-1},\dots ,p_{2^{g+1}-2}\). It holds that \( 2^{g}/{4} \ge \left( 2^{g+1}-2 \right) /8\). Therefore, by Lemma 2.13, the set of parties in A from generations \(1,\dots ,g\) is not unauthorized in \(\varGamma _{1/2,1/8}\), hence, A is not unauthorized.

3.2 A Scheme Realizing for \(\mathbf {b < \frac{1}{6}}\)

We next generalize the scheme \(\varPi ^0\) to a scheme realizing \(\varGamma _{1/2,b}\) provided that \(b < \frac{1}{6}\). We denote the scheme by \(\varPi ^1\). We partition the parties to generations, where the size of generation g is \(m^g\) for some integer \(m\) that will be fixed later. That is, generation g contains the parties \(p_{\frac{m^g-m}{m-1}+1}, \dots , p_{\frac{m^{g+1}-m}{m-1}}\). We define the scheme \(\varPi ^1\) below; in this scheme, \(c<1\) and \(g_0\) are constants that will be chosen such that correctness and security hold.

figure b

For security, we require that

$$\begin{aligned} c\ge \frac{bm}{m-1}. \end{aligned}$$
(3)

Thus, \({\left\lceil c\cdot m^g \right\rceil } \ge c\cdot m^g \ge \frac{bm^{g+1}}{m-1} > b\cdot \frac{m^{g+1}-m}{m-1}\), and, by Lemma 2.13, every set that can learn information on the secret is not unauthorized, thus, the scheme is secure.

For correctness, let \(A =\{p_{i_1}, p_{i_2},\dots , p_{i_t} \}\) be a minimal authorized set in \(\varGamma _{1/2,b}\); in particular, \(t\ge i_t/2\). Let g be the generation of party \(p_{i_t}\). There are two cases.

First Case. For some \(j < g\), the number of parties in A from generation j is at least \({\left\lceil c\cdot m^{j} \right\rceil }\). In this case A can reconstruct the secret using the shares of generation j.

Second Case. For every \(j < g\), the number of parties in A from generation j is less than \({\left\lceil c \cdot m^{j} \right\rceil }\), thus is less than \(c\cdot m^j\). In this case, we show a condition on the parameters m and c that implies that the number of parties from generation g in A must be at least \({\left\lceil c\cdot m^{g} \right\rceil }\), and therefore they can reconstruct the secret.

We first show that, since the first case does not hold, the index \(i_t\) cannot be in the beginning of generation g. Since for \(1\le j \le g-1\) the number of parties from generation j is less than \(c\cdot m^j\),

The number of parties in A from the first \(g-1\) generations is less than

$$\begin{aligned} \sum _{j=1}^{g-1}c \cdot m^j = c \cdot \frac{m^g-m}{m-1}. \end{aligned}$$
(4)

Thus, since the first party in generation g is \(p_{\frac{m^g-m}{m-1}+1}\), by Lemma 2.14 it holds that \(\frac{i_t}{2} \ge \frac{m^g-m}{m-1}(1- c).\)

Since \(t= |A| \ge \frac{i_t}{2}\), by (4), the number of parties from generation g is at least

$$\begin{aligned} \frac{i_t}{2}- c\cdot \frac{m^g-m}{m-1} \ge \frac{\left( m^g -m\right) \left( 1-2c \right) }{m-1}. \end{aligned}$$
(5)

For correctness, we want that the parties in generation g can reconstruct the secret. Therefore, it suffices to require \( \frac{\left( m^g -m\right) \left( 1-2c \right) }{m-1} \ge c\cdot m^g+1.\) That is, \(m^g \left( \frac{1-2c}{m-1} - c\right) \ge 1 + \frac{m(1-2c)}{m-1}.\) If \(\frac{1-2c}{m-1} - c> 0\), then there is a \(g_0\) such that for every \(g\ge g_0\) the condition holds. For the parties in the first \(g_0-1\) generations we share the secret using a (non-evolving) secret-sharing scheme realizing the (a, b)-ramp access structure restricted to the parties in the first \(g_0-1\) generations. Therefore, it suffices to require \(\frac{1-2c}{m-1} - c> 0. \) That is,

$$\begin{aligned} c < \frac{1}{m+1}. \end{aligned}$$
(6)

By (3) and (6),

$$\begin{aligned} b\le & {} \frac{c(m-1)}{m} \le \frac{m-1}{m} \cdot \frac{1}{m+1} = \frac{m-1}{m^2 + m}. \end{aligned}$$
(7)

The maximum value of the right hand side of (7) is maximized when \(m=3\) (recall that \(m\) is an integer); in this case (7) holds when \(b < \frac{1}{6}\). In this case, we take \(c=\frac{bm}{m-1}=1.5 b <1/4\) and (3) and (6) hold.

Lemma 3.2

For every \(b< \frac{1}{6}\), there exists an integer \(g_0\) such that the scheme \(\varPi ^1\) realizes \(\varGamma _{1/2,b}\).

Proof

The correctness and security of the \(\varPi ^1\) for parties in generations \(g \ge g_0\) follows from the discussion above. A traditional secret-sharing scheme is used in Step 3.2 of \(\varPi ^1\) to share the secret for parties in the first \(g_0-1\) generations is correct and secure. Since the shares given to parties in generations \(g \ge g_0\) are independent of the shares given to the parties in the first \(g_0-1\) generations, the combination of both secret-sharing schemes is correct and secure as well. \(\square \)

Example 3.3

If we take \(m=3\) and \(b={1}/{7}\). Then, \(c= 3/14\) and \( \frac{1-2c}{m-1} - c= ({1-{3}/{7}})/{2} - {3}/{14}={1}/{14}\). Thus, for (5) to hold, we can take \(g_0 = 3\), therefore we need to share the secret among the parties in the first 2 generations using a (non-evolving) secret-sharing scheme.

4 Evolving Ramp Schemes Realizing for Every \(\mathbf {a < 1}\) and \(\mathbf {b < a}\)

In the scheme \(\varPi ^1\), in each generation we shared the secret using one threshold secret-sharing scheme; \(\varPi ^1\) can realize \(\varGamma _{1/2,b}\) only when \(b < 1/6\). To realize \(\varGamma _{a, b}\) for every \(a<1\) and \(b < a\), we generalize the previous method and in each generation we share the secret using r threshold secret-sharing schemes, for a constant r.

As in our previous schemes, we partition the parties into generations, where the size of generation g is \(m^g\). That is, generation g contains the parties

$$\begin{aligned} p_{\frac{m^g-m}{m-1}+1},\dots ,p_{\frac{m^{g+1}-m}{m-1}}. \end{aligned}$$

We define the scheme \({\varPi ^2}\) below; in this scheme, \(k_{r}=m-1 \) and the other parameters will be chosen later such that the security and correctness hold.

figure c

We will choose our parameters such that \(c_0 \le 1\) and \({\left\lceil c_{\ell } \cdot m^{g-1} \right\rceil } \le m^{g-1}+{\left\lceil \frac{ k_{\ell } }{m-1}\cdot m^{g} \right\rceil } \) for \(1 \le \ell \le r\), thus, all threshold schemes used in \({\varPi ^2}\) are properly defined. For security of \(\varPi _{ c_{0} }\), by Lemma 2.13, it suffices to require

$$\begin{aligned} c_{0} \ge \dfrac{b\cdot m}{m-1}. \end{aligned}$$
(8)

For security of \(\varPi _{ c_{\ell } }\) for each \(1\le \ell \le r\), we require

$$\begin{aligned} c_{\ell } \ge \dfrac{b\cdot m}{m-1} \cdot \left( 1+ k_{\ell } \right) . \end{aligned}$$
(9)

Thus, \({\left\lceil c_{\ell } \cdot m^{g-1} \right\rceil } \ge c_{\ell } \cdot m^{g-1} \ge \frac{b\cdot m}{m-1} \cdot \left( 1+ k_{\ell } \right) \cdot m^{g-1} \ge b\cdot \left( \frac{m^g}{m-1} + \frac{ k_{\ell } }{m-1}m^g \right) >~b\cdot \left( \frac{m^g-m}{m-1} + \frac{ k_{\ell } }{m-1}m^g + 1\right) \), and by Lemma 2.13 (observing that the maximal index of a party that gets a share in \(\varPi _{ c_{\ell } }\) is \(\frac{m^g-m}{m-1} + {\left\lceil \frac{ k_{\ell } }{m-1}\cdot m^{g} \right\rceil }\)), the scheme is secure.

Next we consider the correctness. Let \(A =\{p_{i_1}, p_{i_2},\dots , p_{i_t} \}\) be a minimal authorized set in \(\varGamma _{a,b}\); in particular, \(t\ge i_t \cdot a\). Let g be the generation of party \(p_{i_t}\). There are a few cases, for which we define \(r-1\) segments for every \(g \ge 2\).

  • Segment 1 contains the parties with indexes

    $$\begin{aligned} \left\{ \frac{m^g-m}{m-1}+1, \dots ,\frac{m^g-m}{m-1}+{\left\lceil \frac{k_{1}}{m-1}\cdot m^g \right\rceil } \right\} . \end{aligned}$$

  • Segment \(\ell \) where \(2\le \ell \le r-1\) contains the parties with indexes

    $$\begin{aligned} \left\{ \frac{m^g-m}{m-1}+{\left\lceil \frac{ k_{\ell -1} }{m-1}\cdot m^g \right\rceil }+1, \dots ,\frac{m^g-m}{m-1}+{\left\lceil \frac{ k_{\ell } }{m-1}\cdot m^g \right\rceil }\right\} . \end{aligned}$$

We defined \( k_{r} =m-1\); thus, these \(r-1\) segments are a partition of generation g.

First Case. For some \(j < g\), the number of parties in A from generation j is at least \({\left\lceil c_{0} \cdot m^{j} \right\rceil }\). In this case A can reconstruct the secret from the scheme \(\varPi _{ c_{0} }\) for generation j.

Observation 4.1

If case 1 does not hold, then for every \(j < g\) the number of parties in A from generations \(1,\ldots ,j\) is less than \(\sum _{i=1}^j c_{0} \cdot m^{j} = c_{0} \cdot \frac{m^{j+1}-m}{m-1}\).

Second Case. Case 1 does not hold and party \(p_{i_t}\) is in the first segment in generation g, that is \(\frac{m^g-m}{m-1}+1 \le i_t \le \frac{m^g-m}{m-1}+{\left\lceil \frac{ k_{1} }{m-1}\cdot m^g \right\rceil }\). In this case we show a condition on the parameters implying that the number of parties in A from generations \(g-1\) and the first segment of generation g must be at least \( c_{1} \cdot m^{g-1}\), therefore they can reconstruct the secret.

We start with a lower bound on \(i_t\). By Observation 4.1 and Lemma 2.14 (with \(j=\frac{m^g-m}{m-1}\) – the index of last party in generation \(g-1\))

$$\begin{aligned} i_t \cdot a \ge \frac{a}{1-a} \left( \frac{m^g-m}{m-1}(1- c_{0} ) \right) . \end{aligned}$$
(10)

The shares of \(\varPi _{ c_{1} }\) are given to the parties in generation \(g-1\) and the parties in the first segment in generation g. As the number of parties in A from generations \(1,\dots ,g-2\) is less than \( c_{0} \cdot \frac{m^{g-1}-m}{m-1}\) (by Observation 4.1), the number of parties in A from generation \(g-1\) and the parties in the first segment in generation g is at least

$$\begin{aligned} i_t\cdot a - c_{0} \cdot \frac{m^{g-1}-m}{m-1}. \end{aligned}$$
(11)

In order to reconstruct the secret from the scheme \(\varPi _{ c_{1} }\) of generation g, the number of parties from generation \(g-1\) and the parties in Segment 1 in generation g must be at least \({\left\lceil c_{1} \cdot m^{g-1} \right\rceil }\). Therefore, by (11), it suffices to require \(i_t \cdot a - c_{0} \cdot \frac{m^{g-1}-m}{m-1} \ge c_{1} \cdot m^{g-1}+1.\) Thus, by (10), it suffices to require \( \frac{a}{1-a} \left( \frac{m^g-m}{m-1}(1- c_{0} ) \right) - c_{0} \cdot \frac{m^{g-1}-m}{m-1} \ge c_{1} \cdot m^{g-1}+1,\) that is,

$$\begin{aligned} m^{g - 1} \left( \frac{ \frac{am}{1-a} \left( 1 - c_{0} \right) - c_{0} }{m-1} - c_{1} \right)\ge & {} \frac{ \frac{am}{1-a} \left( 1 - c_{0} \right) - c_{0} \cdot m}{m-1}+1. \end{aligned}$$
(12)

If \(\left( \frac{ \frac{am}{1-a} \left( 1 - c_{0} \right) - c_{0} }{m-1} - c_{1} \right) > 0\), then there exists \(g_1\) such that for every \(g \ge g_1\) inequality (12) holds. Therefore, it suffices to require that

$$\begin{aligned} \frac{\frac{a}{1-a}m- c_{1} \cdot (m- 1)}{\frac{a}{1-a}m+ 1} > c_{0} . \end{aligned}$$
(13)

Third Case. For each \(2 \le \ell \le r\) we define Case 3.\(\ell \) as:

The number of parties in A from generation \(g-1\) and the first \({\left\lceil \frac{ k_{\ell } \cdot m^{g}}{m-1} \right\rceil }\) parties from generation g is at least \({\left\lceil c_{\ell } \cdot m^{g} \right\rceil }\). In this case A can reconstruct the secret from the scheme \(\varPi _{ c_{\ell } }\) for generation g.

Fourth Case. For each \(2 \le \ell \le r\) we define the Case 4.\(\ell \) as:

Cases 1 and Case \(3.{\ell -1}\) do not hold and \(p_{i_t}\) is in the \(\ell \)-th segment in generation g, that is \(\frac{m^g-m}{m-1}+\left\lceil {\frac{ k_{\ell -1} }{m-1}\cdot m^g}\right\rceil + 1 \le i_t \le \frac{m^g-m}{m-1} + \left\lceil {\frac{ k_{\ell } }{m-1}\cdot m^g}\right\rceil \). In this case we show a condition on the parameters implying that the number of parties in A from generation \(g-1\) and the first \(\ell \) segments of generation g must be at least \( c_{\ell } \cdot m^{g-1}\), therefore they can reconstruct the secret.

The number of parties in A from generations \(1,\dots ,g-1\) and the parties in the first \(\ell -1\) segments in generation g is less than \( c_{0} \cdot \frac{m^{g-1}-m}{m-1} + c_{\ell -1} \cdot m^{g-1}\), by Observation 4.1 and since there are less than \( c_{\ell -1} \cdot m^{g-1}\) parties in A from generation \(g-1\) and the parties in the first \(\ell -1\) segments in generation g (since Case \(3.{\ell -1}\) does not hold). By Lemma 2.14 (with \(j=\frac{m^g-m}{m-1}+{\left\lceil \frac{ k_{\ell -1} }{m-1}\cdot m^g \right\rceil }\) – the index of last party in segment \(\ell -1\))

$$\begin{aligned} i_t\cdot a \ge \frac{a}{1-a} \left( \frac{m^g-m}{m-1}+\frac{ k_{\ell -1} }{m-1}\cdot m^g - { c_{0} \cdot \frac{ m^{g-1}-m}{m-1}} - { c_{\ell -1} \cdot m^{g-1}} \right) . \end{aligned}$$
(14)

The shares of the scheme \(\varPi _{ c_{\ell } }\) of generation g are given to the parties in generation \(g-1\) and the parties in the first \(\ell \) segments in generation g. As the number of parties in A from generations \(1,\dots ,g-2\) is less than \( c_{0} \cdot \frac{m^{g-1}-m}{m-1}\) (by Observation 4.1), the number of parties in A from generation \(g-1\) and the parties in the first \(\ell \) segments in generation g is at least

$$\begin{aligned} i_t\cdot a - c_{0} \cdot \frac{m^{g-1}-m}{m-1}. \end{aligned}$$
(15)

For correctness, we require that the parties in A from generation \(g-1\) and the parties in the first \(\ell \) segments in generation g can reconstruct the secret from the scheme \(\varPi _{ c_{\ell } }\) of generation \(g-1\). Therefore, by (15), it suffices to require \( i_t\cdot a - c_{0} \cdot \frac{m^{g-1}-m}{m-1} \ge c_{\ell } \cdot m^{g-1} +1 \, > \, {\left\lceil c_{\ell } \cdot m^{g-1} \right\rceil }.\) Thus, by (14), it suffices to require

$$\begin{aligned} \frac{a}{1-a} \left( \frac{m^g-m}{m-1}+\frac{ k_{\ell -1} }{m-1}\cdot m^g - { c_{0} \cdot \frac{ m^{g-1}-m}{m-1}} - { c_{\ell -1} \cdot m^{g-1}} \right) \nonumber \\ - c_{0} \cdot \frac{ m^{g-1}-m}{m-1} \quad \ge \quad c_{\ell } \cdot m^{g-1}+1. \end{aligned}$$
(16)

That is,

$$\begin{aligned} \nonumber m^{g-1} \left( \frac{ \frac{am}{1-a} \left( 1 + k_{\ell -1} \right) - c_{0} (1+\frac{a}{1-a}) }{m-1} - \frac{a}{1-a} c_{\ell -1} - c_{\ell } \right) \\ \ge 1 + \frac{m(\frac{a}{1-a} - c_{0} \frac{a}{1-a} - c_{0} )}{m-1}. \end{aligned}$$
(17)

If \( \frac{ \frac{am}{1-a} \left( 1 + k_{\ell -1} \right) - c_{0} (1+\frac{a}{1-a}) }{m-1} - \frac{a}{1-a} c_{\ell -1} - c_{\ell } > 0\), then there exist \(g_\ell \) such that for every \(g \ge g_\ell \) inequality (17) holds. Therefore, it suffices to require that

$$\begin{aligned} \frac{a}{1-a}m+ \frac{a}{1-a} k_{\ell -1} \cdot m- \frac{a}{1-a} c_{\ell -1} (m-1) - c_{\ell } (m-1)> & {} \frac{ c_{0} }{1-a}. \end{aligned}$$
(18)

4.1 Finding the Values of the Parameters for Realizing for Every \(\mathbf {b <a}\)

In order to build a scheme for \(\varGamma _{a,b}\) for \( 0< b< a < 1\), we have to find constants \(m, r, k_{1} ,\dots , k_{r-2} \), and \( c_{0} , c_{1} , \dots , c_r\) that satisfy (8), (9), (13), and (18). In Theorem 4.7 we prove that such constants exist for every \(b < a\). To find the values of the parameters, we first prove that we can choose the values of \( c_{0} ,\dots , c_{r} \) as the minimal values required by the security requirements (i.e., (8) and (9)). We then prove that for large enough \(m\) there is a value of \( k_{1} \) that satisfies inequality (13). Then, we prove that there exists a constant \(\beta <1\) such that for every \( k_{\ell } \) if we can take \( k_{\ell -1} =\beta k_{\ell } \), then we satisfy inequality (18). Thus, if we start with \( k_{r} =m-1\) and with a large enough r and apply the last step iteratively, then \( k_{1} \) is small enough to satisfy (13).

Example 4.2

As an example, for the scheme \(\varGamma _{1/2,0.25}\) we take \(r=2\) and \(m=5\). We start with \( k_{2} = m-1=4\) and take \(\beta =1/3\), thus, \( k_{1} =\beta k_{2} =4/3\). We choose the values of \( c_{0} , c_{1} \), and \( c_{2} \) as the minimal values required by (8) and (9), that is, \( c_{0} =\frac{mb}{m-1}= 5/16\), \( c_{1} =\frac{mb}{m-1}(1+ k_{1} )=35/48\), and \( c_{2} =\frac{mb}{m-1}(1+ k_{2} )=25/16\). Note that for \(a=1/2\) and \(m=5\), inequality (13) requires that \( c_{1} < (5-6 c_{0} )/4\) and \(c_0,c_1\) satisfy this inequality (if this inequality would not hold, we would have taken a larger r). It can be checked that (18) also holds.

Lemma 4.3

Let \( 0< b< a < 1\). If \({\varPi ^2}\) realizes the access structure \(\varGamma _{a,b}\) with the parameters \(r,m, k_{1} ,\dots ,\) \( k_{r} \) and \( c_{0} , c_{1} ,\dots , c_{r} \), then \({\varPi ^2}\) realizes it with \(r,m, k_{1} ,\dots , k_{r} \), \( c_{0} =\frac{m\cdot b}{m-1}\), and \( c_{\ell } = \frac{(1+ k_{\ell } )b\cdot m}{m-1}\)for every \(1\le \ell \le r\).

Proof

By (13), if we decrease \( c_{1} \) then the left side of the inequality increases, and thus the inequality still holds. By (18), if we decrease \( c_{\ell -1} \) and \( c_{\ell } \), the left side increases and, thus, the inequality still holds. In all the inequalities, if we decrease \( c_{0} \), they still hold. Therefore, we can decrease each \( c_{\ell } \) to its minimum value which is \( c_{\ell } = \frac{(1+ k_{\ell } )b\cdot m}{m-1}\) and keep the inequalities. \(\square \)

In all our proofs in this section, we take the minimum value of \( c_{0} , c_{1} ,\dots , c_{r} \), that is, \( c_{0} = \frac{m\cdot b}{m-1}\), and \( c_{\ell } = \frac{(1+k_{\ell })b\cdot m}{m-1}\) for every \(1 \le \ell \le r\).

Lemma 4.4

Let \(b < a\). Every \(m\ge \frac{2b}{a-b}\) and every \( k_{1} \le \frac{a-b}{2b(1-a)}\) satisfy (13).

Proof

We set \( c_{0} = \frac{m}{m-1}b\) and \( c_{1} = (1+ k_{1} ) \frac{m}{m-1}b\) in (13). Next we prove that for any \(b < a\) for every \(0< k_{1} < \frac{a-b}{2b(1-a)}\) inequality (13) holds. By substituting the above \( c_{0} , c_{1} \) in (13) we obtain the inequality \(\frac{\frac{a}{1-a}m- (1+ k_{1} ) \frac{m}{m-1}b \cdot (m-1)}{\frac{a}{1-a}m+1} > \frac{m}{m-1}b. \)

That is,

$$\begin{aligned} k_{1}< & {} \frac{ \frac{a}{1-a} - b - \frac{b}{m-1} - \frac{b a}{(1-a)(m-1)}}{b}\quad =\quad \frac{\frac{a-b}{1-a}-\frac{b}{(m-1)(1-a)}}{b}. \end{aligned}$$
(19)

Thus, every \(m> \frac{2b}{a-b}+1\) and \( k_{1} \le \frac{a-b}{(1-a)2b}\) satisfy inequality (19). \(\square \)

Lemma 4.5

For every \(b < a\), every \(m> \frac{a}{a-b}\), and every \( k_{\ell } \) inequality (18) is satisfied when \( k_{ \ell -1} =\frac{(1-a)b}{a(1-b)} k_{\ell } \).

Proof

We substitute \( c_{0} = \frac{mb}{m-1}\), \( c_{\ell -1} = (1+ k_{\ell -1} ) \frac{mb}{m-1} \), and \( c_{\ell } = (1+ k_{\ell } )\frac{mb}{m-1}\) in (18) and obtain the following requirement.

$$\begin{aligned} \frac{a}{1-a}m+\frac{a}{1-a} k_{\ell -1} m-\frac{a}{1-a}(1+ k_{\ell -1} ) \frac{mb}{m-1}(m-1) -(1+ k_{\ell } ) \frac{mb}{m-1}(m-1)\\ > \left( 1 + \frac{a}{1-a} \right) \frac{mb}{m-1}. \end{aligned}$$

That is,

$$\begin{aligned} \frac{a-b}{1-a} + \frac{a}{1-a}(1-b) k_{\ell -1} -b k_{\ell }> & {} \frac{ b}{(1-a)(m-1)}. \end{aligned}$$
(20)

Taking \( k_{ \ell -1} =\frac{(1-a)b}{a(1-b)} k_{\ell } \), we conclude that (20) holds if and only if \(m> \frac{b}{a-b}+1=\frac{a}{a-b}.\) \(\square \)

Next we show that the schemes \(\varPi _{ c_{0} }, \dots , \varPi _{ c_{r} }\) are all legal threshold secret-sharing schemes, that is, the number of parties needed to reconstruct the secret is at most the number of parties in the scheme.

Lemma 4.6

Assume that \(m\ge \frac{2}{1-b}\). The thresholds in the schemes \(\varPi _{ c_{\ell } }\) for \(0 \le \ell \le r \) are at most the number of parties in the schemes for every \(g \ge 2\), that is, \({\left\lceil c_{0} \cdot m^g \right\rceil } \le m^g\) and \({\left\lceil c_{\ell } \cdot m^{g-1} \right\rceil } \le m^{g-1}+{\left\lceil \frac{ k_{\ell } }{m-1}\cdot m^{g} \right\rceil }\) for \(1 \le \ell \le r\).

Proof

For \(\varPi _{ c_{0} }\), note that \( c_{0} =\frac{mb}{m-1}=b+\frac{b}{m-1}\). Thus, if \(m\ge \frac{b}{1-b}+1\), then \( c_{0} \le 1\) and \({\left\lceil c_{0} \cdot m^g \right\rceil } \le {\left\lceil m^g \right\rceil } =m^g\) as required.

For \(\varPi _{ c_{\ell } }\) (where \(1 \le \ell \le r\)), the threshold is \({\left\lceil c_{\ell } \cdot m^{g-1} \right\rceil } < c_{\ell } \cdot m^{g-1} +1\) and the number of parties is \(m^{g-1}+{\left\lceil \frac{ k_{\ell } }{m-1}\cdot m^{g} \right\rceil }\ge m^{g-1}+ \frac{ k_{\ell } }{m-1}\cdot m^{g}\). Recall that \( c_{\ell } =\frac{(1+ k_{\ell } )b\cdot m}{m-1}\). Thus, it suffices to show that \(\frac{(1+ k_{\ell } )b m}{m-1} \cdot m^{g-1} + 1 \le m^{g-1}+\frac{ k_{\ell } }{m-1}\cdot m^{g}.\)

As \(b <1\) and \(g \ge 2\), it suffices to choose \(m\) such that

$$\begin{aligned} \left( 1 - \frac{bm}{m-1} \right) m\ge & {} 1. \end{aligned}$$
(21)

Taking \(m \ge \frac{2}{1-b}\) satisfies (21). \(\square \)

Theorem 4.7

For every \(b < a\) there is a choice of the parameters such that \({\varPi ^2}\) realizes \(\varGamma _{a,b}\) with share size of \(O(\log i)\) for party \(p_i\).

Proof

In order to prove the theorem, we need to show that for every \(b < a\) there is a choice of the parameters that satisfies (8), (9), (13), and (18). We take \( c_{0} = \frac{mb}{m-1}\) and \( c_{\ell } = (1+ k_{\ell } ) \frac{mb}{m-1} \) for \(1 \le \ell \le r\), thus, inequalities (8) and (9) are satisfied and the scheme is secure.

We take \(m={\left\lceil \frac{2}{a-b} \right\rceil } \ge \max \{\frac{2b}{a-b},\frac{a}{a-b},\frac{2}{1-b}\}\), thus, we can apply Lemmas 4.4 to 4.6. We still need to find r. In order to find it, we apply Lemma 4.5 iteratively starting from \( k_{r} =m-1\) and taking \( k_{ \ell -1} =\frac{(1-a)b k_{\ell } }{a(1-b)} =\left( \frac{(1-a)b}{a(1-b)}\right) ^{r-\ell }(m-1)\) for \(2 \le \ell \le r\). By Lemma 4.5, inequality (18) is satisfied for every \(\ell \). Note that \(\frac{(1-a)b}{a(1-b)} < 1\) (as \(b <a\)), thus, \( k_{1}< k_{2}< \cdots < k_{r} \). We take \(r = {\left\lceil 2+\log _{\frac{a(1-b)}{(1-a)b}} \frac{2(1-a)b\cdot m}{a-b} \right\rceil }\). Thus, we get \( k_{1} \le \left( \frac{(1-a)b}{a(1-b)}\right) ^{\log _{\frac{a(1-b)}{(1-a)b}} \frac{2(1-a)b\cdot m}{a-b} }(m-1) =\frac{a-b}{ 2(1-a)b\cdot m} (m-1) < \frac{a-b}{ 2(1-a)b}; \) by Lemma 4.4, inequality (13) is satisfied.

If we take \(g_0=\max \{2,g_1,\dots ,g_{r}\}\) (where \(g_1,\dots ,g_{r}\) are the constants required for (13) and (18)), then the scheme is correct.

We next analyze the length of the share of \(p_i\) in \({\varPi ^2}\). Let g be the generation of \(p_i\). It suffices to consider only parties in generations \(g\ge g_0\). Recall that the generation g of \(p_i\) is the maximal g such that \((m^g-m)/(m-1) <i\); in particular, \(m^g \le (m-1)i\). Every party \(p_i\) gets O(r) shares in Shamir’s scheme with \(O(m^g)=O(mi)\) parties. The length of the share in Shamir’s scheme with n parties and a one bit secret is \(O(\log n)\). Thus, the size of the share of each party \(p_i\) is \(O(\log i)\) (since \(m\) and r are constants as \(b<a\) are constants). \(\square \)

4.2 An Optimized Scheme with Share Size

Next we show an optimization of the previous scheme such that each party’s share size is O(1). In the optimized scheme we use ramp secret-sharing schemes instead of threshold secret sharing schemes. We next describe the optimized scheme, denoted as \(\varPi ^3\), in which the share size is O(1).

figure d

Chen et al. [6] showed that there exist \((1/2+\epsilon ,1/2-\epsilon )\)-ramp secret-sharing schemes with share size O(1) for every constant \(\epsilon >0\) (see Claim 2.7). In Appendix A, we prove the following claim that shows that Chen et al.’s result implies the existence of (a, b)-ramp secret-sharing schemes with share size O(1) for every constants \(b < a\).

Claim 4.8

For every constants \(0< b< a < 1 \) there are integers \(\ell \) and \(n_0\) such that for every \(n \ge n_0\) there is an (a, b)-ramp secret-sharing scheme with n parties and share size \(\ell \).

Theorem 4.9

For every \(b < a\) there is a choice of the parameters such that \(\varPi ^3\) realizes \(\varGamma _{a,b}\) with share size O(1).

Proof

We modify the proof of \({\varPi ^2}\) to prove the security and correctness of \(\varPi ^3\). For the security of \(\varPi _{ c_{0} }^{'}\), we now have the following requirement.

$$\begin{aligned} c_{0} \ge \frac{bm}{m-1} + \epsilon . \end{aligned}$$
(22)

For security of \(\varPi _{ c_{\ell } }^{'}\) for each \(1\le \ell \le r\), we require

$$\begin{aligned} c_{\ell } \ge \dfrac{b\cdot m}{m-1} \cdot \left( 1+ k_{\ell } \right) + \epsilon . \end{aligned}$$
(23)

Thus, it holds that \({\left\lceil ( c_{\ell } - \epsilon )m^{g-1} \right\rceil } \ge ( c_{\ell } - \epsilon )m^{g-1} \ge \frac{b\cdot m}{m-1} \cdot \left( 1+ k_{\ell } \right) \cdot m^{g-1} \ge b\cdot \left( \frac{m^g}{m-1} + \frac{ k_{\ell } }{m-1}m^g \right) > b\cdot \left( \frac{m^g-m}{m-1} + \frac{ k_{\ell } }{m-1}m^g + 1\right) \), and by Lemma 2.13 (observing that the party with the maximal index which gets a share for \(\varPi _{ c_{\ell } }\) is \(\frac{m^g-m}{m-1} + {\left\lceil \frac{ k_{\ell } }{m-1}\cdot m^{g} \right\rceil }\)), the scheme is secure.

The correctness conditions remain the same. Therefore, we need to prove that inequalities (13) and (18) hold under the new security conditions. Let \(m, r, c_{0} , c_{1} ,\dots , c_{r} , k_{1} , \dots , k_{r} \) be the parameters used to construct \({\varPi ^2}\) for some a and b. We show that there exists \(\epsilon \) such that the parameters \(m, r, c'_{0} = c_{0} + \epsilon , c'_{1} = c_{1} +\epsilon , \dots , c'_{r} = c_{r} + \epsilon , k_{1} , \dots , k_{r} \) satisfy the security and correctness conditions for \(\varPi ^3\). It is easy to see that the security conditions hold, since \( c_{0} \ge b\frac{m}{m-1}\) and increasing it by \(\epsilon > 0\) will satisfy the security condition (22) for \(\varPi ^3\) (the same for the other conditions).

For the correctness, in inequality (13) the right-hand side is increased by \(\epsilon \), and the left-hand side is decreased by \(\frac{\epsilon (m+1)(1-a)}{am+1-a}\). In (13), it is required that the left-hand side is strictly greater than the right-hand side. Thus, for the constants defined in the proof of the correctness of \({\varPi ^2}\), there is a constant \(\delta _1>0\) (which is a function of a and b) such that the left side of inequality (13) equals to \( c_{0} + \delta _1\). Therefore, the left side in inequality (13) with \( c'_{0} ,\dots , c'_{r} \) equals to \( c_{0} + \delta _1 - \frac{\epsilon (m-1)(1-a)}{am+1-a}\). For the inequality to hold, we require that \( c_{0} + \delta _1 - \frac{\epsilon (m-1)(1-a)}{am+1-a} > c_{0} + \epsilon \). Taking \(\epsilon \) such that \(\epsilon + \frac{\epsilon (m-1)(1-a)}{am+1-a} < \delta _1\) will satisfy the inequality. Thus, we take \(\epsilon < \min \{ c_{0} ,\frac{\delta _1(am+1-a)}{m}\}\).

In inequality (18), the right hand side is increased by \(\frac{\epsilon }{1-a}\), and the left hand side is decreased by \(\frac{\epsilon (m-1)}{1-a}\). In (18), it is required that the left-hand side is strictly greater than the right-hand side. Thus, for the constants defined in the proof of the correctness of \({\varPi ^2}\), there is a constant \(\delta _2>0\) (which is a function of a and b) such that the left side of inequality (18) equals to \(\frac{ c_{0} }{1-a} + \delta _2\), Therefore, the left hand side in inequality (18) with \( c'_{0} ,\dots , c'_{r} \) equals to \(\frac{ c_{0} }{1-a} + \delta _2 - \frac{\epsilon (m-1)}{1-a}\). For the inequality to hold, we require that \(\frac{ c_{0} }{1-a} + \delta _2 - \frac{\epsilon (m-1)}{1-a} > \frac{ c_{0} + \epsilon }{1-a}\). Taking \(\epsilon < \frac{\delta _2(1-a)}{m}\) satisfies the inequality.

Taking \(\epsilon < \min \{ c_{0} ,\dots , c_{r} ,\frac{\delta _1(am+1-a)}{m}, \frac{\delta _2(1-a)}{m} \}\) satisfies both inequalities and guarantees that all ramp secret-sharing schemes are properly defined.

The share size each party consists of \(r=O(1)\) shares of ramp secret-sharing schemes, each is of size O(1). Therefore, the share size of each party is O(1).    \(\square \)