Randomness Recoverable Secret Sharing Schemes

Abstract

It is well-known that randomness is essential for secure cryptography. The randomness used in cryptographic primitives is not necessarily recoverable even by the party who can, e.g., decrypt or recover the underlying secret/message. Several cryptographic primitives that support randomness recovery have turned out useful in various applications. In this paper, we study randomness recoverable secret sharing schemes (RR-SSS), in both information-theoretic and computational settings and provide two results. First, we show that while every access structure admits a perfect RR-SSS, there are very simple access structures (e.g., in monotone $\textsf{AC}^0$) that do not admit efficient perfect (or even statistical) RR-SSS. Second, we show that the existence of efficient computational RR-SSS for certain access structures in monotone $\textsf{AC}^0$ implies the existence of one-way functions. This stands in sharp contrast to (non-RR) SSS schemes for which no such results are known. RR-SSS plays a key role in making advanced attributed-based encryption schemes randomness recoverable, which in turn have applications in the context of designated-verifier non-interactive zero knowledge.

1 Introduction

Without randomness, secure cryptography is unachievable. The randomness used in cryptographic primitives is not necessarily, efficiently and even sometimes information-theoretically, recoverable. For example, the randomness used for an ElGamal ciphertext is not efficiently recoverable even by a party holding the secret key. On the other hand, several well-known constructions for PKE, such as the OAEP [7] and its variants [10, 34, 37] are randomness recoverable (RR). Another notable RR-PKE construction is Yao’s construction [39] based on injective trapdoor functions (TDF).

RR-PKE schemes have found applications in constructing optimistic fair exchange protocols [32], signcryption schemes [30], proofs of correct decryptions in electronic-voting applications in [26] (to avoid heavy zero-knowledge proofs) and recently in CCA-secure PKE in [16].

In addition to PKE, RR variants of symmetric encryption schemes (SKE), attribute-based encryption (ABE) and garbled circuits (GC) have been studied in the literature [15, 27].

1.1 RR Secret Sharing and Motivations

In this paper, we initiate the study of secret sharing schemes (SSS) [9, 36] from a randomness recovery point of view. In addition to being an interesting notion on its own, it has applications in settings such as designated-verifier non-interactive zero-knowledge (DV-NIZK) for $\textsf{NP}$ [15, 31], as we will discuss later.

Main Results We take the first steps toward delineating the notion of RR-SSS from both information-theoretic and computational perspectives. First, we show that while every access structure admits a perfect RR-SSS, there are very simple access structures (e.g., in $\textsf{AC}^0$) that do not admit efficient perfect RR-SSS. Our result also applies to the weaker security notions including statistical security. Second, we show that the existence of efficient computational RR-SSS for certain access structures in $\textsf{AC}^0$ implies one-way functions (OWF). Our second result provides strong evidence that realizing RR-SSS for $\textsf{AC}^0$ from assumptions not currently known to imply OWFs (e.g., worst-case complexity-type assumptions) may be impossible.

Applications of RR-SSS and Motivations Assuming the existence of RR-PKE, RR-SSS for access structures in $\textsf{NC}^1$ seems to be an important step towards single-key RR-ABE for circuits in $\textsf{P}$ (see Sect. 1.5). Single-key RR-ABE for $\textsf{P}$, in turn, is sufficient for DV-NIZK for all $\textsf{NP}$ [15, 31]¹. Currently, it is known how to base RR-ABE and DV-NIZK on CDH and LWE [15, 31] but it is still open whether they can be achieved using weaker primitives such as TDFs (which by [15] is implied by RR-PKE and hinting PRG [29]).

Moreover, RR-SSS can be useful in applications in which proofs of well-formedness are needed for recovered shares. This motivates the study of RR-SSS as an independent primitive.

1.2 A Perfect RR-SSS for Every Access Structure

Let us first recall what an SSS is. In an SSS, a secret is shared among a set of participants by giving a share to each one. The shares are computed by applying a public rule on the secret and randomness. Only certain pre-specified subsets of participants are qualified to recover the secret and the secret must remain hidden from every other subset of participants. These requirements are called correctness and privacy, respectively, and can be defined either in the computational or information-theoretic setting. The set of all qualified subsets is called the access structure [20].

In an RR-SSS, we additionally require that every qualified set, in addition to the secret, is also able to recover the randomness.

The most well-known SSS, Shamir’s threshold scheme, is RR. In Shamir’s scheme, a secret $s\in \mathbb {F}$ is shared among a set of n participants as follows ($\mathbb {F}$ is a finite field with at least $n+1$ elements). The randomness $(r_1,\ldots ,r_{t-1})\in \mathbb {F}^{t-1}$ is chosen ($1\le t\le n$), the polynomial $f(x)=s+r_1x+r_2x^2+\ldots +r_{t-1}x^{t-1}$ is constructed, and the share $s_i=f(x_i)$ is given to participant $i\in \{1,\ldots ,n\}$, where $x_1,\cdots ,x_n$ are some distinct public elements of $\mathbb {F}$. It is easy to verify that only a subset A of size at least t is qualified to recover the secret using the shares $\{s_i\}_{i\in A}$. The corresponding access structure is called the (n, t)-threshold access structure. It is also easy to see that in Shamir’s scheme, a qualified set recovers the polynomial f(x), and hence, the randomness.

Not every SSS is RR. For example, consider the well-known Ito-Saito-Nishizeki construction in [20] for a general access structure, which we refer to as the ISN1. The secret is a single bit $s\in \mathbb {F}_2$ and the randomness is

$$\begin{aligned} \mathcal {R}=\{r_{A,i} \mid A \text { is a minimal qualified set and } i\in A \}, \end{aligned}$$

where a qualified set is called minimal if none of its proper subsets are qualified. The $r_{A,i}$’s are randomly chosen bits subject to $\sum _{i\in A}r_{A,i}=s$. The share of a participant i is

$$\begin{aligned} s_i = \{r_{A,i} \mid \text {there exists a minimal qualified set } A \text { such that } i\in A\}\ . \end{aligned}$$

It is easy to verify that the construction is information-theoretically both correct and private. However, as shown in Fig. 1, the ISN1 construction is not RR in general.

Fig. 1

The ISN1 construction is not randomness recoverable in general

A perfect RR-SSS construction A natural question to ask is whether every access structure admits a perfect (i.e., information-theoretically secure) RR-SSS. The answer to this question is not entirely trivial, but in the following, we show that another general construction, also introduced by Ito-Saito-Nishizeki in [19] which we refer to as the ISN2, is RR.

The secret is again a single bit $s\in \mathbb {F}_2$ and the randomness is

$$\begin{aligned} \mathcal {R}=\{r_{B} \mid B \text { is a maximal unqualified set}\},\ \ \end{aligned}$$

where an unqualified set is called maximal if every proper superset of it is qualified. The $r_{B}$’s are randomly chosen bits. The share of a participant i is

$$\begin{aligned} s_i = \Big (s+\sum _{B}r_B,\{r_{B} \mid B \text { is a maximal unqualified set and } i\notin B\}\Big )\ . \end{aligned}$$

It is easy to verify that the construction is both perfectly correct and perfectly private. Also, a minimal qualified set recovers the whole randomness.

Fact 1.1

The ISN2 construction [19] is RR.

1.3 Results on Perfect RR-SSS

We study the RR variant of some questions that have been extensively studied for (standard) perfect SSSs.

On Beimel’s conjecture for RR-SSSs The information ratio, defined to be the ratio between the largest share size and the secret size, is an important parameter that measures the efficiency of a SSS. Both ISN1 and ISN2 constructions have exponential information ratios in the number of participants. A long-standing open problem in the theory of secret sharing is to answer whether exponential upper bound is inevitable. Beimel [5] has conjectured that this is the case.

Conjecture 1.2

(Beimel) There exists an $\varepsilon > 0$ such that, for every integer n, there is an access structure with n participants such that every perfect SSS that realizes it has information ratio $2^{\Omega (n^{\varepsilon })}$.

Surprisingly, the best-known lower bound, due to Csirmaz [12], is $\Omega (n/\log n)$. We prove that an exponential lower bound holds for perfect RR-SSSs.

Theorem 1.3

(Exponential lower bound for perfect RR-SSS) For every integer n, there is an access structure with n participants such that every perfect RR-SSS that realizes it has information ratio $2^{\Omega (n)}$.

We prove the theorem for an access structure on n participants, which is the union of n/3 disjoint (3, 3)-threshold access structures (see Fig. 2); but the result holds in general, i.e., for the union of n/k disjoint (k, k)-thresholds for every $k\ge 2$. Similarly to Csirmaz, we use the so-called Shannon-type information inequalities to prove an exponential lower bound on the information ratio of this access structure for perfect RR-SSSs.

On weaker security notions Several non-perfect security notions for secret sharing have been proposed in the literature. It is well-known [22, Theorem 36] that any lower bound derived using information inequalities applies not only to perfect security but also to standard relaxations such as quasi-perfect [22, Chapter 5], almost-perfect [13, 23], and statistical security. The exponential lower bound of Theorem 1.3 is also valid for these relaxations because we only use (Shannon-type) information inequalities in the proof.

Ruling out the existence of efficient perfect RR-SSS for $\textsf{mAC}^0$. Access structures are in 1-1 correspondence with monotone circuits. The $\textsf{mAC}^0$ class consists of all monotone circuits of depth O(1) and polynomial size, with AND/OR gates with unbounded fan-in. Unfortunately, the above result shows that we cannot have efficient perfect RR-SSS for access structures even in $\textsf{mAC}^0$.

On contrary, the class of access structures admitting efficient perfect (standard) SSSs is much richer. In particular, it contains $\textsf{mNC}^1$, the class of monotone circuits of depth $O(\log n)$ and polynomial size with AND/OR gates with a maximum fan-in of 2, which is known to strictly contain $\textsf{mAC}^0$. We refer to [6] for further discussion on the class of efficient perfect SSSs. It is open whether every access structure in $\textsf{mP}$, the class of monotone circuits of polynomial size with AND/OR gates with unbounded fan-in, admits an efficient perfect SSS.

1.4 Results on Computational RR-SSS

In a computational SSS [35], we require that the sharing and reconstruction algorithms be polynomial-time in the security parameter and the number of participants. Furthermore, we require that a polynomial-time adversary cannot distinguish between the shares of an unqualified set for every pair of secrets.

An unpublished result by Yao shows that assuming the existence of one-way functions, every access structure in $\textsf{mP}$ admits an efficient computational SSS. The construction is a generalization of the results of Benaloh and Leichter [8] that constructs a perfect SSS for polynomial-size monotone formulae. We refer to [38] for details of the construction. In a recent work by Applebaum et al. [4], this result is extended to certain classes of access structures that lack efficient representation. By assuming OWFs with sub-exponential security, they construct computational secret sharing schemes with share sizes that are poly-logarithmic in the representation size of the access structure (which corresponds to the size of the truth table or the graph). It is open whether (efficient) computational SSS for any class of access structures implies OWFs. Assuming the existence of OWFs, an unpublished result of Rudich shows that computational SSS for $\textsf{mNP}$ implies oblivious transfer; see [5, 28].

OWFs from RR-SSS for $\textsf{AC}^0$ As we mentioned above, it is still open whether computational (standard) SSS for any class of access structures implies OWFs. One main obstacle to proving this possibly true statement is that the existence of efficient perfect SSS for every access structure has not yet been (unconditionally) ruled out, even though it is generally believed not to be the case, as it has been manifested in Beimel’s conjecture (Conjecture1.2). However, by our result on the exponential lower bound for RR-SSS (Theorem 1.3), the situation for RR-SSS is different. We use the method developed by Impagliazzo and Luby in [18], together with a variant of Csirmaz’s framework [12] for lower bounding the information ratio of perfect SSSs adapted for the computational setting, to prove that existence of computational RR-SSS for certain access structures in $\textsf{AC}^0$ implies the existence of OWFs.

Construction of computational RR-SSS A perfect linear SSS can be converted into a computational RR-SSS using a one-time KDM-secure SKE naturally and straightforwardly. For the sake of completeness, in Sect. 5, we state this formally. In that section, we introduce a type of PRG with a KDM-like security which turns out convenient in constructing a simple computational RR-SSS from a perfect linear SSS with the same access structure.

1.5 Applications of RR-ABE

The notion of RR-SSS was implicitly used as a key tool to obtain randomness recoverable single-key attribute-based public-key encryption schemes [15, 31], which in turn imply DV-NIZK for all NP [31]. Let us recall the definition of ABE. We have a master public key mpk and a master secret key msk. For any attribute string x, we have an attribute secret key $sk_x$, obtained as $\textsf{KGen}(msk,x)$, where $\textsf{KGen}$ is the key generation algorithm of the ABE. We encrypt a message m under mpk and a given circuit C to get a ciphertext ct. Now someone who has $sk_x$ can decrypt ct to get m iff $C(x)=1$.

We say that the ABE is RR if when $C(x)=1$, then $sk_x$ not only recovers m, but also all the randomness used by the encryption algorithm.

In the single-key security notion, an adversary can ask for only one attribute secret key $sk_x$, and has to win in an indistinguishability sense against a challenger who encrypts with respect to some circuit C where $C(x)=0$.

A standard way to build single-key RR-ABE is as follows: if $|x|=n$, then the master secret key has n PKE secret keys $(sk_1, ..., sk_n)$ and mpk contains the corresponding public keys $(pk_1, ..., pk_n)$. An attribute secret key for x contains those $sk_i$ where $x_i=1$. To encrypt m under mpk and C, we share m according to C to get the shares. We then encrypt each share under $pk_i$, and return all the ciphertexts. The notion of RR-SSS is a key tool in realizing randomness recoverability for the above single-key ABE scheme, as it allows us to recover the randomness used by sharing process, a major source of the overall randomness.

2 Preliminaries

In this section, we present the necessary background.

2.1 Random Variables

We denote random variables (RV) by boldface characters and use $\textsf{supp}(\varvec{X})$ to denote the support of RV $\varvec{X}$. We use the terms RV and distribution interchangeably throughout the paper. The Shannon entropy of $\varvec{X}$ is denoted by $\textrm{H}(\varvec{X})$. The entropy of $\varvec{X}$ conditioned on RV $\varvec{Y}$ is denoted and defined by $\textrm{H}(\varvec{X}|\varvec{Y}):=\textrm{H}(\varvec{X},\varvec{Y})-\textrm{H}(\varvec{Y})$. The mutual information between $\varvec{X},\varvec{Y}$ is defined and denoted by $\textrm{I}(\varvec{X}:\varvec{Y}):=\textrm{H}(\varvec{X})-\textrm{H}(\varvec{X}|\varvec{Y})$.

Let us also recall the functional representation lemma [14, page 626], a well-known lemma in information theory, that will be used in this paper. We use the notation $\varvec{X}\equiv \varvec{Y}$ for identically distributed RVs.

Lemma 2.1

(Functional representation lemma [14]) For every pair of jointly distributed RVs $(\varvec{X},\varvec{Y})$, there exists a RV $\varvec{R}$, independent of $\varvec{X}$, and a mapping $\mu$ such that $(\varvec{X},\varvec{Y})\equiv \big (\varvec{X},\mu (\varvec{X},\varvec{R})\big )$

Remark 2.2

Throughout the paper, we will consider a non-uniform model of computation, however, our results hold true for the uniform model.

We call the family $\varvec{X}=\{\varvec{X}_{\lambda }\}_{\lambda \in \mathbb {N}}$ of RVs efficiently sampleable if there exists a family of polynomial-time algorithms $\textsf{Sample}=\{\textsf{Sample}_{\lambda }\}_{\lambda \in \mathbb {N}}$ such that $\textsf{Sample}_{\lambda }(1^{\lambda })\equiv \varvec{X}_{\lambda }$. We call $\lambda$ the security parameter and refer to $\varvec{X}$ as a family of RVs, or simply an RV, indexed by the security parameter. We recall that a function $\varepsilon :\mathbb {N}\rightarrow \mathbb {R}^{\ge 0}$ is called negligible if for every $d>0$ there exists some $\lambda _0$ such that for every $\lambda >\lambda _0$ it holds that $\varepsilon (\lambda )<\frac{1}{\lambda ^{d}}$.

Definition 2.3

(Computational indistinguishablity) Let $\varvec{X}$ and $\varvec{Y}$ be efficiently sampleable distributions indexed by the security parameter $\lambda$. We say that $\varvec{X}$ and $\varvec{Y}$ are computationally indistinguishable and write $\varvec{X}_{\lambda }{{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{Y}_{\lambda }$ if for every family of polynomial size circuits $\mathcal {D}=\{\mathcal {D}_{\lambda }\}_{\lambda \in \mathbb {N}}$ (i.e., $\mathcal {D}_{\lambda }$ has polynomially many gates in the security parameter), there exists a negligible function $\varepsilon$ such that

$$\begin{aligned} |\Pr [\mathcal {D}_{\lambda }(\varvec{X}_{\lambda })=1]-\Pr [\mathcal {D}_{\lambda }(\varvec{Y}_{\lambda })=1]|\le \varepsilon (\lambda ) \ . \end{aligned}$$

We usually drop the security parameter and write $\varvec{X}{{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{Y}$ for $\varvec{X}_{\lambda }{{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{Y}_{\lambda }$, and $\mathcal {D}(\varvec{X}_{\lambda })$ or $\mathcal {D}(\varvec{X})$ instead of $\mathcal {D}_{\lambda }(\varvec{X}_{\lambda })$.

We will also face functions of the form $\varepsilon (n,\lambda )$, indexed by two parameters, which we require them to be polynomial in n and negligible in $\lambda$ (e.g., to be of the form $\textsf{poly}(n)\textsf{negl}(\lambda )$), where n will be the number of participants in secret sharing schemes. To remove any confusion, we make the definition precise.

Definition 2.4

We say that, $\varepsilon (n,\lambda )$, where $\varepsilon :\mathbb {N}\times \mathbb {N}\mapsto \mathbb {R}^{\ge 0}$, is polynomial in n and negligible in $\lambda$ if for every $\lambda \in \mathbb {N}$, the function $\varepsilon '_\lambda (n):=\varepsilon (n,\lambda )$ is polynomial in n, and for every $n\in \mathbb {N}$, the function $\varepsilon ''_n(\lambda ):=\varepsilon (n,\lambda )$ is negligible in $\lambda$. An example of such a function is $n^2 \frac{1}{2^\lambda }$.

2.2 One-Way Function

Definition 2.5

(OWF) A function $f: \{0,1\}^\star \rightarrow \{0,1\}^\star$ is called a one-way function (OWF) if the following two conditions hold:

• 1. There is a polynomial-time algorithm that on input x outputs f(x).

• 2. For every polynomial-size circuit family $\{\mathcal {C}_\lambda \}_\lambda$, the following probability is negligible:

  $$\begin{aligned} \Pr [f(\mathcal {C}_\lambda (f(\varvec{U}_\lambda )))=f(\varvec{U}_\lambda )]. \end{aligned}$$

The following lemma is due to Impagliazzo, Levin, and Luby [17]. It was used by Impagliazzo and Luby in [18] to prove that short-key SKE implies OWF. In Sect. 4, we use this lemma, in a similar manner, to prove that computational RR-SSS for $\textsf{AC}^0$ implies the existence of OWF.

Lemma 2.6

([17]) If there is a polynomial-time computable function $f: \{0,1\}^\lambda \rightarrow \{0,1\}^{l(\lambda )}$, a polynomial-time samplable distribution $\varvec{D}=\{\varvec{D}_\lambda \}_\lambda$ and a constant $d > 0$ such that $f(\varvec{U}_\lambda ) {{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{D}_\lambda$ and for large enough $\lambda$, $H(\varvec{D}_\lambda ) \ge H(f(\varvec{U}_\lambda )) + 1/{\lambda ^d}$, then there is a OWF.

2.3 Access Structure

In the secret sharing context, there is set of participants, which we denote by $P$, and a distinguished participant called the dealer, which we denote by $0\notin P$.

Definition 2.7

(Access structure) A non-empty subset $\Gamma \subseteq 2^{P}$, with $\emptyset \notin \Gamma$, is called an access structure on $P$ if it is monotone; that is, $A\subseteq B\subseteq P$ and $A\in \Gamma$ imply that that $B\in \Gamma$. A subset $A\subseteq P$ is called qualified if $A\in \Gamma$; otherwise, it is called unqualified. A qualified subset is called minimal if none of its proper subsets is qualified. An unqualified subset is called maximal if every proper superset of it is qualified.

There is a natural one-to-one correspondence between access structures with n participants and monotone Boolean functions with n variables.

2.4 Secret Sharing

A secret sharing scheme (SSS) can be defined in the following two equivalent ways. The first definition is more useful for working in the information-theoretic setting, while the second one is more useful in the computational setting.

Definition 2.8

(SSS in terms of jointly distributed RVs) A tuple $\big (\varvec{S}_{i}\big )_{i\in P\cup \{0\}}$ of jointly distributed RVs is called a SSS on the set of participants $P$ when $|\textsf{supp}(\varvec{S}_{0})|\ge 2$. The RV $\varvec{S}_{0}$ is called the secret RV and its support is called the secret space. The RV $\varvec{S}_{i}$ is called the share RV of the participant $i\in P$ and its support is called his share space.

Definition 2.9

(SSS in terms of sharing map) Let $\mu :\mathcal {S}_0\times \mathcal {R}\rightarrow \big (\mathcal {S}_i\big )_{i\in P}$ be a mapping and $\varvec{R}$ be a distribution on $\mathcal {R}$, called the randomness RV. We refer to $\Pi =(\varvec{R},\mu )$ as a SSS if $|\mathcal {S}_0|\ge 2$. We call $\mu$ the sharing map and $\mathcal {R}$ the randomness space. Also, $\mathcal {S}_0$ is called the secret space and $\mathcal {S}_i$ is called the share space of participant i

The equivalence of these two definitions follows by the functional representation lemma (Lemma 2.1).

The following notation will be used throughout the paper.

Notation 2.10

For a SSS $\Pi =\big (\varvec{S}_{i}\big )_{i\in P\cup \{0\}}$ and a subset ${A}\subseteq P$, we use the notation $\varvec{S}_{{A}}$ for the projection of $\Pi$ on the components in ${A}$; i.e., $\varvec{S}_{{A}}:=\big (\varvec{S}_{i}\big )_{i\in {A}}$. Also, for a sharing map $\mu :\mathcal {S}_0\times \mathcal {R}\rightarrow \big (\mathcal {S}_i\big )_{i\in P}$, $\mu _{{A}}$ stands for the projection of $\mu$ on the components in ${A}$. That is, if $(s_i)_{i\in P}=\mu (s,r)$, then $\mu _{{A}}(s,r):=(s_i)_{i\in {A}}$.

Linear SSS We call a SSS with sharing map $\mu :\mathcal {S}_0\times \mathcal {R}\rightarrow \big (\mathcal {S}_i\big )_{i\in P}$ and randomness $\varvec{R}$ linear when $\mathcal {R}$ and all $\mathcal {S}_i$’s, $i\in P\cup \{0\}$, are vector spaces over a common finite field, $\mu$ is a linear map and $\varvec{R}$ is uniformly distributed over $\mathcal {R}$. Throughout the paper, for simplicity, we assume that he underline finite field is the binary field.

2.5 Security Definitions for SSSs

The security of a SSS can be defined both in information-theoretic and computational settings.

Definition 2.11

(Perfect security) We say that $\Pi =\big (\varvec{S}_{i}\big )_{i\in P\cup \{0\}}$ is a perfect SSS for an access structure $\Gamma$, if the following two conditions hold:

• Perfect correctness $\textrm{H}(\varvec{S}_{0}|\varvec{S}_{{A}})=0$ for every qualified set ${A}\in \Gamma$.

• Perfect privacy $\textrm{I}(\varvec{S}_{0}:\varvec{S}_{{B}})=0$ for every unqualified set ${B}\notin \Gamma$.

If $\Pi$ is a perfect SSS for $\Gamma$, we also say that $\Pi$ realizes $\Gamma$ perfectly or $\Gamma$ admits $\Pi$ perfectly.

Computational secret sharing is defined to realize a family $\Gamma =\{\Gamma _n\}_{n\in \mathbb {N}}$ of access structures, where $\Gamma _n$ is an access structure with n participants with participants set $P_n$. A computational SSS for $\Gamma$ is a tuple $\Pi =\big (\varvec{R},\mu )$ with

$$\begin{aligned} \begin{array}{c} \varvec{R}=\{\varvec{R}_{\lambda ,n}\}_{n,\lambda \in \mathbb {N}} \ , \\ \mu =\{\mu _{\lambda ,n}:\mathcal {S}_{0,\lambda ,n}\times \mathcal {R}_{\lambda ,n}\rightarrow \big (\mathcal {S}_{i,\lambda ,n}\big )_{i\in P_n}\}_{\lambda ,n\in \mathbb {N}} \ , \end{array} \end{aligned}$$

where for every $\lambda ,n\in \mathbb {N}$, the tuple $\big ({\varvec{R}_{\lambda ,n}},\mu _{\lambda ,n})$ is a secret sharing scheme with participant set $P_n$. For simplicity, we drop the subscripts $\lambda$ and n and simply say that $\Pi =\big (\varvec{R},\mu )$ with $\mu :\mathcal {S}_0\times \mathcal {R}\rightarrow \big (\mathcal {S}_i\big )_{i\in P}$ is a family of SSSs indexed by $\lambda$ and n. That is, we implicitly assume that all the components of the scheme (i.e., the sharing map, the secret, randomness, and share spaces and RVs) are indexed by $\lambda$ and n.

Definition 2.12

(Computational security) Let $\Gamma =\{\Gamma _n\}_{n\in \mathbb {N}}$ be a collection of access structures and $\Pi =\big (\varvec{R},\mu )$ with $\mu :\mathcal {S}_0\times \mathcal {R}\rightarrow \big (\mathcal {S}_i\big )_{i\in P}$ be a family of SSSs indexed by the security parameter $\lambda$ and n. We say that $\Pi$ is a computational SSS for $\Gamma$ if the following conditions hold:

• Efficient randomness sampling The RV $\varvec{R}$ is polynomial-time sampleable in $\lambda$ and n.

• Polynomial secret length $\log |\mathcal {S}_0|$ is polynomial in $\lambda$ and n.

• Efficient sharing The sharing map $\mu$ is polynomial-time computable in $\lambda$ and n.

• Efficient secret reconstructionThere exists a polynomial-time algorithm $\textsf{Recon}$ in $\lambda$ and n such that for every qualified set $A \in \Gamma _n$ and secret $s\in \mathcal {S}_{0}$, the reconstruction error probability $\Pr [\textsf{Recon}(A, \mu _{{A}}(s,\varvec{R})) \ne s]$ is negligible in $\lambda$ and polynomial in n (see Definition 2.4).

• Computational privacy for every unqualified set ${B}\notin \Gamma _n$ and every pair of secrets $s,s^\prime \in \mathcal {S}_0$, $\mu _{{B}}(s,\varvec{R}){{\mathop {\equiv }\limits ^{\textrm{c}}}}\mu _{{B}}(s^\prime ,\varvec{R})$. Additionally, we require that the negligible function that exists for these two computationally indistinguishable distributions by Definition 2.3 be polynomial in n (see Definition 2.4).

Remark 2.13

Note that we do not restrict n to be a function of $\lambda$; because, if we do so, we have to change the access structure every time we change the security parameter, which is generally an undesirable property. Nevertheless, we will occasionally consider the case of $n=\textsf{poly}(\lambda )$ towards proving some of our theoretical results. Also note that because n is an independent parameter, we have to parameterize the reconstruction error and distinguisher’s advantage as functions of both n and $\lambda$. Nevertheless, we do not require them to be negligible in n (not even reverse polynomial in n). For our purposes, it suffices to require these quantities to be negligible in $\lambda$ and polynomial in n (see Definition 2.4).

If $\Pi$ is a computational SSS for $\Gamma =\{\Gamma _n\}_{n\in \mathbb {N}}$, we may simply say that $\Pi$ is a computational SSS for $\Gamma _n$. We also say that $\Pi$ realizes $\Gamma _n$ computationally or $\Gamma _n$ admits $\Pi$ computationally.

The following lemma will be used later in the paper. Here, we present a sketch of the proof. We refer to Appendix A for the full proof.

Lemma 2.14

Let $\Pi =(\mu ,\textbf{R})$ be a perfect/computational SSS with t-bit secrets and let $\varvec{S}$ be an RV independent of $\textbf{R}$ over the secret space. Then, for every unqualified set B,

$$\begin{aligned} (\varvec{S},\mu _B(\varvec{S},\textbf{R})) {{\mathop {\equiv }\limits ^{\textrm{c}}}}(\varvec{S},\mu _B(0^t,\textbf{R})). \end{aligned}$$

Proof

(Sketch) In the case of perfect SSS, the assertion immediately follows the independence of $\varvec{S}$ and $\mu _B(\varvec{S},\textbf{R})$. Assume that $\Pi$ is a computational SSS. Let $\mathcal {D}$ be a polynomial-size circuit that distinguishes $(\varvec{S},\mu _B(\varvec{S},\textbf{R}))$ and $(\varvec{S},\mu _B(0^t,\textbf{R}))$ with non-negligable probability. Because $\textbf{R}$ is independent of $\varvec{S}$, there is a secret $s \in \textsf{supp}(\varvec{S})$ such that $\mathcal {D}$ distinguishes $(s,\mu _B(s,\textbf{R}))$ and $(s,\mu _B(0^t,\textbf{R}))$ with non-negligable probability. Let $\mathcal {C}(\cdot )=\mathcal {D}(s,\cdot )$. Then $\mathcal {C}$ distinguishes $\mu _B(s,\textbf{R})$ and $\mu _B(0^t,\textbf{R})$ with non-negligible probability which contradicts the computational privacy of the SSS. $\square$

2.6 Information Ratio

The efficiency of SSSs is usually measured using a parameter called information ratio. The information ratio of an SSS with participants set $P$, secret space $\mathcal {S}_0$ and share space $\mathcal {S}_i$ for participant $i\in P$, is defined to be $\max _{i\in P}\frac{\log |\mathcal {S}_i|}{\log |\mathcal {S}_0|}$.

The perfect information ratio, or simply information ratio, of an access structure is defined to be the infimum of all information ratios of all SSSs that perfectly realize it.

Beimel [5] has conjectured that there are families of access structures with exponential information ratio in the number of participants; see Conjecture 1.2.

Remark 2.15

Beimel has also stated the conjecture in terms of share size instead of information ratio in [5]; this corresponds to the case where the secret is a single bit. There are access structures whose information ratio for exponentially-long secrets (in the number of participants) may be significantly better than the information ratio achievable for short secrets [3]. Nevertheless, it is widely believed that the stronger conjecture (i.e., for information ratio) holds true.

Csirmaz framework for lower bounding information ratio Following [11, 25], Csirmaz proposed a framework in [12] to prove lower bounds on the information ratio of perfect SSSs. His framework is captured in the following lemma which is based on the properties of the entropy function as well as the correctness and privacy properties of perfect SSSs.

Lemma 2.16

(Csirmaz/Perfect) Let $\Pi =(\varvec{S}_{i})_{i\in P\cup \{0\}}$ be a perfect SSS for an access structure $\Gamma$. For every subset $A\subseteq P\cup \{0\}$, let $f(A)=\frac{\textrm{H}(\varvec{S}_{A})}{\textrm{H}(\varvec{S}_{0})}$. Then, the following holds:

• 1. Non-negativity $f(A)\ge 0$ for every $A\subseteq P\cup \{0\}$.

• 2. Monotonicity $f(A)\ge f(B)$ for every $B\subseteq A\subseteq P\cup \{0\}$.

• 3. Submodularity $f(A)+f(B)\ge f(A\cup B) + f(A\cap B)$ for every $A,B\subseteq P\cup \{0,\}$.

• 4. Strong monotonicity $f(A)\ge f(B) + 1$ for every $A\in \Gamma$ and $B\subseteq A$ such that $B\notin \Gamma$.

• 5. Strong submodularity $f(A)+f(B)\ge f(A\cup B) + f(A\cap B) + 1$ for every $A,B\in \Gamma$ such that $A\cap B\notin \Gamma$.

If, using the inequalities (1)–(5), one can prove that for some participant $i\in P$, it holds that $f(\{i\})\ge \sigma$, then $\sigma$ will be a lower bound on the information ratio of the underlying access structure.

2.7 Randomness Recoverable SSS

We call a SSS $\Pi =(\varvec{R},\mu )$ randomness recoverable (RR) if qualified sets, in addition to the secret, can also recover the randomness; that is, there exists a function $\textsf{RNDrecover}$ such that for every qualified set A, $\Pr [\textsf{RNDrecover}(\mu _{{A}}(\varvec{R},s))=\varvec{R}]=1$ for every secret s. When $\Pi$ is a computational SSS, we require that $\textsf{RNDrecover}$ be a polynomial-time algorithm, in the security parameter and the number of participants; we also allow a negligible amount of error; i.e., $\Pr [\textsf{RNDrecover}(\mu _{{A}}(\varvec{R},s))=\varvec{R}]$ can be negligible in the security parameter and polynomial in the number of participants (see Definition 2.4 and Remark 2.13).

The following claim will be used in Sects. 3 and 4.

Claim 2.17

If $\Pi =(\varvec{S}_{i})_{i\in P\cup \{0\}}$ is an RR-SSS with perfect correctness (i.e., zero reconstruction error probability), then for every pair of qualified sets A, B, we have $\textrm{H}(\varvec{S}_{A})=\textrm{H}(\varvec{S}_{B})$, or equivalently $f(A)=f(B)$, using the notation of Lemma 2.16.

Proof

Denote the support of $\varvec{S}_{i}$ by $\mathcal {S}_i$, for $i\in P\cup \{0\}$. Let $(\varvec{R},\mu )$, with $\mu :\mathcal {S}_0\times \mathcal {R}\rightarrow \big (\mathcal {S}_i\big )_{i\in P}$, be the equivalent SSS in terms of Definition 2.9, which exists by the functional representation lemma (Lemma 2.1); that is, $\big (\varvec{S}_{0},(\varvec{S}_{i})_{i\in P}\big )\equiv \big (\varvec{S}_{0},\mu (\varvec{S}_{0},\varvec{R})\big )$. For simplicity, let us assume that $(\varvec{S}_{i})_{i\in P}=\mu (\varvec{S}_{0},\varvec{R})$. Since $\varvec{S}_{P}$ is a function of the secret and randomness and every qualified set can recover both of them, it follows that $\textrm{H}(\varvec{S}_{P}|\varvec{S}_{{A}})=0$, or equivalently $\textrm{H}(\varvec{S}_{{A}})=\textrm{H}(\varvec{S}_{P})$, for every qualified set ${A}$. The claim then follows. $\square$

3 Exponential Lower Bound for Perfect RR-SSS

In this section, we show that the Moon-Moser access structure, to be defined below, has an exponential information ratio for every perfect RR-SSS that realizes it. The result also applies to weaker security notions such as statistical security as will be discussed at the end of this section.

The Moon-Moser access structure Due to an old result by Moon and Moser [33], any graph with n vertices has at most $3^{n/3}$ maximal independent sets. A graph with exactly $3^{n/3}$ maximal independent sets is easy to construct: simply take the disjoint union of n/3 triangle graphs. Motivated by this example, we consider the access structure in Fig. 2, which is the union of n/3 (3, 3)-threshold access structures, and refer to it as the Moon-Moser access structure. Clearly, this access structure lies in $\textsf{AC}^0$.

Fig. 2

The Moon-Moser access structure

Theorem 3.1

For every n, there is an access structure in $\textsf{AC}^0$ such that every perfect RR-SSS that realizes it has information ratio $2^{\mathrm {\Omega }(n)}$.

We first present a notation and a claim and then prove the theorem.

Notation Denote the set of participants of the Moon-Moser access structure, with n participants, by $P=\{a_1,b_1,c_1,\ldots ,a_{n/3},b_{n/3},c_{n/3}\}$, with $\{a_i,b_i,c_i\}$ be a minimally qualified set for every $i=1,\ldots ,n/3$ (see Fig. 2). Let $\Pi =(\varvec{S}_{i})_{i\in P\cup \{0\}}$ be a perfect RR-SSS for this access structure and f be as in Lemma 2.16. For a participant $p_i\in \{a_i,b_i,c_i\}$, we define $p'_i$ and $p''_i$ to be the cyclic rotations of $p_i$ by one and two positions, respectively; i.e., $a''_i=b'_i=c_i$, $b''_i=c'_i=a_i$ and $c''_i=a'_i=b_i$. Also, we denote a set $\{p_{i_1},\ldots ,p_{i_k}\}$ simply by $p_{i_1}\cdots p_{i_k}$.

Claim 3.2

For every qualified set A, every $k=0,1,\ldots ,n/3$, and all choices for $p_1,\ldots ,p_k$ with $p_i\in \{a_i,b_i,c_i\}$, the following inequality holds:

$$\begin{aligned} \begin{array}{rcl} f(A)\ge & {} f(p_1p'_1\ldots p_kp'_k) + 3^{n/3-k} \ . \end{array} \end{aligned}$$

(3.1)

Proof of Claim 3.2

First, let us show that the following inequality is implied by Inequality (3.1):

$$\begin{aligned} \begin{array}{rcl} f(A)\ge & {} f(p_1p'_1\ldots p_{k-1}p'_{k-1}p_k) + 2\times 3^{n/3-k} \ . \end{array} \end{aligned}$$

(3.2)

By Inequality (3.1) we have:

$$\begin{aligned} \begin{array}{rcl} f(A) &{}\ge &{} f(p_1p'_1\ldots p_{k-1}p'_{k-1}p_kp'_k) + 3^{n/3-k} \ , \\ f(A) &{}\ge &{} f(p_1p'_1\ldots p_{k-1}p'_{k-1}p''_kp_k) + 3^{n/3-k} \ . \\ \end{array} \end{aligned}$$

Also by the monotonicity property, we have

$$\begin{aligned} \begin{array}{rl} f(p_1p'_1\ldots p_{k-1}p'_{k-1}p_kp'_k) + f(p_1p'_1\ldots p_{k-1}p'_{k-1}p''_kp_k) \ge &{} \\ f(p_1p'_1\ldots p_{k-1}p'_{k-1}p_kp'_kp''_k) + &{} f(p_1p'_1\ldots p_{k-1}p'_{k-1}p_k) \ . \end{array} \end{aligned}$$

Notice that $p_1p'_1\ldots p_{k-1}p'_{k-1}p_kp'_kp''_k$ is qualified and, hence, by Claim 2.17 we have

$$\begin{aligned} f(A) = f(p_1p'_1\ldots p_{k-1}p'_{k-1}p_kp'_kp''_k) \end{aligned}$$

. Therefore, Inequality (3.2) follows by adding the above three inequalities.

Now, we prove Inequality (3.1) by backward induction on k.

Base Denote $m=n/3$. For $k=m$, by strong submodularity property, we have:

$$\begin{aligned}{} & {} f(p''_1p_1p'_1\ldots p_mp'_m)+f(p''_2p_1p'_1\ldots p_mp'_m) \ge f(p''_1p''_2p_1p'_1\ldots p_mp'_m) \\ {}{} & {} + f(p_1p'_1\ldots p_mp'_m)+1 \ . \end{aligned}$$

Since the sets $p''_1p_1p'_1\ldots p_mp'_m$, $p''_2p_1p'_1\ldots p_mp'_m$ and $p''_1p''_2p_1p'_1\ldots p_mp'_m$ are all qualified, for every qualified set A, by Claim 2.17, we have:

$$\begin{aligned} f(A) = f(p''_1p_1p'_1\ldots p_mp'_m) = f(p''_2p_1p'_1\ldots p_mp'_m) = f(p''_1p''_2p_1p'_1\ldots p_mp'_m) \ . \end{aligned}$$

Therefore,

$$\begin{aligned} f(A) \ge f(p_1p'_1\ldots p_mp'_m)+1 \ ; \end{aligned}$$

that is, Inequality (3.1) holds for $k=n/3$.

Induction Now suppose that by the induction hypothesis

$$\begin{aligned} f(A) \ge f(p_1p'_1\ldots p_{k-1}p'_{k-1}p_kp'_k) + 3^{n/3-k} \ . \end{aligned}$$

By Inequality (3.2), we also have:

$$\begin{aligned} f(A) \ge f(p_1p'_1\ldots p_{k-1}p'_{k-1}p''_k) + 2\times 3^{n/3-k} \ . \end{aligned}$$

By the monotonicity property, we have

$$\begin{aligned} \begin{array}{rl} f(p_1p'_1\ldots p_{k-1}p'_{k-1}p_kp'_k) + f(p_1p'_1\ldots p_{k-1}p'_{k-1}p''_k) \ge &{} \\ f(p_1p'_1\ldots p_{k-1}p'_{k-1}p_kp'_kp''_k) + &{} f(p_1p'_1\ldots p_{k-1}p'_{k-1}) \ . \end{array} \end{aligned}$$

By adding the above three inequalities, noticing that $p_1p'_1\ldots p_{k-1}p'_{k-1}p_kp'_kp''_k$ is qualified, and using Claim 2.17, we get:

$$\begin{aligned} f(A) \ge f(p_1p'_1\ldots p_{k-1}p'_{k-1}) + 3^{n/3-(k-1)} \ ; \end{aligned}$$

that is, Inequality (3.1) holds for $k-1$. This completes the proof of Claim 3.2. $\square$

Proof of Theorem 3.1

Let $p_i\in \{a_1,b_1,c_1,\ldots ,a_{n/3},b_{n/3},c_{n/3}\}$. By letting $k=0$ and $A=\{p_i,p'_i,p''_i\}$ in Inequality (3.1), we have:

$$\begin{aligned} f(p_ip'_ip''_i) \ge 3^{n/3} \ . \end{aligned}$$

Also, $f(p_i)+f(p'_i)+f(p''_i) \ge f(p_ip'_ip''_i)$. Therefore, for every $i\in \{1,\ldots ,n/3\}$, for at least one $p\in \{a_i,b_i,c_i\}$, we have

$$\begin{aligned} f(p) \ge 3^{n/3-1}\ . \end{aligned}$$

$\square$

Remark 3.3

The above proof can be converted, in a straightforward manner, to a proof for the case of an access structure that is the union of n/k disjoint (k, k)-thresholds. Stated explicitly, every perfect RR-SSS that realizes the access structure that has

$$\begin{aligned} \{a_{1,1},a_{1,2},\cdots ,a_{1,k}\}, \{a_{2,1},a_{2,2},\cdots ,a_{2,k}\} ,\cdots , \{a_{n/k,1},a_{n/k,2}, \cdots ,a_{n/k,k}\} \end{aligned}$$

as its minimal qualified sets has information-ratio $2^{\Omega (n\log k / k)}$. The best exponent is achieved for $k=3$, which justifies our choice for the Moon-Moser access structure in this section.

Exponential lower bound for non-perfect RR-SSSs Besides perfect and computational security, several non-perfect security notions for secret sharing have appeared in the literature, including almost-perfect, quasi-perfect, and statistical. We refer to [21] for a comprehensive study of these security notions. Kaced [22, Theorem 36] has shown that any lower bound derived on the information ratio of (standard) SSSs using information inequalities applies not only to perfect security but also to quasi-perfect security (which can be shown to apply to almost-perfect and statistical security too). His result can also be extended to the case of RR-SSSs. Since, we only used (Shannon-type) information inequalities to derive our exponential lower bound on perfect RR-SSS, it also holds for all mentioned non-perfect security notions.

4 Computational RR-SSS for $\textsf{AC}^0$ Implies OWF

In this section, we show that the existence of computational RR-SSS for some access structures in $\textsf{AC}^0$ implies the existence of OWFs. Our method is similar to Impagliazzo and Levin’s method for proving that short-key SKE implies OWFs [18]. The idea is as follows: if $\Pi = (\mu ,\varvec{R})$ is a SSS for an access structure where B is unqualified, then $\varvec{S}\vert \vert \mu _B(\varvec{S},\varvec{R})$ and $\varvec{S}^\prime \vert \vert \mu _B(\varvec{S},\varvec{R})$ are computationally indistinguishable, where $\varvec{S}$ and $\varvec{S}^\prime$ are independent uniform RVs over the secret space. Indeed, when the SSS is perfect, $\mu _B(\varvec{S},\varvec{R})$ reveals no information about $\varvec{S}$ and so the two distributions are information-theoretically indistinguishable. But when the SSS is computational, $\mu _B(\varvec{S},\varvec{R})$ reveals some information about $\varvec{S}$. If this amount is not negligible, then we have two distributions that are computationally indistinguishable but statistically distinguishable and we can apply Lemma 2.6 to deduce the existence of OWF.

In Sect. 3, it was shown that there are access structures in $\textsf{AC}^0$ that do not admit efficient perfect RR-SSSs. In other words, an RR-SSS for such an access structure, that perfectly hides the secret from unqualified sets, has to have shares with exponential length. Hence intuitively, in a computational RR-SSS for such an access structure (because shares are of polynomial length), there are unqualified sets that obtain a considerable amount of information about the secret. This intuition is exactly phrased and proved in this section.

For simplicity, we first study the simpler case where in the definition of computational SSS (Definition 2.12), we require the reconstruction error probability to be equal to zero.

4.1 Zero Reconstruction Error

In this subsection, we present a lemma, a claim, and a corollary for computational SSSs with zero reconstruction errors. These results are modified in Sect. 4.2 to consider non-zero reconstruction error and will be used in Sect. 4.3 to prove the main result of this section.

A variant of Csirmaz’s framework (see lemma 2.16) adapted to the computational setting with perfect correctness (i.e., zero reconstruction error) is needed. The following lemma states this variant.

Lemma 4.1

(Csirmaz/Computational/Perfect correctness) Let $\Pi = (\varvec{S}_i)_{i \in P \cup \{0\}}$ be a computational SSS with perfect correctness for an access structure $\Gamma$. For $A,B \subseteq P \cup \{0\}$, denote $H(\varvec{S}_A)$ with H(A) and $H(\varvec{S}_A\vert \varvec{S}_B)$ with $H(A\vert B)$, respectively. Then, the non-negativity, monotonicity, and submodularity properties hold as in Lemma 2.16 and, one has the following modified formulation of strong monotonicity and strong submodularity:

• 1. Strong monotonicity $H(A) \ge H(B) + H(0\vert B)$ for every $A \in \Gamma$ and $B \subset A$ such that $B \notin \Gamma$.

• 2. Strong submodularity $H(A) + H(B) \ge H(A\cup B) + H(A \cap B) + H(0\vert A\cap B)$ for every $A,B \in \Gamma$ such that $A \cap B \notin \Gamma$.

Proof

Inequality (1) holds because A is qualified and due to the monotonicity property:

$$\begin{aligned} H(A)= H(\{0\}\cup A) \ge H(\{0\} \cup B) = H(B) + H(0\vert B). \end{aligned}$$

Inequality (2) follows from the following relations:

$$\begin{aligned} H(A) + H(B)&= H(\{0\}\cup A) + H(\{0\}\cup B)\\&\ge H(\{0\}\cup A \cup B) + H(\{0\} \cup (A \cap B)) \\&\ge H(A\cup B) + H(A \cap B) + H(0 \vert A \cap B). \end{aligned}$$

In the first equality, we have used the fact that A and B are qualified. The first and second inequalities follow by the submodularity and monotonicity properties, respectively.

$\square$

Notation In what follows, let $P=\{a_1,b_1,a_2,b_2,\cdots ,a_{n/2},b_{n/2}\}$ and $\Gamma$ be an access structure with minimally qualified sets $\{a_1,b_1\},\cdots ,\{a_{n/2},b_{n/2}\}$ (see Fig. 3). Note that this access structure lies in $\textsf{AC}^0$. According to Remark 3.3, $\Gamma$’s information ratio is $2^{\Omega (n)}$. For $p_i \in \{a_i,b_i\}$, let $p_i^\prime$ be the other element of $\{a_i,b_i\}$; i.e., if $p_i = a_i$ then $p^\prime _i = b_i$ and if $p_i = b_i$ then $p^\prime _i = a_i$. Also denote $\{p_1 , p_2 , \cdots , p_k \}$ with $p_1 p_2 \cdots p_k$ and use the notation in Lemma 4.1 for entropies.

Fig. 3

Union of (2, 2)-threshholds

Claim 4.2

Let $\Pi$ be a computational RR-SSS with perfect correctness for $\Gamma$ and A be a qualified set in $\Gamma$ with $H(A) \le c$. Then for all $k = 0,1,\cdots , n/2$,

$$\begin{aligned} H(\varvec{p}_1\varvec{p}_2\cdots \varvec{p}_k) + \frac{c}{2^k} \ge H(A), \end{aligned}$$

where $\varvec{p}_i$ is a uniform RV over $\{a_i,b_i\}$ and $\varvec{p}_i$’s are independent.

Proof

We prove the claim by induction on k. Base: The base ($k=0$) holds by the assumption. Induction: Suppose that by the induction hypothesis we have:

$$\begin{aligned} H(\varvec{p}_1\varvec{p}_2\cdots \varvec{p}_k) + \frac{c}{2^k} \ge H(A), \end{aligned}$$

(4.1)

where $k < n/2$. By the submodularity property

$$\begin{aligned} \begin{aligned} H(\varvec{p}_1\varvec{p}_2\cdots \varvec{p}_k a_{k+1}) + H(\varvec{p}_1\varvec{p}_2\cdots \varvec{p}_k b_{k+1}) \ge H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_k a_{k+1} b_{k+1} )\\ + H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_k). \end{aligned} \end{aligned}$$

(4.2)

Since $\{\varvec{p}_1, \varvec{p}_2, \cdots , \varvec{p}_k, a_{k+1}, b_{k+1} \}$ is qualified, then according to Claim 2.17, we have:

$$\begin{aligned} H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_k a_{k+1} b_{k+1}) = H(A). \end{aligned}$$

(4.3)

Summing up relations (4.1), (4.2) and (4.3), we get:

$$\begin{aligned} H(\varvec{p}_1\varvec{p}_2\cdots \varvec{p}_k a_{k+1}) + H(\varvec{p}_1\varvec{p}_2\cdots \varvec{p}_k b_{k+1}) + \frac{c}{2^{k}} \ge 2H(A). \end{aligned}$$

So:

$$\begin{aligned} H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_k \varvec{p}_{k+1}) + \frac{c}{2^{k+1}}&= \frac{1}{2}\big (H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_k a_{k+1}) \\&\quad \quad + H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_k b_{k+1})\big ) +\frac{c}{2^{k+1}} \ge H(A)\ . \end{aligned}$$

$\square$

The following corollary could be considered as a quantitative contrapositive for Theorem 3.1.

Corollary 4.3

Let $\Pi$ be a computational RR-SSS for $\Gamma$ with perfect correctness and m-bit secrets and let n be a polynomial in $\lambda$. Then for large enough $\lambda$:

$$\begin{aligned} \frac{m}{2} \ge H(0|\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{n/2}), \end{aligned}$$

where $\varvec{p}_i$ is a uniform RV over $\{a_i,b_i\}$ and $\varvec{p}_i$’s are independent.

Proof

Sharing algorithm’s running time and m are polynomials, so for large enough $\lambda$ we have $2^{\frac{n}{2}-1}m \ge H(A)$, where A is an arbitrary qualified set. Applying Claim 4.2 to this inequality, if follows that

$$\begin{aligned} H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{n/2}) + \frac{m}{2} \ge H(A). \end{aligned}$$

(4.4)

On the other hand, $\{\varvec{p}_1^\prime , \varvec{p}_1, \varvec{p}_2,\cdots ,\varvec{p}_{n/2}\}$ and $\{\varvec{p}_2^\prime , \varvec{p}_1, \varvec{p}_2,\cdots ,\varvec{p}_{n/2}\}$ are qualified sets, while $\{\varvec{p}_1, \varvec{p}_2, \cdots , \varvec{p}_{n/2}\}$ is not. So, according to the (computational) strong submodularity property,

$$\begin{aligned} H(\varvec{p}_1^\prime \varvec{p}_1 \varvec{p}_2&\cdots \varvec{p}_{n/2}) + H(\varvec{p}_2^\prime \varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{n/2}) \\&\ge H(\varvec{p}_1^\prime \varvec{p}_2^\prime \varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{n/2}) + H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{n/2}) + H(0\vert \varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{n/2}). \end{aligned}$$

Applying Claim 2.17, we get

$$\begin{aligned} H(A) \ge H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{n/2}) + H(0\vert \varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{n/2}). \end{aligned}$$

Summing up the above inequality and Inequality (4.4), one gets the desired result.$\square$

4.2 Non-zero Reconstruction Error

In this subsection, we provide variants of Lemma 4.1, Claim 4.2, and Corollary 4.3 that do not assume zero reconstruction error.

When the reconstruction error is zero, the entropy of the secret conditioned on the share of a qualified set is zero, because in this case, the secret is determined by the qualified set’s share. When we allow the reconstruction algorithm to fail with some bounded probability, this property no longer holds. The following is a variant of Fano’s inequality that we will use to prove that in this case, conditioned on the share of a qualified set, the entropy of the secret is o(1).

Lemma 4.4

Let $\varvec{X}$ and $\varvec{Y}$ be families of RVs such that $\varvec{Y}$ has polynomial length and f be a function such that $\Pr [\varvec{Y}\ne f(\varvec{X})]$ is negligible. Then $H(\varvec{Y}\vert \varvec{X})$ is o(1).

Proof

Define the indicator RV $\varvec{Z}$ as follows:

$$\begin{aligned} \varvec{Z}= {\left\{ \begin{array}{ll} 1\text { if }\varvec{Y}=f(\varvec{X})\\ 0\text { if }\varvec{Y}\ne f(\varvec{X}) \end{array}\right. } \ . \end{aligned}$$

Since $H(\varvec{Z}\vert \varvec{X}, \varvec{Y}) = 0$, we have:

$$\begin{aligned} H(\varvec{Y}\vert \varvec{X})&= H(\varvec{Y}\vert \varvec{X}) + H(\varvec{Z}\vert \varvec{X}, \varvec{Y}) \nonumber \\&= H(\varvec{Y}, \varvec{Z}\vert \varvec{X}) \nonumber \\&= H(\varvec{Z}\vert \varvec{X}) + H(\varvec{Y}\vert \varvec{X}, \varvec{Z})\nonumber \\&\le H(\varvec{Z}) + \sum _{x \in \textsf{Supp}(\varvec{X})}\big (\Pr [\varvec{X}= x, \varvec{Z}=0]H(\varvec{Y}\vert \varvec{X}=x, \varvec{Z}=0) \nonumber \\&\quad + \Pr [\varvec{X}=x, \varvec{Z}=1]H(\varvec{Y}\vert \varvec{X}=x, \varvec{Z}=1)\big ) \nonumber \\&= o(1) + \sum _{x \in \textsf{Supp}(\varvec{X})}\Pr [\varvec{X}= x, \varvec{Z}=0]H(\varvec{Y}\vert \varvec{X}=x, \varvec{Z}=0) \end{aligned}$$

(4.5)

$$\begin{aligned}&\le o(1) + \Bigg (\sum _{x \in \textsf{Supp}(\varvec{X})}\Pr [\varvec{X}=x,\varvec{Z}=0]\Bigg ) \log (\vert \textsf{Supp}(\varvec{Y})\vert ) \end{aligned}$$

(4.6)

$$\begin{aligned}&= o(1) + \Pr [\varvec{Z}=0]\log (\vert \textsf{Supp} (\varvec{Y}) \vert )\nonumber \\&= o(1) . \end{aligned}$$

(4.7)

Equation (4.5) holds for two reasons: First, $\varvec{Z}$ is a Bernouli RV with $\Pr [\varvec{Z}=0]=o(1)$ (indeed, this probability is negligable), so $H(\varvec{Z})=o(1)$; Second, when $\varvec{Z}=1$, $\varvec{Y}$ is determined by $\varvec{X}$; therefore, $H(\varvec{Y}\vert \varvec{X}=x, \varvec{Z}=1)=0$. Inequality (4.6) holds because $H(\varvec{Y}) \le \log (\vert \textsf{Supp} (\varvec{Y}) \vert )$. Equality (4.7) holds because $\Pr [\varvec{Z}=0]$ is negligable and $\varvec{Y}$ has polynomial length. $\square$

Lemma 4.5

Let $\Pi =(\mu ,\varvec{R})$ be a computational SSS, n be a polynomial in $\lambda$ and $\varvec{S}_0$ be an RV over the secret space. Then for every qualified set A, $H(\varvec{S}_0 \vert \mu _A(\varvec{S}_0,\varvec{R}))=o(1)$.

Proof

Let $\textsf{Recon}$ be the reconstruction algorithm and $\delta = \delta (\lambda ,n)$ be the reconstruction error. Then $\Pr [\textsf{Recon}( {A},\mu _A(\varvec{S}_0,\varvec{R}))\ne \varvec{S}_0] \le \delta (\lambda ,n)$ and because n is a polynomial in $\lambda$, this probability is negligable. Also, the length of $\varvec{S}_0$ is polynomial. Therefore, according to Lemma 4.4, $H(\varvec{S}_0 \vert \mu _A(\varvec{S}_0,\varvec{R}))=o(1)$.

$\square$

The following is a variant of Claim 2.17 that does not assume zero reconstruction error.

Claim 4.6

Let $\Pi =(\mu ,\varvec{R})$ be a computational RR-SSS, n be a polynomial in $\lambda$ and $\varvec{S}_0$ be an RV over the secret space. Then for any two qualified sets A and B, $\vert H(\mu _A(\varvec{S}_0,\varvec{R})) - H(\mu _B(\varvec{S}_0,\varvec{R})) \vert = o(1)$.

Proof

By Lemma 4.5, $H(\varvec{S}_0 \vert \mu _A(\varvec{S}_0,\varvec{R})) = o(1)$. Because $\Pi$ is RR, it can be proved that similarly

$$\begin{aligned} H(\varvec{R}\vert \mu _A(\varvec{S}_0,\varvec{R}))=o(1). \end{aligned}$$

Therefore, $H(\varvec{S}_0, \varvec{R}\vert \mu _A(\varvec{S}_0, \varvec{R})) = o(1)$ and, hence, $H(\varvec{S}_0,\varvec{R}) \le H(\mu _A(\varvec{S}_0,\varvec{R})) + o(1)$. On the other hand, $\mu _A(\varvec{S}_0,\varvec{R})$ is determined by $\varvec{S}_0$ and $\varvec{R}$; thus $H(\mu _A(\varvec{S}_0,\varvec{R})) \le H(\varvec{S}_0,\varvec{R})$. Similar bounds hold for $\mu _B(\varvec{S}_0,\varvec{R})$. The claim follows from these bounds.$\square$

The following is a variant of Csirmaz’s computational framework (4.1) stated for the case of the non-zero reconstruction error.

Lemma 4.7

(Csirmaz/Computational) Let $\Pi = (\varvec{S}_i)_{i \in P \cup \{0\}}$ be a computational SSS for an access structure $\Gamma$ and n be a polynomial in $\lambda$. Then, the non-negativity, monotonicity, and submodularity properties hold as in Lemma 2.16 and, one has the following modified formulation of strong monotonicity and strong submodularity:

• 1. Strong monotonicity $H(A) + o(1) \ge H(B) + H(0\vert B)$ for every $A \in \Gamma$ and $B \subset A$ such that $B \notin \Gamma$.

• 2. Strong submodularity $H(A) + H(B) + o(1) \ge H(A\cup B) + H(A \cap B) + H(0\vert A\cap B)$ for every $A,B \in \Gamma$ such that $A \cap B \notin \Gamma$.

Proof

Inequality (1) follows from the following relations:

$$\begin{aligned} H(A) + o(1) = H(\{0\}\cup A) \ge H(\{0\} \cup B) = H(B) + H(0\vert B). \end{aligned}$$

The left-hand side equality follows from Lemma 4.6. The rest is as in the proof of Lemma 4.1. Inequality (2) follows from the following relations:

$$\begin{aligned} H(A) + H(B) + o(1)&= H(\{0\}\cup A) + H(\{0\}\cup B)\\&\ge H(\{0\}\cup A \cup B) + H(\{0\} \cup (A \cap B)) \\&\ge H(A\cup B) + H(A \cap B) + H(0 \vert A \cap B). \end{aligned}$$

The equality follows from Lemma 4.6. The rest is as in the proof of Lemma 4.1. $\square$

Below is a modification of Claim 4.2 stated for the case of the non-zero reconstruction error.

Claim 4.8

Let $\Pi$ be a computational RR-SSS for $\Gamma$, n be a polynomial in $\lambda$ and A be a qualified set such that $H(A) \le c$. Then for $k = 0,1,\cdots , n/2$ one has:

$$\begin{aligned} H(\varvec{p}_1\varvec{p}_2\cdots \varvec{p}_k) + \frac{c}{2^k} + o(1) \ge H(A), \end{aligned}$$

where $\varvec{p}_i$ is a uniform RV over $\{a_i,b_i\}$ and $\varvec{p}_i$’s are independent.

Proof

Proof of this claim is achieved by applying appropriate and straightforward modifications to the proof of Claim 4.2. Explicitly, Claim 2.17 is used there to deduce $H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{k}a_{k+1}b_{k+1}) = H(A)$. Instead, we apply Claim 4.6 to deduce

$$\begin{aligned} H(\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{k}a_{k+1}b_{k+1}) + o(1) \ge H(A). \end{aligned}$$

Also, the induction hypothesis should be modified to include the term o(1). $\square$

Finally, we state a variant of Corollary 4.3 that does not assume zero reconstruction error.

Corollary 4.9

Let $\Pi$ be a computational RR-SSS for $\Gamma$ with m-bit secrets and n be a polynomial in $\lambda$. Then

$$\begin{aligned} \frac{m}{2} + o(1) \ge H(0|\varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{n/2}), \end{aligned}$$

where $\varvec{p}_i$ is a uniform RV over $\{a_i,b_i\}$ and $\varvec{p}_i$’s are independent.

Proof

The proof is the same as the proof of Corollary 4.3 with the following exceptions: Usages of Claim 4.2 and Claim 2.17 are replaced with those of Claim 4.8 and Claim 4.6, respectively. Indeed, these replacements substitute each claim with a corresponding variant that is adapted to the case of the non-zero reconstruction error. Also, the variant of strong submodularity that is stated in Lemma 4.7 should be used. $\square$

4.3 Main Result

Theorem 4.10

Let $\Gamma$ be the union of n/2 disjoint (2, 2)-thresholds (see Fig. 3). If $\Gamma$ has a computational RR-SSS, then there exists an OWF.

Proof

As in the previous subsections, assume that $\{a_i,b_i\}$, $1 \le i \le n/2$, are the minimal qualified sets. Let $\Pi = (\mu ,\varvec{R})$ be a computational RR-SSS for $\Gamma$ with m-bit secrets and $n=\textsf{poly}(\lambda )$. For $0 \le i \le n/2$, take $\varvec{p}_i$ to be a uniform RV over $\{a_i,b_i\}$ and set $\varvec{B}= \{\varvec{p}_1,\varvec{p}_2,\cdots ,\varvec{p}_{n/2}\}$.

According to Corollary 4.9 we have,

$$\begin{aligned} \frac{m}{2} + o(1) \ge H(0\vert \varvec{p}_1 \varvec{p}_2 \cdots \varvec{p}_{n/2}). \end{aligned}$$

So if we let $\varvec{S}_0$ be a uniform RV over the secret space, then

$$\begin{aligned} \frac{m}{2} + o(1) + H(\mu _{\varvec{B}}(\varvec{S}_0,\varvec{R})) \ge H(\varvec{S}_0 \vert \vert \mu _{\varvec{B}}(\varvec{S}_0,\varvec{R})). \end{aligned}$$

Let $\varvec{S}_0^\prime$ be a uniform secret independent of $\varvec{S}_0$ and $\varvec{R}$. Then

$$\begin{aligned} H(\varvec{S}_0^\prime \vert \vert \mu _{\varvec{B}}(\varvec{S}_0,\varvec{R})) = m + H(\mu _{\varvec{B}}(\varvec{S}_0,\varvec{R})). \end{aligned}$$

These together imply that

$$\begin{aligned} H(\varvec{S}_0^\prime \vert \vert \mu _{\varvec{B}}(\varvec{S}_0,\varvec{R})) + o(1) \ge H(\varvec{S}_0 \vert \vert \mu _{\varvec{B}}(\varvec{S}_0,\varvec{R})) + \frac{m}{2}. \end{aligned}$$

(4.8)

On the other hand, because $(\varvec{S}_0,\varvec{R})$ and $(\varvec{S}_0^\prime ,\varvec{R})$ have the same distribution, we have $\varvec{S}_0\vert \vert \mu _B(\varvec{S}_0,\varvec{R}) {\mathop {\equiv }\limits ^{c}} \varvec{S}_0^\prime \vert \vert \mu _B(\varvec{S}_0^\prime ,\varvec{R})$. Also it follows from the computational privacy of the SSS that $\varvec{S}^\prime _0\vert \vert \mu _B(\varvec{S}_0,\varvec{R}) {\mathop {\equiv }\limits ^{c}} \varvec{S}^\prime _0\vert \vert \mu _B(\varvec{S}_0^\prime , \varvec{R})$. Putting these together, we get

$$\begin{aligned} \varvec{S}_0^\prime \vert \vert \mu _{\varvec{B}}(\varvec{S}_0,\varvec{R}) {{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{S}_0\vert \vert \mu _{\varvec{B}}(\varvec{S}_0,\varvec{R}). \end{aligned}$$

(4.9)

Applying Lemma 2.6 to (4.8) and (4.9) (with $\varvec{D}_\lambda = \varvec{S}_0^\prime \vert \vert \mu _{\varvec{B}}(\varvec{S}_0,\varvec{R})$ and $f(\varvec{S}_0\vert \vert \varvec{R}\vert \vert \varvec{B}) = \varvec{S}_0\vert \vert \mu _{\varvec{B}}(\varvec{S}_0,\varvec{R})$), we get the desired result.$\square$

5 Construction of Computational RR-SSS

In this section, we observe that computational RR-SSS for $\textsf{NC}^1$ can be based on simple minicrypt primitives that have some kind of one-time KDM-like security. In particular, we first observe that an efficient linear SSS (and generally, an efficient SSS with a property that we call randomness simulatability) can be converted into a computational RR-SSS assuming the existence of one-time KDM-secure RR-SKE. Next we introduce the notion of linear-resistant PRG. Then, we see how an efficient perfect linear SSS can be converted into an efficient computational RR-SSS, using a linear-resistant PRG.

5.1 RR-SKE and KDM Security

First, we recall the definition of (RR-)SKE and (one-time) KDM-security.

Definition 5.1

(SKE/RR-SKE) Let $\mathcal {M}=\{\mathcal {M}_{\lambda }\}_{\lambda \in \mathbb {N}}$ be a family of message spaces and $\Sigma =(\textsf{Gen},\textsf{Enc},\textsf{Dec})$ be a tuple of probabilistic polynomial-time algorithms where

• $\textsf{Gen}$, called key-generation algorithm, on input $1^\lambda$ returns a key k,

• $\textsf{Enc}$, called encryption algorithm, gets a message m and a key k as input and returns a ciphertext ct,

• $\textsf{Dec}$, called decryption algorithm, gets a ciphertext ct and a key k as input and returns a message m or $\bot$.

$\Sigma$ is called a symmetric-key encryption (SKE) for $\mathcal {M}$ if for every $m\in \mathcal {M}_{\lambda }$:

$$\begin{aligned} \Pr [k\leftarrow \textsf{Gen}(1^\lambda ); ct\leftarrow \textsf{Enc}_{k}(m):\textsf{Dec}_{k}(ct)=m]=1 \ . \end{aligned}$$

We call $\Sigma$ randomness recoverable SKE (RR-SKE) if additionally there exists a polynomial-time algorithm $\textsf{Recover}$ such that:

$$\begin{aligned} \Pr [k\leftarrow \textsf{Gen}(1^\lambda ); ct\leftarrow \textsf{Enc}_{k}(m;\varvec{R}):\textsf{Recover}_{k}(ct)=\varvec{R}]=1 \ , \end{aligned}$$

where $\varvec{R}$ is the randomness used in the encryption algorithm.

Definition 5.2

Let $\Pi =(\textsf{Gen},\textsf{Enc},\textsf{Dec})$ be an SKE with key-space $\mathcal {K}$ and message-space $\mathcal {M}$. We say that $\Pi$ is one-time KDM-secure, if for each efficiently computable function $f:\mathcal {K}\rightarrow \mathcal {M}$,

$$\begin{aligned} \{ k \leftarrow \textsf{Gen}(1^\lambda ) : \textsf{Enc}_k(f(k)) \} {{\mathop {\equiv }\limits ^{\textrm{c}}}}\{k \leftarrow \textsf{Gen}(1^\lambda ) : \textsf{Enc}_k(0^{\vert f(k)\vert }) \}. \end{aligned}$$

The standard construction of Symmetric-Key Encryption (SKE) based on a pseudorandom function is RR. In the next section, we will discuss SKE schemes that ensure both randomness recoverability and one-time KDM-security. The work of [27] surveys RR-SKE schemes that meet KDM-security criteria for projection functions (simple functions where each output bit is dependent on only one input bit). Additionally, the research by [2] demonstrates how to extend KDM-security from projection functions to general efficient functions. However, this transformation does not maintain the randomness recoverability. To the best of our knowledge, RR-SKE schemes that satisfy one-time KDM-security for general efficient functions have not yet been addressed in the literature.

Lemma 5.3

Assume that $\Pi =(\textsf{Gen},\textsf{Enc},\textsf{Dec})$ is a one-time KDM-secure SKE and $g:\{0,1\}^{l_1+l_2+l_3}\rightarrow \{0,1\}^l$ is an effieciently computable function. Then one has

$$\begin{aligned} (\textbf{x},\textsf{Enc}_{\varvec{k}}(g(\varvec{k},\textbf{x},\textbf{y}))){{\mathop {\equiv }\limits ^{\textrm{c}}}}(\textbf{x},\textsf{Enc}_{\varvec{k}}(0^l)) \end{aligned}$$

where $\varvec{k}$ is $\Pi$’s key and has length $l_1$ and $(\textbf{x},\textbf{y})$ are jointy distributed RVs over $\{0,1\}^{l_2}\times \{0,1\}^{l_3}$ and independent of $\varvec{k}$.

Here, we present a sketch of the proof. We refer to Appendix B for the full proof.

Proof

(Sketch) Let $\mathcal {D}$ be a polynomial-size circuit that distinguishes the distributions $(\textbf{x},\textsf{Enc}_{\varvec{k}}(0^l))$ and $(\textbf{x},\textsf{Enc}_{\varvec{k}}(g(\varvec{k},\textbf{x},\textbf{y})))$ with non-negligable probability. Because $\varvec{k}$ is independent of $(\textbf{x},\textbf{y})$, there are $(x,y)\in \textsf{supp}(\textbf{x})\times \textsf{supp}(\textbf{y})$ such that $\mathcal {D}$ distinguishes $(x,\textsf{Enc}_{\varvec{k}}(g(\varvec{k},x,y)))$ and $(x,\textsf{Enc}_{\varvec{k}}(0^l))$. Let $\mathcal {C}(\cdot )=\mathcal {D}(x,\cdot )$ and $f(\cdot )=g(\cdot ,x,y)$. Then $\mathcal {C}$ distinguishes $\textsf{Enc}_{\varvec{k}}(f(\varvec{k}))$ and $\textsf{Enc}_{\varvec{k}}(0^l)$ with non-negligible probability which is in contradiction with the KDM security of $\Pi$. $\square$

5.2 RR-SSS from Randomness Simulatable SSS and One-Time KDM-Secure RR-SKE

Consider this simple construction for a computational RR-SSS using a general (i.e., not necessarily perfect or linear) efficient standard SSS (which is known to exist for access structures in $\textsf{mP}$, assuming OWF) and an RR-SKE with one-time KDM-security. The construction is as follows. First, use the SSS to share s||k with randomness r to compute the shares for the secret s, where k is the key of the SKE. Then, encrypt r under the secret key k using the SKE and append the ciphertext to the shares. The correctness and randomness recoverability requirements are trivial. Privacy follows from the KDM-security of the SKE. However, in order for the proof to go through, we require a property of the original SSS that we refer to as the randomness simulatability. Every linear SSS has this property but it remains open whether every access structure in $\textsf{mP}$ admits a randomness simulatable SSS.

In the following, we first define the notion of randomness simulatable SSS. Then, we present a theorem that formalizes the above construction.

Definition 5.4

(Randomness simulatable SSS) Let $\Pi =(\varvec{R},\mu )$ be a perfect or computational SSS for an access structure. We say that SSS $\Pi$ is randomness simulatable, if for each RV $\varvec{S}$ over the secret space and each unqualified set B there exists an efficiently computable function g and an efficiently sampleable RV $\widehat{\varvec{R}}$ independent of $(\varvec{S},\varvec{R})$ such that

$$\begin{aligned} (\varvec{S},\varvec{\mu }_B,\varvec{R}) {{\mathop {\equiv }\limits ^{\textrm{c}}}}(\varvec{S},\varvec{\mu }_B,g(\varvec{S},\varvec{\mu }_B,\widehat{\varvec{R}})) \ , \end{aligned}$$

where $\varvec{\mu }_B=\mu _B(\varvec{S},\varvec{R})$ denotes the share of the unqualified set B.

Notice that, ignoring the efficient computability of g and efficient sampleability of $\widehat{\varvec{R}}$, the existence of g and $\widehat{\varvec{R}}$ is always guaranteed by the functional representation lemma (Lemma 2.1). Also, in particular, linear SSSs are randomness simulatable. It is unclear to us whether every access structure in $\textsf{mP}$ —which is known to admit an efficient computational SSS [40] (see also [38])—admits a randomness simulatable scheme.

Theorem 5.5

Let $\Pi$ be a one-time KDM-secure RR-SKE with $\ell$-bit keys. Let $\mu _i$ be the sharing map of the i’th participant in a perfect/computational randomness simulatable SSS for an access structure with t-bit secret, $t>\lambda$, and $\rho$-bit randomness (i.e., the share of participant i is $\mu _i(s,r)$, where s is the secret and r is the randomness). Then, the SSS defined below is a computational RR-SSS for the same access structure.

Proof

Correctness and randomness recoverability trivially hold. We prove privacy. Let $s\in \{0,1\}^{t-\ell }$ be an arbitrary secret and let B be an unqualified set in the access structure. Let $\varvec{R}$ be SSS’s randomness, $\varvec{k}$ denote $\textsf{Gen}(1^\lambda )$ and $\varvec{\mu }_B$ denote $\mu _B(s\vert \vert \varvec{k},\varvec{R})$. For ease of notation, we simply denote the share of B for the secret s by $\varvec{\mu }_B\vert \vert \textsf{Enc}_{\varvec{k}}(\varvec{R})$ (i.e., we ignore the repetitions of $\textsf{Enc}_{\varvec{k}}(\varvec{R})$). Based on the randomness simulatability of the SSS, there exists an efficiently computable function g and an efficiently sampleable RV $\widehat{\varvec{R}}$ independent of $(\varvec{k},\varvec{R})$ such that

$$\begin{aligned} (s\vert \vert \varvec{k},\varvec{\mu }_B,\varvec{R}){{\mathop {\equiv }\limits ^{\textrm{c}}}}(s\vert \vert \varvec{k},\varvec{\mu }_B,g(s\vert \vert \varvec{k},\varvec{\mu }_B,\widehat{\varvec{R}})) \end{aligned}$$

Therefore, one has the following indistinguishability:

$$\begin{aligned} \varvec{\mu }_B\vert \vert \textsf{Enc}_{\varvec{k}}(\varvec{R}) {{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{\mu }_B\vert \vert \textsf{Enc}_{\varvec{k}}(g(s\vert \vert \varvec{k},\varvec{\mu }_B,\widehat{\varvec{R}})) \end{aligned}$$

(5.1)

According to Lemma 2.14, one has

$$\begin{aligned} (\varvec{k},\mu _B(s\vert \vert \varvec{k},\varvec{R})){{\mathop {\equiv }\limits ^{\textrm{c}}}}(\varvec{k},\mu _B(0^{t},\varvec{R})). \end{aligned}$$

In other words, $(\varvec{k},\varvec{\mu }_B) {{\mathop {\equiv }\limits ^{\textrm{c}}}}(\varvec{k},\varvec{\mu }_B^\prime )$, where $\varvec{\mu }_B^\prime =\mu _B(0^{t},\varvec{R})$. Because g is efficiently computable and $\widehat{\varvec{R}}$ is efficiently sampleable and independent of $(\varvec{k},\varvec{R})$, we have

$$\begin{aligned} \varvec{\mu }_B\vert \vert \textsf{Enc}_{\varvec{k}}(g(s\vert \vert \varvec{k},\varvec{\mu }_B,\widehat{\varvec{R}})) {{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{\mu }_B^\prime \vert \vert \textsf{Enc}_{\varvec{k}}(g(s\vert \vert \varvec{k},\varvec{\mu }_B^\prime ,\widehat{\varvec{R}})). \end{aligned}$$

(5.2)

On the other hand, because $(\varvec{\mu }_B^\prime ,\widehat{\varvec{R}})$ is independent of $\varvec{k}$, by Lemma 5.3, we have:

$$\begin{aligned} \varvec{\mu }_B^\prime \vert \vert \textsf{Enc}_{\varvec{k}}(g(s\vert \vert \varvec{k},\varvec{\mu }_B^\prime ,\widehat{\varvec{R}})) {{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{\mu }_B^\prime \vert \vert \textsf{Enc}_{\varvec{k}}(0^l). \end{aligned}$$

(5.3)

Equations (5.1), (5.2) and (5.3) then imply that

$$\begin{aligned} \varvec{\mu }_B\vert \vert \textsf{Enc}_{\varvec{k}}(\varvec{R}) {{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{\mu }_B^\prime \vert \vert \textsf{Enc}_{\varvec{k}}(0^l) \ . \end{aligned}$$

Because $\varvec{\mu }_B^\prime \vert \vert \textsf{Enc}_{\varvec{k}}(0^l)$ hides the secret s, privacy follows. $\square$

5.3 Linear-Resistant PRG

In this section, we present a variant of pseudo-random generators (PRG), with a KDM-like security for the class of linear functions.

Recall that a polynomial-time deterministic algorithm, $G:\{0,1\}^\star \rightarrow \{0,1\}^{\star }$ that maps $\lambda$-bit strings to $\ell (\lambda )$-bit strings is said to be PRG if $\ell (\lambda )>\lambda$ and $G(\varvec{U}_\lambda ){{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{U}_{\ell (\lambda )}$.

In the following definition, $\{0,1\}$ is identified with $\mathbb {F}_2$, the finitie field with two elements, and $+$ stands for the addition in the field or bitwise-XOR; that is, for $x=x_1,\ldots ,x_{\ell }$ and $y=y_1,\ldots ,y_{\ell }$, $x+y=(x_1\oplus y_1)||\cdots ||(x_\ell \oplus y_\ell )$.

Definition 5.6

Let $G:\{0,1\}^\lambda \rightarrow \{0,1\}^{\ell }$ be a polynomial-time deterministic algorithm with $\ell :=\ell (\lambda )>\lambda$. We call G a linear-resistant PRG if for every $\mathbb {F}_2$-linear function $L:\{0,1\}^\lambda \rightarrow \{0,1\}^{\ell }$, $G(\varvec{U}_\lambda )+L(\varvec{U}_\lambda ){{\mathop {\equiv }\limits ^{\textrm{c}}}}\varvec{U}_\ell$.

Clearly, every linear-resistant PRG is also a PRG. However, the converse is not necessarily correct. For example, if $G:\{0,1\}^{\lambda -1}\rightarrow \{0,1\}^{\ell -1}$ is a PRG, then so is $G':\{0,1\}^\lambda \rightarrow \{0,1\}^{\ell }$ defined as $G'(s_1\cdots s_\lambda )=s_1||G(s_2\cdots s_\lambda )$. It is clear that $G'$ is not linear-resistant.

It is easy to see that linear-resistant PRG implies one-time KDM-secure SKE against the class of all affine functions: simply consider the standard one-time-pad encryption scheme $\textsf{Enc}_k(m)=G(k)+m$. More precisely, if the input and output lengths of the linear-resistant PRG G are $\lambda$ and $\ell$, the key and message spaces of the constructed scheme are $\mathcal {K}=\mathbb {F}_2^{\lambda }$ and $\mathcal {M}=\mathbb {F}_2^{\ell }$, respectively, and it has KDM-security against all affine functions from $\mathbb {F}_2^{\lambda }$ to $\mathbb {F}_2^{\ell }$.

In particular, since this scheme is deterministic, the resulting SKE is RR.

Another variant of PRG that has a KDM-like property is the hinting PRG which can be used to achieve one-time KDM-secure SKE against any class of functions that can be computed in fixed polynomial time [27, Appendix B]. Also, note that both of these primitives can be instantiated using a random oracle. Despite the similarity between linear-resistant PRG and hinting PRG, the relationship between these primitives remains open, as is the (im)possibility of constructing linear-resistant PRG from OWF. In contrast, black-box separation between hinting PRG and PKE is known [1].

5.4 RR-SSS from Linear Perfect SSS and Linear-Resistant PRG

Consider the following simple construction for a computational RR-SSS using an efficient (standard) linear perfect SSS and a linear-resistant PRG G. To share a secret s, use the linear SSS to share s||r with randomness G(r) to compute the shares, where r is the randomness. It is clear that every qualified set can recover not only s but also r. Privacy follows from the linear-resistance security of the PRG. Notice that the class of access structures that admit efficient linear SSS is equivalent to the class of monotone boolean functions that admit efficient MSP (monotone-span programs [24]) which includes $\textsf{NC}^1$ (e.g., using the Benaloh-Leichter [8] construction).

We state the above construction in a theorem:

Theorem 5.7

Let $\mu$ be the sharing map of a perfect linear SSS for an access structure with $k\lambda$-bit secrets, $k>1$, and $\ell$-bit randomness (i.e., the shares of participants are the outputs of $\mu (s,r)$, where s is the secret and r is the randomness). Let $G:\{0,1\}^{\lambda }\rightarrow \{0,1\}^{\ell }$ be a linear-resistant PRG. Then, the SSS defined by the sharing map $\mu '(s,r)=\mu (s||r,G(r))$ is a computational RR-SSS for the same access structure, where $s\in \{0,1\}^{(k-1)\lambda }$ is the secret and $r\in \{0,1\}^\lambda$ is the randomness with uniform distribution.

Proof

Correctness and randomness recoverability trivially hold. We prove privacy. Let B be an unqualified set and let $\mu _{{B}}(s_1||s_2,r)=L_1(s_1) + L_2(s_2)+ L_3(r)$ be the share of B for the secret $s_1\vert \vert s_2$ and randomness $r\in \{0,1\}^\ell$ in the perfect linear scheme, where $L_i$’s are linear functions, $s_1\in \{0,1\}^{(k-1)\lambda }$ and $s_2\in \{0,1\}^\lambda$.

By perfect privacy of the linear scheme, for any $s\in \{0,1\}^{(k-1)\lambda }$, the RVs $L_2(s)+L_3(\varvec{r})$ and $L_3(\varvec{r})$ have the same distributions, where $\varvec{r}$ is a uniform RVs on $\ell$-bit strings (they correspond to the shares of the secrets $s||0^{\lambda }$ and $0^{k\lambda }$, respectively). Therefore $\textsf{supp}(L_2(s)+L_3(\varvec{r}))=\textsf{supp}(L_3(\varvec{r}))$ which implies that $L_2(s)+\textsf{range}(L_3)=\textsf{range}(L_3)$. As a result $L_2(s) \in \textsf{range}(L_3)$ and because s is arbitrary, we have $\textsf{range}(L_2) \subseteq \textsf{range}(L_3)$. If f and g are linear functions from V to W such that range of g is a subspace of the range of f, then for a suitable linear function h over V one has $g=f\circ h$. By this fact, there is a linear function L such that $L_2=L_3\circ L$.

Let $s,s^\prime \in \{0,1\}^{(k-1)\lambda }$ be two arbitrary secrets and $\varvec{r}$ be as before. Again, by perfect privacy of the linear scheme, $L_1(s)+L_3(\varvec{r})$ and $L_1(s^\prime )+L_3(\varvec{r})$ have the same distributions (they correspond to the shares of the secrets $s||0^{\lambda }$ and $s^\prime ||0^{\lambda }$, respectively). Since G is linear-resistant, by a standard reduction argument, $L_1(s)+L_3(G(\varvec{r})+L(\varvec{r}))$ and $L_1(s^\prime )+L_3(G(\varvec{r})+L(\varvec{r}))$ are computationally indistinguishable where $\varvec{r}$ is a uniform RV on $\lambda$-bit strings. Therefore, $\mu _{{B}}^\prime (s,\varvec{r})=L_1(s)+L_2(\varvec{r})+L_3(G(\varvec{r}))$ and $\mu ^\prime _{{B}}(s^\prime ,\varvec{r})=L_1(s^\prime )+L_2(\varvec{r})+L_3(G(\varvec{r}))$ are computationally indistinguishable, which is the desired result. $\square$

We conclude this section with the following remark that relates the observations of this section and the previous ones.

Remark 5.8

Notice that in the proof of Theorem 5.5, we do not require that the SKE be KDM-secure against the whole class of efficiently computable functions. Indeed, security against all the functions g for all unqualified sets is sufficient. Since the class of linear SSSs is randomness simulatable with linear g’s, and one-time secure RR-SKE against the class of linear functions is implied by linear-resistant PRG, Theorem 5.7 follows by Theorem 5.5, via a simpler construction though.

6 Conclusion

We initiated the study of SSS from the viewpoint of randomness recovery. By proving an exponential lower bound for the information ratio of an RR-SSS that realizes some very simple access structure in monotone $\textsf{AC}^0$, we showed that the situation is very different for RR-SSS, compared to the standard SSS, for which the best-known lower bound is sub-linear. We also managed to shed some light on the complexity of the computational RR-SSS, by proving that computational RR-SSS for certain access structures in monotone $\textsf{AC}^0$ implies OWF. This computational result is essentially a consequence of our information-theoretic lower bound; This can be justified by the very general idea that an algorithm that hides the secret from a bounded adversary but is unable to do so against an unbounded adversary implies OWF.

In the final section, we observed that an efficient perfect linear SSS can be converted into a computational RR-SSS for the same access structure using a type of PRG that we called linear-resistant PRG. We also noted that using a one-time KDM-secure RR-SKE, one can convert an efficient perfect/computational SSS into an RR-SSS, assuming that the SSS has the extra property of randomness simulatability.

Appendices

Full Proof of Lemma 2.14

In the case of perfect SSS, the assertion immediately follows the independence of $\varvec{S}$ and $\mu _B(\varvec{S},\textbf{R})$. Assume that $\Pi$ is a computational SSS, $\textbf{R}=\{\textbf{R}_\lambda \}_\lambda$, $\varvec{S}=\{\varvec{S}_\lambda \}_\lambda$ and $t=t(\lambda )$. For contradiction, let $\textsf{poly}$ be a polynomial and $\mathcal {D}=\{\mathcal {D}_\lambda \}_\lambda$ be a family of polynomial-size distinguishers such that for infinitely many $\lambda$,

$$\begin{aligned} \vert \Pr [\mathcal {D}_\lambda (\varvec{S}_\lambda ,\mu _B(\varvec{S}_\lambda ,\textbf{R}_\lambda ))=1] - \Pr [\mathcal {D}_\lambda (\varvec{S}_\lambda ,\mu _B(0^{t(\lambda )},\textbf{R}_\lambda ))=1]\vert \ge \frac{1}{\textsf{poly}(\lambda )}. \end{aligned}$$

Therefore, for each $\lambda$, there is $s_\lambda \in \textsf{supp}(\textsf{s}_\lambda )$ such that

$$\begin{aligned} \vert \Pr [\mathcal {D}_\lambda (s_\lambda ,\mu _B(s_\lambda ,\textbf{R}_\lambda ))=1] - \Pr [\mathcal {D}_\lambda (s_\lambda ,\mu _B(0^{t(\lambda )},\textbf{R}_\lambda ))=1]\vert \ge \frac{1}{\textsf{poly}(\lambda )}. \end{aligned}$$

Therefore, for $\mathcal {C}_\lambda (\cdot )=\mathcal {D}_\lambda (s_\lambda ,\cdot )$ one has

$$\begin{aligned} \vert \Pr [\mathcal {C}_\lambda (\mu _B(s_\lambda ,\textbf{R}_\lambda ))=1] - \Pr [\mathcal {C}_\lambda (\mu _B(0^{t(\lambda )},\textbf{R}_\lambda ))=1]\vert \ge \frac{1}{\textsf{poly}(\lambda )} \ , \end{aligned}$$

which contradicts the computational privacy of the SSS.

Full Proof of Lemma 5.3

Let $\varvec{k}=\{\varvec{k}_\lambda \}_\lambda$ where $\varvec{k}_\lambda =\textsf{Gen}(1^\lambda )$, $\textbf{x}=\{\textbf{x}_\lambda \}_\lambda$, $\textbf{y}=\{\textbf{y}_\lambda \}_\lambda$ and $g=\{g_\lambda \}_\lambda$. Assume that the assertion is false and there is a polynomial $\textsf{poly}$ and a polynomial-size distinguisher $D=\{\mathcal {D}_\lambda \}_\lambda$ and infinitely many $\lambda$ for which:

$$\begin{aligned} \vert \Pr [\mathcal {D}_\lambda (\textbf{x}_\lambda ,\textsf{Enc}_{\varvec{k}_\lambda }(g_\lambda (\varvec{k}_\lambda ,\textbf{x}_\lambda ,\textbf{y}_\lambda )))=1] - \Pr [\mathcal {D}_\lambda (\textbf{x}_\lambda ,\textsf{Enc}_{\varvec{k}_\lambda }(0^{l(\lambda )}))=1] \vert \ge \frac{1}{\textsf{poly}(\lambda )}. \end{aligned}$$

Because $\varvec{k}$ is independent of $\textbf{x}$ and $\textbf{y}$, for each such $\lambda$, there is $(x_\lambda ,y_\lambda )\in \mathsf {supp(\textbf{x}_\lambda )}\times \textsf{supp}(\textbf{y}_\lambda )$ such that:

$$\begin{aligned} \vert \Pr [\mathcal {D}_\lambda (x_\lambda ,\textsf{Enc}_{\varvec{k}_\lambda }(g_\lambda (\varvec{k}_\lambda ,x_\lambda ,y_\lambda )))=1] - \Pr [\mathcal {D}_\lambda (x_\lambda ,\textsf{Enc}_{\varvec{k}_\lambda }(0^{l(\lambda )}))=1] \vert \ge \frac{1}{\textsf{poly}(\lambda )}. \end{aligned}$$

Letting $\mathcal {C}_\lambda (\cdot )=\mathcal {D}_\lambda (x_\lambda ,\cdot )$ and $f_\lambda (\cdot )=g_\lambda (\cdot ,x_\lambda ,y_\lambda )$, we have

$$\begin{aligned} \vert \Pr [\mathcal {C}_\lambda (\textsf{Enc}_{\varvec{k}_\lambda }(f_\lambda (\varvec{k}_\lambda )))=1] - \Pr [\mathcal {C}_\lambda (\textsf{Enc}_{\varvec{k}_\lambda }(0^{l(\lambda )}))=1] \vert \ge \frac{1}{\textsf{poly}(\lambda )} \ , \end{aligned}$$

which contradicts the KDM-security of $\Pi$.