Adaptive Extractors and Their Application to Leakage Resilient Secret Sharing

Abstract

We introduce Adaptive Extractors, which unlike traditional randomness extractors, guarantee security even when an adversary obtains leakage on the source after observing the extractor output. We make a compelling case for the study of such extractors by demonstrating their use in obtaining adaptive leakage in secret sharing schemes.

Specifically, at FOCS 2020, Chattopadhyay, Goodman, Goyal, Kumar, Li, Meka, Zuckerman, built an adaptively secure leakage resilient secret sharing scheme (LRSS) with both rate and leakage rate being $\mathcal {O}(1/n)$, where $n$ is the number of parties. In this work, we build an adaptively secure LRSS that offers an interesting trade-off between rate, leakage rate, and the total number of shares from which an adversary can obtain leakage. As a special case, when considering t-out-of-n secret sharing schemes for threshold $t = \alpha n$ (constant $0<\alpha <1$), we build a scheme with a constant rate, constant leakage rate, and allow the adversary leakage from all but $t-1$ of the shares, while giving her the remaining $t-1$ shares completely in the clear. (Prior to this, constant rate LRSS scheme tolerating adaptive leakage was unknown for any threshold.)

Finally, we show applications of our techniques to both non-malleable secret sharing and secure message transmission.

1 Introduction

Randomness extractors [28] are a fundamental primitive in the world of theoretical computer science, which have found widespread applications in derandomization techniques, cryptography, and so on. A randomness extractor $\mathsf {Ext}$ is a function that takes as input an n-bit entropic source W, a uniformly random d-bit string S (seed) and outputs $\mathsf {Ext}(W;S)$ such that $\mathsf {Ext}(W;S)$ “looks uniform” to an unbounded eavesdropper $\mathsf {Eve}$ even given the seed S. Unfortunately, the standard notion of extractors offers no guarantees whatsoever if the adversary $\mathsf {Eve}$ obtains some information about W, after observing, the output of the extractor. In this work, we address this gap.

Does the security of extractors hold even after the adversary obtains some information on W, “after the fact”?

Naturally, we have to be careful about what information $\mathsf {Eve}$ can learn about W and S, after the fact. For instance, the function f, which on input w, s and the extractor challenge y, outputs 1 if and only if $y=\mathsf {Ext}(w;s)$, is an after the fact leakage function, which can break extractor security, with high probability, with only 1 bit of leakage. Hence, one needs to define the leakage function family carefully.

In this work, we introduce the notion of adaptive extractors with respect to an after the fact leakage family $\mathcal {F}$. Formally, we say that an extractor is an adaptive extractor with respect to a function family $\mathcal {F}$, if for each $f \in \mathcal {F}$, an adversary cannot (statistically) distinguish $(S,f(W,\mathsf {Ext}(W;S)),\mathsf {Ext}(W;S))$ from (S, f(W, U), U). Our notion of adaptive extractors can be seen as a generalization of exposure-resilient extractors introduced by Zimand [33] (Zimand’s extractors allow the adversary to adaptively learn up to $n^\delta$ bits of the source, for some $\delta <1$ bits; the adversary can determine which bits to query based on an arbitrary function of the extractor output.), and of the notion of adaptive non-malleable extractors introduced by Aggarwal et al. in [2] (where adaptive non-malleability particularly guarantees that the adversary cannot distibuish between $(S, \mathsf {Ext}(W;g(S,\mathsf {Ext}(W;S))), \mathsf {Ext}(W;S))$ and $(S, \mathsf {Ext}(W;g(S,U)), U)$). We then observe that every randomness extractor is also an adaptive extractor with respect to a leakage family depending arbitrarily on the source and the output, with some loss in parameters. We note that this observation is similar to how the authors in [2, Lemma 3.5] show that every non-malleable extractor is adaptive non-malleable, with some loss in parameters. We demonstrate that, in spite of the loss in parameters that adaptivity incurs, such extractors can be powerful. In particular, we use them to build constant-rate secret sharing schemes resilient to adaptive leakage. We now describe these contributions in greater detail.

Secret Sharing. Secret sharing schemes [10, 30] are a fundamental cryptographic primitive and have many applications, such as in multi-party computation [7, 14], and leakage-resilient circuit compilers [19, 23, 29]. These are cryptographic primitives that allow a dealer to distribute a secret to $n$ parties, such that only an authorized subset of parties can reconstruct the original secret and any unauthorized set of parties have no information about the underlying secret (privacy). For instance, in a $t-$out-of-$n$ threshold secret sharing scheme, there are n parties, and any collection of t ($t \le n$) or more parties would correspond to an authorized set, and any collection of less than t parties would be unauthorized. Note that an implicit assumption is that the unauthorized set of parties has no information about secrets of the remaining shares. A rich study on leakage attacks initiated by Kocher [24] tells us that this is an idealized assumption that may not hold in practice. Such leakage can be dangerous and completely break the security of the underlying primitive¹.

Leakage Resilient Secret Sharing (LRSS). Dziembowski and Pietrzak in [17] introduced the problem of leakage resilience in secret sharing schemes. This problem has received much attention (for example, [1, 3, 9, 12, 15, 18, 20, 25, 27, 31],  [11, 13]), wherein researchers have strived to improve various parameters such as its rate (defined as (message length)/(length of longest share)), leakage model as well as leakage rate (defined as (number of bits of leakage allowed)/(the size of a share)).

At a high level, in an LRSS, the adversary is allowed leakage on shares of the secret. This is captured by permitting the adversary to specify functions $\ell _1, \ell _2, \ldots ,$ and receive, in response, $\ell _i(sh_i)$ (where $sh_i$ denotes the $i^{\text {th}}$ share). Informally, security of an LRSS requires that privacy should hold even given this leakage. In our work, we explore the stronger setting where the adversary specifies which share to receive leakage from, in an adaptive manner - i.e., the adversary specifies $i, \ell _i$ and upon learning $\ell _i(sh_i)$, it may make the next leakage query by specifying $j,\ell _j$. In this adaptive leakage setting², the construction of [13] achieved a rate of $\mathcal {O}(1/n)$ as well as a leakage rate of $\mathcal {O}(1/n)$. A consequence of this is that there currently does not exist a scheme with constant rate and leakage rate for any threshold in this strong leakage model, whereas we do know of such constructions for the non-adaptive leakage model. Our work fills this gap precisely.

1.1 Our Results

Our first and main result on the LRSS scheme in the adaptive leakage model is as follows. Here n denotes the number of parties, t denotes the threshold and $l$ denotes the message length.

Result 1: We build an LRSS scheme, tolerating $\psi$ adaptive queries, each dependent on $X$ shares (with $\psi \cdot X\le n- t +1$) and the reveal of the remaining $t-1$ shares, such that it achieves a rate of $(X^{\varTheta (\psi X/t)})^{-1}$, while allowing $\varTheta (l)$ bits of leakage per query, for threshold access structures. In particular, for a constant $X$ and $n= \varTheta (t)$, this gives the first constant-rate adaptive LRSS scheme for the threshold access structure. Finally, we also generalize our constructions to the first constant-rate adaptive LRSS for general access structures.

Further, in the full version of our paper, we also show the following applications of our LRSS scheme.

Result 2: As an application of our LRSS, we show compilers to get a leakage resilient non-malleable secret sharing (LRNMSS) scheme (which are LRSS schemes, additionally resilient to tampering attacks), and an information-theoretic secure message transmission protocol (SMT), tolerant against leakage and tampering attacks. The rates of both these schemes translate appropriately from the rate of the LRSS. In particular, for a constant LRSS, we get constant-rate schemes for both LRNMSS and SMTs.

1.2 Our Techniques

We begin by describing the leakage model for LRSS and then give a technical overview of our scheme. For simplicity, we provide our technical overview for threshold access structures (which we can extend to general access structures as well). Let t denote the threshold and $n$, the number of parties.

Leakage Model. We allow the adversary to obtain adaptive leakage on $n- (t-1)$ shares and then reveal the full shares of the remaining $t-1$ shares. Each adaptive query can be on a set of at most $X$ shares (where X is some value between 1 and $t-1$), and different queries must be on sets that are disjoint from the prior queries. For the purposes of this exposition, we make the following restriction to our model: we assume that the adversary makes adaptive queries but only on a single share each time, i.e., it doesn’t make any leakage query on multiple shares.

Warm-up Construction. To motivate our construction, we consider the following modification³ of a construction due to Srinivasan and Vasudevan in [31, Section 3.2.1]. Take any t-out-of-n secret sharing scheme $(\mathsf {MShare},\mathsf {MRec})$ and then do as follows:

• Sample shares $(m_1,..,m_n)$ of the message m using $\mathsf {MShare}$.

• Choose an extractor seed s and split s into $(sd_1,..,sd_n)$ using a t-out-of-n secret sharing scheme.

• Now, for every $m_i$, choose an extractor source $w_i$ uniformly and compute $y_i = m_i \oplus \mathsf {Ext}(w_i; s)$.

• Finally, output the final shares $\{sh_{i}\}$ as $\{(w_i,y_i,sd_i)\}$.

For now, consider a weak model, where the adversary obtains only non-adaptive and independent leakage from a total of (say) $t-1$ shares, in addition to $t-1$ full shares. The hope is to show that the $t-1$ leakage queries are independent of the message shares $m_i$, following which the privacy of $\mathsf {MShare}$ can be used to get the $t-1$ full shares. One might hope to show this independence of leakage from the $m_i$’s, using the security of the extractor as follows: Pick $sd_i$ uniformly at random and independent of s; then the leakage function on $\{sh_{i}\}$, can be answered as an auxiliary leakage query on the source $w_i$. Once s is revealed in the extractor security game, the reduction can pick the other $sd_j$ values in a consistent manner. However, this proof strategy has a flaw. For extractor security, it is important that the auxiliary leakage query on w is independent of s; however, there is a dependence on s via $y_i$. In other words, it is unclear how to prove that this construction satisfies leakage resilience even in a weak model where the adversary obtains leakage only independently and non-adaptively.

Fortunately, with adaptive extractors, we can show that this construction is secure not only in this weak model but also in a stronger model where the adversary is allowed to leak from $t-1$ shares adaptively, before receiving $t-1$ full shares. Furthermore, this construction even has a constant rate! The high-level idea of security is as follows. We wish to reduce the adaptive leakage queries on the shares to an adaptive extractor leakage query. Since the adaptive leakage query on $w_j$ cannot depend on the seed, we need to first show that the share $sd_j$ in the corresponding query is independent of the seed s. Indeed, using the privacy of secret sharing⁴, we can show that for the first $t-1$ queries, the shares $sd_j$ in $sh_j$ can be replaced with shares of 0 (hence removing the dependence on s). Then, using the adaptive extractor security, we can replace the $y_j$’s (for the first $t-1$ queries) with uniform, where the leakage can be asked on the $w_j$’s. Now, the privacy of $\mathsf {MShare}$ can be invoked to get the $t-1$ full shares.

Main Construction. Our next goal is to leverage adaptive extractors to go beyond leaking from just $t-1$ shares. The main bottleneck is that for any subsequent leakage query (beyond $t-1$), the $sd_j$’s will reveal s, and hence the adaptive leakage query on subsequent $w_j$’s will no longer remain independent of the seed s. Thus, extractor security fails. This is the challenge we must address to achieve our main result where the adversary is allowed to obtain adaptive leakage on $n-(t-1)$ shares (in total) and reveal $t-1$ of the remaining shares.

One approach to facilitating leakage from more than $t-1$ shares could be to use independent extractor seeds to extract independent random masks. Consider the following modification of the above construction: mask the share of a message $m_i$ not just with one extractor output but with many. In particular, let $y_i = m_i \oplus \mathsf {Ext}(w_i; s^1) \oplus \mathsf {Ext}(w_i; s^2) \ldots \oplus \mathsf {Ext}(w_i; s^h)$, for some parameter h, where $s^1 \ldots s^h$ are independent seeds. We might hope that because we are using h seeds, we could hope to leak from $h(t-1)$ shares and use the security of each seed per batch of $t-1$ shares. Unfortunately, this doesn’t work for the following reason: reconstruction is only possible if we recover all h seeds. This means that we ultimately need to somehow share all the seeds in a manner where they can be reconstructed from $t-1$ shares. In other words, once we leak from $t-1$ shares, we can no longer argue security by leveraging any of the seeds because they can all be reconstructed from $t-1$ shares. We overcome this challenge by carefully using a multi-layered approach for both masking the message shares as well as for reconstructing the seeds.

Construction Overview:

• 1. Pick h extractor seeds $s^1, \ldots , s^h$ and $hn$ extractor sources $w_1^1, \ldots w_1^h, \ldots , w_n^1$, $\ldots ,w_n^h$.

• 2. Secret share each of the h seeds using a t-out-of-$n$ secret sharing scheme to obtain shares; let the share of $s^j$ be $sd_1^j, \ldots , sd_n^j$

• 3. Each share $m_j$ is masked using the h seeds in a layered manner as follows:

  • (a) In level $h+1$: Set $y_j^{h+1} = m_j$.

  • (b) For every subsequent lower level $i (i\ge 1)$, compute $x_j^{i} = y_j^{i+1} \oplus \mathsf {Ext}^i(w_j^i; s_i)$ and set $y_j^{i} = (x_j^{i} || sd_j^i).$ [Note that we use a different extractor per-level since the length of the extractor outputs (and the length of $y_j^i$s they mask) increase with level.]

    Finally set $Sh_j = (w^1_j,\cdots ,w^h_j,y^1_j)$.

• 4. Output $(Sh_1,\cdots ,Sh_n)$

A pictorial representation of the construction can be found in Fig. 1. In order to give an overview of the proof, we first recall that we are in a setting where each adaptive query of an adversary is a query on a single share – we can extend our results to the case of joint leakage but, for the sake of simplicity, we don’t focus on that for now.

Fig. 1.

The main construction. (Color figure online)

At a high-level, the idea of the security proof is that we view the leakage queries in batches of $t-1$ queries. For the first set of $t-1$ queries, we rely on the adaptive security of the extractor outputs evaluated using seed $s^1$ and, in particular, all of these outputs can be replaced by uniform. (This also relies on the adaptive privacy of the secret sharing scheme, a notion we define and instantiate.) For the second set of $t-1$ queries, we can no longer assume that $s^1$ is hidden, since we can not use the privacy of the secret sharing scheme any more. However, two things come to our rescue: first, the second batch of queries helps unmask at most $t-1$ shares of $s^2$ and therefore, adaptive extractor security on seed $s^2$ can be leveraged; second, the extractor outputs $\mathsf {Ext}(w_j^1; s^1)$ (where j was a share that was leaked from in the first batch) continue to remain uniform. The reason for the latter is that all extractor sources are uniformly chosen, and our model requires a disjoint set of indices to be leaked from across batches. In short, for the first batch of queries, we use adaptive security of the extractor outputs evaluated on the first seed and, for every subsequent batch, we move to argue extractor security using the subsequent seed. Since we have h independent seeds, we can do this h times and therefore answer h batches of queries, i.e., we can obtain leakage on $h(t-1)$ shares.

1.3 Related Work

We first list out some of the parameters that are relevant to LRSS schemes:

• Rate: This is defined as $\frac{\mathsf {message length}}{\mathsf {share length}}$.

• Global Limit: This refers to the total number of shares on which the leakage queries can depend on.

• Per-query Limit: This refers to the number of shares that a specific query can depend on.

• Per-query Leakage Rate: This is the ratio of the total allowable leakage from a single leakage query to the size of a share.

The problems of leakage resilient and non-malleable secret sharing have seen a flurry of activity in recent times [1, 5, 9, 11,12,13, 18, 20, 25,26,27, 31]. Here we compare our work with only the most relevant works in this area. The only prior LRSS schemes allowing for a joint and adaptive leakage model are [13, 25]. While our model allows adaptive queries on up to $n-t+1$ shares, each dependent on at most $X$ shares (where $X$ is some value between 1 and $t-1$), before fully revealing the remaining $t-1$ shares, [13] allows adaptive queries on all $n$ shares, each dependent on at most $t-1$ shares before revealing $t-1$ full shares. Both the schemes require the adaptive queries to be on disjoint sets of shares. However, our scheme/analysis offers a more fine-grained trade-off between the various parameters and allows us to obtain better results for certain settings. In particular, when we consider the instance where X is constant (and $t = \alpha n$, for a constant $\alpha < 1$), we get a constant-rate adaptive LRSS achieving a constant leakage rate, while [13] gets a rate and leakage rate of $\mathcal {O}(1/n)$ each, in all instances. To put this in context, even if [13] makes independent adaptive leakage queries on all shares, their rate is $\mathcal {O}(1/n)$ and the maximum number of bits they can leak is at most a constant fraction of the size of a single share, while we can leak close $(n-t+1)$ times a constant fraction of the size of a single share!

The work of [13] also consider a variant of joint leakage, allowing overlap of the query sets, the detailed parameters of which are given in Table 1. We give a detailed comparison of the parameters achieved by the various schemes in Table 1, for the threshold setting with $t = \alpha n$ (for a constant $\alpha < 1$).

Table 1. LRSS prior work

• *All works mentioned here are information-theoretic. We write all comparisons for the threshold setting with threshold $t = \alpha n$ (where $\alpha < 1$ is a constant and $n$ denotes the total number of parties).

• ** For our result, the unauthorized queries cannot overlap with the leakage queries.

• c is a small constant and $l_{msg}$ is the message length.

• All schemes (except the joint overlapping schemes of [13] (threshold and n-out-of-n) actually work for general access structures.

• Full Shares: Number of complete shares that an adversary can see (at the end of all leakage queries, in the adaptive schemes).

Open Problems. We believe that it would be interesting to explore the direction of building adaptive extractors against restricted classes of leakage families such as those captured by computational/bounded depth circuits, local functions, etc.

1.4 Organization of the Paper

We provide the preliminaries and definitions in Sect. 2. Then, we define and build adaptive extractors in Sect. 3. We define and build leakage resilient secret sharing schemes in Sect. 4.

2 Preliminaries and Definitions

2.1 Notation

We denote the security parameter by $\kappa$. For any two sets S and $S'$, $S\backslash S'$ denotes the set of elements that are present in S, but not in $S'$. For any natural number n, [n] denotes the set $\{1,2,\cdots ,n\}$ and [0] denotes a null set. $s\in _RS$ denotes uniform sampling from set S. $x\leftarrow X$ denotes sampling from a probability distribution X. The notation $\Pr _{X}[x]$ denotes the probability assigned by X to the value x. x||y represents concatenation of two binary strings x and y. |x| denotes length of binary string x. $U_{l}$ denotes the uniform distribution on $\{0,1\}^l$. All logarithms are base 2. If S is a subset of [n] :

• If $x_1,..,x_n$ are some variables or elements, then $x_{S}$ denotes the set $\{x_i \text { such that } i\in S\}$.

• For some function f outputting n values $y_1,\cdots ,y_n$ on input x, $f(x)_S$ denotes $(y_i)_{i \in S}$.

• If $T_1,..,T_n$ are sets, then $T_{S}$ denotes the union $\cup _{i\in S} T_i$.

Statistical Distance. Let $X_1,X_2$ be two probability distributions over some set S. Their statistical distance is

(they are said to be $\varepsilon$-close if $\mathbf {SD}\left( {X_1, X_2} \right) \le \varepsilon$ and denoted by $X_{1}\approx _{\varepsilon }X_{2}$).

For an event E, $\mathbf {SD}_{E}{(A;B)}$ denotes $\mathbf {SD}\left( {A|E ; B|E} \right)$.

Entropy. The min-entropy of a random variable W is ${\mathbf {H}_{\infty }}(W) = -\log (\max _{w}\Pr [W=w])$.

For a joint distribution (W, Z), following  [16], we define the (average) conditional min-entropy of W given Z as

$${\widetilde{\mathbf {H}}_{\infty }}(W\mid Z) = -\log (\mathop {\mathbf {E}}\limits _{e\leftarrow Z}(2^{-{\mathbf {H}_{\infty }}(W\mid Z=z)}))$$

(here the expectation is taken over e for which $\Pr [E=e]$ is nonzero).

For any two random variable W, Z, (W|Z) is said to be an $(n,t')$-average source if W is over $\{0,1\}^{n}$ and ${\widetilde{\mathbf {H}}_{\infty }}(W|Z)\ge t'.$

We require some basic properties of entropy and statistical distance, which are given by the following lemmata.

Lemma 1

 [16] Let A, B, C be random variables. Then if B has at most $2^\lambda$ possible values, then ${\widetilde{\mathbf {H}}_{\infty }}(A\mid B)\ge {\mathbf {H}_{\infty }}(A, B)-\lambda \ge {\mathbf {H}_{\infty }}(A)-\lambda$ and, more generally, ${\widetilde{\mathbf {H}}_{\infty }}(A\mid B,C)\ge {\widetilde{\mathbf {H}}_{\infty }}(A, B \mid C)-\lambda \ge {\widetilde{\mathbf {H}}_{\infty }}(A\mid C)-\lambda$.

Lemma 2

 [32] For any random variables A, B,  if $A\approx _{\epsilon } B$, then for any function f, $f(A)\approx _{\epsilon } f(B).$

Lemma 3

For any random variables A, B over $\mathcal {A}$, and events $E,E'$ with non-zero probabilities,

$$\mathbf {SD}\left( {A\wedge E , B\wedge E'} \right) \le |\Pr [E]-\Pr [E']| + \Pr [E']\cdot \mathbf {SD}\left( {A| E , B| E'} \right) $$

where,

and

Lemma 4

[4] Let $X,Y,X',Y'$ be random variables such that $\mathbf {SD}\left( {(X,Y), (X',Y')} \right) \le \epsilon$ and S be any set such that $\Pr [Y\in S ]>0$ and $\Pr [Y'\in S] >0$, then

$$\mathbf {SD}\left( {X|Y\in S , X'|Y'\in S} \right) \le \frac{2\epsilon }{\Pr [Y'\in S]}$$

2.2 Secret Sharing Schemes

Secret sharing schemes provide a mechanism to distribute a secret into shares such that only an authorized subset of shares can reconstruct the secret and any unauthorized subset of shares has “almost” no information about the secret. We now define secret sharing schemes formally.

Definition 1

Let $\mathcal {M}$ be a finite set of secrets, where $|\mathcal {M}| \ge 2$ . Let $[n]$ be a set of identities (indices) of $n$ parties. A sharing function $\mathsf {Share}:\mathcal {M}\rightarrow (\{0,1\}^l)^n$ is a $(\mathcal {A}, n, \epsilon _s)$- secret sharing scheme with respect to a monotone access structure⁵ $\mathcal {A}$ if the following two properties hold :

• 1. Correctness: The secret can be reconstructed by any set of parties that are part of the access structure $\mathcal {A}$. That is, for any set $T \in \mathcal {A}$, there exists a deterministic reconstruction function $\mathsf {Rec}: (\{0,1\}^l)^{|T|} \rightarrow \mathcal {M}$ such that for every $m \in \mathcal {M}$,

  $$\Pr [\mathsf {Rec}(\mathsf {Share}(m)_{T} ) = m] = 1$$

  where the probability is over the randomness of the $\mathsf {Share}$ function and if $(sh_1,..,sh_n) \leftarrow \mathsf {Share}(m)$, then $\mathsf {Share}(m)_T$ denotes $\{sh_i\}_{i\in T}$. We will slightly abuse the notation and denote $\mathsf {Rec}$ as the reconstruction procedure that takes in $T \in \mathcal {A}$ and $\mathsf {Share}(m)_T$ as input and outputs the secret.

• 2. Statistical Privacy: Any collusion of parties not part of the access structure should have “almost” no information about the underlying secret. More formally, for any unauthorized set $U \notin \mathcal {A}$, and for every pair of secrets $m, m' \in \mathcal {M}$,

  $$\varDelta ((\mathsf {Share}(m))_U ; (\mathsf {Share}(m'))_U ) \le \epsilon _s $$

An access structure $\mathcal {A}$ is said to be (n, t)-threshold if and only if $\mathcal {A}$ contains all subsets of $[n]$ of size at least t.

Rate of a secret sharing scheme is defined as $\frac{\text {message size}}{\text {share size}}$(which would be equal to $\frac{\log |\mathcal {M}|}{l}$).

We now study a stronger privacy requirement, adaptive privacy (introduced by Bellare and Rogaway  [6]⁶).

2.2.1 Adaptive Privacy

Statistical privacy captures privacy against any non-adaptively chosen unauthorized set U. Adaptive privacy preserves privacy even when the choice of U to be adaptive, which means the following. Let $U=\{i_1,..,i_q\}$. We say $i_j$ is chosen adaptively, if its choice depended on $\{share_j\}_{j\in \{i_1,..,i_{j-1}\}}$. The choice of which share to query next depends on all the previously observed shares. We give the formal definition below.

We say a ($\mathcal {A},n,\epsilon _s$)-secret sharing scheme satisfies adaptive privacy with error $\epsilon _{adp}$ if, for any distinguisher $\mathcal {D}$, the advantage in the following game is at most $\epsilon _{adp}$.

⁷

While generally, any secret sharing scheme may not be adaptively private, we can show that for the threshold setting, the scheme of [30] and for the general access structures, the scheme of [8] are both adaptively private (which is proved in the full version of our paper). We use them to instantiate our schemes.

Consistent Re-sampling. For any $(\mathcal {A},n,\epsilon _s)$-secret sharing scheme $(\mathsf {Share},$$\mathsf {Rec})$, for any message m and a subset $\mathcal {L}\subseteq [n]$, when we say “$(sh_1,..,sh_n)\leftarrow \mathsf {Share}(m)$ consistent with $sh^{*}_{\mathcal {L}}$ on $\mathcal {L}$” or “$(sh_1,..,sh_n)\leftarrow \mathsf {Share}(m|sh^{*}_{\mathcal {L}}$)” we mean the following procedure:

• Sample and output $(sh_1,..,sh_n)$ uniformly from the distribution $\mathsf {Share}(m)$ conditioned on the event that $sh_{\mathcal {L}}=sh^{*}_{\mathcal {L}}$

• If the above event is a zero probability event then output a string of all zeroes (of appropriate length).

We require the following consistent re-sampling feature⁸, which informally states that for any $(\mathcal {A},n,\epsilon _s)$-secret sharing scheme and any message m, the distribution of shares which are re-sampled as shares of m, conditioned on some set T of shares (which are also generated as shares of m) chosen adaptively, is identical to the distribution of shares of m generated directly.

Lemma 5

For any $(\mathcal {A},n,\epsilon _s)$-secret sharing scheme $(\mathsf {Share},\mathsf {Rec})$ and for any message m, the following two distributions are identical.

Here, $T \subseteq [N]$ can be any subset chosen as: every index (except the first) depends arbitrarily on the shares corresponding to all the previous indices.

We give a full proof of the above lemma in the full version of our paper.

3 Adaptive Extractors

Extractors (introduced by Nissan and Zuckerman  [28]) output a near uniform string y, from a source w that only has min-entropy, using a short uniform string s, called the seed, as a catalyst. Average-case extractors are extractors whose output remains close to uniform, even given the seed and some auxiliary information (or leakage) about the source (independent of the seed), as long as the source has enough average entropy given this leakage. We give their formal definition below.

Definition 2

 [16] Let $\mathsf {Ext}: \{0,1\}^{\eta }\times \{0,1\}^{d}\rightarrow \{0,1\}^{l}$ be a polynomial time computable function. We say that $\mathsf {Ext}$ is an efficient average-case $(\eta ,\mu ,d,l,\epsilon )$-strong extractor if for all pairs of random variables (W, Z) such that W is an $\eta$-bit string satisfying ${\widetilde{\mathbf {H}}_{\infty }}(W | Z) \ge \mu$, we have

$$ \mathsf {Ext}(W;U_d),U_d, Z \approx _{\epsilon } U_l,U_d, Z $$

3.1 Definition

Average-case extractors, unfortunately, provide no guarantees on the extractor output being uniform when an adversary can obtain an ‘adaptive’ leakage on the source, that is dependent on the extractor output and the seed. This is not surprising, as if an adversary can obtain arbitrary adaptive leakage on the source, then we cannot hope for the extractor output to remain uniform. For example, given $y = \mathsf {Ext}(w,s)$, an adversary can distinguish the extractor output from uniform with high probability by querying a single bit of auxiliary information that tells her whether $\mathsf {Ext}(w,s)=y$. However, as we will see later, in many applications, the adaptive leakage that the adversary obtains comes from a specific function family. Hence, by carefully defining this function family, we show how to obtain useful notions of extractors that guarantee security even in the presence of an adaptive auxiliary information. We introduce and call this notion adaptive extractors and now proceed to formally define them.

Definition 3

An $(\eta ,\mu ,d,l,\epsilon )$- extractor $\mathsf {Ext}$ is said to be an $(\mathcal {F},\delta )$-adaptive extractor if for all pairs of random variables (W, Z) such that W is an $\eta$-bit string satisfying ${\widetilde{\mathbf {H}}_{\infty }}(W | Z) \ge \mu$, and any function f in the function family $\mathcal {F}$, it holds that

$$Z,U_d, f(W,\mathsf {Ext}(W;U_d),U_d), \mathsf {Ext}(W;U_d)\approx _{\delta }Z, U_d, f(W,U_l,U_d), U_l$$

We call $\delta$, the adaptive error of the extractor.

3.2 Construction

Generic Relation. We show that every extractor is in fact an adaptive extractor for the family of leakage functions where the adaptive leakage depends only on the source and the extractor output (i.e., it doesn’t depend on the seed except via the extractor output), with some loss in security. This loss, in fact, depends only on the number of bits of the extractor output that the adaptive leakage function depends on. For ease of exposition, we omit auxiliary information z that depends only on the source (but not on the extractor output or seed) from the notation below. We now explicitly define this family below:

$$\mathcal {F}_{a,\zeta } \subseteq \{f':\{0,1\}^{\eta }\times \{0,1\}^{l}\rightarrow \{0,1\}^{\zeta }\} $$

such that for every $f'\in \mathcal {F}_{a,\zeta }$ there exists two functions $f:\{0,1\}^{l}\rightarrow \{0,1\}^a$ and

$$ g:\{0,1\}^{\eta +a}\rightarrow \{0,1\}^{\zeta } \text { such that } \forall w,y, \ f'(w,y)=g(w,f(y))\} $$

Here, ‘$\zeta$’ denotes the number of bits of adaptive leakage and ‘a’ denotes the number of bits of the extractor output (or the uniform string) that the adaptive leakage depends on. This is captured by requiring that every function $f'$ has an equivalent representation in terms of some g and f such that $f'(w,y)=g(w,f(y))$ where f’s output is only a bits long. w and y should be interpreted as the source and the extractor output (or the uniform string) respectively.

The following theorem shows that any $(\eta ,\mu ,d,l,\epsilon )$- average case extractor can be shown to be adaptive secure against the above family $\mathcal {F}_{a,\zeta }$, with an adaptive error of $2^{a+2}\epsilon$. Informally, we can reduce the adaptive security to the extractor security (as in Definition 2) in the following way: to answer the adaptive leakage query, the reduction makes a guess, v, for the extractor challenge dependent value $f(y_b)$ (where, $y_b$ is the extractor challenge), which is of a-bits, and gets the leakage g(w, v) from the source. Now, it gets the challenge $y_b$ from the extractor challenger and if $f(y_b)$ matches the guess v, then the reduction can successfully simulate the challenge and the adaptive leakage response, else it cannot proceed (and aborts). Hence, the winning probability in the extractor game is the probability of a correct guess ($2^{-a}$), multiplied with the winning probability of the adaptive extractor adversary. We formalize this proof in the theorem below.

Theorem 1

Every $(\eta ,\mu ,d,l,\epsilon )$- average case extractor $\mathsf {Ext}$ is an $(\eta ,\mu +\zeta ,d,l,\epsilon )$- extractor that is $(\mathcal {F}_{a,\zeta },2^{a+2}\epsilon )$-adaptive, for any $\mu + \zeta \le \eta$ and $a\le l$.

Proof

For simplicity, we omit the auxiliary information Z, that depends only on the source (and not on the extractor output). Let W be the source of $\eta$ bits, such that ${\mathbf {H}_{\infty }}(W) \ge \mu + \zeta$. Consider $f' \in \mathcal {F}_{a,\zeta }$, with the corresponding functions (f, g) (recall $f'(w,y) = g(w,f(y))$, where f outputs a bits and g outputs $\zeta$ bits). To prove adaptive security (Definition 3), we need to show that:

$$ U_d , f'(W, Y), Y \approx _{2^{a+2}\epsilon } U_d , f'(W, U_l), U_l,$$

where Y is the random variable $\mathsf {Ext}(W;U_d)$. Expanding the description of $f'$, this gives:

$$ U_d , g(W, f(Y)), Y \approx _{2^{a+2}\epsilon } U_d , g(W, f(U_l)), U_l$$

To prove this, we consider the following two sets $\mathcal {B}=\{b: \Pr [f(Y)=b]>0\}$ and $\mathcal {A}=\{0,1\}^{d+\zeta +l}$. For each $b \in \mathcal {B}$, we begin by using the statistical distance Lemma 3 with random variables A, B and events $E,E'$ set as $(U_d , g(W, f(Y)), Y)$, $(U_d , g(W, f(U_l)), U_l)$, $f(Y) = b$ and $f(U_l) = b$, respectively. By use of law of total probability and Lemma 3, we get:

$$\begin{aligned} \mathbf {SD}((U_d ,&g(W, f(Y)), Y),\ (U_d , g(W, f(U_l)), U_l))&\\&\le \Pr [f(U_l) \not \in \mathcal {B}] + \sum _{b \in \mathcal {B}} \mathbf {SD}\left( {A \wedge E, B \wedge E'} \right)&\\&\le \Pr [f(U_l) \not \in \mathcal {B}] + \sum _{b \in \mathcal {B}} ((|\Pr [E] -\Pr [E']|) + \Pr [E']\cdot \mathbf {SD}\left( {A|E, B|E'} \right) )&\end{aligned}$$

But now, note that, by extractor security, since $Y \approx _{\epsilon } U_l$, by applying Lemma 2, we have $f(Y) \approx _{\epsilon } f(U_l)$. Further, by the definition of statistical distance, we have that, for each $b \in \mathcal {B}$, $|\Pr [f(Y) = b]- \Pr [f(U_l) = b]| \le \epsilon$ and $\Pr [f(U_l) \notin \mathcal {B}]\le \epsilon$ (since $\Pr [f(Y)\not \in \mathcal {B}]=0]$). Applying this to above inequality, we get:

$$\begin{aligned} \mathbf {SD}((U_d ,&g(W, f(Y)), Y),\ (U_d , g(W, f(U_l)), U_l))&\\&\le \epsilon + \sum _{b \in \mathcal {B}} (\epsilon + \Pr [E']\cdot \mathbf {SD}\left( {A|E, B|E'} \right) )&\\&= (|\mathcal {B}| + 1)\epsilon + \sum _{b \in \mathcal {B}} \Pr [E']\cdot \mathbf {SD}(A|E, \ B|E')&\end{aligned}$$

Finally, we apply the statistical distance Lemma 4 on the random variables (A, f(Y)) and $(B,f(U_l))$ with set $S = \{b\}$. Note that, given events E and $E'$ the value of f(Y) and $f(U_l)$ are fixed to a b, which means the leakage g(W, b) is only a leakage on W. Thus, we can use extractor security to get: $(U_d,g(W,b),Y)\approx _{\epsilon }(U_d,g(W,b),U_l)$. Hence, applying this to the above inequality, we get:

$$\begin{aligned} \mathbf {SD}((U_d ,&g(W, f(Y)), Y),\ (U_d , g(W, f(U_l)), U_l))&\\&\le (|\mathcal {B}| + 1)\epsilon + \sum _{b \in \mathcal {B}} \Pr [E']\cdot \frac{2\epsilon }{ \Pr [f(U_l) = b]}&\\&\le 4|\mathcal {B}|\epsilon \le 2^{a+2}\epsilon&\end{aligned}$$

Concrete Instantiation. We show that the extractor due to Guruswami et al. [21] is an adaptive extractor even when the leakage depends on the entire extractor output. We state the result from [21] below.

Lemma 6

  [21] For every constant $\nu > 0$ all integers $\eta \ge \mu$ and all $\epsilon \ge 0$, there is an explicit (efficient) $(\eta ,\mu ,d,l,\epsilon )-$strong extractor with $l=(1-\nu )\mu - \mathcal {O} (\log (\eta )+\log (\dfrac{1}{\epsilon }))$ and $d\le \mathcal {O} (\log (\eta )+\log (\dfrac{1}{\epsilon })).$

Let $\mathsf {Full}_{\zeta }$ ($=\mathcal {F}_{l,\zeta }$), denote the leakage function family which computes leakage (of size $\zeta$) dependent on the entire extractor output and the source. The following lemma shows that one can appropriately set the parameters of the [21] extractor to get negligible error, while extracting a constant fraction of the bits from the source, and while adaptively leaking a constant fraction of bits from it.

Lemma 7

For all positive integers $l, \zeta$, every constant $\nu >1$ and $\epsilon \ge 0$, there is an explicit (efficient) $(\eta ,\mu +\zeta ,d,l,\epsilon )-$extractor that is $(\mathsf {Full}_{\zeta },\delta )$-adaptive with $d= \mathcal {O}(\log (\frac{\eta }{\epsilon }))$, $\mu = \nu l + \mathcal {O}(\log (\frac{\eta }{\epsilon }))$, any $\eta \ge \mu + \zeta$ and $\delta = \epsilon \cdot 2^{l+2}$.

On further implication, for any $c>1$, there exists constants $\alpha ,\beta$ such that $d\le \alpha l$, $\mu \le \beta l$, $\eta \ge \beta l+\zeta$, $\epsilon =2^{-cl}$ and $\delta = 2^{(1-c)l+2}$ when $l=\omega (\log \eta )$.

Proof

The proof of the first part of the lemma follows directly from Theorem 1 and Lemma 6 and the further implication can be obtained by simple substitution.

Further, we use the following generalization of adaptive extractors: for an adaptive extractor $\mathsf {Ext}$, if we consider k independent sources $W_1,\cdots ,W_k$ and a single seed S, all the extractor outputs $(\mathsf {Ext}(W_i;S))_{i \in [k]}$ look uniform, even given adaptive leakage on each $W_i$, dependent on not just $\mathsf {Ext}(W_i;S)$ (or uniform), but also all the prior extractor outputs and adaptive leakages (queried before i). As the sources are independent, this lemma can be proved using a simple hybrid argument (the detailed proof is given in our full version).

Lemma 8

Let k be an arbitrary positive integer, $W_1,\cdots ,W_k$ be k independent $(\eta ,\mu +\zeta )$ sources and S be the uniform distribution on $\{0,1\}^d$. Let $\mathsf {Ext}$ be an $(\eta ,\mu +\zeta ,d,l,\delta ')$-extractor that is $(\mathsf {Full}_{\zeta },\delta )$-adaptive. For each $i\in [k]$, let $E^0_i$ denotes $\mathsf {Ext}(W_i;S)$, $E^1_i$ denotes uniform distribution on $\{0,1\}^l$. For $b\in \{0,1\}$, we define $\mathsf {AdLeak}^b$ as follows. Then for any stateful distinguisher $\mathcal {D}'$ we have $\mathsf {AdLeak}^0\approx _{k\delta }\mathsf {AdLeak}^1$.

$\mathsf {AdLeak}^b:$

• Let Tr and $\mathcal {S}$ be a null string and null set respectively.

• For upto k times

  • $(j,g_j)\leftarrow \mathcal {D}'(Tr)$ where $j\in [k]\backslash \mathcal {S}$ and $g_{j}:\{0,1\}^{\eta +l}\rightarrow \{0,1\}^{\zeta }$.

  • Append $(j,g_j,g_j(w_j,E^b_j),E^b_j)$ to Tr.

  • Add j to $\mathcal {S}$.

• Output Tr.

4 Leakage Resilient Secret Sharing

Leakage-resilience of a secret sharing scheme is defined specific to a leakage model/ leakage family. We begin by formally defining leakage-resilience and then describe the leakage model.

Definition 4

An $(\mathcal {A}, n, \epsilon _s)$-secret sharing scheme is said to be an $(\mathcal {A}, n, \epsilon _s, \epsilon _l)$- leakage resilient secret sharing scheme against a leakage family $\mathcal {F}$ if for all functions $f \in \mathcal {F}$ and for any two messages $m, m' , \mathbf {SD}\left( {f(Share(m)) , f(Share(m'))} \right) \le \epsilon _l.$

Fig. 2.

LRSS definition- $\mathsf {Leak}_{Share}^{m}$ distribution

4.1 Leakage Models

We consider two leakage models in this paper. For now, we restrict our discussion to an (n, t)-threshold access structure.

• Adaptive Leakage and Reveal Model: The adversary can adaptively obtain leakage on individual shares for any $n-t+1$ shares. After this, he can additionally even get all the remaining $t-1$ shares in their entirety.

• Joint Leakage and Reveal Model: The adversary can ask any number of joint leakage queries on disjoint sets of size $X$ (a parameter). After this, he can additionally get any (at most $t-1$) of the remaining shares in their entirety. While this model completely subsumes the adaptive leakage and reveal model, the amount of leakage per share supported in the latter would be lesser.

We provide a formal description of the adaptive leakage and reveal model and the joint leakage and reveal model in Sect. 4.1.1 and Sect. 4.5 respectively. We give a construction that is leakage resilient with respect to both these models in Sect. 4.2. We prove leakage resilience of this scheme in the adaptive leakage and reveal model in Sect. 4.3. We provide a proof sketch of leakage resilience in the joint adaptive and reveal model in Sect. 4.5.2.

Fig. 3.

LRSS construction

4.1.1 Adaptive Leakage and Reveal Model $\mathcal {F}_{leak}^{\psi ,\tau }$

The model allows for leakage on individual shares and then also reveals at most $t-1$ of the remaining shares in clear. We have two parameters in the model $\tau$ and $\psi$ where $\tau$ denotes the amount of leakage provided in each leakage query and $\psi$ captures the maximum number of leakage queries allowed. We allow $\psi$ ranging from 1 to $n-t+1$. Though we allow $\psi$ to be $n-t+1$, we have it as an explicit parameter because lower $\psi$ would imply a weaker leakage model and possibly have better constructions. In fact, our multi-layered construction in Sect. 4.2 becomes compact (and offers better rate) as $\psi$ decreases.

Let (Share, Rec) (where $Share:\{0,1\}^l\rightarrow (\{0,1\}^\gamma )^n)$ be a t-out-of-n secret sharing scheme. We formalize leakage obtained in this model on shares of a message m as $\mathsf {Leak}_{Share}^{m}$ in Fig. 2, where an arbitrary stateful distinguisher $\mathcal {D}$ makes the queries. For any two messages m and $m'$, we require $\mathsf {Leak}^{m}_{Share}\approx _{\epsilon _{lr}}\mathsf {Leak}^{m'}_{Share}$, for (Share, Rec) to be $\epsilon _{lr}$ leakage resilient against the adaptive leakage and reveal model.

4.2 LRSS Construction for the Adaptive Leakage and Reveal Model

We refer the reader to the Introduction (Sect. 1.2) for a high-level overview of the construction and proof. We proceed to describe the construction in detail in Fig. 3 and prove its security in Sect. 4.3.

4.3 Proof of Leakage Resilience in the Adaptive Leakage and Reveal Model

Theorem 2

For any $\psi \le n-t+1$ and $l,\tau >0$, ($\mathsf {Share}^h,\mathsf {Rec}^h$) is an $((n,t),\varepsilon )$-secret sharing scheme for $l$ bit messages and is $2(\epsilon +h(\epsilon '+(t-1)\delta ))$-leakage resilient in the Adaptive Leakage and Reveal model $\mathcal {F}_{leak}^{\psi ,\tau }$ where $h=\lceil \psi /(t-1)\rceil$.

Further, there exists an instantiation of the scheme with rate is $(2^{\varTheta (h)}+h\tau /l)^{-1}$. When $\tau = \varTheta (l)$ and either $n=\varTheta (t)$ or h is a constant, the scheme achieves constant rate and constant leakage rate asymptotically.

Proof

The correctness of the scheme follows directly from the correctness of underlying extractors and secret sharing schemes. The (adaptive) privacy of the scheme is directly implied by the leakage resilience (against the adaptive leakage and reveal model).

Leakage Resilience. For any message m we define the following the sequence of hybrids. In these hybrids we assume that $\mathcal {D}$ always asks legitimate queries as per the model and won’t write explicit checks for legitimacy (for example, we assume that $\mathcal {D}$ doesn’t ask leakage on same share twice).

Fig. 4.

Hybrid $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$

We analyze the leakage queries made by $\mathcal {D}$ as bunches of $(t-1)$ queries. We now introduce some useful notation. Let $\mathcal {S}_1,\cdots ,\mathcal {S}_h$ denote the sets of indices queried by $\mathcal {D}$, where $\mathcal {S}_i$ contains the indices queried by $\mathcal {D}$ from the $((i-1)(t-1)+1)^{th}$ query to $i(t-1)^{th}$ leakage queries (i.e., $\mathcal {S}_1$ contains the first $t-1$ queries, $S_2$ the next $t-1$ queries and so on). For $i\in [h]$, we use $\mathcal {S}_{[i]}$ to denote $\bigcup \limits _{j=1}^{i} \mathcal {S}_j$, which captures the set of indices queried in the first $i(t-1)$ leakage queries. For $i\in [h]$, let $Z_{[i]}$ denotes the set of leakage queries and the corresponding responses to the first $i(t-1)$ leakage queries. $Z_{[h+1]}$ denotes $Z_{[h]}$ together with the final reveal queries as well as any relevant state information. We prove leakage resilience using a hybrid argument, with the following sequence of hybrids, $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{0}}},\ \{\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}},\ \mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}\}_{q\in [h]}$ and $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}$. The order of the hybrids is $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{0}}}$, $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{1}}},\ \mathsf {Leak}\mathsf {{B}}^{{m}}_{{{1}}},\cdots , \mathsf {Leak}\mathsf {{A}}^{{m}}_{{{h}}},\ \mathsf {Leak}\mathsf {{B}}^{{m}}_{{{h}}},\ \mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}$, where we will show that $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}$ is independent of m, and $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{0}}}$ will correspond to the distribution $\mathsf {Leak}^{m}_{\mathsf {Share}^{h}}$. This will allow us to show that $\mathsf {Leak}^{m}_{\mathsf {Share}^{h}}$ is indistinguishable from $\mathsf {Leak}^{m'}_{\mathsf {Share}^{h}}$. We begin by giving an informal description of these hybrids.

Fig. 5.

Hybrid $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}$

$\underline{\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}{} \textit{:}}$ We start with $q=1$. $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{1}}}$ follows the actual leakage game i.e., $\mathsf {Leak}^m_{Share^h} (\equiv \mathsf {Leak}\mathsf {{B}}^{{m}}_{{{0}}}$) except for the following change: we replace the shares $sd^1_j$, for each $j \in \mathcal {S}_1$ (the shares of $s^1$ corresponding to the first $t-1$ leakage queries), with shares of a dummy seed $\widetilde{s}^{1} = 0^d$. In general, for each $1<q\le h$, the only change we make in $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$ (in comparison to the previous hybrid $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q-1}}}$) is that we replace the shares $sd^q_{j}$, for each $j \in \mathcal {S}_q$ (the shares of $s^q$ corresponding to the q-th set of $t-1$ leakage queries), with shares of a dummy seed $\widetilde{s}^{q}$. After answering the leakage queries corresponding to $\mathcal {S}_q$, shares of $s^q$ are re-sampled consistent with the dummy seed shares used so far. The hybrid is formally described in Fig. 4.

Fig. 6.

Hybrid $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}$. (Color figure online)

$\underline{\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}{} \textit{:}}$ For $q=1$, $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{1}}}$ follows the hybrid $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{1}}}$ except for the following change: in $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{1}}}$, we replace the values $x^1_j$, for each $j \in \mathcal {S}_1$ with random, instead of evaluating the h layers of masking to get $x^1_j$ (and hence $x^1_j$’s for $j\in \mathcal {S}_1$ are independent of $m_{\mathcal {S}_1}$, $s^i$ and the shares of $s^i$, for each $1<i\le h$). Note that in $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{1}}}$, the shares $Sh_j$ corresponding to $\mathcal {S}_1$ no longer depend on the seed $s^1$. We carefully use the adaptive extractor security of $\mathsf {Ext}^1$ to move to $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{1}}}$. In general, for each $1<q\le h$, the only change we make in $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}$ (in comparison to the previous hybrid $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$) is that we replace the values $x^q_j$, for each $j \in \mathcal {S}_q$ with random, instead of evaluating the $h-(q-1)$ layers of masking to get $x^q_j$ (and hence, for these queries in $\mathcal {S}_q$, $s^i$ and the shares of $s^i$, for each $q<i\le h$, and the shares m are not used to evaluate $x^q_j$). Further, we continue the steps of masking to evaluate $x^{q-1}_j,x^{q-2}_j,\cdots ,x^{1}_j$, for each $j \in \mathcal {S}_q$ as in the previous hybrid. The hybrid is formally described in Fig. 5.

$\underline{\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{ }}}{} \textit{:}}$ In the hybrid $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{h}}}$, all the shares used in the leakage phase are independent of the shares of the message m. Hence, the only part of the view of $\mathcal {D}$ that depends on the shares of m corresponds to the reveal phase. In the final hybrid $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{ }}}$, we replace the $t-1$ shares of m used in the reveal phase by shares of $0^l$. This hybrid is formally described in Fig. 6.

The formal descriptions of all hybrids are given below with the change from the prior hybrid highlighted in red color.

We begin by proving the statistical closeness of $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$ and $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q-1}}}$, for each $q \in [h]$, which follows from adaptive privacy of $\mathsf {SdShare}^q$, as atmost only $t-1$ dummy seed shares are used.

Claim 1

For $q\in [h]$, if $\mathsf {SdShare}^q$ is $\epsilon '_q$-adaptively private against (n, t)-threshold access structures, then $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}} \approx _{\epsilon '_q} \mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q-1}}}$.

Proof

Answering the first $(q-1)$ sets of leakage queries (when $q>1$): Observe that the hybrids are identical up to answering the first $(q-1)(t-1)$ leakage queries and differ in answering the remaining queries. For any $k\in [q-1]$ and, $j\in \mathcal {S}_k$ the leakage response only depends on $\widetilde{sd}^{k}_{j}$, $w^1_j,\cdots ,w^h_j$ and $\{s^i,sd^i_j\}_{1\le i<k}$ (as $x^k_j$ is chosen uniformly). We let $\mathsf {Pre}$ denote the union of these random variables upon which the leakage responses to $j\in \mathcal {S}_{[q-1]}$ depend.

Answering the $q^{th}$ Set of Leakage Queries: Consider $j\in \mathcal {S}_q$. To answer this leakage query, it suffices to compute $Sh_j=(w^1_j,\cdots ,w^h_j,y^1_j)$. The hybrids only differ in computation of $y^1_j$ (particularly in computation of $y^q_j$, which is used to compute $y^1_j$) and the distribution of extractor sources is identical in both. We highlight the differences here. $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$ (Step 8-(a)-ii-C), iteratively computes $y^h_j,\cdots ,y^q_j,\cdots ,y^1_j$ as follows.

• $(y^h_j,\cdots ,y^{q+1}_j)$ are computed using $y^{h+1}_j$ and $\{w^{i}_j,sd^{i}_j,s^i\}_{i\in [h]\backslash [q]}$. Note that the distribution of $y^h_j,\cdots ,y^{q+1}_j$ is identical in both hybrids.

• $x^q_j$ is computed using $y^{q+1}_j,w^q$ and $s^q$. $x^q_j$ is also identical in both hybrids.

• $y^q_j$ is computed as $x^q_j||\widetilde{sd}^{q}_{j}$ (where $\widetilde{sd}^{q}_{[n]}$ are shares of a dummy seed $\widetilde{s}^{q}{}$ which are generated before answering any queries in $\mathcal {S}_q$ in Step 8-(a)-i (when $c=q$)). Whereas in $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q-1}}}$, $y^q_j=x^q_j||sd^q_j$ (where $sd^q_{[n]}$ are shares of $s^q$)

• $(y^{q-1}_j,\cdots ,y^1_j)$ are computed using $y^q_j$ and $\{sd^i_j,w^i_j,s^i\}_{i\in [q-1]}$. The computation of $(y^{q-1}_j,\cdots ,y^1_j)$ given the later random variables is again identical to $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q-1}}}$.

• Now $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$ defines $Sh_j=(w^1_j,\cdots ,w^h_j,y^1_j)$

For convenience, in this proof we distinguish (whenever necessary) the random variables that have same literal in both the hybrids but are distributionally different with subscripts A and B respectively. For example, $y^q_{j,A}$ and $y^q_{j,B}$ denote the distributions of $y^q_j$ in $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$ and, $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q-1}}}$ respectively.

Let $\mathsf {Pre}'=(\{w^q_j,\{sd^i_j,w^i_j,s^i\}_{i\in [h]\backslash \{q\}}\}_{j\in [n]\backslash \mathcal {S}_{[q-1]}})$. $\mathsf {Pre}'$ captures the information required to answer all queries after the first $q-1$ sets of leakage queries, except for any information regarding $s^q,\widetilde{s}^q$ and their shares. Note that $\mathsf {Pre}'$ is identical in both hybrids⁹. Since, $|\mathcal {S}_q|\le t-1$, with a reduction to adaptive privacy of $\mathsf {SdShare}^q$ we have

$$\begin{aligned} \mathsf {Pre},\mathsf {Pre}',s^q,\widetilde{s}^q,{\{\widetilde{sd}^{q}_{j}\}_{j\in \mathcal {S}_{q,A}}} \approx _{\epsilon '_q} \mathsf {Pre},\mathsf {Pre}',s^q,\widetilde{s}^q,{\{{sd}^q_j\}_{j\in \mathcal {S}_{q,B}}} \end{aligned}$$

as $(\mathsf {Pre},\mathsf {Pre}')$ is independent of the randomness used to generate the shares of $\widetilde{s}^q$ and $s^q$. Note that the information on LHS suffices to answer the first q sets of queries as per $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$. Similarly, RHS suffices to answer queries in $\mathcal {S}_{[q]}$ as per $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q-1}}}$. Therefore, we have,

$$\begin{aligned} \mathsf {Pre},\mathsf {Pre}',s^q,\tilde{s}^q,\{\widetilde{sd}^{q}_{j}\}_{j\in \mathcal {S}_{q,A}},{Z_{[q],A}}\approx _{\epsilon '_q} \mathsf {Pre},\mathsf {Pre}', s^q,\tilde{s}^q,\{{sd}^q_j\}_{j\in \mathcal {S}_{q,B}},{Z_{[q],B}}\end{aligned}$$

(1)

Answering the Leakage and Reveal Queries Made After the $q^{th}$ Set of Leakage Queries: After all the $q^{th}$ set leakage queries are answered, $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$ computes $(sd^q_1,\cdots ,sd^q_n)\leftarrow \mathsf {SdShare}^q(s^q|\widetilde{sd}^{q}_{\mathcal {S}_{q,A}})$. Given $(sd^q_1,\cdots ,sd^q_n),s^q,\mathsf {Pre}$ and $\mathsf {Pre}'$, for any $j\in [n]\backslash \mathcal {S}_q$, $Sh_j$ is easily computed (Steps 8-(b) and 8-(c)). With this, any further queries can be correctly answered as per $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$. Let $(\widehat{sd}^q_1,\cdots ,\widehat{sd}^q_n)\leftarrow \mathsf {SdShare}^q(s^q|sd^{q}_{\mathcal {S}_{q,B}})$. By Lemma 2, we have

$$ \mathsf {Pre},\mathsf {Pre}',s^q,\tilde{s}^q, {Z_{[q],A}}, {sd^q_{[n],A}}\approx _{\epsilon '_q} \mathsf {Pre},\mathsf {Pre}', s^q,\tilde{s}^q, {Z_{[q],B}}, {\widehat{sd}^q_{[n],B}} $$

Note that ${\widehat{sd}^q_{[n]}}$ is identical to $sd^q_{[n],B}$ (of $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q-1}}}$) even given $s^q$ and $\{{sd}^q_j\}_{j\in \mathcal {S}_q}$ by the property of consistent resampling in Claim 5. Therefore, we have,

$$ \mathsf {Pre},\mathsf {Pre}',s^q, Z_{[q],A},{sd^q_{[n],A}} \approx _{\epsilon '_q} \mathsf {Pre},\mathsf {Pre}', s^q, Z_{[q],B},{sd^q_{[n],B}} $$

Since the above LHS and RHS are sufficient to answer any further queries, we have

$$Z_{[h+1],A}\approx _{\epsilon '_q}Z_{[h+1],B}$$

which proves the claim.

Now, we prove the statistical closeness of $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$ and $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}$, for each $q \in [h]$ using the adaptive extractor security. The high-level idea behind the reduction is that in hybrid $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$, the shares corresponding to the first $q(t-1)$ queries (i.e., $\mathcal {S}_{[q]}$) no longer depend on the seed $s^q$ and hence, we can use the adaptive extractor security of $\mathsf {Ext}^q$ to move to $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}$.

Claim 2

For $q\in [h]$, if $\mathsf {Ext}^q$ is an $(\eta _q,\mu _q+\tau ,d_q,l_q,\delta '_q)$- extractor that is $(\mathsf {Full}_{\tau },\delta _q)$-adaptive, then $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}} \approx _{(t-1)\delta _q} \mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}$

Proof

Observe that the hybrids are identical up to answering the first $(q-1)(t-1)$ leakage queries and differ in answering the $q^{th}$ set of queries. Further, after answering the $q^{th}$ set of leakage queries, the responses to all remaining leakage/reveal queries are answered identically in both hybrids.

Answering the first $(q-1)$ Sets of Leakage Queries (when $q>1$):

For any $k\in [q-1]$ and $j\in \mathcal {S}_k$ the leakage response only depends on $\widetilde{sd}^{k}_{j}$, $w^1_j,\cdots ,w^h_j$, $\{s^i,sd^i_j\}_{1\le i<k}$ and $x^k_j$, where the latter is uniformly chosen. We let $\mathsf {Pre}$ denote the leakage responses $Z_{[q-1]}$ and the union of these random variables upon which the leakage responses to $j\in \mathcal {S}_{[q-1]}$ depend.

Answering the $q^{th}$ Set of Leakage Queries:

Consider $j\in \mathcal {S}_q$ and $f_j$ be the corresponding leakage function. To answer this leakage query, we require computing $f_j(Sh_j)$ where $Sh_j=(w^1_j,\cdots ,w^h_j,y^1_j)$. The hybrids only differ in computation of $y^1_j$ (particularly in computation of $x^q_j$, which is used to compute $y^1_j$) and the distribution of extractor sources is identical in both. The hybrids iteratively computes $y^q_j,\cdots ,y^1_j$ as follows.

• $x^q_{j}$ is chosen uniformly from $\{0,1\}^{l_q}$ in $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}$. In contrast, $x^q_{j}$ of $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$ depended on $\mathsf {Ext}^q(w^q_j;s^q)$ and $y^{q+1}_{j}$.

• $(y^q_{j},\cdots ,y^1_{j})$ is determined given $x^q_{j},\widetilde{sd}^{q}_{j}$ and $\{sd^i_j,w^i_j,s^i\}_{i\in [q-1]}$ in both the hybrids.

• Both hybrids define $Sh_j=(w^1_j,\cdots ,w^h_j,y^1_j)$

Let $\mathsf {Pre}' = \{w^i_j,sd^i_j,s^i,y^{h+1}_j,\widetilde{sd}^{q}_{j}\}_{i\in [h]\backslash \{q\},j\in [n]\backslash \mathcal {S}_{[q-1]}}$.We capture $\mathsf {Pre}'$ as the information which along with $\{w^q_j,s^q\}_{j\in \mathcal {S}_{q}}$ is sufficient to answer any leakage queries on $j\in \mathcal {S}_{q}$. Also, $\mathsf {Pre}'$ is identical in both hybrids.

Let $j_1,\cdots ,j_{t-1}$ be the order of indices in which leakage queries are made in $\mathcal {S}_q$. Firstly, we prove that $(\mathsf {Pre},\mathsf {Pre}',f_{j_1}(Sh_{j_1}))$ of both hybrids are statistically close. After that we proceed to show that $(\mathsf {Pre},\mathsf {Pre}',f_{j_1}(Sh_{j_1}),\cdots ,f_{j_{(t-1)}}(Sh_{j_{(t-1)}}))$ of both the hybrids are statistically close, which implies that the hybrids are statistically close up to answering first q sets of queries. For convenience, in this proof we distinguish (whenever necessary) the random variables that have same literal in the hybrids but are distributionally different with subscripts A and B respectively. For example, $x^q_{j,A}$ and $x^q_{j,B}$ denote the distributions of $x^q_j$ in $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$ and $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}$ respectively.

Firstly, in both hybrids the distribution of $(j_1,f_{j_1})$ only depends on $Z_{[q-1]}$ (and any internal randomness of $\mathcal {D}$) and hence are identical. Note that given $\mathsf {Pre}'$, $f_{j_1}(Sh_{j_1})$ in $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$, can be captured as $\mathsf {Full}_{\tau }$-adaptive leakage on the extractor source $w^q_{j_1}$ and ($x^q_{j_1,A}$=) $\mathsf {Ext}^q(w^q_{j_1};s^q)\oplus y^{q+1}_{j_1}$. This is because $(y^{q+1}_{j_1},\mathsf {Pre}')$ are independent of $(w^q_{j_1},s^q)$. Let $g_1$ be a function that takes $\mathsf {Pre}',w^q_{j_1}$ and $x^q_{j_1,A}$(or $x^q_{j_1,B}$) as input, computes $y^1_{j_1,A}$ (or $y^1_{j_1,B}$) and outputs $f_j(w^1_{j_1},\cdots ,w^h_{j_1},y^1_{j_1,A})$ (or $f_j(w^1_{j_1},\cdots ,w^h_{j_1},y^1_{j_1,B})$). With a reduction to adaptive security of $\mathsf {Ext}^q$ we have

$$\begin{aligned}&\mathsf {Pre},\mathsf {Pre}',s^q,g_1(\mathsf {Pre}',w^q_{j_1},\mathsf {Ext}^q(w^q_{j_1};s^q)\oplus y^{q+1}_{j}) \\&\approx _{\delta _q} \mathsf {Pre},\mathsf {Pre}',s^q,g_1(\mathsf {Pre}',w^q_{j_1},U_{l_q}\oplus y^{q+1}_{j})\\&\equiv \mathsf {Pre},\mathsf {Pre}',s^q,g_1(\mathsf {Pre}',w^q_{j_1},x^q_{j_1,B}) \end{aligned}$$

Therefore

$$\mathsf {Pre},\mathsf {Pre}',s^q,f_{j_1}(Sh_{j_1,A})\approx _{\delta _q}\mathsf {Pre},\mathsf {Pre}',s^q,f_{j_1}(Sh_{j_1,B})$$

With this, we showed that the hybrids are statistically close up to responding to the first query in the $q^{th}$ set. Although, superficially, it may seem that all the leakage responses corresponding to $j\in \mathcal {S}_q$ can be captured as adaptive extractor leakage on the source $w^q_j$, but it’s not the case because of the following subtlety. The extractor sources used in each query are independent of each other, but the seed is the same. For example, one cannot directly capture $f_{j_2}(Sh_{j_2})$ as $\mathsf {Full}_{\tau }$-adaptive leakage (as we did with $f_{j_1}(Sh_{j_1})$). This is because the choice of $j_2,f_{j_2}$ depends on $f_{j_1}(Sh_{j_1})$ which in turn depends on $\mathsf {Ext}^q(w^q_j;s^q)$, and hence is not independent of the seed $s^q$. We observe in Lemma 8 that adaptive extractors allow us to handle even such (stronger) form of adaptive leakages across different sources with same seed.

Proceeding, with a reduction to Lemma 8 with $k=(t-1), \{W_i = W^q_{j_i}:\ i\in [k] \}$, $S = s^q$ and $\mathsf {Ext}= \mathsf {Ext}^q$ and the $i^{th}$ leakage function being $g_i$ such that $g_i$ (hardwired with $\mathsf {Pre}',y^{q+1}_{j_i})$ takes $w^q_{j_i}$ and $\mathsf {Ext}^q(w^q_{j_i};s^q)$ (resp. $U_{l_q}$) as input, computes $y^1_{j_i,A}$ (resp. $y^1_{j_i,B}$) and outputs $f_{j_i}(w^1_{j_i},\cdots ,w^h_{j_i},y^1_{j_i,A})$ (resp. $f_{j_i}(w^1_{j_i},\cdots ,w^h_{j_i},y^1_{j_i,B})$).

$$\begin{aligned} \begin{array}{c} \mathsf {Pre},\mathsf {Pre}',s^q,\{f_{j_i},f_{j_i}(Sh_{j_i,A})\}_{j_i\in \mathcal {S}_{q,A}},\mathcal {S}_{q,A} \\ \\ \approx _{(t-1)\delta _q}\mathsf {Pre},\mathsf {Pre}',s^q,\{f_{j_i},f_{j_i}(Sh_{j_i,B})\}_{j_i\in \mathcal {S}_{q,B}},\mathcal {S}_{q,B} \end{array} \end{aligned}$$

This shows that the hybrids are statistically close up to answering the first q sets of leakage queries.

Answering the Leakage and Reveal Queries Made After the $q^{th}$ Set of Leakage Queries: After all the $q^{th}$ set of leakage queries are answered, both hybrids compute $(sd^q_1,\cdots ,sd^q_n)\leftarrow \mathsf {SdShare}(s^q|\widetilde{sd}^{q}_{\mathcal {S}_q})$. Let $\mathsf {Pre}'' = \{w^q_j,sd^q_j,s^q\}_{j\in [n]\backslash \mathcal {S}_q}$. Note that $\mathsf {Pre}'$ in conjunction with $\mathsf {Pre}''$ completely defines $Sh_j$ for any $j\in [n]\backslash \mathcal {S}_{[q]}$. Since $\mathsf {Pre}''$ corresponding to $\mathsf {Leak}\mathsf {{A}}^{{m}}_{{{q}}}$(resp. $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}$) is only correlated to $\mathcal {S}_q, s^q$ and $\widetilde{sd}^{q}_{\mathcal {S}_q}$(which is in $\mathsf {Pre}'$) of the respective hybrids, we have

$$\begin{aligned} \begin{array}{c} \mathsf {Pre},\mathsf {Pre}',\mathsf {Pre}^{''}_A,s^q,\{f_{j_i},f_{j_i}(Sh_{j_i,A})\}_{j_i\in \mathcal {S}_{q,A}},\mathcal {S}_{q,A} \\ \\ \approx _{(t-1)\delta _q}\mathsf {Pre},\mathsf {Pre}',\mathsf {Pre}^{''}_B,s^q,\{f_{j_i},f_{j_i}(Sh_{j_i,B})\}_{j_i\in \mathcal {S}_{q,B}},\mathcal {S}_{q,B} \end{array} \end{aligned}$$

Since responses to leakage/reveal queries after the $q^{th}$ set are can be derived from the LHS and RHS respectively depending on the hybrid, we have

$$Z_{[h+1],A} \approx _{(t-1)\delta _q}Z_{[h+1],B}$$

This proves the claim.

Finally, we use the adaptive security of $\mathsf {MShare}$ to show that $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}$ is statistically close to $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{h}}}$.

Claim 3

If $\mathsf {MShare}$ is $\epsilon$-adaptively private against (n, t)-threshold access structures, then $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}} \approx _{\epsilon } \mathsf {Leak}\mathsf {{B}}^{{m}}_{{{h}}}$.

Proof

The hybrids answer the leakage queries identically and differ only in answering the reveal queries.

Answering the Leakage Queries:

For any $k\in [h]$ and $j\in \mathcal {S}_k$ the leakage response only depends on $\widetilde{sd}^{k}_{j}$, $w^1_j,\cdots ,w^h_j$, $\{s^i,sd^i_j\}_{1\le i<k}$ and $x^k_j$, where the latter is uniformly chosen. We let $\mathsf {Pre}$ denote the leakage responses $Z_{[h]}$ and the union of these random variables upon which the leakage responses to $j\in \mathcal {S}_{[h]}$ depend.

Answering the Reveal Queries: Let $\mathsf {Pre}'=\{w^i_j,sd^i_j,s^i\}_{i\in [h],j\in [n]\backslash \mathcal {S}_{[h]}}$. Note that given $y^{h+1}_j$ for all j queried in the reveal phase, $(\mathsf {Pre},\mathsf {Pre}')$ has sufficient information to answer all the reveal queries.

• $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{h}}}$ samples $(m_1,\cdots ,m_n)\leftarrow \mathsf {MShare}(m)$ and sets $y^{h+1}_{j}=m_j$ for all j queried in the reveal phase.

• $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}$ samples $(\tilde{m}_0,\cdots ,\tilde{m})\leftarrow \mathsf {MShare}(\tilde{m})$ and sets $y^{h+1}_j=\tilde{m}_j$ for all j queried in the reveal phase.

Let $\mathsf {RevealB}$ and $\mathsf {RevealC}$ denote the sets of indices queried in the reveal phase of $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{h}}}$ and $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}$ respectively. As reveal queries are at most $t-1$ in number, we now invoke adaptive privacy of $\mathsf {MShare}$ and get

$$\mathsf {Pre},\mathsf {Pre}',\tilde{m},m,\{m_j\}_{j\in \mathsf {RevealB}}\approx _{\epsilon }\mathsf {Pre},\mathsf {Pre}',\tilde{m},m,\{\tilde{m}_j\}_{j\in \mathsf {RevealC}}$$

Note that $(\mathsf {Pre}, \mathsf {Pre}')$ is independent of the randomness used in generating shares of m and $\tilde{m}$, therefore adaptive privacy of $\mathsf {MShare}$ can be invoked even given these random variables.

Since $Sh_j$ for j queried in reveal phase of $\mathsf {Leak}\mathsf {{B}}^{{m}}_{{{h}}}$ (resp. $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}$) is determined by the above LHS (resp. RHS) we have

$$\underbrace{Z_{[h+1]}}_{of \ \mathsf {Leak}\mathsf {{B}}^{{m}}_{{{q}}}}\approx _\epsilon \underbrace{Z_{[h+1]}}_{of \ \mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}}$$

With the above claims and use of triangle inequality we know that for any message m, $\mathsf {Leak}\mathsf {{}}^{{m}}_{{{Share^h}}}\approx _{\epsilon +\sum _{i\in [h]}((t-1)\delta _i + \epsilon '_i)}\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}$. Note that the description of $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}$ is independent of m. Hence for any message $m\ne m'$, we have $\mathsf {Leak}\mathsf {{C}}^{{m}}_{{{}}}\equiv \mathsf {Leak}\mathsf {{C}}^{{m'}}_{{{}}}$. Since, $\mathsf {Leak}\mathsf {{}}^{{m'}}_{{{Share^h}}}\approx _{h\epsilon '+h(t-1)\delta +\epsilon }\mathsf {Leak}\mathsf {{C}}^{{m'}}_{{{}}}$ we get

$$\mathsf {Leak}\mathsf {{}}^{{m}}_{{{Share^h}}}\approx _{2\epsilon +2\sum _{i\in [h]}((t-1)\delta _i + \epsilon '_i)}\mathsf {Leak}\mathsf {{}}^{{m'}}_{{{Share^h}}}$$

4.4 Parameters

For $i\in [h]$, we instantiate $\mathsf {SdShare}^i$ on seeds of length $d_i$ with the (adaptively) private Shamir secret sharing scheme, which results in individual seed share length being $d_i$. We instantiate $\mathsf {MShare}$ on messages of length $l_i$ with the (adaptively) private Shamir secret sharing scheme, which results in individual seed share length being $l_i$.

Recall Lemma 7 which states that for any $c>1$, there exists constants $\alpha ,\beta$ such that $d\le \alpha l$, $\mu \le \beta l$, $\eta \ge \beta l+\tau$, $\epsilon =2^{-cl}$ and $\delta = 2^{-(c-1)l+2}$ when $l=\omega (\log \eta )$. Fix any $c>1$, and constants $\alpha ,\beta$ corresponding to this c given by Lemma 7. For each $i\in [h]$, we instantiate ($\eta _i,\mu _i+\tau ,d_i,l_i,\delta '_i$)-extractor $\mathsf {Ext}^i$ that is $(\mathsf {Full}_{\tau },\delta _i)$-adaptive as per this lemma as follows.

• We set $l_1=l$, $\delta '_1=2^{-cl}$, $\delta _1=2^{-\varOmega (l)}$, $d_1\le \alpha l_1$, $\mu _1\le \beta l_1$ and $\eta _1=\beta l_1+\tau$.

• For $i>1$, we set $l_i=l_{i-1}+d_{i-1}$, $\delta '_i=2^{-cl_i}$, $\delta _i=2^{-\varOmega (l_i)}$, $d_i\le \alpha l_i$, $\mu _i\le \beta l_i$ and $\eta _i=\beta l_i+\tau$.

With this setting, individual share length of $\mathsf {Share}^h$ is $l_h+d_h+\sum _{i\in [h]}\eta _i = h\tau +\varTheta ((1+\alpha )^hl)$. Therefore, $\mathsf {Share}^h$ acheives constant rate and constant leakage rate whenever $\tau =\mathcal {O}(l)$ and either $n=\varTheta (t)$ or h is a constant.

Fig. 7.

Joint LRSS definition- $\mathsf {JLeak}_{Share}^{m}$ distribution

As our instantiations of $\mathsf {SdShare}^i$’s and $\mathsf {MShare}$ are perfectly adaptively private, we have $\mathsf {Share}^h$ to be a perfectly adaptively private secret sharing scheme which is $t\cdot 2^{-\varOmega (l)}$-leakage resilient against the adaptive leakage and reveal model.

4.5 LRSS for Joint Leakage and Reveal Model

4.5.1 Joint Leakage and Reveal Model $\mathcal {J}^{X,\psi ,\tau }$

The model allows for $\psi$ number of joint leakage queries on disjoint sets where each query depends on $X$ number of shares and additionally also reveals $t-1$ of the remaining shares (on which leakage isn’t queried) in clear. The parameter $\tau$ captures the amount of leakage provided in each leakage query.

Let (Share, Rec) (where $Share:\{0,1\}^l\rightarrow (\{0,1\}^\gamma )^n)$ be a secret sharing scheme for an (n, t)- threshold access structure. We formalize leakage obtained in this model on shares of a message m as $\mathsf {JLeak}_{Share}^{m}$ in Fig. 7, where an arbitrary stateful distinguisher $\mathcal {D}$ makes the queries. For any two messages m and $m'$, we require $\mathsf {JLeak}^{m}_{Share}\approx _{\epsilon _{lr}}\mathsf {JLeak}^{m'}_{Share}$, for (Share, Rec) to be $\epsilon _{lr}$ leakage resilient against this model.

4.5.2 Leakage Resilience of $(\mathsf {Share}^{h}, \mathsf {Rec}^h)$ in $\mathcal {J}^{X,\psi ,\tau }$ Model

Theorem 3

For any $\psi ,X>0$ such that $\psi \cdot X\le n-t+1$ and $l,\tau >0$, ($\mathsf {Share}^{h},\mathsf {Rec}^h$) is an $((n,t),\varepsilon )$-secret sharing scheme for $l$ bit messages and is $\epsilon _{lr}$-leakage resilient in the joint leakage and reveal model $\mathcal {J}^{X,\psi ,\tau }$ where $h=\lceil \frac{\psi }{\lfloor (t-1)/X\rfloor }\rceil$ and $\epsilon _{lr}= 2(\epsilon +h\epsilon '+(t-1)\sum _{i\in [h]}2^{Xl_i}\delta '_i))$.

Further, there exists an instantiation of the scheme with rate is $(X^{\varTheta (h)}+ h\tau /l)^{-1}$. When $\tau = \varTheta (l)$, $X$ is a constant and when either $n=\varTheta (t)$ or h is a constant, the scheme achieves constant rate and leakage rate asymptotically.

The proof for the joint leakage setting is very similar to the proof of Theorem 2 for the adaptive setting (on single shares). We give a complete proof of this in our full version.

Further, we can also extend our construction to get LRSS for general access structures as well, the details of which are given in the full version of our paper.