Stronger Leakage-Resilient and Non-Malleable Secret Sharing Schemes for General Access Structures

Abstract

In this work we present a collection of compilers that take secret sharing schemes for an arbitrary access structure as input and produce either leakage-resilient or non-malleable secret sharing schemes for the same access structure. A leakage-resilient secret sharing scheme hides the secret from an adversary, who has access to an unqualified set of shares, even if the adversary additionally obtains some size-bounded leakage from all other secret shares. A non-malleable secret sharing scheme guarantees that a secret that is reconstructed from a set of tampered shares is either equal to the original secret or completely unrelated. To the best of our knowledge we present the first generic compiler for leakage-resilient secret sharing for general access structures. In the case of non-malleable secret sharing, we strengthen previous definitions, provide separations between them, and construct a non-malleable secret sharing scheme for general access structures that fulfills the strongest definition with respect to independent share tampering functions. More precisely, our scheme is secure against concurrent tampering: The adversary is allowed to (non-adaptively) tamper the shares multiple times, and in each tampering attempt can freely choose the qualified set of shares to be used by the reconstruction algorithm to reconstruct the tampered secret. This is a strong analogue of the multiple-tampering setting for split-state non-malleable codes and extractors.

We show how to use leakage-resilient and non-malleable secret sharing schemes to construct leakage-resilient and non-malleable threshold signatures. Classical threshold signatures allow to distribute the secret key of a signature scheme among a set of parties, such that certain qualified subsets can sign messages. We construct threshold signature schemes that remain secure even if an adversary leaks from or tampers with all secret shares.

1 Introduction

In a secret sharing scheme, a dealer who holds a secret s chosen from a domain $\mathcal {M}$ can compute a set of shares by evaluating a randomized function on s which we write as $\mathbf {Share}(s) = (s_1, \ldots ,s_n)$.

A secret sharing comes with an access structure $\mathcal {A}$, which is a family of subsets of the indices $1, \ldots ,n$, such that if one is given a subset of the shares of s corresponding to a set $A\in \mathcal {A}$ (a qualified set), then one can compute s efficiently, whereas any subset of shares corresponding to a set not in $\mathcal {A}$ (an unqualified set) contains no, or almost no information about the secret. An important special case is threshold secret sharing, where the access structure contains all set of size at least some threshold value.

Secret-sharing is one of the most basic and oldest primitives in cryptography, introduced by Blakley and Shamir in the late seventies [6, 22]. It allows to strike a meaningful balance between availability and confidentiality of secret information. Namely, we can store the n shares in n different servers and ensure that (i) as long as a qualified set of servers is alive, the secret is available, and (ii) even if an unqualified set of shares is stolen, the secret remains confidential.

After its introduction, several variants of secret sharing have been suggested that address the problem of authenticity of the secret: we want to guarantee that we reconstruct the original value, even if not all players are honest. One such variant is robust secret sharing, where the dealer is honest but some unqualified set of share holders are malicious and may return incorrect shares. It is required that the secret is still correctly reconstructed from the set of all shares in such a case. In verifiable secret sharing, the dealer may be dishonest as well, but via interaction in the sharing phase we can enforce that a unique secret is still determined and that this is the value that will be reconstructed later.

In all these older settings, the adversary is of the classic type that completely corrupts a certain subset of the players in the protocol, either to steal information or to corrupt data, whereas the players who are not corrupted are “completely honest”. In many scenarios, however, this may not be the most realistic model of attacks. Instead, it may make more sense to assume that the adversary will try to attack all share holders, and will have some partial success in all or most of the cases.

For the case of attacks against confidentiality, we can model this as leakage resilient secret sharing, where the adversary is allowed to specify a leakage function $\mathsf {Leak}$ and will be told the value $\mathsf {Leak}(s_1,...,s_n)$. Then, under certain restrictions on $\mathsf {Leak}$, we want that the adversary learns essentially nothing about s. Typically, so called local leakage is considered, where $\mathsf {Leak}(s_1,...,s_n) = (\mathsf {Leak}_1(s_1),...,\mathsf {Leak}_n(s_n))$ for local leakage functions $\mathsf {Leak}_i$ with bounded output size. This makes sense in a scenario where shares are stored in physically separated locations. It is known that some secret sharing schemes are naturally leakage-resilient against local leakage whereas others are not [5]. Boyle et al. [8] showed how to construct (locally) leakage-resilient verifiable secret sharing for threshold access structures. Goyal and Kumar [16] construct a specific type of leakage-resilient 2-out-of-n secret sharing as part of non-malleable secret sharing construction. To the best of our knowledge, it is not known how to construct leakage-resilient schemes from regular secret sharing schemes in general.

The case of attacks that try to corrupt the secret has been considered only recently, and for this purpose the notion of non-malleable secret sharing was introduced by Goyal and Kumar [16]. In this model, the adversary specifies a tampering function f which acts on the shares, and then the reconstruction algorithm is applied to a qualified subset of $f(s_1,...,s_n)$. The demand, simplistically speaking, is that either the original secret is reconstructed or it is destroyed, i.e., the reconstruction result is unrelated to the original secret. Note that since f is allowed to touch all shares, we cannot avoid the case where an unrelated secret is reconstructed, as f could always replace all shares by shares of a different secret. In line with all previous works, we consider local tampering functions, which individually tamper with each share. This is a sensible assumption if, for example, each share is stored in a different server. Of course, such a tampering is closely related to the earlier notion of non-malleable codes against split-state tampering [14]. The main difference between non-malleable codes and secret sharing schemes is that, in addition to non-malleability, we also insist that the correctness and privacy properties of the secret sharing scheme are satisfied. Interestingly, some non-malleable codes can also be seen as primitive versions of general non-malleable secret sharing schemes. In fact, non-malleable codes in the 2-split-state model (where each codeword is split into two halfs which are tampered independently) are 2-out-of-2 non-malleable secret sharing schemes [2].

The first non-malleable secret sharing schemes were constructed in [16] for threshold access structures, and, in a follow-up work [17], for general access structures, where an adversary is allowed to independently tamper with each share in a minimal reconstruction set. In the latter work, a general compiler was given that builds a non-malleable secret sharing scheme from a regular secret sharing scheme.

An application of non-malleable secret sharing to secure message transmission was given in [16], but another very natural application, which does not seem to have been considered before, is to threshold cryptography. Let us consider, for instance, a threshold signature scheme. In such an application, the secret key is secret-shared among n servers, who then collaborate to generate a signature such that the signature itself is the only new information released.

Some threshold signature schemes have “built-in” protection against tampering. Namely, they establish a public commitment to each share of the secret key, and when a server contributes to a new signature, it must prove in zero-knowledge that it is behaving consistently with the commitment. If the commitment cannot be tampered, this will imply that tampered shares cannot contribute to a signature. However, in many protocols for signature generation, one can avoid zero-knowledge proofs by optimistically generating a signature assuming that all players behave correctly. The observation is that one can always verify the signature in the end and take some alternative action if it fails. This will be very efficient if players behave honestly almost always. Such a protocol is not secure if executed on tampered shares, and adding zero-knowledge proofs does not make sense in this case.

It therefore seems natural to try to use a non-malleable secret sharing scheme instead. This of course raises the question of how we can generate signatures efficiently and securely – existing threshold signatures assume regular secret sharing, and it is not clear how we can use existing non-malleable schemes without resorting to generic multiparty computation.

However, suppose for a moment that we could solve this issue. Now, if the shares have in fact been tampered with, this tampering will become clear once it is found out that the signature does not verify, and one can then take action (e.g., stop the system and restore the secret key from a back-up). The intuition is that we have managed to make the tampering harmless, because non-malleability implies that the faulty signature is generated from an unrelated secret.

Unfortunately, however, the original definition is unlikely to be sufficient to prove this intuition for a realistic system. The problem is that a real-life system will most likely have to serve many different signature requests that arrive in an uncoordinated fashion over an asynchronous network like the Internet. Therefore, once the first faulty signature has been detected and action has been taken, we should assume that in the mean time several other signature requests have already been served, possibly by different qualified sets of servers.

The standard definition of non-malleable secret sharing [16, 17] is not sufficient to prove security in this case because it only talks about one invocation of the reconstruction algorithm. What we need is a stronger definition, namely non-malleability with concurrent reconstruction. In this model, we consider an experiment where, after the tamperings have been done, the reconstruction algorithm is run (in parallel) on several qualified subsets. We require that all the instances of the reconstruction return either the original secret or something unrelated. It is not known how to construct secret sharing schemes with this stronger property.

1.1 Our Contributions

In this paper, we resolve all of the above open questions:

• We present a general compiler that transforms any secret sharing scheme into a leakage-resilient one for the same access structure and preserves the efficiency of the original scheme. The compiled scheme withstands bounded size local leakage from all shares. The result extends to attacks that are strictly stronger than previously considered: the adversary can be told complete information on an unqualified set of shares and can in addition be given local leakage from all the other shares, and still will not learn the secret. To the best of our knowledge, this is the first result of its kind.

  If the share length of the underlying secret sharing scheme is $\ell$, then the compiler can yield a leakage-resilient scheme with shares of length $O(\ell )$ and leakage rate $1-c$ for an arbitrarily small constant $c>0$. Moreover, if we allow a blow-up of the share length in the compiled scheme from $\ell$ to $\omega (\ell )$, then we can achieve a leakage rate of $1-o(1)$.

• We present another compiler that transforms any secret sharing scheme realizing an access structure $\mathcal {A}$ where every qualified set T has size at least 3 into a scheme for the same access structure that is non-malleable with concurrent reconstruction with respect to individual share tampering. More precisely, the adversary chooses a polynomial (in the number of parties) number of qualified sets $T_1,T_2,\dots$, where it may be the case that $T_i=T_j$ for some i and j, along with associated tampering functions $f^{(1)},f^{(2)},\dots$, where $f^{(i)}$ tampers each share independently. We may think of this setting as a strong analogue of the multiple-tampering paradigm for non-malleable codes and extractors: The adversary is allowed to (non-adaptively) tamper the shares multiple times, and in each tampering attempt is further allowed to freely choose the qualified set to be used by the reconstruction algorithm in the tampering experiment.

• We present a compiler that turns any threshold signature scheme into one that is secure against tampering, assuming the original scheme is secure in the standard sense. In particular, the compiled scheme is secure even if faulty signatures are constructed from several qualified sets after tampering. We allow the adversary to either tamper with all shares of the secret key, or to maliciously corrupt an unqualified subset of the signature servers. The compiler adds two rounds to the signing protocol of the original scheme. The computational complexity is essentially that of the original signature protocol plus that of the reconstruction in a non-malleable secret sharing scheme. The overhead is actually only necessary each time the system is initialized from storage that may have been tampered, and therefore its cost amortizes over all signatures generated while the system is on-line.

• We present a compiler that turns any threshold signature scheme into one that is secure in the standard sense even if the adversary, additionally, obtains size-bounded leakage from all secret key shares. The compiler follows the same blueprint and is as efficient as our compiler for non-malleable threshold signatures.

1.2 Independent Work

In the late stages of this work, it came to our knowledge that other independent, concurrent works obtained results similar to ours. Srinivasan and Vasudevan [24] give a compiler that transforms a secret sharing scheme for any access structure into a leakage-resilient secret sharing scheme for the same access structure. Their compiler is rate-preserving and has leakage rate approaching 1. In comparison, if the underlying secret sharing scheme has constant rate, our leakage-resilient secret sharing compiler achieves rate $\varOmega (1/n)$ and leakage rate $1-c$ for an arbitrarily small constant $c>0$, and must have rate 0 if we require leakage rate $1-o(1)$. They also construct leakage resilient schemes in a stronger leakage model, where leakage functions may be chosen adaptively.

Srinivasan and Vasudevan use the results obtained to construct positive rate non-malleable threshold secret sharing schemes against a single tampering that modifies each share independently for 4-monotone access structures¹. In comparison, the non-malleable secret sharing compiler that we obtain for a single tampering works for all 3-monotone access structures but has rate $\varTheta (\frac{1}{n\log m})$ in the same setting, where m denotes the length of the secret and n denotes the number of parties, and so converges to 0. Finally, they consider applications to leakage-resilient secure multiparty computation.

Badrinarayanan and Srinivasan [3] construct non-malleable secret sharing schemes with respect to independent share tampering, both against a single tampering and against multiple tamperings. They are able to realize all 4-monotone access structures. Moreover, they optimize the rates of their constructions to obtain schemes with positive rate and a concretely efficient scheme. However, their tampering model is weaker than ours: While in our model, named concurrent reconstruction, the adversary is allowed to (non-adaptively) tamper the shares multiple times and in each tampering can choose a potentially different reconstruction set for the tampering experiment, the model studied in [3] forces the adversary to always choose the same reconstruction set for all tamperings. Their schemes are not secure in the stronger concurrent reconstruction model, and the authors explicitly mention the concurrent reconstruction model as a natural strengthening of their tampering model. In contrast, our compiler transforms any secret sharing scheme realizing a 3-monotone access structure into a (rate-0) non-malleable secret sharing scheme secure against multiple tamperings in the concurrent reconstruction model.

Kumar, Meka, and Sahai [20] also study leakage-resilient and non-malleable secret sharing. They consider a stronger leakage model than ours, where each leaked bit may depend on up to p shares which can be chosen adaptively by the adversary. They give a compiler that transforms a standard secret sharing scheme into a leakage-resilient one in the model just described, for p logarithmic in the number of parties. It is also shown that noticeably improving the dependence of the share length on p obtained there would lead to non-trivial progress on important open questions related to communication complexity. Finally, they consider the notion of leakage-resilient non-malleable secret sharing with respect to independent share tampering. Here, the adversary has access to leakage from the shares, which he can then make use of to choose tampering functions. They construct schemes in this model for the case of a single tampering. For comparison, our non-malleable secret sharing schemes cannot withstand leakage, but, as already mentioned in the previous paragraph, allow the adversary to tamper the shares multiple times, each time with a potentially different reconstruction set in the associated tampering experiment.

1.3 Technical Overview

In this section, we give a high-level overview of the proof ideas and techniques used to construct each one of our compilers.

All of our secret sharing scheme compilers are based on the same key idea: Let $s_1,\dots ,s_n$ denote the shares obtained via the underlying secret sharing scheme. We encode each share $s_i$ using some (randomized) coding scheme $(\mathbf {Enc},\mathbf {Dec})$ to obtain two values $L_i$ and $R_i$. Then, the new compiled shares are obtained by, for each $i=1,\dots ,n$, giving $L_i$ to the i-th party, and $R_i$ to every other party. At the end of this procedure, the i-th party has a compiled share, denoted $S_i$, of the form $S_i=(R_1,\dots ,R_{i-1},L_i,R_{i+1},\dots ,R_n)$.

Reconstruction of the underlying secret is possible from any qualified set of parties, as they will learn the corresponding pairs $(L_i,R_i)$, and hence the underlying share $s_i$. The different compilers arise by instantiating the idea above with coding schemes satisfying different properties. One basic property that is required from all coding schemes is that one half of the codeword $(L_i,R_i)$ reveals almost nothing about $s_i$.

Leakage-Resilient Secret-Sharing Scheme. In order to obtain a leakage-resilient secret-sharing scheme via the idea above, we instantiate the coding scheme $(\mathbf {Enc},\mathbf {Dec})$ as follows: Let $\mathsf {Ext}$ be a strong seeded extractor. Roughly speaking, a strong seeded extractor is a deterministic function that produces a close-to-uniform output when given a sample from a source with high min-entropy along with a short, independent, and uniform seed, even when the seed is known to the distinguisher. Then, $\mathbf {Enc}(m)$ samples (L, R) from the preimage $\mathsf {Ext}^{-1}(m)$ close to uniformly at random. Here, L corresponds to the weak source, while R corresponds to the uniform, independent seed. To recover m from a codeword c, we simply set $\mathbf {Dec}(L,R):=\mathsf {Ext}(L,R)$. This coding scheme is efficient if $\mathsf {Ext}$ is itself efficient, and furthermore $\mathsf {Ext}$ supports efficient close-to-uniform preimage sampling. More precisely, this means that, given m, there exists an efficient algorithm that samples an element of $\mathsf {Ext}^{-1}(m)$ close to uniformly at random. The idea behind this coding scheme is the same as the one used by Cheraghchi and Guruswami [11] in order to obtain split-state non-malleable codes from non-malleable extractors (variations of these objects are defined in Sect. 2, but are not important for this discussion).

We instantiate our compiler with linear strong seeded extractors coupled with a careful choice of parameters in order to obtain a leakage-resilient scheme with good leakage rate. A result of [9] ensures that we can efficiently sample close to uniformly from the preimage of any linear strong seeded extractor, provided the error of the extractor is small enough.

We now discuss why this construction is leakage-resilient. For simplicity, assume that $L_i$ and $R_i$ are independent and uniform for $i=1,\dots ,n$. This is not true in practice, and a little more care is needed to show that leakage-resilience holds in Sect. 4. However, it lets us present the main idea behind the proof in a clearer way.

Suppose the adversary holds shares from a set of unqualified parties T. Without loss of generality, let $T=\{1,\dots , t\}$. Furthermore, we also assume the adversary learns some limited information about all shares, i.e., he learns $\mathsf {Leak}_i(S_i)$ for some function $\mathsf {Leak}_i$ and all $i=1,\dots ,n$. Note that the adversary knows the pairs $(L_i,R_i)$ for $i=1,\dots ,t$, and hence the shares $s_1,\dots ,s_t$ obtained via the underlying secret sharing scheme. Furthermore, he knows $R_i$ (the seeds of the extractor) for $i=t+1,\dots ,n$. The goal of the adversary is now to obtain extra knowledge about $L_{t+1,},\dots ,L_n$ from the leaked information. Since, by hypothesis, the leaked information about $L_i$ is only a small linear fraction of its length, and is independent of $R_i$, we can condition $L_i$ on the output of $\mathsf {Leak}_i(S_i)$. As a result, $L_i$ conditioned on $\mathsf {Leak}_i(S_i)$ is still independent of $R_i$, and still has high min-entropy. This means that the output of $\mathsf {Ext}(L_i,R_i)$ still looks close-to-uniform to the adversary, even when $R_i$ is given (recall that we use a strong extractor). It follows that the leaked information gives almost no information about the shares outside T, and hence we can use the statistical privacy of the underlying secret sharing scheme to conclude the proof.

Non-Malleable Secret-Sharing Scheme with Concurrent Reconstruction. In order to obtain a non-malleable scheme, we use the same basic idea as before, but with a few modifications. To begin, we require the following primitives:

• A secret sharing scheme $(\mathbf {Share},\mathbf {Rec})$ for an access structure in which every qualified set has size at least 3;

• A strong two-source non-malleable extractor $\mathbf {nmExt}$ secure against multiple tamperings which supports efficient preimage sampling, in the sense that we can sample uniformly from its preimages $\mathbf {nmExt}^{-1}(z)$.

A non-malleable extractor is a stronger notion of an extractor introduced in [11]. More precisely, its output must still be close to uniform even conditioned on the output of the extractor on a tampered version of the original input. Similarly as before, such an extractor is said to be strong if the property above still holds when the distinguisher is also given the value of one of the input sources. Since their introduction, non-malleable extractors have received a lot of attention due to their connection to split-state non-malleable codes [9,10,11, 21]. We note that constructions of such strong non-malleable extractors handling a sublinear (in the input length) number of tamperings and supporting efficient preimage sampling are known [9, 18].

The coding scheme $(\mathbf {Enc},\mathbf {Dec})$ is obtained from $\mathbf {nmExt}$ analogously to the leakage-resilient scheme. Namely, $\mathbf {Enc}(m)$ samples (L, R) uniformly at random from $\mathbf {nmExt}^{-1}(m)$, and we set $\mathbf {Dec}(L',R'):=\mathbf {nmExt}(L',R')$.

To encode the shares $(s_1,\dots ,s_n)$ into $(S_1,\dots ,S_n)$, we proceed as follows:

• 1. Sample $P\leftarrow \{0, 1\}^p$;

• 2. Set $(L_i,R_i)\leftarrow \mathbf {Enc}(P||s_i)$ for $i=1,\dots ,n$, where || denotes string concatenation;

• 3. Set $S_i=(R_1,\dots ,R_{i-1},L_i,R_{i+1},\dots ,R_n)$ for $i=1,\dots ,n$.

We will now briefly walk through the proof of statistical privacy and non-malleability for a single reconstruction set. Statistical privacy follows from the statistical privacy properties of the underlying secret sharing scheme and the fact that $(\mathbf {Enc},\mathbf {Dec})$ as defined above can be seen as a 2-out-of-2 secret sharing scheme.

In order to show statistical privacy, fix an unqualified set of parties T, which we may assume is $T=\{1,\dots ,t\}$. First, the fact that a split-state non-malleable code is also a 2-out-of-2 secret sharing scheme implies that we can replace the values $R_{t+1},\dots ,R_n$ in all shares by independent and uniformly random values. Second, the pairs $(L_1,R_1),\dots ,(L_t,R_t)$ encode shares $s_1,\dots ,s_t$, respectively, belonging to an unqualified set of the underlying secret sharing scheme. As a result, the statistical privacy of that scheme implies we can replace these encodings by those induced by a different secret.

In order to show non-malleability, fix a qualified set of parties T, with $t=|T|\ge 3$. For simplicity, assume again $T=\{1,\dots ,t\}$. An adversary that wishes to tamper the shares in T chooses tampering functions $f_1,\dots ,f_t$, one per share. Write a tampered share $S'_i=f_i(S_i)$ as $S'_i=(R'^{(i)}_1,\dots ,R'^{(i)}_{i-1},L'_i,R'^{(i)}_{i+1},\dots ,R'^{(i)}_n)$ for $i=1,\dots ,t$. We now have the following reconstruction procedure, which may output a special symbol $\bot$ if it detects tampering:

• 1. For each $i=1,\dots ,n$, check that $R'^{(j_1)}_i=R'^{(j_2)}_i$ for all $j_1,j_2\ne i$. If this is not the case, then output $\bot$;

• 2. If the check holds, set $R'_1=R'^{(2)}_1$ and $R'_i=R'^{(1)}_i$ for $i=2,\dots ,t$. Then, decode and parse $P'_i||s'_i\leftarrow \mathbf {Dec}(L'_i,R'_i)$ for $i=1,\dots ,t$;

• 3. If $P'_i\ne P'_j$ for some $i,j\le t$, output $\bot$. Else, output $\mathbf {Rec}^T(s'_1,\dots ,s'_t)$.

Note that the consistency checks in Steps 1 and 3 correspond to properties that must be satisfied if $(S'_1,\dots ,S'_t)$ is a valid set of shares. Roughly speaking, in order to show non-malleability we must be able to simulate the reconstruction of tampered shares without knowledge of the encoded secret m (except if the adversary does not modify any share, in which case we may output m).

We prove non-malleability in two steps. First, we consider the following intermediate tampering experiment on $(S_1,\dots ,S_t)$:

• For each $i=1,\dots ,n$, check that $R'^{(j_1)}_i=R'^{(j_2)}_i$ for all $j_1,j_2\ne i$. If this is not the case, then output $\bot$;

• If the check holds, set $R'_1=R'^{(2)}_1$ and $R'_i=R'^{(1)}_i$ for $i=2,\dots ,t$. For each $i=1,\dots ,t$, set $\mathsf {output}_i=\mathsf {same}^*$ if $L'_i=L_i$ and $R'_i=R_i$. Otherwise, set $\mathsf {output}_i\leftarrow \mathbf {Dec}(L'_i,R'_i)$;

• If $\mathsf {output}_i=\mathsf {same}^*$ for all $i=1,\dots , t$, output $\mathsf {same}^*$. Else, output $(\mathsf {output}_1, \dots ,\mathsf {output}_t)$.

This is an intermediate tampering experiment in the sense that it corresponds to a stage of the reconstruction procedure on the tampered shares where the values of the shares that remain the same have not yet been revealed. A key result we show is that the output of the intermediate tampering experiment described above has almost no correlation with the initial values $P||s_i$ for $i=1,\dots ,n$. In particular, we can replace each such value by an independent and uniformly random one, and hence by a set of uniform values independent of the secret m encoded by the shares $s_1,\dots ,s_n$. We leverage a novel property of strong non-malleable extractors (Lemmas 24 and 28) to prove this result, which may be of independent interest.

By the result just described, we now know how to simulate the intermediate tampering experiment for any secret m without any knowledge of m itself. However, to be able to simulate the behavior of the real reconstruction procedure on the tampered shares, we must know what the simulator must output when $\mathsf {output}_i=\mathsf {same}^*$ and $\mathsf {output}_j\ne \mathsf {same}^*$ for some $i,j\le t$. In the second step, we show that the reconstruction procedure will output $\bot$ (i.e., tampering is detected, and hence the procedure is aborted) with high probability in this situation. This is because, with high probability, the decoded prefixes will not match among all parties in this case. As a result, we can simply have our simulator output $\bot$ in such a case, and it will coincide with the output of the real reconstruction procedure with high probability.

The argument above implies that our secret sharing scheme is non-malleable against a single tampering of a reconstruction set. This result extends to the concurrent reconstruction setting, where the adversary is allowed to tamper the shares multiple times with different tampering functions and qualified sets. We refer to the later sections for details on the proof for the general case.

Threshold Signature Scheme Secure Against Tampering. Finally, our threshold signature compiler starts from the assumption that the secret key is to be secret-shared among a set of servers. We assume that we have protocols for generating n signature shares as well as a protocol for computing the final signature from these shares. Further, we assume that these protocols are secure even if an adversary maliciously corrupts an unqualified subset of size t of the $n \ge 2t+1$ servers.

To construct the compiled protocol, we first apply our second compiler from above, such that we now share the secret key using non-malleable secret sharing. Recall that this scheme involves encoding the original share $s_i$ to get a pair $(L_i,R_i)$ where the i-th server holds $L_i$ and all other servers hold $R_i$. If now the i-th server wants to generate a signature share, it requests $R_i$ from all other servers and waits until it gets back $n-t$ responses. If all received $R_i$ are the same, it accepts the value and decodes $(L_i, R_i)$ to obtain key share $s_i$. Note that since $n \ge 2t+1$ and the server gets $n-t$ responses, we ensure that it gets back at least one honest response. At this point the server generates a signature share as it would do in the original protocol.

A rough intuition on why this is secure follows: Recall that our model says that the adversary can either tamper with the shares, or corrupt t of servers. If he tampers, he is not allowed to corrupt anyone, and this means that the servers are executing the non-malleable reconstruction protocol securely, and will either get the correct original shares (and thus create correct signatures) or will get something unrelated, in which case the output cannot compromise any secret key share. In the other case, the adversary has chosen to corrupt a set of servers. However, then we know that the shares we start from are correct. This means that sending the required $R_i$’s in the clear to i-th server does not leak any extra information than it should. In fact, it merely enables the server to get his original share. The checks we enforce ensure that an honest player get its correct original share, and hence security follows from the threshold signature scheme we started with.

1.4 Open Questions

Several exciting questions remain open. The first natural direction is to improve the rates of our constructions. This can be achieved indirectly by coming up with better explicit constructions of strong seeded extractors and strong seedless non-malleable extractors. Another possibility is to improve the relationship between the share length of the compiled scheme and the number of parties. All of our constructions, as well as the constructions of Goyal and Kumar [16, 17], have share sizes which are at least linear in the number of parties, and it would be interesting to see whether one can obtain a weaker dependence.

Our work introduces stronger definitions for non-malleable secret sharing schemes. However, our new notions, as well as the previous ones, are fundamentally non-adaptive in the sense that the tampering functions and reconstruction sets have to be chosen without seeing any of the shares a priori. We believe it would be more in the spirit of secret sharing if the tampering functions and reconstruction sets could be chosen after seeing some unqualified set of shares. On a similar note, a logical next step would be to define and attempt to construct continuous non-malleable secret sharing schemes (in the spirit of [15]), where the adversary is allowed to choose the tampering function and qualified set to be reconstructed adaptively.

Our definition of leakage-resilient secret sharing schemes is also non-adaptive. It would be interesting to construct schemes which remain leakage resilient even if the adversary has access to an unqualified set of shares prior to choosing the leakage functions. Moreover, we obtain leakage rate $1-c$ for an arbitrarily small constant $c>0$ while preserving the share length (up to a multiplicative constant). However, our share length suffers a polynomial blow-up if we want to achieve leakage rate $1-o(1)$. It would be interesting to give constructions of leakage-resilient schemes (even in the non-adaptive setting) with an improved tradeoff between leakage rate and share length.

1.5 Organization

The rest of the paper is organized as follows: We present notation, relevant definitions, and known lemmas that we use throughout the paper in Sect. 2. We present and study our compiler for non-malleable secret sharing in Sect. 3. In Sect. 4, we present our compiler for leakage-resilient secret sharing. Finally, in Sect. 5, we discuss our compiler for non-malleable and leakage-resilient threshold signatures. Most detailed arguments have been deferred to the full version of this work [1].

2 Preliminaries

We denote the set $\{1,\dots ,n\}$ by [n]. Random variables are usually denoted by uppercase letters such as X, Y, and Z. We denote sets by calligraphic letters such as $\mathcal {A}$ and $\mathcal {M}$. We may denote the probability that a random variable X belongs to a set $\mathcal {S}$ by $X(\mathcal {S})$. We use the notation $z\leftarrow Z$ to denote that z is sampled according to distribution Z. If instead we write, say, $s\leftarrow \mathcal {S}$, this means that s is sampled uniformly at random from the set $\mathcal {S}$. Given an n-tuple x and a set $\mathcal {S}\subseteq [n]$ with $\mathcal {S}=\{i_1,\dots ,i_s\}$ and $i_j<i_{j+1}$ for $j=1,\dots ,s-1$, we define $x_\mathcal {S}=(x_{i_1},\dots ,x_{i_s})$. By an efficient algorithm, we mean an algorithm that runs in time polynomial in the length of the input.

2.1 Statistical Distance and Min-Entropy

In this section, we introduce statistical distance and min-entropy, along with related results.

Definition 1

(Statistical Distance). Let X and Y be two distributions over a set S. The statistical distance between X and Y, denoted by $\varDelta (X;Y)$, is given by

$$\begin{aligned} \varDelta (X;Y) := \max _{T \subseteq S}(|X(T) - Y(T)|) = \frac{1}{2} \sum _{s \in S}|X(s)-Y(s)|. \end{aligned}$$

We say X is $\varepsilon$-close to Y, denoted $X \approx _\varepsilon Y$, if $\varDelta (X;Y) \le \varepsilon$, and we write $\varDelta (X; Y|Z)$ as shorthand for $\varDelta ((X, Z); (Y, Z))$.

The following known properties of the statistical distance are useful throughout the paper.

Lemma 2

For any two random variables X and Y, and any randomized function f, we have that

$$ \varDelta (f(X); f(Y)) \le \varDelta (X; Y). $$

Lemma 3

([11]). Fix random variables X and Y such that

$$\begin{aligned} X\approx _{\varepsilon } Y. \end{aligned}$$

Let $X'$ and $Y'$ denote X and Y conditioned on an event E, respectively. If $X(E)=p$ (i.e., the probability of event E under X is p), then

$$\begin{aligned} X'\approx _{\varepsilon /p} Y'. \end{aligned}$$

Definition 4

(Min-Entropy and Conditional Min-Entropy). Fix a distribution X over $\mathcal {X}$. The min-entropy of X, denoted by $\mathbf {H}_\infty (X)$, is given by

$$\begin{aligned} \mathbf {H}_\infty (X):=-\log \left( \max _{x\in \mathcal {X}} X(x)\right) . \end{aligned}$$

Moreover, the conditional min-entropy of X given Z, denoted by $\mathbf {H}_\infty (X|Z)$, is given by

where denotes the expected value over Z.

The following property of the conditional min-entropy is also fundamental.

Lemma 5

([13]). Let (X, Z) be some joint probability distribution. Then, if Z is supported on at most $2^\ell$ values, we have

$$\begin{aligned} \mathbf {H}_\infty (X|Z)\ge \mathbf {H}_\infty (X)-\ell . \end{aligned}$$

2.2 Non-Malleable Codes and Extractors

In order to design our compilers, we will need to use some variants of extractors and non-malleable codes. We present the relevant definitions and results in this section.

Non-malleable codes are coding schemes with strong robustness guarantees against adversarial errors. We begin by defining coding schemes.

Definition 6

(Coding Scheme). A tuple of functions $(\mathbf {Enc},\mathbf {Dec})$ where $\mathbf {Enc}:\mathcal {M}\rightarrow \mathcal {C}$ may be randomized but $\mathbf {Dec}:\mathcal {C}\rightarrow \mathcal {M}\cup \{\bot \}$ is deterministic is said to be a coding scheme if the correctness property

$$\begin{aligned} \Pr (\mathbf {Dec}(\mathbf {Enc}(m)) = m) = 1 \end{aligned}$$

holds for every $m\in \mathcal {M}$, where the probability is taken over the randomness of the encoder $\mathbf {Enc}$.

Definition 7

(Non-Malleable Code [14]). We say that a coding scheme $(\mathbf {Enc}: \mathcal {M}\rightarrow \mathcal {X}\times \mathcal {X},\, \mathbf {Dec}: \mathcal {X}\times \mathcal {X}\rightarrow \mathcal {M}\cup \{\bot \})$ is $\varepsilon$-non-malleable in the split-state model if for all functions $F, G : \mathcal {X}\rightarrow \mathcal {X}$ there exists a distribution $SD^{{F}, {G}}$ over $\mathcal {M}\cup \{\mathsf {same}^*,\bot \}$ such that

$$\begin{aligned} \varvec{\mathsf {Tamper}^{{F}, {G}}_{{m}}} \approx _{\varepsilon } \varvec{\mathsf {Sim}^{F,G}_m} \end{aligned}$$

for all $m\in \mathcal {M}$, where

$$\begin{aligned} \varvec{\mathsf {Tamper}^{{F}, {G}}_{{m}}} = \left\{ \! \begin{aligned}&(L, R) \leftarrow \mathbf {Enc}(m) \\&\text {Output } \mathbf {Dec}(F(L), G(R)) \end{aligned} \right\} , \end{aligned}$$

and

$$\begin{aligned} \varvec{\mathsf {Sim}^{F,G}_m}= \left\{ \! \begin{aligned}&d \leftarrow SD^{{F}, {G}} \\&\text {If } d=\mathsf {same}^*\text {, output } m \\&\text {Else, output } d \end{aligned} \right\} . \end{aligned}$$

Additionally, $SD^{{F}, {G}}$ should be efficiently samplable given oracle access to $F(\cdot )$ and $G(\cdot )$.

We will also require a few variants of randomness extractors. We begin with the basic definition.

Definition 8

(Extractor). An efficient function $\mathsf {Ext}:\mathcal {X}\times \{0, 1\}^d \rightarrow \mathcal {Z}$ is a strong $(k,\varepsilon )$-extractor if for all X, W such that X is distributed over $\mathcal {X}$ and $\mathbf {H}_\infty (X|W) \ge k$ we have

$$\mathsf {Ext}(X,U_d),W, U_d\approx _{\varepsilon } U_{\mathcal {Z}},W, U_d.$$

Moreover, we say $\mathsf {Ext}$ supports efficient preimage sampling if, given $z\in \mathcal {Z}$, there exists an efficient algorithm that samples an element of $\mathsf {Ext}^{-1}(z)$ uniformly at random.

We describe some known explicit constructions of linear strong extractors that we will need to instantiate our leakage-resilient secret sharing compiler of Sect. 4 in [1]. We will also need a stronger notion of an (independent-source) extractor, for which the output still looks uniform even conditioned on the output of the extractor on a tampered version of the original input.

Definition 9

(Strong Two-Source Non-Malleable Extractor). A function $\mathbf {nmExt}:\mathcal {X}^2\rightarrow \mathcal {Z}$ is said to be a $(k,\varepsilon ,\tau )$ strong two-source non-malleable extractor if the following property holds: For independent distributions X, Y over $\mathcal {X}$ and W independent of Y such that $\mathbf {H}_\infty (X|W),\mathbf {H}_\infty (Y)\ge k$, and for all tampering functions $(f_1,g_1),\dots ,(f_\tau ,g_\tau )$ it holds that

$$\begin{aligned} \mathbf {nmExt}(X,Y),W,Y, \{\mathcal {D}_{f_i,g_i}(X,Y)\}_{i\in [\tau ]}\approx _\varepsilon U_\mathcal {Z}, W, Y,\{\mathcal {D}_{f_i,g_i}(X,Y)\}_{i\in [\tau ]}, \end{aligned}$$

where $\mathcal {D}_{f,g}(X,Y)$ is defined as

$$\begin{aligned} \mathcal {D}_{f,g}(X,Y):= {\left\{ \begin{array}{ll} \mathsf {same}^*,&{}\text { if } f(X)=X \text { and } g(Y)=Y,\\ \mathbf {nmExt}(f(X),g(Y)),&{}\text { otherwise.} \end{array}\right. } \end{aligned}$$

The function $\mathbf {nmExt}$ is said to support efficient preimage sampling if, given $z\in \mathcal {Z}$, there is an efficient algorithm that samples an element of the preimage $\mathbf {nmExt}^{-1}(z)$ uniformly at random.

There exist explicit constructions of strong two-source non-malleable extractors with good parameters, supporting efficient preimage sampling, both against single and multiple tamperings [9, 21]. Although it is not stated in [9] that the extractor found there is strong, it is known that this property holds [19]. A statement and proof of this result appears in [18]. We will use the following two explicit non-malleable extractors.

Lemma 10

([21]). For any field $\mathbb {F}$ of cardinality $2^N$, there exists a constant $\delta \in (0,1)$ and a function $\mathbf {nmExt}:\mathbb {F}^2\rightarrow \{0, 1\}^\ell$ such that $\mathbf {nmExt}$ is an efficient $((1-\delta )N,\varepsilon ,1)$ strong two-source non-malleable extractor with $\ell =\varOmega (N)$ and $\varepsilon =2^{-\varOmega (N/\log N)}$. Moreover, $\mathbf {nmExt}$ supports efficient preimage sampling and it is a balanced function, i.e., the preimage sets $\mathbf {nmExt}^{-1}(z)$ have the same size for all $z\in \{0, 1\}^\ell$.

Lemma 11

([9, 18]). For any field $\mathbb {F}$ of cardinality $2^N$, there exists a constant $\delta \in (0,1)$ and a function $\mathbf {nmExt}:\mathbb {F}^2\rightarrow \{0, 1\}^\ell$ such that $\mathbf {nmExt}$ is an efficient $(N-N^{\delta },\varepsilon ,\tau )$ strong two-source non-malleable extractor with $\ell =N^{\varOmega (1)}$, $\tau =N^{\varOmega (1)}$, and $\varepsilon =2^{-N^{\varOmega (1)}}$. Moreover, $\mathbf {nmExt}$ supports efficient preimage sampling and it is a balanced function, i.e., the preimage sets $\mathbf {nmExt}^{-1}(z)$ have the same size for all $z\in \{0, 1\}^\ell$.

The connection between non-malleable extractors with efficient preimage sampling and split-state non-malleable codes is made clear by the following result.

Lemma 12

([11]). Fix an explicit two-source $(n,\varepsilon ,1)$-non-malleable extractor $\mathbf {nmExt}:\mathbb {F}^2\rightarrow \{0, 1\}^\ell$ that supports efficient preimage sampling. The coding scheme $(\mathbf {NMEnc},\mathbf {NMDec})$ is defined as follows:

• $\mathbf {NMEnc}(m)$: Sample $(L,R)\leftarrow \mathbf {nmExt}^{-1}(m)$, and output (L, R);

• $\mathbf {NMDec}(L',R')$: Output $\mathbf {nmExt}(L',R')$.

Then, $(\mathbf {NMEnc},\mathbf {NMDec})$ is an efficient split-state $\varepsilon '$-non-malleable code for $\varepsilon '=\varepsilon (2^\ell +1)$.

Combining Li’s non-malleable extractor [21] and Lemma 12 immediately leads to the following result, also found in [21].

Corollary 13

([21]). For any field $\mathbb {F}$ of cardinality $2^N$, there exists an efficient split-state $\varepsilon$-non-malleable code $(\mathbf {NMEnc},\mathbf {NMDec})$ with $\mathbf {NMEnc}:\{0, 1\}^\ell \rightarrow \mathbb {F}^2$, $\mathbf {NMDec}:\mathbb {F}^2 \rightarrow \{0, 1\}^\ell \cup \{\bot \}$, $\ell =\varTheta (N/\log N)$, and $\varepsilon =2^{-\varOmega (N/\log N)}$.

2.3 Secret-Sharing Schemes

In this section, we introduce our definitions of leakage-resilient and non-malleable secret sharing schemes. We begin by defining basic secret sharing concepts.

Definition 14

(Access Structure). We say $\mathcal {A}$ is an access structure for n parties if $\mathcal {A}$ is a monotone class of subsets of [n], i.e., if $A\in \mathcal {A}$ and $A\subseteq B$, then $B\in \mathcal {A}$. We call sets $T\in \mathcal {A}$ authorized or qualified, and unauthorized or unqualified otherwise.

Definition 15

(Secret Sharing Scheme [4]). Let $\mathcal {M}$ be a finite set of secrets, where $|\mathcal {M}| \ge 2$. A (randomized) sharing function $\mathbf {Share}:\mathcal {M}\rightarrow \mathcal {S}_1\times \dots \times \mathcal {S}_n$ is an $(n, \varepsilon )$-Secret Sharing Scheme for secret space $\mathcal {M}$ realizing access structure $\mathcal {A}$ if the following two properties hold:

• 1. Correctness. The secret can be reconstructed by any authorized set of parties. That is, for any set $T \in \mathcal {A}$, where $T = \{i_1, \ldots , i_t\}$, there exists a deterministic reconstruction function $\mathbf {Rec}^T : \otimes _{{i} \in {T}} \mathcal {S}_i \rightarrow \mathcal {M}$ such that for every $m \in \mathcal {M}$,

  $$\begin{aligned} \Pr [\mathbf {Rec}^T(\mathbf {Share}(m)_T) = m] = 1, \end{aligned}$$

  where the probability is taken over the randomness of $\mathbf {Share}$.

• 2. Statistical Privacy. Any collusion of unauthorized parties should have “almost” no information about the underlying secret. More formally, for all unauthorized sets $T \notin \mathcal {A}$ and for every pair of secrets $a, b \in \mathcal {M}$, we have

  $$\begin{aligned} \mathbf {Share}(a)_T\approx _\varepsilon \mathbf {Share}(b)_T. \end{aligned}$$

Besides the usual secret sharing properties, we can additionally require that the unauthorized parties do not learn anything about the underlying secret, even if given some leakage from all the shares. This leads to the notion of leakage-resilient secret sharing.

Definition 16

(Leakage-Resilient Secret-Sharing Scheme). A secret sharing scheme $(\mathbf {Share},\mathbf {Rec})$ realizing access structure $\mathcal {A}$ is said to be an $(n, \varepsilon , \rho )$-leakage-resilient secret sharing scheme if the following property additionally holds:

• Leakage-Resilient Statistical Privacy. For all unauthorized sets $T \notin \mathcal {A}$, functions $\mathsf {Leak}_i: \mathcal {S}_i \rightarrow \{0, 1\}^{\lfloor \rho \log |\mathcal {S}_i|\rfloor }$ for $i = 1, \ldots , n$, and for every pair of secrets $a, b \in \mathcal {M}$, we have

  $$\begin{aligned} \mathbf {Share}(a)_T, \{ \mathsf {Leak}_i(\mathbf {Share}(a)_i)\}_{i\in [n]} \approx _\varepsilon \mathbf {Share}(b)_T, \{ \mathsf {Leak}_i(\mathbf {Share}(b)_i)\}_{i\in [n]}. \end{aligned}$$

Alternatively, we can require some security against tampering attacks on the shares produced by the secret sharing scheme: Either the secret reconstructed from the tampered shares is the same as the original secret, or it is almost independent of it. The notion of non-malleable secret sharing was first considered in [16, 17], but only with respect to tampering attacks on qualified sets belonging to the minimal access structure.

Definition 17

(Non-Malleable Secret Sharing Scheme). Let $(\mathbf {Share}, \mathbf {Rec})$ be an $(n, \varepsilon )$-secret sharing scheme for secret space $\mathcal {M}$ realizing access structure $\mathcal {A}$. Let $\mathcal {F}$ be some family of tampering functions. For each $f \in \mathcal {F}$, $m \in \mathcal {M}$ and authorized set $T \in \mathcal {A}$, define the tampering experiment

$$\begin{aligned} \varvec{\mathsf {STamper}^{{f}, {T}}_{{m}}} = \left\{ \! \begin{aligned}&\mathbf {s}\leftarrow \mathbf {Share}(m) \\&\widetilde{\mathbf {s}}\leftarrow f(\mathbf {s}) \\&\widetilde{m}\leftarrow \mathbf {Rec}(\widetilde{\mathbf {s}}_T) \\&\text {Output }\widetilde{m}\end{aligned} \right\} , \end{aligned}$$

which is a random variable over the randomness of the sharing function $\mathbf {Share}$. We say that $(\mathbf {Share}, \mathbf {Rec})$ is $\varepsilon '$-non-malleable with respect to $\mathcal {F}$ if for each $f \in \mathcal {F}$ and authorized set $T \in \mathcal {A}$, there exists a distribution $SD^{{f}, {T}}$ (corresponding to the simulator) over $\mathcal {M}\cup \{\mathsf {same}^*, \bot \}$ such that we have

$$\begin{aligned} \varvec{\mathsf {STamper}^{{f}, {T}}_{{m}}}\approx _{\varepsilon '} \varvec{\mathsf {SSim}^{{f}, {T}}_{{m}}}, \end{aligned}$$

for all $m \in \mathcal {M}$ and authorized sets $T \in \mathcal {A}$, where

$$\begin{aligned} \varvec{\mathsf {SSim}^{{f}, {T}}_{{m}}} = \left\{ \! \begin{aligned}&\widetilde{m}\leftarrow SD^{{f}, {T}} \\&\text {If }\widetilde{m}= \mathsf {same}^*\text {, output } m\\&\text {Else, output } \widetilde{m}\end{aligned} \right\} . \end{aligned}$$

Additionally, $SD^{{f}, {T}}$ should be efficiently samplable given oracle access to $f(\cdot )$.

We also consider a stronger notion of non-malleable secret sharing, where the adversary is allowed to tamper the shares multiple times, and in each tampering attempt is free to choose the qualified set to be used by the reconstruction algorithm in the tampering experiment.

Definition 18

(Non-Malleability with Concurrent Reconstruction). Let $(\mathbf {Share}, \mathbf {Rec})$ be an $(n, \varepsilon )$-secret sharing scheme for secret space $\mathcal {M}$ realizing access structure $\mathcal {A}$. Let $\tau$ be a fixed constant. Let $\mathcal {F}$ be some family of tampering functions. For $m\in \mathcal {M}$, $\mathbf {f}=(f^{(1)},\dots ,f^{(\tau )}) \in \mathcal {F}^\tau$, and $\mathbf {T}=(T_1,\dots ,T_\tau )\in \mathcal {A}^\tau$, define the tampering experiment

$$ \varvec{\mathsf {SCRTamper}^{{\mathbf {f}}, T}_{{m}}} = \left( \varvec{\mathsf {STamper}^{{f^{(1)}}, {T_1}}_{{m}}}, \varvec{\mathsf {STamper}^{{f^{(2)}}, {T_2}}_{{m}}}, \ldots , \varvec{\mathsf {STamper}^{{f^{(\tau )}}, {T_\tau }}_{{m}}} \right) , $$

where each $\varvec{\mathsf {STamper}^{{f^{(i)}}, {T_i}}_{{m}}}$ is defined as in Definition 17. We say that $(\mathbf {Share}, \mathbf {Rec})$ is $(\varepsilon ',\tau )$-concurrent-reconstruction-non-malleable with respect to $\mathcal {F}$ if for each tuple $\mathbf {f} \in \mathcal {F}^\tau$ and tuple of authorized sets $\mathbf {T}\in \mathcal {A}^\tau$, there exists a distribution $SD^{{\mathbf {f}}, {\mathbf {T}}}$ over $(\mathcal {M}\cup \{\bot ,\mathsf {same}^*\})^\tau$ such that

$$\begin{aligned} \varvec{\mathsf {SCRTamper}^{{\mathbf {f}}, \mathbf {T}}_{{m}}}\approx _{\varepsilon '} \varvec{\mathsf {SCRSim}^{{\mathbf {f}}, \mathbf {T}}_{{m}}} \end{aligned}$$

for all $m\in \mathcal {M}$, where

$$\begin{aligned} \varvec{\mathsf {SCRSim}^{{\mathbf {f}}, \mathbf {T}}_{{m}}} = \left\{ \! \begin{aligned}&(\widetilde{m}_1,\dots ,\widetilde{m}_\tau ) \leftarrow SD^{{\mathbf {f}}, {\mathbf {T}}} \\&\text {Output }(\widetilde{m}'_1,\dots ,\widetilde{m}'_\tau ), \text { where } \widetilde{m}'_i=m \text { if } \widetilde{m}_i=\mathsf {same}^*,\\&\text {and } \widetilde{m}'_i=\widetilde{m}_i \text { otherwise} \end{aligned} \right\} . \end{aligned}$$

Additionally, $SD^{{\mathbf {f}}, {\mathbf {T}}}$ should be efficiently samplable given oracle access to $f^{(i)}(\cdot )$ for $i=1,\dots ,\tau$.

In this work, we will focus on the case where each share is tampered independently. With this in mind, we define the family of so-called t-split-state tampering functions, which we denote by $\mathcal {F}_{t}^{\text {split}}$.

Definition 19

(t-Split-State Tampering Functions). The family of t-split-state tampering functions over a domain $\mathcal {X}$, denoted by $\mathcal {F}_{t}^{\text {split}}$ (the domain is omitted for brevity), consists of all functions $f:\mathcal {X}^t\rightarrow \mathcal {X}^t$ for which there exist functions $f_i:\mathcal {X}\rightarrow \mathcal {X}$ with $i\in [t]$ such that $f(x)=(f_1(x_1),\dots ,f_t(x_t))$, where $x=(x_1,\dots ,x_t)$ and $x_i\in \mathcal {X}$ for $i\in [t]$.

We show separations between Definitions 17, 18, and the definition of non-malleable secret sharing from [17] under split-state tampering in [1].

Observe that split-state tampering of non-malleable codes and extractors as in Definitions 7 and 9 corresponds to considering the family of tampering functions $\mathcal {F}_{2}^{\text {split}}$.

The following result states that split-state non-malleable codes are 2-out-of-2 non-malleable secret sharing schemes.

Lemma 20

([2]). Suppose $(\mathbf {NMEnc},\mathbf {NMDec})$ is an $\varepsilon$-non-malleable code in the split-state model. Fix messages m and $m'$, and let $(L,R)\leftarrow \mathbf {NMEnc}(m)$ and $(L',R')\leftarrow \mathbf {NMEnc}(m')$. Then, we have

$$\begin{aligned} L\approx _{2\varepsilon } L' \quad \text {and}\quad R\approx _{2\varepsilon } R'. \end{aligned}$$

3 Non-Malleable Secret-Sharing

3.1 Non-Malleable Secret-Sharing Scheme Against Individual Tamperings

Before proceeding to the more general case of non-malleability with concurrent reconstruction, we describe our candidate secret sharing scheme and prove it is non-malleable against a single tampering with respect to functions which tamper the shares independently.

Theorem 21

Fix a number of parties n and an integer p. Furthermore, assume we have access to the following primitives:

• 1. For $\varepsilon _1 \ge 0$, let $(\mathbf {AShare}, \mathbf {ARec})$ be an $(n, \varepsilon _1)$-secret sharing scheme realizing an access structure $\mathcal {A}$ such that $|T|\ge 3$ holds whenever $T\in \mathcal {A}$. Suppose the corresponding shares lie in $\{0, 1\}^r$ and the secrets in some set $\mathcal {M}$;

• 2. Let $\mathbf {nmExt}:\{0, 1\}^N\times \{0, 1\}^N\rightarrow \{0, 1\}^{\ell }$ be the $((1-\delta )N,\varepsilon _2,1)$ strong two-source non-malleable extractor from Lemma 10, where $\ell =r+p$. Hence, $\ell \le \varOmega (N)$ and $\varepsilon _2=2^{-\varOmega (N/\log N)}$.

Then, there exists an $(n, \varepsilon _1\,+\,4n\varepsilon _2(2^\ell +1))$-secret sharing scheme realizing access structure $\mathcal {A}$ that is $n(2^{\ell +1}(\varepsilon _2\,+\,2^{-\delta N/2+1})\,+\,2^{-p})$-non-malleable w.r.t. $\mathcal {F}_{n}^{\text {split}}$. The resulting scheme $(\mathbf {NMShare}, \mathbf {NMRec})$ shares an element of $\mathcal {M}$ into n shares, where each share contains n elements of $\{0, 1\}^N$. Finally, if the two primitives are efficient and the access structure $\mathcal {A}$ supports efficient membership queries, then the constructed scheme $(\mathbf {NMShare},\mathbf {NMRec})$ is also efficient.

We describe our construction of the non-malleable secret sharing scheme $(\mathbf {NMShare}, \mathbf {NMRec})$.

• $\mathbf {NMShare}$: Our sharing function takes as input a secret $m \in \mathcal {M}$ and proceeds as follows:

  • 1. Share m using $\mathbf {AShare}$ to obtain $s_1, \ldots , s_n \leftarrow \mathbf {AShare}(m)$;

  • 2. Pick $P \leftarrow \{0, 1\}^p$;

  • 3. For each $i \in [n]$, encode the share $s_i$ to obtain

    $$\begin{aligned} (L_i, R_i) \leftarrow \mathbf {nmExt}^{-1}(P||s_i); \end{aligned}$$

  • 4. For each $i \in [n]$, construct $share_i=(R_1, \ldots , R_{i-1}, L_i, R_{i+1}, \ldots , R_n)$;

  • 5. Output $(share_1, \ldots , share_n)$.

• $\mathbf {NMRec}$: Our reconstruction function takes as input shares $\{share_i : i \in T\}$ corresponding to an authorized set $T \in \mathcal {A}$ and proceeds as follows:

  • 1. Sort T so that $T = \{i_1, \ldots , i_t\}$, where $t = |T|$, and $i_j < i_{j+1}$;

  • 2. For each $j \in [t]$, parse the shares in T to obtain

    $$\begin{aligned} (R_1^{(i_j)}, \ldots , R_{i_j-1}^{(i_j)}, L_{i_j}, R_{i_j+1}^{(i_j)}, \ldots , R_n^{(i_j)}) \leftarrow share_{i_j}; \end{aligned}$$

  • 3. For every $\ell \in [n]$, check that the $R_\ell ^{(i_j)}$ have the same value for all j such that $i_j\ne \ell$. If this is not the case, output $\bot$;

  • 4. For every $j \in [t]$, decode and parse $P_{i_j}||s_{i_j} \leftarrow \mathbf {nmExt}(L_{i_j}, R_{i_j}^{(i_k)})$, where $i_k$ is the smallest element of $T-\{i_j\}$;

  • 5. If there exist $j,j'\in [t]$ such that $P_{i_j}\ne P_{i_{j'}}$, output $\bot$;

  • 6. Else, reconstruct $m \leftarrow \mathbf {ARec}(s_{i_1}, \ldots , s_{i_t})$, and output m.

Correctness and Efficiency: Follows in a straightforward manner from the construction.

Statistical Privacy: Fix two secrets a and b, and let T be an unauthorized set of size t. Without loss of generality, we may assume that $T=\{1,2,\dots ,t\}$. Set

$$\begin{aligned} aS_T&\leftarrow \mathbf {NMShare}(a)_T,\\ bS_T&\leftarrow \mathbf {NMShare}(b)_T. \end{aligned}$$

Furthermore, let $as_1,\dots ,as_n$ and $bs_1,\dots ,bs_n$ be the shares obtained from $\mathbf {AShare}(a)$ and $\mathbf {AShare}(b)$, respectively, in Step 1 of the $\mathbf {NMShare}$ procedure.

Our goal is to show that the distributions of these two sets of shares, $aS_T$ and $bS_T$, are close in statistical distance. More precisely, we will show that

$$\begin{aligned} aS_T\approx _{\varepsilon _1+4n\varepsilon _2(2^\ell +1)}bS_T \end{aligned}$$

for all unauthorized sets T and secrets a, b.

We have $aS_T=(aS_1,\dots ,aS_t)$ and $bS_T=(bS_1,\dots ,bS_t)$, with

$$\begin{aligned}&aS_i=(aR_1,\dots ,aR_{i-1},aL_i,aR_{i+1},\dots ,aR_n),\\&bS_i=(bR_1,\dots ,bR_{i-1},bL_i,bR_{i+1},\dots ,bR_n). \end{aligned}$$

As a result, we can write

$$\begin{aligned}&aS_T=[(aL_i,aR_i)_{i\le t},aR_{t+1},\dots ,aR_n],\\&bS_T=[(bL_i,bR_i)_{i\le t},bR_{t+1},\dots ,bR_n]. \end{aligned}$$

Our first claim is that we can replace $aR_{t+1},\dots ,aR_n$ by encodings of independent, uniformly random messages with small penalty in statistical distance by invoking Lemma 20.

Lemma 22

Let $R^*_{t+1},\dots ,R^*_n\in \mathbb {F}$ be sampled as follows: For each $j=t+1,\dots ,n$, independently sample a uniformly random message $m^*$, encode and parse $(L^*,R^*)\leftarrow \mathbf {nmExt}^{-1}(m^*)$, and set $R^*_j=R^*$. Then,

$$\begin{aligned} (aL_i,aR_i)_{i\le t},aR_{t+1},\dots ,aR_n \approx _{2n\varepsilon _2(2^\ell +1)} (aL_i,aR_i)_{i\le t},R^*_{t+1},\dots ,R^*_n. \end{aligned}$$

Proof

The proof can be found in [1].   $\square$

Observe that, by the statistical privacy of the underlying secret sharing scheme, we have

$$\begin{aligned}&\varDelta ((aL_i,aR_i)_{i\le t};(bL_i,bR_i)_{i\le t})\nonumber \\&\le \varDelta ((aL_i,aR_i)_{i\le t};(bL_i,bR_i)_{i\le t}|P) \nonumber \\&\le \varepsilon _1, \end{aligned}$$

(1)

where P is the prefix used when encoding the shares with $\mathbf {nmExt}^{-1}$. This is because T is an unauthorized set, and each $(aL_i,aR_i)$ (resp. $(bL_i,bR_i)$) depends on $(aL_j,aR_j)$ (resp. $(bL_j,bR_j)$) for $j\ne i$ only through the share $as_i$ or $bs_i$ it encodes, when the prefix P is fixed. Combining Lemma 22 with (1) and a repeated application of the triangle inequality yields

$$\begin{aligned}&\varDelta (aS_T;bS_T)\\&=\varDelta ([(aL_i,aR_i)_{i\le t},aR_{t+1},\dots ,aR_n];[(bL_i,bR_i)_{i\le t},bR_{t+1},\dots ,bR_n])\\&\le \varDelta ([(aL_i,aR_i)_{i\le t},aR_{t+1},\dots ,aR_n];[(aL_i,aR_i)_{i\le t},R^*_{t+1},\dots ,R^*_n])\\&\quad +\varDelta ([(aL_i,aR_i)_{i\le t},R^*_{t+1},\dots ,R^*_n];[(bL_i,bR_i)_{i\le t},R^*_{t+1},\dots ,R^*_n])\\&\quad +\varDelta ([(bL_i,bR_i)_{i\le t},R^*_{t+1},\dots ,R^*_n];[(bL_i,bR_i)_{i\le t},bR_{t+1},\dots ,bR_n])\\&\le 2n\varepsilon _2(2^\ell +1)+\varepsilon _1+2n\varepsilon _2(2^\ell +1)\\&=\varepsilon _1+4n\varepsilon _2(2^\ell +1), \end{aligned}$$

which concludes the proof of statistical privacy.

Statistical Non-Malleability: Let T be an authorized set of size $t \ge 3$. Without loss of generality, we may assume that $T=\{1,2,\dots ,t\}$. Let $f_1, \ldots , f_t$ be the corresponding tampering functions. Let $s_1, \ldots , s_n \in \{0, 1\}^{k+p}$ be arbitrary strings, and let $\mathbf {s}= (s_1, \ldots , s_n)$.

Definition 23

We define the following partial tampering experiment $\textsf {IntTamp}^{T,f}_{\mathbf {s}}$.

• 1. For each $i \in [n]$, $(L_i, R_i) \leftarrow \mathbf {nmExt}^{-1}(s_i)$.

• 2. For each $i \in [n]$, let $S_i=(R_1, \ldots , R_{i-1}, L_i, R_{i+1}, \ldots , R_n)$.

• 3. For each $j \in [t]$, let $f_j$ be a function that maps $S_j$ to

  $$\begin{aligned} \widetilde{R}_1^{(j)}, \ldots , \widetilde{R}_{j-1}^{(j)}, \widetilde{L}_j, \widetilde{R}_{j+1}^{(j)}, \ldots , \widetilde{R}_n^{(j)}. \end{aligned}$$

• 4. Check whether $\widetilde{R}_i^{(j_1)} = \widetilde{R}_i^{(j_2)}$ for all distinct $i, j_1, j_2$ where $i \in [n]$, and $j_1, j_2 \in T$. If any of them is not true, then $\textsf {IntTamp}^{T,f}_{\mathbf {s}} = \bot$.

• 5. For each $i \ge 2$, let $\widetilde{R}_i = \widetilde{R}_i^{(1)}$, and let $\widetilde{R}_1 = \widetilde{R}_1^{(2)}$.

• 6. For each $i \in [t]$, if $L_i = \widetilde{L}_i$ and $R_i = \widetilde{R}_i$, then $\textsf {output}_i = \mathsf {same}^*$, else $\textsf {output}_i = \mathbf {nmExt}(\widetilde{L}_i,\widetilde{R}_i)$.

• 7. $\textsf {IntTamp}^{T,f}_{\mathbf {s}} = (\textsf {output}_1, \textsf {output}_2, \ldots , \textsf {output}_t)$.

We require the following auxiliary lemma.

Lemma 24

Let $\mathbf {nmExt}: \{0, 1\}^N \times \{0, 1\}^N \rightarrow \{0, 1\}^\ell$ be a $(k, \varepsilon , \tau )$ strong non-malleable two-source extractor. Also, let $h_1: \{0, 1\}^N \rightarrow {\mathcal Z}$, $h_2: \{0, 1\}^N \rightarrow {\mathcal Z}$, and $h_3: \{0, 1\}^N \rightarrow \{0,1\}$ be functions for some set ${\mathcal Z}$. For functions $F, G: \{0, 1\}^N \rightarrow \{0, 1\}^N$, let $\mathcal {A}_{F,G}$ be an algorithm that takes as input $x, y \in \{0, 1\}^N$, and does the following: If $h_1(x) \ne h_2(y)$, or if $h_3(y) = 1$, then output $\bot$, else if $F(x) = x$, and $G_j(y) = y$, output $\mathsf {same}^*$, else output $\mathbf {nmExt}(F(x), G(y))$. For X, Y uniform and independent in $\{0, 1\}^N$, we have that

$$ \varDelta := \varDelta \left( \mathbf {nmExt}(X,Y) \; ; \; U_\ell \; | \; Y, \; \mathcal {A}_{F, G}(X, Y)\right) \le \varepsilon + 2^{-\frac{N-k}{2}+1}. $$

Proof

The proof can be found in [1].    $\square$

Lemma 24 can be used to prove the following key component of our non-malleability proof.

Lemma 25

For any $\mathbf {s}, \mathbf {s}' \in \{0, 1\}^{n\ell }$ we have that

$$\begin{aligned} \textsf {IntTamp}^{T,f}_{\mathbf {s}}\; \approx _{n2^{\ell +1}\gamma } \; \textsf {IntTamp}^{T,f}_{\mathbf {s}'}, \end{aligned}$$

where $\gamma = \varepsilon + 2^{-\delta N/2+1}$.

Proof

We show that, for $\mathbf {s}= (s_1,s_2 \ldots , s_n)$, and $\mathbf {s}' = (s'_1, s_2, \ldots , s_n)$, we have

$$\begin{aligned} \textsf {IntTamp}^{T,f}_{\mathbf {s}}\; \approx _{2^{\ell +1}\gamma } \; \textsf {IntTamp}^{T,f}_{\mathbf {s}'}. \end{aligned}$$

The general result then follows by a hybrid argument using an analogous reasoning.

For $i = 2, \ldots , n$, let $(L_i, R_i) \leftarrow \mathbf {nmExt}^{-1}(s_i)$, and let $L_1^*, R_1^*$ be chosen independently and uniformly at random from $\{0, 1\}^N$. Fix $L_2, \ldots , L_n, R_2, \ldots , R_n$. Assume that we run Steps 3 to 7 of the $\textsf {IntTamp}^{T,f}_{\mathbf {s}}$ experiment described above, with $L_1, R_1$ replaced by $L_1^*, R_1^*$. We replace Step 5 by the following:

• For each $i \ne 2$, let $\widetilde{R}_i = \widetilde{R}_i^{(2)}$, and let $\widetilde{R}_2 = \widetilde{R}_2^{(3)}$,

i.e., we ensure that $\widetilde{R}_2, \ldots , \widetilde{R}_n$ are not a function of $L_1^*$. Notice that due to the consistency check in Step 4, the output of the tampering experiment remains the same. Then, recalling the variables we have fixed, it follows that $\widetilde{L}_1$ is a deterministic functions of $L_1^*$, and $\widetilde{R}_1, \ldots , \widetilde{R}_n, \widetilde{L}_2, \ldots , \widetilde{L}_n$ are deterministic functions of $R_1^*$. Define

$$\begin{aligned} h_1(L_1^*)&:=(\widetilde{R}_2^{(1)}, \ldots , \widetilde{R}_n^{(1)}),\\ h_2(R_1^*)&:= (\widetilde{R}_2^{(3)}, \widetilde{R}_3^{(2)}, \ldots , \widetilde{R}_n^{(2)}), \\ F(L_1^*)&:= \widetilde{L}_1,\\ G(R_1^*)&:= \widetilde{R}_1^{(2)}. \end{aligned}$$

Also, let $h_3(R_1^*) = 1$ if and only if any of the checks in Step 4 with $j_1, j_2 \ne 1$ (i.e., the checks that are not dependent on $L_1^*$) fail. We can now instantiate Lemma 24 with $h_1, h_2, h_3, F, G$ and the strong two-source non-malleable extractor from Lemma 10 to obtain

$$\begin{aligned} \varDelta (\mathbf {nmExt}(L_1^*,R_1^*); U_\ell \; | \; \mathcal {A}_{F,G}(L_1^*,R_1^*), L_2, \ldots , L_n, R_2, \ldots , R_n, R_1^*) \le \gamma \;. \end{aligned}$$

(2)

Let $(L'_1,R'_1)\leftarrow \mathbf {nmExt}^{-1}(s'_1)$, and observe that $\Pr [U_\ell = s]=2^{-\ell }$ for all s.

We now apply Lemma 3 to (2) by conditioning the right hand side of the statistical distance term in (2) on $U_\ell =s_1$. Since the remaining random variables on the right hand side are independent of $U_\ell$, they are unaffected by this conditioning. The corresponding conditioning on the left hand side of the statistical distance term in (2) is $\mathbf {nmExt}(L_1^*,R_1^*)=s_1$. Under this fixing, the tuple

$$\begin{aligned} (L_1^*,R_1^*),(L_2,R_2),\dots ,(L_n,R_n) \end{aligned}$$

is jointly distributed exactly as $(L_i,R_i)_{i=1,\dots ,n}$. Therefore, we can replace all occurrences of $L_1^*$ and $R_1^*$ by $L_1$ and $R_1$, respectively, on the left hand side of the statistical distance term in (2). Combining these observations with (2), Lemma 3, and the fact that $\Pr [U_\ell =s_1]=2^{-\ell }$, we conclude that

$$\begin{aligned} \varDelta (\mathcal {A}_{F,G}(L_1,R_1), R_1;\mathcal {A}_{F,G}(L^*_1,R^*_1),R^*_1|L_2, \ldots , L_n, R_2, \ldots , R_n)\le 2^\ell \gamma . \end{aligned}$$

Letting $(L'_1,R'_1)\leftarrow \mathbf {nmExt}^{-1}(s'_1)$, the same reasoning with $s'_1$ in place of $s_1$ and $(L'_1,R'_1)$ in place of $(L_1,R_1)$ leads to

$$\begin{aligned} \varDelta (\mathcal {A}_{F,G}(L^*_1,R^*_1), R^*_1;\mathcal {A}_{F,G}(L'_1,R'_1),R'_1|L_2, \ldots , L_n, R_2, \ldots , R_n)\le 2^\ell \gamma . \end{aligned}$$

Applying the triangle inequality yields

$$\begin{aligned} \varDelta (\mathcal {A}_{F,G}(L_1,R_1), R_1;\mathcal {A}_{F,G}(L'_1,R'_1),R'_1|L_2, \ldots , L_n, R_2, \ldots , R_n)\le 2^{\ell +1} \gamma , \end{aligned}$$

(3)

Observe that $\textsf {IntTamp}^{T,f}_{\mathbf {s}}$ and $\textsf {IntTamp}^{T,f}_{\mathbf {s}'}$ are deterministic functions of the left hand side and right hand side of (3), respectively. As a result, we conclude that

$$\begin{aligned} \textsf {IntTamp}^{T,f}_{\mathbf {s}}\; \approx _{2^{\ell +1}\gamma } \; \textsf {IntTamp}^{T,f}_{\mathbf {s}'}, \end{aligned}$$

as desired.   $\square$

We prove statistical non-malleability of our proposed construction with recourse to Lemma 25.

Theorem 26

The secret sharing scheme $(\mathbf {NMShare},\mathbf {NMRec})$ defined above is $\varepsilon$-non-malleable with respect to $\mathcal {F}_n^{split}$ for $\varepsilon =n(2^{\ell +1}\gamma +2^{-p})$, where $\gamma =\varepsilon _2+2^{-\delta N/2+1}$.

Proof

The proof can be found in [1].    $\square$

To conclude this section, we remark that we can instantiate Theorem 26 with concrete parameters to obtain a compiler that transforms regular secret sharing schemes into non-malleable ones. The blowup in the share length is logarithmic in the original share length and at most quasilinear in the number of parties n. The error for statistical privacy suffers an exponentially small additive blowup, while the error for non-malleability is exponentially small. Concrete instantiations can be found in [1].

3.2 Non-Malleability with Concurrent Reconstruction

In this section, we show that the secret sharing scheme described in Sect. 3.1 also satisfies the stronger notion of non-malleability with concurrent reconstruction as in Definition 18. Recall that in the concurrent reconstruction setting, the adversary is allowed to choose qualified sets $T_1,\dots ,T_\tau$ along with associated tampering functions $f^{(1)},\dots ,f^{(\tau )}$, and can observe the outcomes of the experiments $\varvec{\mathsf {STamper}^{{f^{(i)}}, {T_i}}_{{m}}}$ for $i\in [\tau ]$. We have the following result.

Theorem 27

Fix a number of parties n and an integer p. Furthermore, assume we have access to the following primitives:

• 1. For $\varepsilon _1 \ge 0$, let $(\mathbf {AShare}, \mathbf {ARec})$ be an $(n, \varepsilon _1)$-secret sharing scheme realizing an access structure $\mathcal {A}$ such that $|T|\ge 3$ holds whenever $T\in \mathcal {A}$. Suppose the corresponding shares lie in $\{0, 1\}^r$ and the secrets in some set $\mathcal {M}$;

• 2. Let $\mathbf {nmExt}:\{0, 1\}^N\times \{0, 1\}^N\rightarrow \{0, 1\}^{\ell }$ be the $(N-N^{\delta },\varepsilon _2,\tau )$ strong two-source non-malleable extractor from Lemma 11, where $\ell =r+p$. Hence, $\tau =N^{\delta }$, $\ell \le N^{\varOmega (1)}$, and $\varepsilon _2=2^{-N^{\varOmega (1)}}$.

Then, there exists an $(n, \varepsilon _1 + 4n\varepsilon _2(2^\ell +1))$-secret sharing scheme realizing access structure $\mathcal {A}$ that is $(\varepsilon ,\tau )$-concurrent-reconstruction-non-malleable w.r.t. $\mathcal {F}_{n}^{\text {split}}$, where

$$\begin{aligned} \varepsilon =n(2^{\ell +1}(\varepsilon _2 + 4\tau 2^\tau 2^{-N^\delta /4\tau }) + \tau \cdot 2^{-p}). \end{aligned}$$

The resulting scheme $(\mathbf {NMShare}, \mathbf {NMRec})$ shares an element of $\mathcal {M}$ into n shares, where each share contains n elements of $\{0, 1\}^N$. Finally, if the two primitives are efficient and the access structure $\mathcal {A}$ supports efficient membership queries, then the constructed scheme $(\mathbf {NMShare},\mathbf {NMRec})$ is also efficient.

The candidate scheme for Theorem 27 has been defined in Sect. 3.1, and statistical privacy is already proved there. We now present the proof of non-malleability, beginning with an auxiliary lemma which generalizes Lemma 24 to the case of multiple tamperings.

Lemma 28

Let $\mathbf {nmExt}: \{0, 1\}^N \times \{0, 1\}^N \rightarrow \{0, 1\}^\ell$ be an $(N-N^{\delta }, \varepsilon , \tau )$ strong non-malleable two-source extractor. Also, let $h_{1j}: \{0, 1\}^N \rightarrow {\mathcal Z}$, $h_{2j}: \{0, 1\}^N \rightarrow {\mathcal Z}$, and $h_{3j}: \{0, 1\}^N \rightarrow \{0,1\}$ for $1 \le j \le \tau$ be functions mapping to some set ${\mathcal Z}$. For functions $F_1,\dots ,F_\tau , G_1, \ldots , G_\tau : \{0, 1\}^N \rightarrow \{0, 1\}^N$, let $\mathcal {A}_{F_j,G_j}$ be an algorithm that takes as input $x, y \in \{0, 1\}^N$ and does the following: If $h_{1j}(x) \ne h_{2j}(y)$, or if $h_{3j}(y) = 1$, then output $\bot$, else if $F_j(x) = x$, and $G_j(y) = y$, output $\mathsf {same}^*$, else output $\mathbf {nmExt}(F_j(x), G_j(y))$. For X, Y uniform and independent in $\{0, 1\}^N$, we have that

$$\begin{aligned} \varDelta := \varDelta \left( \mathbf {nmExt}(X,Y) \; ; \; U_\ell \; | \; Y, \; \mathcal {A}_{F_1, G_1}(X, Y), \ldots , \mathcal {A}_{F_\tau , G_\tau }(X, Y)\right) \qquad \qquad \, \\ \le \varepsilon + 4\tau 2^\tau 2^{-N^\delta /4\tau }. \end{aligned}$$

Proof

The proof can be found in [1].    $\square$

Given a tuple of qualified sets $\mathbf {T}= (T_1, \ldots , T_\tau )$ and a tuple of associated tampering functions $\mathbf {f}=(f^{(1)},\dots ,f^{(\tau )})$, we define the intermediate tampering experiment for $\mathbf {T}$ as follows:

$$ \textsf {IntTamp}^{\mathbf {T},\mathbf {f}}_{\mathbf {s}} := \textsf {IntTamp}^{T_1,f^{(1)}}_{\mathbf {s}}, \ldots , \textsf {IntTamp}^{T_\tau ,f^{(\tau )}}_{\mathbf {s}}. $$

We may also denote the tampering function f associated to a reconstruction set $T\in \mathbf {T}$ by $f^{(T)}$. The following lemma is the main component of our proof of non-malleability with concurrent reconstruction. Its proof follows similarly to that of Lemma 25, but using Lemma 28 instead of Lemma 24.

Lemma 29

For any $\mathbf {s}, \mathbf {s}' \in \{0, 1\}^{n\ell }$ we have that

$$\begin{aligned} \textsf {IntTamp}^{\mathbf {T},\mathbf {f}}_{\mathbf {s}}\; \approx _{n2^{\ell +1}\gamma } \; \textsf {IntTamp}^{\mathbf {T},\mathbf {f}}_{\mathbf {s}'}, \end{aligned}$$

where $\gamma = \varepsilon _2 +4\tau 2^\tau 2^{-N^\delta /4\tau }$.

Proof

The proof can be found in [1].    $\square$

The following result states that statistical non-malleability holds for our proposed construction. The proof is similar to that of Theorem 26.

Theorem 30

The secret sharing scheme $(\mathbf {NMShare},\mathbf {NMRec})$ is $(\varepsilon ,\tau )$ concurrent reconstruction non-malleable with respect to $\mathcal {F}_n^{split}$ for $\varepsilon =n( 2^{\ell +1}\gamma +\tau 2^{-p})$, where $\gamma =\varepsilon _2 +4\tau 2^\tau 2^{-N^\delta /4\tau }$.

Proof

The proof can be found in [1].    $\square$

Similarly to Sect. 3.1, we can instantiate Theorem 27 with concrete parameters to obtain a compiler that transforms regular secret sharing schemes into ones satisfying non-malleability with concurrent reconstruction. The blowup in the share length is now polynomial in the original share length and the number of parties n. As before, the error for statistical privacy suffers an exponentially small additive blowup, while the error for non-malleability is exponentially small. Concrete instantiations can be found in [1].

4 Leakage-Resilient Secret-Sharing Scheme

In this section, we give a construction of a compiler that turns any secret sharing scheme into a leakage-resilient one. More precisely, we have the following result.

Theorem 31

Fix a number of parties n and $\rho \in (0,1)$. Furthermore, suppose we have access to the following primitives:

• 1. For any $\varepsilon _1 \ge 0$, let $(\mathbf {AShare}, \mathbf {ARec})$ be any $(n, \varepsilon _1)$-secret sharing scheme which shares an element of the set $\mathcal {M}$ into n shares of length $\ell$, and

• 2. Let $\mathsf {Ext}:\{0, 1\}^N \times \{0, 1\}^d \rightarrow \{0, 1\}^\ell$ be a strong $(k,\varepsilon _2)$-extractor such that

  $$\begin{aligned} \rho \le \frac{N-k}{(n-1)d+N}. \end{aligned}$$

  (4)

  Moreover, assume that $\mathsf {Ext}$ supports close-to-uniform preimage sampling, i.e., there is an efficient algorithm $\mathcal {S}$ such that the output of $\mathcal {S}$ on input z, denoted $\mathcal {S}(z)$, satisfies

  $$\begin{aligned} \mathcal {S}(z)\approx _{\varepsilon _3} D_z \end{aligned}$$

  (5)

  for every $z\in \{0, 1\}^\ell$, where $D_z$ is uniformly distributed over $\mathsf {Ext}^{-1}(z)$.

Then, there exists an $(n, \varepsilon _1+2 \varepsilon _2 \cdot n \cdot 2^{\ell n}+2n\cdot \varepsilon _3, \rho )$-leakage resilient secret sharing scheme realizing access structure $\mathcal {A}$.

Remark 1

Note that, in general, the preimage sampling algorithm $\mathcal {S}$ considered in Theorem 31 may fail to return an element of $\mathsf {Ext}^{-1}(z)$. In such a case, we say that $\mathcal {S}$ fails.

We describe our construction of the non-malleable secret sharing scheme $(\mathbf {LRShare}, \mathbf {LRRec})$.

• $\mathbf {LRShare}$: Our sharing function takes as input a secret $m \in \mathcal {M}$ and proceeds as follows:

  • 1. Share m using $\mathbf {AShare}$ to obtain $s_1, \ldots , s_n \leftarrow \mathbf {AShare}(m)$;

  • 2. For each $i \in [n]$, sample $(L_i,R_i)\leftarrow \mathcal {S}(s_i)$;

  • 3. If $\mathcal {S}(s_i)$ fails for some i, set $share_i=(\bot , s_i)$ for all $i\in [n]$;

  • 4. Else, for each $i \in [n]$ construct $share_i=(R_1, \ldots , R_{i-1}, L_i, R_{i+1}, \ldots , R_n)$;

  • 5. Output $(share_1, \ldots , share_n)$.

• $\mathbf {LRRec}$: Our reconstruction function takes as input shares $\{share_i : i \in T\}$ corresponding to an authorized set $T \in \mathcal {A}$ and proceeds as follows:

  • 1. Sort T so that $T = \{i_1, \ldots , i_t\}$, where $t = |T|$, and $i_j < i_{j+1}$;

  • 2. If $share_i$ contains $\bot$, then recover $s_{i_1},\dots ,s_{i_t}$ directly from $share_{i_1},\dots ,share_{i_t}$ and reconstruct $m \leftarrow \mathbf {ARec}(s_{i_1}, \ldots , s_{i_t})$;

  • 3. Else, for each $j \in [t]$ obtain $L_j$ from $share_j$ and $R_j$ from $share_k$ for some $k \in T \setminus \{j\}$, and compute $s_j = \mathsf {Ext}(L_j, R_j)$. Reconstruct $m \leftarrow \mathbf {ARec}(s_{i_1}, \ldots , s_{i_t})$;

  • 4. Output m.

The proof of Theorem 31 has a similar structure to the proof of statistical privacy in Sect. 3.1, but some additional care must be taken to deal with the leakage. It can be found in [1]. We also study the tradeoff between share-length and leakage rate we can achieve via the compiler using linear strong extractors in [1].

5 Threshold Signatures

(n, t)-Threshold signatures, introduced by Desmedt [12], allow to distribute the secret key of a signature scheme among n players such that any subset of t players can sign messages. Threshold signatures exist based on the RSA [23] and discrete logarithm [7] problems.

Definition 32

(Threshold Signature Scheme [23]). An (n, t)-threshold signatures scheme is defined by a tuple of algorithms $(\mathbf {TGen}, \mathbf {TSign}, \mathbf {TRec}, \mathbf {TVerify})$. The key generation algorithm $\mathbf {TGen}$ takes the security parameter $1^\lambda$ as input and outputs a verification key $vk$ and secret keys $sk_1, \dots , sk_n$. The (possibly interactive) signing algorithm $\mathbf {TSign}$ takes a secret key $sk_i$ and a message $m \in \mathcal {M}$ as input and after potentially interacting with the other parties it outputs a signature share $\sigma _i$. The reconstruction algorithm $\mathbf {TRec}$ takes the verification key $vk$, any t signature shares, and outputs a signature $\sigma$. The verification algorithm $\mathbf {TVerify}$ takes a signature $\sigma$, a message m, and a verification key $vk$ as input and outputs a bit $b \in \{0,1\}$. We call a threshold signature scheme secure if the following holds:

• 1. Correctness. Any authorized set of parties can generate a valid signature. That is, for any set $T = \{i_1, \ldots , i_t\}$ of size at least t and for any $m \in \mathcal {M}$, it holds that

  $$ \Pr [\mathbf {TVerify}(vk, \mathbf {TRec}(vk, \sigma _{i_1}, \dots , \sigma _{i_t}), m) = 1] = 1, $$

  where $\sigma _i \leftarrow \mathbf {TSign}(sk_i, m)$ and $(vk, sk_1, \dots , sk_n) \leftarrow \mathbf {TGen}(1^\lambda )$.

• 2. Unforgeability. No collusion of unauthorized parties can forge a signature. More formally, we consider a probabilistic polynomial time adversary $A$, who can corrupt up to $t-1$ parties to learn their secret keys. The adversary may, on behalf of the corrupt parties, engage in a polynomial number of (possibly interactive) signature share generations with the honest parties for messages of its choice. Let Q be the set of messages that the adversary signs in this fashion. We require that the probability of $A$ outputting a valid message signature pair $(m^*, \sigma ^*)$ with $m^* \not \in Q$ is negligible in $\lambda$.

In this work we extend the notion of threshold signatures in two directions. We propose non-malleable as well as leakage-resilient threshold signatures. These two separate notions require that a threshold signature scheme remains secure even if tampering or leakage on the secret keys of each player occurs. Throughout this section we assume a asynchronous communication network with eventual delivery. In such a network each message can be delayed arbitrarily, but it is guaranteed that any sent message eventually arrives at its destination. We also assume that any pair of parties is connected by a secure point-to-point channel.

5.1 Non-Malleable Threshold Signatures

A non-malleable threshold signature scheme requires that even an adversary, who obtains a polynomial number of signature shares under tampered keys for messages of its choice, may not produce a valid forgery. We model this security guarantee as follows:

Definition 33

(Non-Malleable Threshold Signature Scheme). Let

$$\begin{aligned} \mathcal {S}= (\mathbf {NMTGen}, \mathbf {NMTSign}, \mathbf {NMTRec},\mathbf {NMTVerify}) \end{aligned}$$

be a secure threshold signature scheme according to Definition 32. Let $\mathcal {F}$ be some family of tampering functions. For each $f \in \mathcal {F}$, and any probabilistic polynomial time adversary A, define the tampering experiment

where the oracle $\widetilde{\mathcal {O}}( \cdot ) = (\mathbf {NMTSign}(\widetilde{sk}_1, \cdot ), \dots , \mathbf {NMTSign}(\widetilde{sk}_n, \cdot ))$ allows the adversary to obtain a polynomial number of (honestly generated) signature shares generation for messages of its choice. Let Q be the set of messages that $A$ queries to $\widetilde{\mathcal {O}}$. We say $\mathcal {S}$ is non-malleable w.r.t. $\mathcal {F}$ if for all $f \in \mathcal {F}$

$$ \Pr [\mathbf {NMTVerify}(vk, \mathbf {TRec}(vk, \sigma ^*, m^*) = 1 \ \wedge \ m^* \not \in Q] \le \mathsf {negl}(\lambda ). $$

Our construction follows the same blueprint as our non-malleable secret sharing schemes.

Theorem 34

For any number of parties $n \ge 2t+1$ and threshold t, if we have the following primitives:

• 1. A non-interactive² secure (n, t)-threshold signatures scheme $(\mathbf {TGen}, \mathbf {TSign}, \mathbf {TRec}, \mathbf {TVerify})$.

• 2. A coding scheme $(\mathbf {NMEnc}, \mathbf {NMDec})$ that is $\varepsilon$-non-malleable w.r.t $\mathcal {F}_{2}^{\text {split}}$, where $\varepsilon \le \mathsf {negl}(\lambda )$.

then there exists a non-malleable threshold signature scheme w.r.t. $\mathcal {F}_n^{split}$.

We construct a non-malleable threshold signature scheme $\mathcal {S} = (\mathbf {NMTGen}, \mathbf {NMTSign}, \mathbf {NMTRec}, \mathbf {NMTVerify})$ as follows.

• $\mathbf {NMTGen}$: Our key generation function takes the security parameter $1^\lambda$ as its input and proceeds as follows:

  • 1. $(vk, sk'_1, \dots , sk'_n) \leftarrow \mathbf {TGen}(1^\lambda )$

  • 2. For each $i \in [n]$, encode the key $sk'_i$ to obtain $(L_i, R_i) \leftarrow \mathbf {NMEnc}(sk'_i)$;

  • 3. For each $i \in [n]$, construct $sk_i=(R_1, \ldots , R_{i-1}, L_i, R_{i+1}, \ldots , R_n)$;

  • 4. Output $(vk, sk_1, \ldots , sk_n)$.

• $\mathbf {NMTSign}$: Party i with secret $sk_i=(R_1, \ldots , R_{i-1}, L_i, R_{i+1}, \ldots , R_n)$ constructs its signature share as follows:

  • 1. Request $R_i$ from all other parties and wait for the first $n-t$ responses $(R^1_i, \dots , R^{n-t}_i)$.

  • 2. Check whether $R^1_i = \dots = R^{n-t}_i$ and output $\bot$ if not.

  • 3. Reconstruct the secret key $sk' \leftarrow \mathbf {NMDec}(L_i, R^1_i)$ and output $\bot$ if $sk' = \bot$.

  • 4. Compute signature share $\sigma _i \leftarrow \mathbf {TSign}(sk'_i, m)$.

  • 5. Output $\sigma _i$.

• $\mathbf {NMTRec}$: Given verification key $vk$ and signature shares $\sigma _{i_1}, \dots , \sigma _{i_{t}}$, we construct a signature as follows:

  • 1. $\sigma \leftarrow \mathbf {TRec}(vk, \sigma _{i_1}, \dots , \sigma _{i_t})$.

  • 2. Output $\sigma$.

• $\mathbf {NMTVerify}$: Given verification key $vk$, signature $\sigma$, and message m, we do the following:

  • 1. $b \leftarrow \mathbf {TVerify}(vk, \sigma , m)$.

  • 2. Output b.

Notice that the way $\mathbf {NMTSign}$ is formulated now, a single tampered share can make the protocol output $\bot$. If this is undesirable, the two first steps in $\mathbf {NMTSign}$: can be replaced by

• 1. Request $R_i$ from all other parties and collect responses $R_i^1, R_i^2, \ldots$.

• 2. If and when a subset of the responses of size $n-t$ are all identical to some $R_i$, use this $R_i$ in the following steps.

In an asynchronous network with eventual delivery, all $n-t$ honest parties will eventually get the request for $R_i$ and send their value. Therefore party i eventually receive all these $n-t$ shares (and possibly some corrupted shares too). Therefore, if there is no tampering, then party i will eventually receive $n-t$ copies of the correct share. In all cases party i will hear from at least one honest party as in the original scheme, so security follows along the lines of the security for the original scheme. We present the analysis for the original scheme in [1], which yields Theorem 34.

5.2 Leakage-Resilient Threshold Signatures

In a leakage-resilient threshold signature scheme, the adversary may obtain an unqualified subset of secret keys and a bounded amount of leakage from all other secret keys. Even given this information, we require that the adversary may not be able to output a valid forgery.

Definition 35

(Leakage-Resilient Threshold Signature Scheme). Let $\mathcal {S} = (\mathbf {LTGen}, \mathbf {LTSign}, \mathbf {LTRec},\mathbf {LTVerify})$ be a tuple of probabilistic polynomial time algorithms. Let $\mathcal {F}$ be a family of leakage functions. For each $f \in \mathcal {F}$, and any probabilistic polynomial time adversary A, define the following experiment

where the oracle $\mathcal {O}( \cdot )$ allows the adversary, on behalf of the corrupted parties, to engage in a polynomial number of (possibly interactive) signature shares generation for messages of its choice. Let Q be the set of messages that $A$ queries to $\mathcal {O}$. We say $\mathcal {S}$ is leakage-resilient w.r.t. $\mathcal {F}$ if for all $f \in \mathcal {F}$

$$ \Pr [\mathbf {NMTVerify}(vk, \mathbf {TRec}(vk, \sigma ^*, m^*) = 1 \ \wedge \ m^* \not \in Q] \le \mathsf {negl}(\lambda ). $$

Building upon our previous results, we construct a leakage-resilient threshold signature scheme.

Theorem 36

For any number of parties $n \ge 2t+1$ and threshold t, if we have the following primitives:

• 1. A non-interactive secure (n, t)-threshold signatures scheme $(\mathbf {TGen}, \mathbf {TSign}, \mathbf {TRec}, \mathbf {TVerify})$.

• 2. A two-source $(n-\ell -\log 1/\varepsilon , 2\varepsilon )$-extractor $\mathbf {nmExt}$ with efficient preimage sampling from the space $\mathcal {X}= \{0,1\}^n$, where $\varepsilon \le \mathsf {negl}(\lambda )$.

then the construction from Theorem 34, where we replace each call to $\mathbf {NMEnc}$ with $\mathbf {nmExt}^{-1}$ and each call to $\mathbf {NMDec}$ with $\mathbf {nmExt}$, is a leakage-resilient threshold signature scheme w.r.t. $\mathcal {F}_{\ell ,n}^{split}$, where $\mathcal {F}_{\ell ,n}^{split}$ is the set of leakage functions that tamper with each share independently and the output of each tampering function is bounded in size by $\ell$ bits.

Proof

The proof can be found in [1].    $\square$