Communication-Efficient Proactive Secret Sharing for Dynamic Groups with Dishonest Majorities

Abstract

In Secret Sharing (SS), a dealer shares a secret s among n parties such that an adversary corrupting no more than t parties does not learn s, while any $t+1$ parties can efficiently recover s. Proactive Secret Sharing (PSS) retains confidentiality of s even when a mobile adversary corrupts all parties over the secret’s lifetime, but no more than a threshold t in each epoch (called a refresh period). Withstanding such adversaries is becoming increasingly important with the emergence of settings where private keys are secret shared and used to sign cryptocurrency transactions, among other applications. Feasibility of (single-secret) PSS for static groups with dishonest majorities was recently demonstrated, but with a protocol that requires inefficient communication of $O(n^4)$.

In this work, using new techniques, we improve over prior work in two directions: batching without incurring a linear loss in corruption threshold and communication efficiency. While each of properties we improve upon appeared independently in the context of PSS and in other previous work, handling them simultaneously (and efficiently) in a single scheme faces non-trivial challenges. SomePSS protocols can handle batching of $\ell \sim n$ secrets, but all of them are for the honest majority setting. The techniques typically used to accomplish such batching decrease the tolerated corruption threshold bound by a linear factor in $\ell$, effectively limiting the number of elements that can be batched with dishonest majority. We solve this problem by finding a way to reduce the decrease to $\sqrt{\ell }$ instead, allowing to reach the dishonest majority setting when $\ell \sim n$. Specifically, this work introduces new bivariate-polynomials-based sharing techniques allowing to batch up to $n-2$ secrets in our PSS. Next, we tackle the efficiency bottleneck and construct a PSS protocol with $O(n^3/\ell )$ communication complexity for $\ell$ secrets, i.e., an amortized communication complexity of $O(n^2)$ when the maximum batch size is used.

T. Lepoint and A. Leroux—Work performed while the author was at SRI International.

1 Introduction

Secret sharing (SS) is a fundamental cryptographic primitive used to construct secure distributed protocols and systems  [1, 9, 10, 17,18,19, 22, 26], and in particular secure multiparty computation (MPC) [2, 4,5,6, 11,12,13, 25, 27, 30, 32]. In standard SS  [7, 34], a secret s is encoded in a distributed form among n parties such that an adversary corrupting up to t parties cannot learn the secret s, while any $t+1$ parties can efficiently recover s. In some settings, SS should guarantee confidentiality of shared secrets and correctness of the computations performed on the shares (if such computation is required), even when the protocol is run for a long time  [30]. Similarly, there are settings where secret shared private keys are used sporadically over long period of time, for example to (threshold) sign cryptocurrency transactions  [8, 16, 24, 28] or in other financial applications and settings  [29]. Requiring security for long durations brings forward a new challenge, as it gives a mobile adversary the chance to eventually corrupt all parties. Ensuring security against such (mobile) adversaries has recently become of increasing importance. An SS protocol that withstands mobile adversaries is called a Proactive Secret Sharing (PSS) protocol  [26, 30].

In this work, we construct an efficient PSS protocol with the following key properties: (i) batching without incurring linear loss in the corruption threshold, (ii) tolerating dishonest majorities, and (iii) efficient communication. We achieve this with new techniques based on bivariate sharing. Below, we summarize gradually the progression from standard SS for passive adversaries to PSS for static groups with dishonest majorities. We explain why either the tolerated threshold or the performance of existing protocols fall short in simultaneously achieving the goals we strive towards. Protocols required to handle dynamic groups are left out of this version due to space constraints, the details of handling dynamic groups can be found in the full version [20].

Prior Work. A SS protocol  [7, 34] typically consists of two sub-protocols: Share and Reconstruct. Share can be used by a dealer to share a secret s among n parties such that an adversary corrupting no more than t parties does not learn s, while any $t+1$ parties can efficiently recover s via Reconstruct. Initially, SS schemes only considered (exclusively) passive or active adversaries. In the malicious setting, we say that a SS scheme is verifiable if some auxiliary information is exchanged that allows players to verify that the shares are consistent; such a SS scheme is called Verifiable Secret Sharing (VSS).

The Mixed Adversary Model and Gradual Secret Sharing. In  [27], Hirt, Maurer, and Lucas introduced the concept of mixed adversaries in SS and MPC, to capture the trade-off between passive and active corruptions. In particular, they develop an MPC protocol using gradual VSS against mixed adversaries that corrupt k parties actively out of less than $n-k$ corrupted parties total. One of the main benefits of gradual SS is to ensure fairness, i.e., if corrupted parties can deny the output of a protocol to the set of honest parties, then they cannot learn the secret themselves. The key idea is to additively share the secret s (i.e., $s = \sum _{i=1}^d s_i$) and then linearly share each of the $s_i$ to the parties under polynomial of (gradually) increasing degrees $i=1$ to $i=d$. In the Reconstruct protocol, the parties open the shares gradually, from $i=d$ to $i=1$ and incorrect parties cannot deviate without being detected.

Proactive Secret Sharing (PSS). It may be desirable to guarantee the security of standard (and gradual) SS throughout the entire lifetime of the secret. The notion of proactive security was first suggested by Ostrovsky and Yung  [30], and applied to SS later  [26]. Proactive security protects against a mobile adversary that can change the subset of corrupted parties over time. Such an adversary could eventually gain control of all parties over a long enough period, but is limited to corrupting no more than t parties during the same time period. In this work, we use the definition of PSS from  [16, 27]: in addition to Share and Reconstruct, a PSS scheme contains a Refresh and a Recover sub-protocols. Refresh produces new shares of s from an initial set of shares. An adversary who controls a subset of the parties before the refresh and the remaining subset of parties after, will not be able to reconstruct the value of s. Recover is required when one of the participant is rebooted to a clean initial state. In this case, the Recover protocol is executed by all other parties to provide shares to the rebooted party. Such rebooting should ideally be performed sequentially for randomly chosen parties (irrespective of their state of corruption) at a predetermined rate – hence the “proactive” security concept. In addition, Recover could be executed after an active corruption is detected.

Dynamic Proactive Secret Sharing (DPSS). PSS initially considered only static groups. DPSS schemes are both proactively secure and allow the set of parties to change over time  [3, 15, 33, 36, 37]. To the best of our knowledge, there are currently no DPSS schemes for dynamic groups with dishonest majorities. The authors in [3] extended the PSS introduced in [2] with ideas from [12,13,14] to produce a DPSS scheme for honest majorities only. We follow a similar approach to extend our PSS to dynamic settings (details in the full version [20]).

Table 1. Overview of features and limitations of current PSS protocols. Communication complexity is amortized over the number of secrets handled by the schemes. Note that batching is briefly mentioned in  [16], but no technical details are provided. A detailed comparison of complexity of the sub-protocols and tolerated corruption thresholds is provided in Table 2 and in the full version [20].

Limitations of Prior Work. Our goal in this work is to address limitations and gaps in, and open problems left by, prior PSS work, as shown in Table 1. First, the only PSS in the dishonest majority setting  [16, 21] assumes a static group of parties, i.e., unchanged during the secret lifetime. In this work, we present a PSS protocol with dishonest majorities. Security of our protocols is computational. Second, existing PSS protocols for the dishonest majority setting [16, 21] do not explicitly handle batching of secrets  [23], i.e., sharing, refreshing, and recovering shares of several secrets in parallel. While the authors in  [16] mention a batched version of their PSS, the paper does not provide any detail on the effect of batching on the communication complexity nor on the security impact in the mixed adversary setting. In this work, we introduce a notion of batched PSS that retains fairness against mixed adversaries. Third, previous PSS protocols [16, 21] have a large communication complexity, $O(n^4)$, and an open problem is how to reduce the communication bottleneck in the PSS (due to the Refresh and Recover sub-protocols) to $O(n^2)$ or $O(n^3)$. Moreover, the additional fairness feature of [16] is costly in terms of communication and it is not clear how this additional cost can be handled. We solve these open questions by reducing the (amortized) communication complexity to $O(n^2)$ in the batched setting, and $O(n^3)$ in the single secret setting. In theses improvements, we obtain fairness with no additional cost in asymptotic communication complexity.

Table 2. Comparison of amortized communication complexity of sub-protocols in this work and existing PSS schemes in the dishonest majority setting for $\ell$ secrets. The communication complexities stated in the column “Dynamic” are the worst-case of three sub-protocols required to handle dynamic groups (see [20]). We note that the complexity of the Recover sub-protocol is per party, and this is the bottleneck since it has to be repeated n times, once when each party is (eventually) rebooted. This explains the $O(n^4)$ overall communication complexity of [16, 21], this is not an issue in our work because our bottleneck is the Reconstruct sub-protocol not the Recover one.

Our Contributions. In this work, we develop a new communication-efficient PSS protocol for groups dishonest majorities. To achieve this, we proceed in the following steps.

(1) Batched PSS (Without Linear Loss in the Corruption Threshold). The main feature of this work is a new PSS scheme with $O(n^2)$ amortized communication complexity, improving by a quadratic factor the complexity of the best known construction for dishonest majority [16]. This improvement is mainly obtained through a bivariate polynomials based batching technique, which deviates from how secret sharing is performed in all previous PSS schemes for dishonest majorities. While bivariate polynomials have been used before for secret sharing, we devise a new approach to compute blinding bivariate polynomial (used in the recover protocol, Protocol 2) that will result in a significant improvement in the communication complexity. It is well-known that linear secret sharing with threshold t can be extended to share $\ell$ secrets $s_1, \ldots , s_\ell$ by sampling a random polynomial f of degree t such that $f(\beta _i) = s_i$ for public values $\beta _1, \ldots , \beta _\ell$ and distributing shares $f(\alpha _i)$ for $i=1, \ldots , n$ to the n parties. However, in order to learn no information about $(s_1, \ldots , s_\ell )$ an adversary must learn at most $t-\ell +1$ evaluations of f, which yields a secret sharing scheme with threshold $t-\ell +1$. To remove this linear dependency, we revisit the idea of using secret sharing with bivariate polynomials (e.g.,  [35]). Our new approach to construct PSS from bivariate polynomials preserves secrecy with a corruption threshold of $t - \sqrt{\ell }+1$ for any $\ell \le n-2$. This yields a batched PSS scheme with sublinear reduction in the corruption threshold.¹ Since gradual SS consists of a ladder of polynomial shares, the same linear dependency in the number of secrets being batched applies to the mixed adversarial model considered in  [27], which then becomes secure against mixed adversaries that corrupt k parties actively out of less than $n-k-\ell$ corrupted parties total. Similarly, we introduce the notion of batched gradual VSS, a batched generalization of gradual VSS  [27] which is secure against adversaries corrupting either $t-\lfloor \sqrt{\ell }\rfloor$ parties passively, or ${((n-\lfloor \sqrt{\ell }\rfloor )}/{2}) -1$ parties actively, or k parties actively out of $n-k-\lfloor \sqrt{\ell }\rfloor$. Gradual SS aims to obtain fairness during the reconstruction, we note that our gradual batched PSS obtains this fairness property without any additional asymptotic costs.

(2) Efficient Communication. The techniques used above were also carefully designed to limit the communication complexity. As shown in Table 2, our (fully) batched PSS with dishonest majorities has an overall complexity² of $O(n^2)$ per secret.

(3) Accommodating Dynamic Groups. Additionally, we develop sub-protocols for nodes to join the (SS) group, and leave it, without increasing the overall (asymptotic) communication complexity. Protocols required to handle dynamic groups are left out of this version due to space constraints, the details of handling dynamic groups can be found in the full version  [20].

Intuition Behind New Techniques for the Proactive Setting. We summarize here the main intuition behind the techniques that enable our performance and threshold improvements outlined in Sect. 1.

(1) Addressing the Recover Bottleneck in PSS. As mentioned above, the real bottleneck of PSS is the Recover protocol. This protocol is costly in itself and is performed regularly on each of the participants (adding a O(n) complexity factor to the overall communication complexity). The main challenge is to efficiently generate a set of blinding polynomials. We revisit the Recover protocol to overcome this limitation by optimizing the number of blinding polynomials generated. This improvement is made possible by the use of bivariate polynomials. The Recover protocol is also a necessary building block for our new Refresh protocol and the “gradual” Reconstruct protocol (see item (3) below), as it enables a subset of participants to generate random polynomials and share them with the rest of the parties.

(2) Batching with Bivariate Polynomials: Batching O(n) secrets saves O(n) in the overall communication complexity, but usually reduces the threshold by a linear factor proportional to the number of batched secrets. This severely limits the number of elements one can batch. We use bivariate polynomials to perform sharing (of a batch of secrets) instead of univariate polynomials. As mentioned above, the real bottleneck in this protocol is the generation of blinding polynomials in Recover that protects the secrets without changing their values. We develop a new technique to generate these polynomials in $O(n^2)$ with the number of blinding values being quadratic in $n-t_P$. To obtain information theoretic security for the batched secrets we need this term $(n-t_P)^2$ to be greater than $\ell$. This leads to only a sub-linear $\sqrt{\ell }$ reduction in the threshold, as opposed to linear in $\ell$. Note that our generation of blinding bivariate polynomial is optimal. Indeed, this blinding polynomial has degree d and the data size of a bivariate polynomial of this degree is $O(n^2)$ when we take $d=O(n)$ (in practice, we take $d=n-2$ for maximum security). Hence, our technique cannot yield a protocol with better communication complexity than $O(n^2)$.

(3) Gradual Property only Needed in Reconstruction. We also observe that, in previous work, the “gradual” feature of the underlying SS scheme (to withstand dishonest majorities) is critically used during the Reconstruct operation only. We will therefore work only with regular shares. To recreate a gradual SS, we develop a new (gradual technique at the core of the) Reconstruct protocol that creates directly a ladder of blinding polynomials that sum to 0, adds the shares of the first element of the ladder, and then gradually reveals everything while preserving confidentiality of the shared secrets. At the bottom layer, what is revealed is the actual shared secret because all the blinding polynomials of the ladder add up to 0. This enables us to save an additional factor (after batching) of O(n) in Reconstruct. This results in a final communication complexity of $O(n^2)$ for the Reconstruct which was the bottleneck as shown in Table 2. This also implies that we can obtain fairness during the reconstruction without increasing the total communication complexity.

Outline. The rest of this paper is organized as follows: Sect. 2 overviews some preliminaries required for the rest of the paper. Section 3 provides the definition of batched PSS, i.e., multi-secret PSS with dishonest majorities. Section 4 presents a concrete efficient instantiation of a batched (static) PSS using bivariate polynomials. Technical details, i.e., sub-protocols and their proofs, required to extend the above PSS scheme to deal with dynamic groups are provided in the full version  [20].

2 Preliminaries

Throughout this paper, we consider a set of n parties $\mathcal {P}= \{P_1, ..., P_n\}$, connected by pairwise synchronous secure (authenticated) channels and an authenticated broadcast channel. $\mathcal {P}$ want to share and proactively maintain a confidential secret s over a finite field $\mathbb {F} = \mathbb {Z}_q$ for a prime q.

For integers a, b, we denote $[a,b]= \{k : a\le k\le b\}$ and $[b]=[1,b]$.³ We denote by $\mathbb {P}_k$ the set of polynomials of degree k exactly over $\mathbb {F}$. When a variable v is drawn randomly from a set S, we denote $v\leftarrow S$.

2.1 Mixed Adversaries

We first recall the model of mixed adversaries from  [27]; we consider a central adversary $\mathcal {A}$ with polynomially bounded computation power who corrupts some parties passively (i.e., $\mathcal {A}$ learns the view of a $P_i$) and actively (i.e., $\mathcal {A}$ makes a $P_i$ behave arbitrarily) during a stage $\sigma$. We denote by $\mathcal {P}_P$ (resp. $\mathcal {P}_A\subseteq \mathcal {P}_P$) the set of passively (resp. actively) corrupted parties and denote by $t_P$ (resp. $t_A$) its cardinality. A multi-threshold is a set of pairs of thresholds $(t_1,t_2)$. We say that $(t_P,t_A) \le T$ for a multi-threshold T if there exists $(t_1,t_2) \in T$ such that $t_P \le t_1$ and $t_A \le t_2$. For two multi-thresholds $T_a,T_b$ we say that $T_a \le T_b$ if for all $(t_{a1},t_{a2}) \in T_a$, it holds that $(t_{a1},t_{a2}) \le T_b$.

2.2 Security Properties

Throughout the paper, we study four security properties: correctness, secrecy, robustness, and fairness. We denote the corresponding multi-thresholds $T_c$, $T_s$, $T_r$, and $T_f$. Each property is considered guaranteed if $(t_P, t_A)$ is smaller than the corresponding multi-threshold. These properties are standard analytic tools for protocols security. For a protocol $\varPi$:

• Correctness: Given the inputs from $P_1,..,P_n$, each party engaged in $\varPi$ either obtains the correct output or obtains a special output $\perp$.

• Secrecy: The adversary cannot learn more information about other parties’ inputs and outputs than can be learned from its own inputs and outputs.

• Robustness: The adversary cannot deny their output to the honest parties.

• Fairness: Either every party obtains its output or nobody does.

We have $T_r \le T_c$ and $T_f \le T_s \le T_c$ since we cannot define secrecy, fairness or robustness without correctness and secrecy is required by fairness. Note that all the protocols in this work are not robust when there are more than a few (generally 1 or 2) active corruptions. Thus, we do not study robustness of the developed protocols as they do not provide it in most cases. As such, unless explicitly specified, the robustness threshold is $T_r = \lbrace (n,1) \rbrace$.

2.3 Definitions for Verifiable, Proactive, and Dynamic PSS

Verifiable Secret Sharing (VSS). A VSS scheme enables an (untrusted) dealer to securely share a secret s among the parties in $\mathcal {P}$, such that a set of honest parties can reconstruct s if they reveal their shares to each other.

Definition 1

(Verifiable Secret Sharing [27]). A $(T_s, T_r)$-secure Verifiable Secret Sharing (VSS) scheme is a pair of protocols $\texttt {Share}$ and $\texttt {Reconstruct}$, where $\texttt {Share}$ takes inputs s from the dealer and $\texttt {Reconstruct}$ outputs s to each party, if the following conditions are fulfilled:

• Secrecy: if $(t_P, t_A)\le T_s$, then in $\texttt {Share}$ the adversary learns no information about s;

• Correctness: After $\texttt {Share}$, the dealer is bound to the values $s'$, where $s'= s$ if the dealer is honest. In $\texttt {Reconstruct}$, either each honest party outputs $s'$ or all honest parties abort.

• Robustness: the adversary cannot abort $\texttt {Share}$, and cannot abort $\texttt {Reconstruct}$ if $(t_P, t_A)\le T_r$.

Proactive Secret Sharing (PSS). A PSS scheme is a VSS scheme secure against a mobile adversary, i.e., realizes proactive security. We recall the definition of PSS from  [16]. In particular, a PSS scheme is a VSS scheme extended with two additional sub-protocols: $\texttt {Refresh}$ and $\texttt {Recover}$. An execution of PSS will be divided into phases. A refresh phase (resp. recovery phase) is the period of time between two consecutive executions of $\texttt {Refresh}$ (resp. $\texttt {Recover}$). Furthermore, the period of time between $\texttt {Share}$ and the first $\texttt {Refresh}$ (resp. $\texttt {Recover}$) is a refresh phase (resp. recovery phase), and similarly for the period of time between the last $\texttt {Refresh}$ (resp. $\texttt {Recover}$) and $\texttt {Reconstruct}$.

Definition 2

(Proactive Secret Sharing [16]). A Proactive Secret Sharing (PSS) scheme consists of four protocols $\texttt {Share}$, $\texttt {Reconstruct}$, $\texttt {Refresh}$, and $\texttt {Recover}$. $\texttt {Share}$ takes inputs s from the dealer and $\texttt {Reconstruct}$ outputs $s'$ to each party. $\texttt {Refresh}$ is executed between two consecutive phases $\sigma$ and $\sigma +1$ and generates new shares for phase $\sigma +1$ that encode the same secrets as the shares for phase $\sigma$. $\texttt {Recover}$ allows parties that lost their shares to obtain new shares encoding s with the help of the other honest parties. A $(T_s, T_r, T_c)$-secure PSS scheme fulfills the following conditions:

• Termination: all honest parties complete each execution of $\texttt {Share}$, $\texttt {Refresh}$, $\texttt {Recover}$, and $\texttt {Reconstruct}$.

• Secrecy: if $(t_P, t_A)\le T_s$, then in $\texttt {Share}$ the adversary learns no information about s. If $(t_P, t_A)\le T_s$ in both phases $\sigma$ and $\sigma +1$, and if $\texttt {Refresh}$ and $\texttt {Recover}$ are run between phases $\sigma$ and $\sigma +1$, then the adversary learns no information about s.

• Correctness: After $\texttt {Share}$, the dealer is bound to the values $s'$, where $s'= s$ if the dealer is honest. If $(t_P, t_A)\le T_c$, upon completing $\texttt {Refresh}$ or $\texttt {Recover}$, either the shares held by the parties encodes s or all honest parties abort. In $\texttt {Reconstruct}$ either each honest party outputs $s'$ or all honest parties abort.

• Robustness: the adversary cannot abort $\texttt {Share}$, and cannot abort $\texttt {Refresh}$, $\texttt {Recover}$, and $\texttt {Reconstruct}$ if $(t_P, t_A)\le T_r$.

Dynamic Proactive Secret Sharing (DPSS). A DPSS scheme is a PSS scheme extended by a Redistribute protocol that enables (secure distributed) transfer of the secret s from one group of participants to another. Our DPSS definition is inspired by a previous one in [3]. The only difference is that we do not combine Refresh, Recover and Redistribute into one phase. We define a redistribute phase analogously to the refresh and recover phases. The refresh phases are denoted by $\sigma$, the redistribute phases by $\omega$, $n^{(\omega )}$ is the number of participants at phase $\omega$. The multi-thresholds $T_r,T_c,T_s$ are considered as functions of n (the number of participants). We denote $T_r^{(\omega )},T_c^{(\omega )},T_s^{(\omega )}$ the thresholds at phase $\omega$ computed from $n^{(\omega )}$.

Definition 3

(Dynamic Proactive Secret Sharing). A Dynamic Proactive Secret Sharing (DPSS) scheme consists of a PSS constituted of four protocols $\texttt {Share}$, $\texttt {Reconstruct}$, $\texttt {Refresh}$, $\texttt {Recover}$ according to Definition 2 completed by a Redistribute protocol. Redistribute is executed between consecutive redistribute phases $\omega$ and $\omega +1$ and allows a set of $n^{(\omega )}$ participants at phase $\omega$ to transfer its shares to the set of $n^{(\omega +1)}$ participants of phase $\omega +1$. In the following, when we denote $(t_P, t_A)\le T_s^{(\omega )}$, it is implicit that this is true during redistribute phase $\omega$. A $(T_s, T_r, T_c)$-secure DPSS scheme fulfills the following conditions:

• For any phase $\omega$, Share, Reconstruct, Refresh and Recover is a $T_s^{(\omega )},T_r^{(\omega )},T_c^{(\omega )}$)-secure PSS under Definition 2.

• Termination: all honest parties complete each execution Redistribute.

• Secrecy: if $(t_P, t_A)\le T_s^{(\omega )}$ and $(t_P, t_A)\le T_s^{(\omega +1)}$, the adversary learns no information about s during the execution of $\texttt {Redistribute}$ between phases $\omega$ and $\omega +1$.

• Correctness: After $\texttt {Share}$, the dealer is bound to the values $s'$, where $s'= s$ if the dealer is honest. If $(t_P, t_A)\le T_c^{(\omega )}$, upon completing Redistribute, either the shares held by the parties encodes s or all honest parties abort.

• Robustness: the adversary cannot abort Redistribute if $(t_P, t_A)\le T_r^{(\omega )}$.

2.4 Homomorphic Commitments and VSS

To obtain security against malicious adversaries, we use a homomorphic commitment scheme, e.g., Pedersen commitments  [32]. We assume that all values (secrets, polynomial coefficients, commitments) are in $\mathbb {Z}_q$ for a prime q and that a cyclic group $\mathbb {G}$ of order q with two random generators g, h is distributed to the parties. Commitment to a secret s is $C(s,r) = g^s\cdot h^r$ for a random value r. Due to the use of Pedersen commitment scheme, our protocols are computationally secure under the Discrete Logarithm Problem (DLP) hardness assumption.

2.5 Bivariate Polynomials

We rely on bivariate polynomials as a building block in our design of a batched SS scheme for groups with dishonest majorities. We use polynomials of degree d in both x and y variables. Such a polynomial g is uniquely defined by $(d+1)^2$ points g(x, y) with $(x,y) \in X\times Y$ and $|X|=|Y|=d+1$. Indeed, for any $(x_0,y_0)$, the value $g(x_0,y_0)$ can be found by the interpolation of $g(x,y_0)$ for all $x \in X$. The values $g(x,y_0)$ can be interpolated with g(x, y) for all $y \in Y$. In the following, when we say that g is a bivariate polynomial of degree d, it means that g is of degree d in both its variables.

3 Batched PSS for a Static Group with a Dishonest Majority

In this section, we introduce the definition of (Dynamic) Batched Proactive Secret Sharing (BPSS). In order to understand why the batched setting requires new definitions, we first explain the issue arising when using batching in PSS against mixed adversaries in Sect. 3.1. Then, we introduce the definition of a $\ell$-Batch $\ell '$-Gradual Secret Sharing in Sect. 3.2.

3.1 The Issue with the Number of Shared Secrets

Recall the naive version of Shamir’s (t, n)-secret sharing  [34] for $t<n$: a secret $s\in \mathbb {F}$ is stored in the constant coefficient of a polynomial $f\in \mathbb {P}_t$. Each party $P_r$ for $r\in [n]$ will receive $f(\alpha _r)$ where the $\alpha _j$’s are (public) distinct nonzero elements and reconstruction is performed by interpolating of the value in 0 using $t+1$ evaluations of f.

The extension the above secret sharing scheme to handle batching is a well-known construction  [23]: to share $\ell$ secrets $s_1, \ldots , s_\ell$, sample a polynomial $f\in \mathbb {P}_{t+\ell -1}$ such that $f(i) = s_i$ and set $\alpha _r\notin [\ell ]$. However, now one must ensure that $t+\ell -1<n$ so that $(s_1, \ldots , s_\ell )$ remains information-theoretically hidden given up to t evaluations of f in the $\alpha _r$’s; i.e., there is a linear dependency between the number of shared batched secrets and the bound on the tolerated corruption threshold (with respect to n).

Now, let us recall the core idea from  [27] to design a fair secret sharing scheme against mixed adversaries. We consider Shamir’s secret sharing extended with homomorphic commitments in order to provide verifiability  [31]. Now, during the reconstruction step, all correct parties broadcast their shares, and secrecy is given up against all subsets at one. Therefore, the reconstruction protocol does not achieve fairness (that is, every party obtains its output or nobody does). In order to achieve fairness and handle mixed adversaries, Hirt et al.  [27] propose to first split the secret into additive summands, i.e., $s = s^{(1)} + \cdots + s^{(d)}$, with $d=n-1$ and then use Shamir’s (i, n)-secret sharing on $s^{(i)}=f_i(0)$ for all $i\in [d]$. Next, $P_r$ for $r\in [n]$ receives as share the tuple $(f_1(\alpha _r), \ldots , f_{d}(\alpha _r))$. Reconstruction then recovers each of the $s^{(i)}$ for i from $d=n-1$ to 1 sequentially. If there is a violation of fairness at any step, i.e., an $s^{(i)}$ cannot be reconstructed, the protocol aborts. A mixed adversary cannot abort before the degree $i_0=t_P$ (for $i < t_P$ the adversary already knows all the values $f_i(0)$). In this case, to preserve fairness the honest parties need to be able to recover all the remaining values $f_i(0)$. Thus we have $i_0+1 \le n-t_A$. By putting the two constraints together we obtain the bound $(t_P, t_A) \le (n-k-1, k)$. Additionally, since $t_A \le t_P$, we get $k \le \lceil \frac{n}{2} \rceil -1$.

Now, assume we want to design a batched secret sharing scheme against mixed adversaries. Combining the above arguments prevents a mixed adversary from aborting before the degree $i_0=t_P+\ell -1$ and therefore we obtain the bound $(t_P, t_A) \le (n-k-\ell , k)$. In particular, this implies that as soon as one batches $\ell \ge n/2$ secrets, achieving security with a dishonest majority is not attainable.

To overcome this issue, we introduce a notion of $\ell$-Batch $\ell '$-Gradual Secret Sharing against mixed adversaries with bound $(t_P, t_A) \le (n-k-\ell ', k)$ in Sect. 3.2; and then similarly to  [16], it is easy to extend the latter primitive to define a Batched PSS against mixed adversaries. In Sect. 4, we will instantiate such a primitive for $\ell \le n-2$ and $\ell '=\lfloor \sqrt{\ell }\rfloor$ by revisiting the idea of secret sharing using bivariate polynomials (e.g.,  [35]).

3.2 Batched Gradual Secret Sharing Against Mixed Adversaries

Definition 4

(Gradual VSS [27]). A $(T_s,T_r,T_c)$-secure VSS scheme is gradual if the following conditions are fulfilled: If Reconstruct aborts, each party outputs a non-empty set $B \subset \mathcal {P}_A$ and the adversary cannot obtain information about the secret s if $(t_P,t_A) \le T_s$ and $t_P \le n- |B| -1$.

Note that this definition is equivalent to fairness when the adversary is bounded by a multi-threshold $T_f = \lbrace (n-k-1,k) :k\in [0, \lceil \frac{n}{2}\rceil -1] \text { and } (n-k-1,k) \le T_s \rbrace$.

Batched Gradual VSS. We naturally extend Definitions 1 and 4 to batch $\ell$ secrets. A Batch VSS scheme enables a dealer to share $\ell$ secrets $s_1, \ldots , s_\ell$ among the parties in $\mathcal {P}$, such that the parties can reconstruct the secrets.

Definition 5

($\ell$-Batch VSS). A $(T_s, T_r)$-secure $\ell$-Batch VSS scheme is a pair of protocols $\texttt {Share}$ and $\texttt {Reconstruct}$, where $\texttt {Share}$ takes inputs $s_1, \ldots , s_\ell$ from the dealer and $\texttt {Reconstruct}$ outputs $s'_1, \ldots , s'_\ell$ to each party, if the following conditions are fulfilled:

• Secrecy: if $(t_P, t_A)\le T_s$, then in $\texttt {Share}$ the adversary learns no information about $s_1, \ldots , s_\ell$;

• Correctness: After $\texttt {Share}$, the dealer is bound to the values $s'_1, \ldots , s'_\ell$, where $s'_i= s_i$ if the dealer is honest. In $\texttt {Reconstruct}$, either each honest party outputs $s'_1, \ldots , s'_\ell$ or all honest parties abort.

• Robustness: the adversary cannot abort $\texttt {Share}$, and cannot abort $\texttt {Reconstruct}$ if $(t_P, t_A)\le T_r$.

Definition 6

($\ell$-Batch $\ell '$-Gradual VSS). A $(T_s,T_r,T_c)$-secure $\ell$-Batch VSS is $\ell '$-gradual if the following conditions are fulfilled: If Reconstruct aborts, each party outputs a non-empty set $B \subset \mathcal {P}_A$ and the adversary cannot obtain information about the secret s if $(t_P,t_A) \le T_s$ and $t_P \le n- |B|-\ell '$.

This definition is equivalent to fairness when the adversary is bounded by a multi-threshold $T_f = \lbrace (n-k-\ell ',k) : k\in [0, \lceil \frac{n-\ell '}{2}\rceil -1] \text { and } (n-k-\ell ',k) \le T_s \rbrace$.

4 Efficient Batched PSS Using Bivariate Polynomials

We defer the definitions of the ideal functionalities for $\texttt {Share}$, $\texttt {Reconstruct}$, $\texttt {Refresh}$, and $\texttt {Recover}$, and their formal simulator-based security proofs, to the full version  [20]. In this section, we introduce the protocols and prove in preliminary lemmas the core elements of their security proofs.

In the protocols below, we highlight the , as the full protocols include (standard) use of commitments and openings to resist against malicious/mixed adversaries.

4.1 The Share Protocol

We assume that $\alpha _1, \ldots , \alpha _n, \beta _1, \ldots , \beta _\ell \in \mathbb {F}$ are distinct public values. The number $\ell$ is assumed to be smaller than d, the degree of the bivariate polynomial produced by the sharing. With $d=n-2$ in practice, we have the bound $\ell \le n-2$ that we mentioned above.

Lemma 1

Let $d\le n-1$. Share is correct and preserves the secrecy of a batch of secrets $s_1, \ldots , s_\ell$ if $(t_P,t_A) \le \big \lbrace (d,d) \big \rbrace$.

Proof

Correctness follows from the use of homomorphic commitments which allow the parties to verify that the dealer distributed shares for a bivariate polynomial g of degree d in both variables.

For secrecy, we show that the adversary cannot find the values $s_1, \ldots , s_\ell$ when $t_P\le d$. Without loss of generality, we assume that the adversary controls passively $\lbrace P_1, \ldots , P_{t_P} \rbrace$ and that the dealer is honest. Hence, the adversary knows the values $\{g(\alpha _r,\alpha _{r'})\}_{r'\in [d+1]}$ for $r \in [t_P]$. It can interpolate $g(\alpha _r,\beta _j) =f_j(\alpha _r)$ for all $r \in [t_P]$ and $j \in [\ell ]$. For every j, since $t_P \le d$, $f_j(\beta _j) = s_j$ is information-theoretically hidden.   $\square$

Remark 1 (Communication)

In Step 4, the dealer broadcasts $(d+1)^2$ commitments, and in Step 5, $(d+1)\cdot n$ messages are sent. With $d=O(n)$, we obtain an amortized communication complexity of $O(n^2)/\ell$.

Remark 2 (Corruption Threshold)

Lemma 1 claims security for up to d corruption when we mentioned several time already that our protocol is secure up to $d+1- \sqrt{\ell }$. This is because the Share protocol in itself tolerates more corruptions. The threshold $d+1- \sqrt{\ell }$ is a consequence of the Recover protocol, as is explained below.

4.2 The Recover Protocol

The Recover protocol enables a set of $d+1$ parties $\lbrace P_1, \ldots , P_{d+1}\rbrace$ to send to a recovering party $P_{r_C}$ its shares $(g\{\alpha _{r_C},\alpha _{r'})\}_{r' \in [d+1]}$. In [16], to perform the recovery of one value $f(\alpha _{r_C})$, each participant $P_r$ generates one blinding polynomial $f_r$ verifying $f(\alpha _{r_C})=0$ and share it among the other participants so that $P_{r_C}$ can receive $f(\alpha _r) + \sum _{u=1}^n f_u(\alpha _r)$ for $r \in [n]$ and interpolate $f(\alpha _{r_C})$. This is inefficient as each value $f(\alpha _r)$ requires O(n) communication to be blinded. In our secret sharing, each participant $P_r$ have a polynomial $g(\alpha _r, \cdot )$. Just like in [16], our Recover protocol requires each $P_r$ to generate one polynomial $f_r$ verifying $f_r(\alpha _{r_C})=0$ and share it to the other. The number of blinding polynomials remains the same, but the size of the sharing has been multiplied by a factor O(n), it yields an optimal O(1) communication complexity per value. Yet, it will be enough to blind the batch of $\ell$ secrets when the corruption threshold is decreased to $d+1- \sqrt{\ell }$. Indeed, $P_{r_C}$ is going tor receive the values $g(\alpha _r,\alpha _{r'}) + f_{r'}(\alpha _r)$ from each of the $P_r$ for $r' \in [d+1]$. When $P_{r'}$ and $P_{r_C}$ are corrupted, the adversary will be able to learn the values $g(\alpha _r,\alpha _{r'})$ for $r \in [d+1]$ that were unknown to the adversary prior to Recover. However, when both $P_r$ and $P_{r'}$ are honest, the value $g(\alpha _r,\alpha _{r'})$ is blinded by $f_{r'}(\alpha _r)$. Therefor, the security of the $\ell$ secrets is going to be protected by the $(d+1-t_P)^2$ values corresponding to pairs $(P_r,P_{r'})$ of honest participants in $\mathcal {P}^2$. That yields the bound $t_P \le d+1 - \sqrt{\ell }$. The formal security analysis of Recover is provided in the full version  [20].

Overall, our Recover protocol consists of the following steps:

• (a) First, the set of parties jointly generate random univariate polynomials $f_1, \ldots , f_{d+1}$ of degree d that evaluates to 0 in $\alpha _{r_C}$.

• (b) Then, every party uses its shares of $f_{r'}$’s to randomize its shares $g(\alpha _r,\alpha _{r'})$ so that $P_{r_c}$ can interpolate $g(\alpha _{r_C},\alpha _{r'})$ for $r'\in [d+1]$.

Remark 3 (Communication)

In Step 1, $(d+1)^2$ commitments are broadcast. In Step 2, $(d+2)(d+1)$ openings are sent. In Step 5, $(d+1)^2$ openings are sent. With $d=O(n)$, we obtain an amortized communication complexity of $O(n^2)/\ell$.

4.3 The Reconstruct Protocol

Recall that gradual verifiable secret sharing was introduced in  [27] to capture the notion of a mixed adversary by gradually reducing the number of corrupted parties against which secrecy is guaranteed during reconstruction, and at the same time increasing the number of corrupted parties against which robustness is guaranteed. In particular, in  [27] a secret s is split into summands $s= s_1+\cdots +s_d$ and each $s_i$ is secret shared using a polynomial of degree i. During reconstruction, the protocol aborts at step $n-k$ only if strictly less than $n-k+1$ parties opened their commitments correctly and therefore the number of active parties is lower bounded by k. Now, if the total number of corruptions is less than $n-k$, then the adversary learns nothing, which retains secrecy against adversaries controlling k parties actively out of $n-k$ compromised parties.

Now, let’s assume we instead have a sharing of $0=e_1+\cdots +e_d$ (as polynomials), where $e_1, \ldots , e_{d-1}$ are bivariate polynomials of degrees $1, \ldots , d-1$ respectively. Then the above protocol can be reproduced with $s_i=e_i(\beta )$ for $i<d$ and $s_d= s+e_d(\beta )$; this is the core idea in the protocol below. The core novelty of the protocol is in how to construct this ladder. We will show that by using (i) some fixed public values $\lambda _1, \ldots , \lambda _d$ such that $\sum _{i=1}^d \lambda _i=0$ and (ii) the Recover above to share freshly generated polynomials, gradually constructing such a ladder is possible. The key idea is the following: at each step from $i=d$ to $i=2$, the current bivariate polynomial of degree i is blinded by a random bivariate polynomial of degree $i-1$ generated by a subset of size i of the parties and recovered with a $i+1$-th party using Recover. All the blinding polynomials $e_i$ will be constructed so that $e_1+\cdots +e_d = \Big (\sum _{k=1}^d\lambda _k\Big ) \cdot Q$, at the end of the protocol for Q a random bivariate polynomial, so that $\sum _{k=1}^d\lambda _k = 0$ can eventually be factored out. Note that it does not harm the security to take public $\lambda _i$ values. Indeed, the security requires that each of the $s_i$ appears uniformly random (up to $s_1$ that depends on s and the previous $s_i$). The way that each $g_i$ is constructed from the $Q_i$ polynomials that are random polynomials ensures this property.

The Reconstruct protocol is described in Protocol 3, and its correctness and security proofs can be found in the full version  [20].

Remark 4

We reiterate that we have the invariant $\sum _{k=i}^d g_k = g+\left( \sum _{k=i}^d \lambda _k\right) \cdot Q_{i-1}$, for all $i\ge 2$, that comes from the fact that $\sum _{k=1}^d\lambda _k=0$. In particular since $Q_0=0$, it holds that $\sum _{k=1}^d g_k = g$. Hence, Step 3 (b) and Step 4 yield $s_j = \sum _{i=1}^d g_i(\beta _j,\beta _j) = g(\beta _j, \beta _j)$.

Remark 5 (Communication)

Note that the $\texttt {Recover}$ in Steps 2(b) and 3(e) are ran a maximum of $d+t_A = O(n)$ times total, which yields a communication complexity of $O(n^3/\ell )$. Ignoring the $\texttt {Recover}$, Step 2 requires $O(n^2)$ communication (broadcast of commitments for the new polynomials and new shares). Then, each iteration of the loop is performed in $O(i^2) =O(n^2)$ with $(i+1)^2$ openings in 3(a), $(i-1)^2$ commitments in 3(d) and $i^2$ commitments in 3(f). Overall, the communication complexity of Reconstruct is $O(n^3/\ell )$ for $\ell$ secrets.

Theorem 1

The pair of protocols (Share, Reconstruct) constitutes a $(T_s,T_c)$-secure (under the DLP assumption) $\ell$-Batch $\sqrt{\ell }$-Gradual VSS, as in Definition 6, for $T_s =\lbrace (n-1 - \lfloor \sqrt{\ell } \rfloor ,n-1 - \lfloor \sqrt{\ell } \rfloor )\}$ and $T_c=\lbrace (n,n-1) \rbrace$.

The proof of Theorem 1 is in the full version of this paper  [20].

4.4 The Refresh Protocol

Similarly to Reconstruct, the Refresh protocol uses a blinding polynomial Q to guarantee privacy of the secrets. This blinding polynomial Q needs to verify $Q(\beta _j,\beta _j)=0$ for $j \in [\ell ]$. The easiest way to achieve this property is to take $Q(x,y) = (x-y)R(x,y)$ where R is a random bivariate polynomial of degree $d-1$. However, this polynomial Q is equal to zero on the entire diagonal (x, x). To obtain the level of secrecy required for Refresh we also need to refresh the shares g(x, x) for any $x \not \in \lbrace \beta _1, \ldots , \beta _\ell \rbrace$.To solve this issue, inspired by the univariate blinding factor in Recover, we blind the other diagonal values by a univariate polynomial that evaluates to 0 in the $\beta _j$. More precisely, at the end of the protocol, we constructed $g'$ as $g'(x,y) = g(x,y)+ Q(x,y) = g(x,y) + (x-y)\cdot R(x,y) + h(x)\cdot \prod _{j\in \ell }(y-\beta _j)$ where h is a random univariate polynomial in $\mathbb {P}_d$ and R is a random bivariate polynomial.

Concretely, the Recover protocol is used to build and share the blinding polynomial in the following manner:

• (a) First, a set of d participants generates R a random bivariate polynomial of degree $d-1$ and uses Recover to share it with the remaining participants.

• (b) Then, every party generates a random univariate polynomial $h_r$ and share it among each other, so that every participant $P_r$ can compute its value $h(\alpha _r) = \sum _{u=1}^n h_u(\alpha _r)$

• (c) Finally, all parties compute $g'(\alpha _r,\alpha _{r'})=g(\alpha _r,\alpha _{r'}) + (\alpha _r - \alpha _{r'}) \cdot R(\alpha _{r}, \alpha _{r'}) + h(\alpha _r)\cdot \prod _{j\in \ell }(\alpha _{r'}-\beta _j)$ from their blinded shares.

Refresh is described in Protocol 4 and its correctness and security proofs can be found in the full version  [20].

Remark 6 (Communication)

The bottleneck of the communication is during Step 2 when $(n-d)$ Recover are performed. In the case of maximum security (when $n-d-1=O(1)$), the communication complexity is $O(n^2)/\ell$ for $\ell$ secrets.

Theorem 2

The four protocols Share, Reconstruct, Refresh, Recover constitute a $T_s,T_c$-secure (under the DLP assumption) $\ell$-Batch PSS with multi-threshold $T_c= \lbrace (n,n-1) \rbrace$ and $T_s = \lbrace (n-1 - \lfloor \sqrt{\ell } \rfloor ,n-1 - \lfloor \sqrt{\ell } \rfloor ) \rbrace$ and $\ell = n-2$.

The proof of Theorem 2 is in the full version of this paper  [20].