Secret Sharing for mNP: Completeness Results

Abstract

We show completeness results for secret sharing schemes realizing $\mathsf {mNP}$ access structures. We begin by proposing a new, Euclidean-type, division technique for access structures. Using this new technique we obtain several results in characterizing access structures for efficient (unconditionally secure) secret sharing schemes:

• We show a useful transformation that achieves efficient schemes for complex access structures using schemes realizing simple access structures.

• We show that, assuming every access structure in $\mathsf {P} \cap \mathsf {mono}$ admits efficient secret sharing, the existence of an efficient secret sharing for an access structure in $\mathsf {mNP}$ that is also complete for $\mathsf {mNP}$ under Karp/Levin monotone-reductions implies secret sharing schemes for all of $\mathsf {mNP}$.

• We finally improve upon the above completeness result by obtaining the same under ordinary Karp/Levin reductions.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Secret sharing schemes enable a dealer, holding a secret piece of information, to distribute this secret among a set $\mathcal {P}_{n}=\{P_{1}, \ldots , P_{n}\}$ of n players such that only some predefined authorized subsets of players can reconstruct the secret from their shares. The (monotone) collection $\varGamma _{n} \subseteq 2^{\mathcal {P}_{n}}$ of authorized sets that can reconstruct the secret is called an access structure. The security of a secret sharing scheme requires that any unauthorized set B of players, i.e., $B \notin \varGamma _{n}$, pulling its shares together and attempt to reconstruct the secret should fail with high probability. Consequently, the security is termed unconditional (computational) if the players are computationally unbounded (computationally bounded).

A secret sharing scheme realizing an access structure $\varGamma _{n}$ over n players is termed size-efficient, if the total length of the n shares is polynomial in n; semi-efficient, if the share distribution is computable in $\mathsf {poly}(n)$ time; and efficient, if both share distribution and reconstruction are computable in $\mathsf {poly}(n)$ time. The notions of semi-efficiency and efficiency are stronger than size-efficiency.

A major problem in this field is the characterization of access structures in terms of secret sharing schemes that they admit, where the security and efficiency of the later is measured as a combination of the following:

• Unconditional/computational security, and

• size-efficiency/semi-efficiency/efficiency.

For concrete characterization, now onwards, we use the term access structure for referring to an infinite family of access structures $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$ (for every n, $\varGamma _{n}$ is an access structure over $\mathcal {P}_{n}$) and the term “scheme realizing $\varGamma$” for referring to an infinite family of secret sharing schemes $\{\varPi _{n}\}_{n \in \mathbb {N}}$ such that for every n, $\varPi _{n}$ realizes $\varGamma _{n}$.

Associating sets $A \subseteq \mathcal {P}_{n}$ with there characteristic vectors $x_{A} \in \{0,1\}^{n}$, we can define a language $L_{\varGamma } \subseteq \{0,1\}^{*}$ associated with an access structure $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$. Namely, $L_{\varGamma }=\cup _{n=1}^{\infty } \{x_{A} \in \{0,1\}^{n}~|~A\in \varGamma _{n}\}$. An access structure $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$ is said to be in the complexity class $\mathsf {P} \cap \mathsf {mono}$ if the associated language $L_{\varGamma } \in \mathsf {P} \cap \mathsf {mono}$. The $\varGamma$ is said to be in $\mathsf {mNP}$ if $L_{\varGamma } \in \mathsf {mNP}$.

The question of access structures characterization has been widely studied. The extensive work in this area can be divided under the following two category of security: unconditional and computational. The most general class of access structures with known characterization results under them are given below.

• Unconditional Security

  • $\varvec{\mathsf {P} \cap \mathsf {mono}}$ : It has been extensively studied whether there exists efficient secret sharing schemes for every access structures in $\mathsf {P} \cap \mathsf {mono}$? In fact, it is wide open if the same is true for all of $\mathsf {mP}$ - the class of access structure strictly contained in $\mathsf {P} \cap \mathsf {mono}$. With several schemes realizing different classes of access structures [6–8, 11, 12, 16], the most general class of access structures in $\mathsf {P} \cap \mathsf {mono}$ that admit efficient perfect secret sharing are those that can be described by a polynomial-size monotone span program [13].

  • $\varvec{\mathsf {mNP}}$ : The question of obtaining unconditionally secure efficient schemes for access structures in $\mathsf {mNP}$ was met with an impossibility result. Steven Rudich observed that if $\mathsf {NP} \ne \mathsf {coNP}$, then for Hamiltonian access structure in $\mathsf {NP}$ there exists no semi-efficient secret-sharing scheme (specifically, schemes with perfect privacy) [4].

• Computational Security

  • $\varvec{\mathsf {P} \cap \mathsf {mono}}$ : It is known that the whole of $\mathsf {mP}$ admit efficient secret sharing schemes that are computationally secure - assuming that one-way functions exists [4, 17].

  • $\varvec{\mathsf {mNP}}$ : Komargodski, Naor and Yogev [14] showed semi-secret sharing schemes for all of $\mathsf {mNP}$ (and therefore cover all of $\mathsf {P} \cap \mathsf {mono}$), where the reconstruction algorithm is polynomial-time if the $\mathsf {NP}$-witnesses for the authorized sets are given. Their scheme assumes existence of witness encryption [9] for whole of $\mathsf {NP}$ and one-way functions.

1.1 Our Results

An important corollary of the main result of Komargodski, Naor and Yogev [14] is the following completeness theorem for secret sharing schemes realizing $\mathsf {mNP}$ access structures:

Theorem 1

[14]. Assume that one-way functions exists. Then existence of an efficient computational secret sharing for an access structure in $\mathsf {mNP}$ that is also complete for $\mathsf {mNP}$ under Karp/Levin reductions implies efficient computational secret sharing scheme for every access structure in $\mathsf {mNP}$.

The above theorem was established using the following two results:

• A secret sharing scheme for an access structure $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$ implies witness encryption for the associated language $L_{\varGamma }$.

• Completeness theorem of witness encryption: Using standard Karp/Levin reductions between $\mathsf {NP}$-complete languages, one can transform a witness encryption for a single $\mathsf {NP}$-complete language to a witness encryption scheme for any other language in $\mathsf {NP}$.

Beside one-way functions, the completeness result in Theorem 1, therefore, is obtained based on the existence of witness encryption which in turn relies on strong computational assumptions related to indistinguishability obfuscation [2, 3].

In this paper we obtain such completeness results for $\mathsf {mNP}$ access structures assuming that efficient secret sharing schemes exists for access structures in $\mathsf {P} \cap \mathsf {mono}$. More importantly, our completeness results hold under reductions with unconditional security. As a corollary, our completeness results also partially resolve the following problem that was left open in [14]: Is there a way that can use secret sharing scheme for access structures in $\mathsf {P} \cap \mathsf {mono}$ to achieve secret sharing scheme for access structures in $\mathsf {mNP}$?

In particular, this paper makes the following important contributions:

• Our foremost contribution lies in defining a new Euclidean-type division technique for access structures. Namely, for a given pair of access structures (more like a pair of dividend and divisor), this new technique distill a list of access structures, possibly simpler then dividend and divisor (more like a remainder). Unlike the ordinary Euclidean division for numbers, the remainder access structures are not fixed and choosing them carefully is of great importance as it allows for simplified reductions among schemes realizing these access structures.

• We next illustrate the usefulness of our proposed division property by describing a transformation that achieves efficient secret sharing scheme for a given access structure using secret sharing schemes for appropriately defined divisor and remainder access structures.

• The above transformation helps us to achieve our first completeness theorem: Namely we show that, assuming access structures in $\mathsf {P} \cap \mathsf {mono}$ admit efficient secret sharing, the existence of an efficient secret sharing for an access structure in $\mathsf {mNP}$ that is also complete for $\mathsf {mNP}$ under Karp/Levin monotone-reductions implies secret sharing schemes for all of $\mathsf {mNP}$.

• The above completeness theorem is obtained for $\mathsf {NP}$-completeness under monotone-reductions. Removing the later restriction proved to be an important achievement of our work. A clever construction of remainder access structures helped us to obtain our second completeness theorem: Namely we show, assuming access structures in $\mathsf {P} \cap \mathsf {mono}$ admit efficient secret sharing, the existence of an efficient secret sharing for an access structure in $\mathsf {mNP}$ implies efficient secret sharing for all of $\mathsf {mNP}$.

2 Preliminaries

2.1 Access Structure and Its Complexity

Let $\mathcal {P}_{n}\mathop {=}\limits ^{\mathsf {def}}\{P_{1}, \ldots , P_{n}\}$ be a set of n players. A collection $\varGamma \subseteq 2^{\mathcal {P}_{n}}$ of subsets of $\mathcal {P}_{n}$ is called monotone increasing if, $A \in \varGamma$ and $A \subseteq B \subseteq \mathcal {P}_{n}$ implies $B \in \varGamma$. A collection $\varGamma ^{\prime } \subseteq 2^{\mathcal {P}_{n}}$ is called monotone decreasing if, $A \in \varGamma ^{\prime }$ and $B \subseteq A$ implies $B \in \varGamma ^{\prime }$.

Definition 1

(Access Structure). An access structure on $\mathcal {P}_{n}$ is a tuple $(\varGamma _{n}, \varGamma ^{\prime }_{n})$, where $\varGamma _{n}, \varGamma ^{\prime }_{n} \subseteq 2^{\mathcal {P}_{n}}$, such that

• $\varGamma _{n}$ is monotone increasing; $\varGamma ^{\prime }_{n}$ is monotone decreasing, and

• $\varGamma _{n} \cap \varGamma ^{\prime }_{n}= \emptyset$.

For an access structure $(\varGamma _{n}, \varGamma ^{\prime }_{n})$, the collection $\varGamma ^{\prime }_{n}$ is often called an adversary access structure. We call an access structure complete if, the adversary access structure $\varGamma ^{\prime }_{n}$ complements $\varGamma _{n}$ in full. We consider only complete access structures in this paper and they are simply denoted by $\varGamma _{n}$.

Definition 2

(Complete Access Structure). An access structure $(\varGamma _{n}, \varGamma ^{\prime }_{n})$ is called complete if, $\varGamma ^{\prime }_{n}=2^{\mathcal {P}_{n}} \backslash \varGamma _{n}$, i.e., $\varGamma _{n} \cup \varGamma ^{\prime }_{n} = 2^{\mathcal {P}_{n}}$.

An access structure $\varGamma _{n}$ can be freely identified with its characteristic Boolean function $f_{\varGamma _{n}}: \{0,1\}^{n} \rightarrow \{0,1\}$. To each set $A \subseteq \mathcal {P}_{n}$ associate a unique (characteristic vector) $v^{A}=(v^{A}_{1}, \ldots , v^{A}_{n}) \in \{0,1\}^{n}$ as follows: for every j in $1 \le j \le n$, $v^{A}_{j}=1$ iff $P_{j} \in A$. Define, $D_{\varGamma _{n}}=\{v^{A}~|~A\in \varGamma _{n}\} \subseteq \{0,1\}^{n}$.

Definition 3

(Associated Boolean function). For access structure $\varGamma _{n}$, the corresponding boolean function $f_{\varGamma _{n}}: \{0,1\}^{n} \rightarrow \{0,1\}$ is defined as follows: for $x \in \{0,1\}^{n}$, $f_{\varGamma _{n}}(x)=1~\text {iff}~x \in D_{\varGamma _{n}}$.

Clearly, the boolean function $f_{\varGamma _{n}}$ is monotone. Associating access structures $\varGamma _{n}$ with their boolean functions $f_{\varGamma _{n}}$, we can associate a language $L_{\varGamma } \subseteq \{0,1\}^{*}$ to a family of access structures $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$.

Definition 4

(Associated Language). For an access structure $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$, the corresponding language $L_{\varGamma } \subseteq \{0,1\}^{*}$ is defined as follows: $L_{\varGamma }=\{x \in \{0,1\}^{*}~|~f_{\varGamma _{|x|}}(x)=1\}$, where |x| denotes the length of the binary string x.

For any access structure $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$, the corresponding language $L_{\varGamma }$ is clearly in the complexity class $\mathsf {mono}$ - the class of monotone languages.

Definition 5

(Access Structure Complexity). An access structure $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$ is said to be

• 1. in $\mathsf {P} \cap \mathsf {mono}$ if $L_{\varGamma } \in \mathsf {P} \cap \mathsf {mono}$,

• 2. in $\mathsf {NP} \cap \mathsf {mono}$ if $L_{\varGamma } \in \mathsf {NP} \cap \mathsf {mono}$.

It is a well known fact that, $\mathsf {P} \cap \mathsf {mono} \ne \mathsf {mP}$ [1, 15], where the complexity class $\mathsf {mP}$ denotes languages that admit monotone circuits of polynomial-size; but $\mathsf {NP} \cap \mathsf {mono}=\mathsf {mNP}$ [10], where $\mathsf {mNP}$ denotes the class of languages accepted by polynomial-size monotone non-deterministic circuits. We will refer to access strutures in $\mathsf {NP} \cap \mathsf {mono}$ by $\mathsf {mNP}$ access structures.

2.2 Secret Sharing

An n-party secret sharing scheme involves $n+1$ players: A dealer $\mathcal {D}$, a set $\mathcal {P}_{n}=\{P_{1}, \ldots , P_{n}\}$ of n participants, and an access structure $\varGamma _{n}$ over $\mathcal {P}$. A secret sharing scheme for an arbitrary $\varGamma _{n}$ allows the dealer to distribute shares of a secret value such that

• Privacy: any unauthorized set $B \subseteq \mathcal {P}$ of participants, i.e., $B \notin \varGamma _{n}$, must not obtain any information on the secret from their collective shares.

• Reconstructability: any authorized coalitions $A \subseteq \mathcal {P}$ of participants, i.e., $A \in \varGamma _{n}$, must always reconstruct the secret from their collective shares.

Definition 6

(Secret Sharing). An n-party secret sharing for an access structure $\varGamma _{n}$ over $\mathcal {P}_{n}=\{P_{1}, \ldots , P_{n}\}$ is a tuple $\varPi =\big (\mathsf {Share}, \mathsf {Rec}, \varSigma , \varSigma _{1}, \ldots , \varSigma _{n}\big )$ such that the following holds:

• Algorithms

  • $\mathsf {Share}.\varPi$: The share distribution algorithm $\mathsf {Share}.\varPi$ is a probabilistic algorithm that, on input $s \in \varSigma$ returns $(\mathsf {Sh}_{1}, \ldots , \mathsf {Sh}_{n}) \mathop {\leftarrow }\limits ^{\$} \mathsf {Share}.\varPi (s)$, where $\mathsf {Sh}_{i} \in \varSigma _{i}$, $1 \le i \le n$.

  • $\mathsf {Rec}.\varPi$: The secret reconstruction algorithm $\mathsf {Rec}.\varPi$ is a deterministic algorithm that on input $(\sigma _{1}, \ldots , \sigma _{n}) \in \prod _{i=1}^{n} (\varSigma _{i}\cup \{*\})$ returns a value $\sigma \leftarrow \mathsf {Rec}.\varPi (\sigma _{1}, \ldots , \sigma _{n})$ where $\sigma \in \varSigma \cup \{\bot \}$. The distinguished symbols $*$ and $\bot$ have the following meanings: $\sigma _{i}=*$ means the ith share is missing, and $\bot \leftarrow \mathsf {Rec}.\varPi (\sigma _{1}, \ldots , \sigma _{n})$ indicates that the algorithm is unable to recover the underlying secret.

• Property

  • $\varvec{\mathsf {Correctness}}$ : For every authorized set of players $A \subseteq \mathcal {P}_{n}$, i.e., $A \in \varGamma _{n}$, and for every $s \in \varSigma$, we have

    $$\begin{aligned} \mathsf {Rec}\big (\mathsf {Share}.\varPi (s)_{A}\big )=s \end{aligned}$$

    (1)

    where $\mathsf {Share}.\varPi (s)_{A}$ restricts the n length vector $(\mathsf {Sh}_{1}, \ldots , \mathsf {Sh}_{n}) \mathop {\leftarrow }\limits ^{\$} \mathsf {Share}.\varPi (s)$ to its A-entries, i.e., $\mathsf {Share}.\varPi (s)_{A}=\{\mathsf {Sh}_{i}\}_{P_i \in A}$.

  • $\varvec{\mathsf {Security}}$ : The security of a secret sharing scheme is measured by the maximum probability with which a adversary $\mathcal {A}$ can win the following privacy game - $\mathsf {PrivacySS}$.

The game is played between the dealer $\mathcal {D}$ and an adversary $\mathcal {A}$ as follows:

• 1. $\mathcal {A}$ first picks a pair of secrets $s_{0}, s_{1} \in S$, and gives them to $\mathcal {D}$.

• 2. $\mathcal {D}$ chooses a random bit $b\in \{0,1\}$ and executes $\mathsf {Share}.\varPi (s_{b})$.

• 3. $\mathcal {A}$ queries shares of a set of participants $B \subseteq \mathcal {P}$ such that $B \notin \varGamma _{n}$.

• 4. $\mathcal {A}$ outputs a guess $b^{\prime }$ for b using the shares $\mathsf {Share}.\varPi (s_{b})_{B}$.

The adversary is said to win the game if $b^{\prime }=b$. We measure its success as

$$ \text {Adv}^{\mathsf {PrivacySS}}(\mathcal {A})=2\cdot \mathsf {Pr}[b^{\prime }=b]-1. $$

Fig. 1.

$\mathsf {PrivacySS}$: The Privacy Game

Definition 7

(Privacy). A secret sharing scheme is said to have:

• * $\mathsf {Perfect\text {-}Privacy}$, when $\mathcal {A}$ is unbounded and $\text {Adv}^{\mathsf {PrivacySS}}(\mathcal {A})=0$

• * $\epsilon \text {-}\mathsf {Statistical~Privacy}$, when $\mathcal {A}$ is unbounded and $\text {Adv}^{\mathsf {PrivacySS}}(\mathcal {A})<\epsilon$, where $\epsilon > 0$.

• * $\mathsf {Computational\text {-}Privacy}$, when $\mathcal {A}$ is a probabilistic polynomial time ($\mathsf {PPT}$) algorithm and $\text {Adv}^{\mathsf {PrivacySS}}(\mathcal {A})<\eta (k)$, where $\eta (\cdot )$ is a negligible function, and k denotes the underlying security parameter of the scheme¹.

• $\varvec{\mathsf {Efficiency}}$ : Different measure of efficiency is used in the secret sharing literature. A secret sharing scheme $\varPi$ is termed

• * Size Efficient, if the total length of the n shares is polynomial in n.

• * Semi Efficient, if the share distribution algorithm $\mathsf {Share}.\varPi$ is computable in $\mathsf {poly}(n)$ time.

• * Efficient, if both $\mathsf {Share}.\varPi$ and $\mathsf {Rec}.\varPi$ are computable in $\mathsf {poly}(n)$ time.

Definition 8

(Secret Sharing for Languages). A family of secret sharing schemes $\varPi =\{\varPi _{n}\}_{n \in \mathbb {N}}$ is said to realize $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$ if for every $n \in \mathbb {N}$, $\varPi _{n}$ realizes $\varGamma _{n}$. Then $\varPi$ is also called a secret sharing scheme for the corresponding language $L_{\varGamma }$ (see Definition 4).

Consequently, $\varPi =\{\varPi _{n}\}_{n \in \mathbb {N}}$ realizing $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$ is said to be (size/semi) efficient if for every $n\in \mathbb {N}$, $\varPi _{n}$ realizing $\varGamma _{n}$ is (size/semi) efficient.

In the following, all the secret sharing schemes that we will present are both efficient and have perfect privacy.

3 A Division Property for Access Structures

For $n,m \in \mathbb {N}$, consider the following access structures:

• $\varGamma _{n}$ - an access structure over $\mathcal {P}_{n}=\{P_{1}, \ldots , P_{n}\}$

• $\varDelta _{m}$ - an access structure over $\mathcal {Q}_{m}=\{Q_{1}, \ldots , Q_{m}\}$, and

• for every i in $1 \le i \le m$, $\varGamma _{n}^{(i)}$ - an access structure over $\mathcal {P}_{n}$.

Definition 9

We say $\varGamma _{n} \bmod \varDelta _{m} \mathop {=}\limits ^{\mathsf {def}} \{\varGamma _{n}^{(1)}, \ldots , \varGamma _{n}^{(m)}\}$ if, for every $A \subseteq \mathcal {P}_{n}$ the set $A \bmod \varDelta _{m} \mathop {=}\limits ^{\mathsf {def}} \big \{Q_{i} \in \mathcal {Q}_{m}~|~A \in \varGamma _{n}^{(i)} \big \} \subseteq \mathcal {Q}_{m}$ satisfies the following property:

$$\begin{aligned} A \in \varGamma _{n} \iff A \bmod \varDelta _{m} \in \varDelta _{m} \end{aligned}$$

(2)

The division property in Definition 9 closely resembles the ordinary Euclidean division for integers, where $\varGamma _{n}$ is dividend, $\varDelta _{m}$ is divisor, and remainder is formed by the list of access structures $\{\varGamma _{n}^{(1)}, \ldots , \varGamma _{n}^{(m)}\}$. Clearly, the size (the number of authorized sets) of each $\varGamma _{n}^{(i)}$ is at most that of $\varGamma _{n}$. We will later see the importance of obtaining smaller size (and therefore simpler) $\varGamma _{n}^{(i)}$’s.

4 A Transformation

Theorem 2

Let $\varGamma _{n}, \varGamma _{n}^{(1)}, \ldots , \varGamma _{n}^{(m)}$ be access structures on $\mathcal {P}_{n}$, and $\varDelta _{m}$ be an access structure on $\mathcal {Q}_{m}$ such that $\varGamma _{n} \bmod \varDelta _{m} = \{\varGamma _{n}^{(1)}, \ldots , \varGamma _{n}^{(m)}\}$. Assume

• 1. $\varPi _{\varDelta _{m}}=(\mathsf {Share}.\varPi _{\varDelta _{m}}, \mathsf {Rec}.\varPi _{\varDelta _{m}})$ is a perfect secret sharing scheme realizing $\varDelta _{m}$, and

• 2. for every i in $1\le i \le m$, $\varPi _{\varGamma _{n}^{(i)}}=(\mathsf {Share}.\varPi _{\varGamma _{n}^{(i)}}, \mathsf {Rec}.\varPi _{\varGamma _{n}^{(i)}})$ is a perfect secret sharing realizing $\varGamma _{n}^{(i)}$

then there exists $\varPi _{\varGamma _{n}}$ - a perfect secret sharing scheme realizing $\varGamma _{n}$.

Proof: The secret sharing scheme $\varPi _{\varGamma _{n}}$ can be described as follows:

• $\mathsf {Share}.\varPi _{\varGamma _{n}}$: The share distribution algorithm distributes a secret s among players in $\mathcal {P}_{n}=\{P_{1}, \ldots , P_{n}\}$ as follows:

  • Compute $(s_{1}, \ldots , s_{m}) \mathop {\leftarrow }\limits ^{\$} \mathsf {Share}.\varPi _{\varDelta _{m}}(s)$

  • For every i in $1 \le i \le m$, compute $(s_{i1}, \ldots , s_{in})\mathop {\leftarrow }\limits ^{\$} \mathsf {Share}.\varPi _{\varGamma _{n}^{(i)}}(s_{i})$

  The player $P_{j}$, for every j in $1 \le j \le n$, gets the following share:

  $$ P_{j} \leftarrow (s_{1j}, s_{2j}, \ldots , s_{mj}) $$

• $\mathsf {Rec}.\varPi _{\varGamma _{n}}$: For every authorized set $A \in \varGamma _{n}$, the players in A pull together their respective shares and reconstruct the secret as follows. Let $A \bmod \varDelta _{m}=\{Q_{i_{1}}, \ldots , Q_{i_{r}}\} \subseteq \mathcal {Q}_{m}$, for some r in $1 \le r \le m$. By the definition of $A \bmod {\varDelta _{m}}$, $A \in \varGamma _{n}^{(i_{j})}$, j in $1\le j \le r$, and therefore players in A reconstruct intermediate shares $s_{i_{j}}$’s using reconstruction algorithm $\mathsf {Rec}.\varPi _{\varGamma _{n}^{(i_{j})}}$’s respectively. As $A \bmod \varDelta _{m}$ is in $\varDelta _{m}$, the secret is finally reconstructed by computing $s \leftarrow \mathsf {Rec}.\varPi _{\varDelta _{m}}(s_{i_{1}}, \ldots , s_{i_{r}})$.

• $\mathsf {Privacy}$: Secret is perfectly hidden from the combined shares of any unauthorized set $A^{\prime } \notin \varGamma _{n}$. Let $A^{\prime } \bmod \varDelta _{m}=\{Q_{i_1}, \ldots , Q_{i_{u}}\}$ and it does not belongs to $\varDelta _{m}$. The players in $A^{\prime }$ can compute intermediate shares $s_{i_{j}}$’s, $1 \le j \le u$, of the secret s. But these shares $\{s_{i_{1}}, \ldots , s_{i_{u}}\}$ will not reveal any information (perfectly hidden) about s as $\{Q_{i_1}, \ldots , Q_{i_{u}}\} \notin \varDelta _{m}$.

5 Completeness Under Monotone-Reductions

Theorem 3

Assume access structures in $\mathsf {P} \cap \mathsf {mono}$ admit efficient secret sharing. Then existence of an efficient secret sharing for an access structure in $\mathsf {mNP}$ that is also complete for $\mathsf {mNP}$ under Karp/Levin monotone-reductions implies secret sharing schemes for all of $\mathsf {mNP}$.

Proof: Let $\varDelta = \{\varDelta _{m}\}_{m \in \mathbb {N}}$ be an access structure in $\mathsf {mNP}$ that is also complete for $\mathsf {mNP}$ under monotone-reductions and suppose it admits an efficient secret sharing scheme. Consider an arbitrary access structure $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$ from $\mathsf {mNP}$. We now show, for every $n \in \mathbb {N}$, $\varGamma _{n}$ admits an efficient secret sharing scheme. For any fix n, there exists (completeness of $\varDelta$) an $m \in \mathbb {N}$ such that $\varGamma _{n}$ is monotone-reducible to $\varDelta _{m}$, i.e., there exists a polynomial time computable monotone function $K_{R}: 2^{\mathcal {P}_{n}} \rightarrow 2^{\mathcal {Q}_{m}}$ such that the following holds:

$$\begin{aligned} \forall A \subseteq \mathcal {P}_{n}, A \in \varGamma _{n} \iff K_{R}(A) \in \varDelta _{m}. \end{aligned}$$

(3)

Define, for every i in $1 \le i \le m$, an access structure $\varGamma _{n}^{(i)}$ over $\mathcal {P}_{n}$ as follows:

$$\begin{aligned} \text {For}~i\in [m], \varGamma _{n}^{(i)}=\big \{ A \subseteq \mathcal {P}_{n}~|~Q_{i} \in K_{R}(A) \big \}. \end{aligned}$$

(4)

The theorem follows by proving the following claims (see Theorem 2):

• Claim 1: Each $\varGamma _{n}^{(i)}$ is in $\mathsf {P} \cap \mathsf {mono}$, $1 \le i \le m$

• Claim 2: $\varGamma _{n} \bmod \varDelta _{m} = \{\varGamma _{n}^{(1)}, \ldots , \varGamma _{n}^{(m)}\}$.

Proof of Claim 1: We first show $\varGamma _{n}^{(i)}$ is monotone, i.e., for every $A, B \subseteq \mathcal {P}_{n}$ with $\varGamma _{n}^{(i)} \ni A \subseteq B$, we show $B \in \varGamma _{n}^{(i)}$. Firstly, $Q_{i} \in K_{R}(A)$ as $A \in \varGamma _{n}^{(i)}$. Secondly, the monotone property of $K_{R}$ map implies $K_{R}(A) \subseteq K_{R}(B)$. These two mean that $Q_{i} \in K_{R}(B)$, implying B belongs to $\varGamma _{n}^{(i)}$.

We now show $\varGamma _{n}^{(i)}$ is in $\mathsf {P}$. For any set $A \subseteq \mathcal {P}_{n}$, $A \in \varGamma _{n}^{(i)}$ iff $Q_{i} \in K_{R}(A)$. But, $K_{R}$ is a polynomial time computable function and therefore computing $K_{R}(A)$ is efficient, implying $\varGamma _{n}^{(i)}$ is in $\mathsf {P}$.

Proof of Claim 2: We now prove $\varGamma _{n} \bmod \varDelta _{m} = \{\varGamma _{n}^{(1)}, \ldots , \varGamma _{n}^{(m)}\}$, i.e., for every $A \subseteq \mathcal {P}_{n}$, $A \in \varGamma _{n}$ iff $A \bmod \varDelta _{m} \in \varDelta _{m}$. But

$$\begin{aligned} A \bmod \varDelta _{m}= & {} \{Q_{i} \in \mathcal {Q}_{m}~|~A \in \varGamma _{n}^{(i)}\} \\= & {} \{Q_{i} \in \mathcal {Q}_{m}~|~Q_{i} \in K_{R}(A)\} \\= & {} K_{R}(A) \end{aligned}$$

Therefore, for every set $A \subseteq \mathcal {P}_{n}$

This completes the proof.

6 Completeness Without Monotone-Reductions

Theorem 4

Assume access structures in $\mathsf {P} \cap \mathsf {mono}$ admit efficient secret sharing. Then existence of an efficient secret sharing for an access structure in $\mathsf {mNP}$ that is also complete for $\mathsf {mNP}$ under ordinary (not necessarily monotone) Karp/Levin reductions implies efficient secret sharing for all those $\varGamma = \{\varGamma _{n}\}_{n \in \mathbb {N}} \in \mathsf {mNP}$ that satisfy the following: for every n there exists a $k_{n} \in \mathbb {N}$ such that $\varGamma _{n}= B_{k_{n}} \cup \{A \subseteq \mathcal {P}_{n}~|~|A| \ge k_{n}+1\}$, where $B_{k_{n}}$ is a subset of $A_{k_{n}}\mathop {=}\limits ^{\mathsf {def}}\{A \subseteq \mathcal {P}_{n}~|~|A|=k_{n}\}$.

Proof: Let $\varDelta = \{\varDelta _{m}\}_{m \in \mathbb {N}}$ be an access structure in $\mathsf {mNP}$ that is also complete and it admits an efficient secret sharing scheme. Consider an arbitrary access structure $\varGamma =\{\varGamma _{n}\}_{n \in \mathbb {N}}$ from $\mathsf {mNP}$ satisfying the following: for every n there exists a $k_{n} \in \mathbb {N}$ such that $\varGamma _{n}= B_{k_{n}} \cup \{A \subseteq \mathcal {P}_{n}~|~|A| \ge k_{n}+1\}$, where $B_{k_{n}}$ is a subset of $A_{k_{n}}$, the set of all $k_{n}$-size subsets of $\mathcal {P}_{n}$. We now show that $\varGamma _{n}$ admits efficient secret sharing scheme for every $n \in \mathbb {N}$. For any fix n, there exists (completeness of $\varDelta$) $m \in \mathbb {N}$ such that $\varGamma _{n}$ is Karp/Levin reducible to $\varDelta _{m}$, i.e., there exists a polynomial time computable function $K_{R}: 2^{\mathcal {P}_{n}} \rightarrow 2^{\mathcal {Q}_{m}}$ with the following property:

$$\begin{aligned} \forall A \subseteq \mathcal {P}_{n}, A \in \varGamma _{n} \iff K_{R}(A) \in \varDelta _{m}. \end{aligned}$$

(5)

We now define, for every i in $1 \le i \le m$, an access structure $\varGamma _{n}^{(i)}$ on $\mathcal {P}_{n}$ as follows:

$$\begin{aligned} \varGamma _{n}^{(i)}= \big \{ A \subseteq \mathcal {P}_{n}~|~Q_{i} \in K_{R}(A) \wedge |A|=k_{n} \big \}\cup \{A \subseteq \mathcal {P}_{n}~|~|A| \ge k_{n}+1\} \end{aligned}$$

(6)

It is easy to see that, for every i in $1 \le i \le m$, $\varGamma _{n}^{(i)}$ is in $\mathsf {P} \cap \mathsf {mono}$. To prove the theorem, it suffices to show (by Theorem 2) that $\varGamma _{n} \bmod \varDelta _{m} = \{\varGamma _{n}^{(1)}, \ldots , \varGamma _{n}^{(m)}\}$, i.e., for every $A \subseteq \mathcal {P}_{n}$, $A \in \varGamma _{n}$ iff $A \bmod \varDelta _{m} \in \varDelta _{m}$. We consider the following exhaustive cases.

• $|A| < k_{n}$: Clearly, $A \notin \varGamma _{n}$ and $A \bmod \varDelta _{m} = \emptyset \notin \varDelta _{m}$, and therefore $A \in \varGamma _{n}$ iff $A \bmod \varDelta _{m} \in \varDelta _{m}$ holds true.

• $|A| \ge k_{n}+1$: In this case, $A \in \varGamma _{n}$ and $A \bmod \varDelta _{m} = \mathcal {Q}_{m} \in \varDelta _{m}$, and therefore $A \in \varGamma _{n}$ iff $A \bmod \varDelta _{m} \in \varDelta _{m}$ holds true.

• $|A| = k$: Finally, in this case

  $$\begin{aligned} A \bmod \varDelta _{m}= & {} \{Q_{i} \in \mathcal {Q}_{m}~|~A \in \varGamma _{n}^{(i)}\} \\= & {} \{Q_{i} \in \mathcal {Q}_{m}~|~(Q_{i} \in K_{R}(A) \wedge |A|=k_{n}) \vee (|A| \ge k_{n}+1)\}\\= & {} \{Q_{i} \in \mathcal {Q}_{m}~|~Q_{i} \in K_{R}(A)\} \\= & {} K_{R}(A) \end{aligned}$$

  Hence, $A \in \varGamma _{n} \mathop {\iff }\limits ^{eqn-5} K_{R}(A) \in \varDelta _{m} \iff A \bmod \varDelta _{m} \in \varDelta _{m}$.

Corollary 1

Assume access structures in $\mathsf {P} \cap \mathsf {mono}$ admit efficient secret sharing. Then existence of an efficient secret sharing for an access structure in $\mathsf {mNP}$ implies efficient secret sharing for all of $\mathsf {mNP}$.

Proof: It suffices (by Theorem 4) to prove the following: the class of access structures $\varGamma = \{\varGamma _{n}\}_{n \in \mathbb {N}} \in \mathsf {mNP}$ as described in Theorem 4 cover whole of $\mathsf {mNP}$. This follows by a technique developed in [5]. We now show access structures in $\mathsf {mNP}$ are in one-one correspondence with access structures of the type described in Theorem 4.

Let $\hat{\varGamma }=\{\hat{\varGamma }_{n}\}_{n\in \mathbb {N}}$ be an arbitrary access structure in $\mathsf {mNP}$. For every $n\in \mathbb {N}$, we now define, based on $\hat{\varGamma }_{n}$, an access structure $\tilde{\varGamma }_{2n}$. First identify $\hat{\varGamma }_{n}$ with the set $L_{\hat{\varGamma }_{n}} \subseteq \{0,1\}^{n}$. Now define $\tilde{\varGamma }_{2n}$ over a set of 2n players $\tilde{\mathcal {P}}_{2n}=\{P_{i,b}\}_{1 \le i \le n; b\in \{0,1\}}$:

$$ \tilde{\varGamma }_{2n}=B_{n} \cup \{A \subseteq \tilde{\mathcal {P}}_{2n}~|~|A| \ge n+1\} $$

where the collection $B_{n}$ consists of precisely the following n-size subsets of $\tilde{\mathcal {P}}_{2n}$: for every $x=(x_{1}, \ldots , x_{n}) \in L_{\hat{\varGamma }_{n}}$, the set $\{P_{1,x_{1}}, \ldots , P_{n,x_{n}}\}$ is in $B_{n}$. Clearly, the complexity of checking whether a set $A \subseteq \tilde{\mathcal {P}}_{2n}$ is in $\tilde{\varGamma }_{2n}$ is exactly the complexity of deciding the membership in $L_{\hat{\varGamma }_{n}}$. However $L_{\hat{\varGamma }}=\{L_{\hat{\varGamma }_{n}}\}_{n \in \mathbb {N}}$ is in $\mathsf {mNP}$ (as $\hat{\varGamma } \in \mathsf {mNP}$) and so $\tilde{\varGamma }=\{\tilde{\varGamma }_{2n}\}_{n \in \mathbb {N}}$ is in $\mathsf {mNP}$. Finally, $\tilde{\varGamma }=\{\tilde{\varGamma }_{2n}\}_{n \in \mathbb {N}}$ is clearly of the type described in Theorem 4. This proves the corollary.