Secret Sharing and Statistical Zero Knowledge

Abstract

We show a general connection between various types of statistical zero-knowledge (SZK) proof systems and (unconditionally secure) secret sharing schemes. Viewed through the SZK lens, we obtain several new results on secret-sharing:

• Characterizations: We obtain an almost-characterization of access structures for which there are secret-sharing schemes with an efficient sharing algorithm (but not necessarily efficient reconstruction). In particular, we show that for every language $L \in {{\mathbf {SZK}}_{\mathbf {L}}}$ (the class of languages that have statistical zero knowledge proofs with log-space verifiers and simulators), a (monotonized) access structure associated with L has such a secret-sharing scheme. Conversely, we show that such secret-sharing schemes can only exist for languages in ${\mathbf {SZK}}$.

• Constructions: We show new constructions of secret-sharing schemes with both efficient sharing and efficient reconstruction for access structures associated with languages that are in ${\mathbf {P}}$, but are not known to be in ${\mathbf {NC}}$, namely Bounded-Degree Graph Isomorphism and constant-dimensional lattice problems. In particular, this gives us the first combinatorial access structure that is conjectured to be outside ${\mathbf {NC}}$ but has an efficient secret-sharing scheme. Previous such constructions (Beimel and Ishai; CCC 2001) were algebraic and number-theoretic in nature.

• Limitations: We also show that universally-efficient secret-sharing schemes, where the complexity of computing the shares is a polynomial independent of the complexity of deciding the access structure, cannot exist for all (monotone languages in) $\mathbf {P}$, unless there is a polynomial q such that ${\mathbf {P}} \subseteq {\mathbf {DSPACE}}(q(n))$.

V. Vaikuntanathan—Supported in part by NSF CNS-1350619, CNS-1414119, the Qatar Computing Research Institute, NEC Corporation, Alfred P. Sloan Research Fellowship, Microsoft Faculty Fellowship, and a Steven and Renee Finn Career Development Chair.

P.N. Vasudevan—Supported by the Qatar Computing Research Institute.

1 Introduction

Secret-sharing [8, 29], a foundational primitive in information-theoretic cryptography, enables a dealer to distribute shares of a secret to n parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. Moreover, the shares of any unauthorized set of parties should reveal no information about the secret, even if the parties are computationally unbounded. The (monotone) collection of authorized sets is called an access structure.

We call a secret-sharing scheme efficient if both the sharing algorithm (executed by the dealer) and reconstruction algorithm (executed by the parties) run in time polynomial in n. Associating sets $S \subseteq [n]$ with their characteristic vectors $x_S \in \{0,1\}^n$, we can define a language $L_{\mathcal {A}}$ associated with an access structure $\mathcal {A}$.¹ Namely, $L_{\mathcal {A}}$ is simply the set of all $x_S$ such that $S \in \mathcal {A}$. For an access structure $\mathcal {A}$ to have an efficient secret sharing scheme, it must be the case that the language $L_{\mathcal {A}}$ is computable in polynomial time.

A major open question in information-theoretic cryptography is:

Q1: Characterize access structures with efficient secret-sharing schemes

Indeed, this question has been widely studied [6, 8, 19, 20, 29], culminating with the result of Karchmer and Wigderson [20] who showed efficient secret sharing schemes for various log-space classes.² We refer the reader to Beimel’s excellent survey [4] for more details. In any event, it is wide open whether all of $\mathbf {mP}$, the class of languages recognized by monotone polynomial-size circuits, has efficient secret sharing schemes.

Restricting the reconstruction algorithm to be a linear function of the shares gives us a special kind of secret-sharing scheme called a linear secret-sharing scheme. The Karchmer-Wigderson secret sharing scheme [20] for log-space classes is a linear secret-sharing scheme. We also know that linear and even the slightly more general quasi-linear schemes [5, 20] cannot exist for access structures outside $\mathbf {NC}$, the class of languages computable by boolean circuits of polylogarithmic depth. Finally, Beimel and Ishai [5] showed non-linear secret-sharing schemes for two specific access structures associated to algebraic problems (related to computing quadratic residuosity and co-primality) which are in $\mathbf {P}$ but are believed not to be in $\mathbf {NC}$.

We will also study secret-sharing schemes (which we call semi-efficient) where the dealer is efficient, namely runs in time polynomial in n, however the reconstruction algorithm need not be efficient. Aside from their theoretical interest, such secret-sharing schemes may find use in scenarios where sharing happens in the present (and thus has to be efficient) but reconstruction happens in a future where computational resources might be cheaper. This also justifies our desire to achieve information-theoretic (unconditional) security since not only the honest parties, but also the adversary gains more computational resources with time.

Beimel and Ishai [5] show a semi-efficient secret-sharing scheme for the language of quadratic residuosity modulo a composite, which is believed not to be in $\mathbf {P}$. However, quite surprisingly, a characterization of access structures with semi-efficient secret-sharing schemes also appears to be open:

Q2: Characterize access structures with semi-efficient secret-sharing schemes

As a parenthetical remark, we note that a different interpretation of efficiency is sometimes used in the secret-sharing literature. Namely, a secret-sharing scheme is termed efficient [9, 11, 21] if the total length of the n shares is polynomial in n. Let us call this notion size efficiency. This makes no reference to the complexity of either the sharing or the reconstruction algorithms. In this work, we use the strong interpretation of efficient, namely where both the sharing and reconstruction algorithms run in time $\mathsf {poly}(n)$ and that of semi-efficient where only the sharing algorithm needs to run in time $\mathsf {poly}(n)$. We note that either of these two notions is stronger than size efficiency.

It is against this backdrop that we begin our study. Our main contribution is to develop an interactive proof lens to study these questions. As concrete results of this connection, we obtain an almost-characterization of access structures with semi-efficent secret-sharing schemes (almost solving Q2), new combinatorial access structures conjectured to lie outside $\mathbf {NC}$ which have efficient secret-sharing schemes (extending [5]), and limitations on an ambitious notion of universally efficient secret-sharing. We describe our results in detail below.

1.1 Our Results

Our central tool is a special type of two-message interactive proof system (that we call Special Interactive Proofs). Roughly speaking, the restriction on the proof system for a language L (aside from the fact that it has two messages) is that the verifier uses a special procedure to accept or reject. In particular, the verifier V on input x and a uniformly random bit b, comes up with a message m to send to the prover. The prover wins (the verifier accepts) if he can guess the bit b, given m. If $x \in L$, the prover should have a distinguishing (and therefore an accepting) strategy. However, if $x \notin L$, the verifier messages for bits 0 and 1 should be statistically indistinguishable.

Before we proceed, we must clarify what it means to have a secret sharing scheme for a language L which is not necessarily monotone. We follow the approach of Beimel and Ishai [5] and define a (monotonized) access structure on 2n parties $\{P_{i,0},P_{i,1}\}_{i\in [n]}$ associated with L (more precisely, $L\cap \{0,1\}^n$): for every i, the pair of parties $\{P_{i,0},P_{i,1}\}$ is in the access structure, as is every set of parties $\{P_{1,x_1},P_{2,x_2},\ldots ,P_{n,x_n}\}$ for all $x \in L$. These are the minimal sets that make up the access structure $\mathcal {A}_L$. Note that the complexity of deciding whether a set $S \in \mathcal {A}_L$ is precisely the complexity of deciding the language L.

Our research in this direction was motivated by the fact that if, for some language L, $\mathcal {A}_L$ has a semi-efficient secret sharing scheme, then L has a special interactive proof: the verifier simply shares a random bit b according to the sharing algorithm and sends the prover the shares corresponding to the input, and the prover has to guess b. The honest prover runs the reconstruction algorithm, and completeness and soundness are guaranteed by correctness and privacy of the secret sharing scheme, respectively. We then investigated the circumstances under which the converse might also hold. We were able to show the following:

Theorem 1

(Informal). Let L be a language and let $\mathcal {A}_L$ be the associated access structure. If L has a special interactive proof with a log-space verifier, then $\mathcal {A}_L$ has a semi-efficient secret-sharing scheme. Conversely, if $\mathcal {A}_L$ has a semi-efficient secret-sharing scheme, then L has a special interactive proof.

Our proof goes through the notion of partial garbling schemes, defined and studied in the work of Ishai and Wee [18].

Characterizing Semi-Efficient Secret-Sharing. Using Theorem 1, we characterize access structures that have semi-efficient secret-sharing schemes: we show that all languages in $\mathbf {SZK}_{\mathbf {L}}$, the class of languages with statistical zero knowledge proof systems [28] where the verifier and simulator run in log-space, have semi-efficient secret-sharing schemes. This follows from the observation, using a result of Sahai and Vadhan [28], that L has a special interactive proof with a log-space verifier if and only if $L \in \mathbf {SZK}_{\mathbf {L}}$. Conversely, it is easy to see that if a language L has a semi-efficient secret-sharing scheme, then $L \in \mathbf {SZK}$, the class of languages with statistical zero knowledge proof systems with polynomial-time verifier and simulator. Together, this almost characterizes languages with semi-efficient secret-sharing schemes.

The class $\mathbf {SZK}_{\mathbf {L}}$, which is contained in $\mathbf {SZK}$, and hence in $\mathbf {AM}\cap \mathbf {co}\mathbf {AM}$, contains several problems of both historical and contemporary significance to cryptography, such as Quadratic Residosity, Discrete Logarithm, and the Approximate Closest Vector Problem, as well as other well-studied problems like Graph Isomorphism. For further details, including those about complete problems and about prospects of basing cryptography on the worst-case hardness of $\mathbf {SZK}_{\mathbf {L}}$, see [12]. As a result of these containments, our characterization captures as a special case the Beimel-Ishai secret-sharing scheme for the language of quadratic residuosity modulo composites [5].

We also show a version of this theorem for efficient (as opposed to semi-efficient) secret-sharing schemes. In particular:

Theorem 2

(Informal). Let L be a language and let $\mathcal {A}_L$ be the associated access structure. If L has a special interactive proof with a log-space verifier and a polynomial-time prover, then $\mathcal {A}_L$ has an efficient secret-sharing scheme. Conversely, if $\mathcal {A}_L$ has an efficient secret-sharing scheme, then L has a special interactive proof with a polynomial-time prover.

Constructions of Efficient Secret-Sharing Schemes. We show new constructions of efficient secret-sharing schemes for languages that are in $\mathbf {P}$ but are not known to be in $\mathbf {NC}$, namely Bounded-Degree Graph Isomorphism [2, 26], and lattice Shortest and Closest Vector problems in constant dimensions [16, 24]. Our constructions arise from special interactive proofs for these languages together with an application of Theorem 2. In particular, our construction for Bounded-Degree Graph Isomorphism gives us the first efficient secret-sharing scheme for a combinatorial access structure conjectured to be in $\mathbf {P}\!\!\setminus \!\!\mathbf {NC}$ (The results of Beimel and Ishai were for algebraic access structures associated to quadratic residuosity modulo primes and co-primality). Moreover, our interactive proofs and secret-sharing schemes are simple, natural and easy to describe.

Limitations on Universally Efficient Secret-Sharing Schemes. Consider secret sharing schemes that are defined not for a given access structure, but uniformly for some class of access structures. The sharing algorithm in such a case gets a description of the access structure, in the form of a circuit or a Turing machine that decides membership in the access structure. Typically, the sharing algorithm runs for as much time as the Turing machine (and therefore as much time as required to decide membership). However, there is no a-priori reason why this should be the case. Indeed, one can reasonably require that the sharing algorithm runs in some fixed polynomial time t(n), even though the access structure may take arbitrary polynomial time to decide. (We allow the reconstruction algorithm to run in arbitrary polynomial time to make up for the deficiency of the sharing algorithm). Can such universally efficient secret-sharing schemes exist?

Our definition is inspired by the recent progress on (computationally secure) succinct randomized encodings [7, 10, 23, 25]. Indeed, these works show, assuming indistinguishability obfuscation [3, 14], that $\mathbf {P}$ has computationally secure succinct randomized encoding schemes. One could also reasonably ask: Can such succinct randomized encodings exist unconditionally for all of $\mathbf {P}$? It was observed in [7] that this cannot be the case under certain complexity-theoretic assumptions about speeding up non-deterministic algorithms.

Using our interactive proof characterization, we show that unconditionally secure universally efficient secret-sharing schemes (and succinct randomized encodings) cannot exist for all languages in $\mathbf {P}$, unless there is a fixed polynomial q such that $\mathbf {P}\subseteq \mathbf {DSPACE}(q(n))$ (the class of languages computable by a deterministic single-tape Turing machine with q(n) space). We remind the reader that $\mathbf {P}\ne \mathbf {DSPACE}(q(n))$ for any fixed q, although non-containment either way is not known.

1.2 Related Work and Open Problems

In this work, we insist on statistical (or unconditional) security from our secret-sharing schemes. A number of works relax this to computational security and achieve stronger positive results. Settling for computational security and assuming the existence of one-way functions, Yao [32, 34] showed an efficient secret-sharing scheme for all monotone languages in $\mathbf {P}$ recognized by polynomial-sized monotone circuits. We mention that even here, we are far from a characterization as there are monotone languages in $\mathbf {P}$ that cannot be recognized by polynomial-sized monotone circuits [27, 30].

Komargodski, Naor and Yogev [22] also exploit the relaxation to computational security, and show secret-sharing schemes for all of monotone $\mathbf {NP}$, where the sharing algorithm is polynomial-time, and the reconstruction algorithm is polynomial-time given the $\mathbf {NP}$ witness. Their result relies on strong computational assumptions related to indistinguishability obfuscation [3, 14].

While we show semi-efficient secret-sharing schemes for monotonized access structures corresponding to all languages in $\mathbf {SZK}_{\mathbf {L}}$, it remains open to characterize which monotone languages in $\mathbf {SZK}$ have semi-efficient secret-sharing schemes. The central difficulty is that even if a language is monotone, there is no reason why the verifier in the SZK proof for the language should inherit monotonicity-like properties (and indeed, this is hard to even define).

2 Preliminaries and Definitions

Notation. Given a set S, we denote by $2^S$ the set of all subsets of S. Let $T = (t_1, \dots , t_n)$ and $B = \{i_1, \dots , i_m\} \subseteq [n]$; $T_B$ is used to denote the tuple $(t_{i_1}, \dots , t_{i_m})$.

We use languages and Boolean functions interchangeably. Given a language L, we overload L to also denote the corresponding Boolean function, namely, $L(x) = 0$ if $x \notin L$ and $L(x) = 1$ otherwise. Given a randomized algorithm A, we denote by A(x) the random variable arising from running A on x, and by A(x; r) the output when A is run on x with randomness r.

Given a distribution D over a finite set X and an $x\in X$, we denote by D(x) the probability mass D places on x, and for a subset $S\subseteq X$, $D(S) = \sum _{x\in S} D(x)$. $x\leftarrow D$ indicates that x is a sample drawn according to the distribution D. For a set S, $x\leftarrow S$ indicates that x is drawn uniformly at random from S.

We use the notion of statistical distance (also called total variation distance or $\ell _1$ distance) between distributions, defined as follows.

Definition 3

(Statistical Distance). The statistical distance between two distributions $D_1$ and $D_2$ over the domain X is defined as

$$ d(D_1, D_2) = \frac{1}{2}\sum _{x\in X} | D_1(x) - D_2(x) | = \max \limits _{S \subseteq X} \left( D_1(S) - D_2(S)\right) $$

Of particular interest to us is the following relationship of statistical distance to the advantage of any unbounded procedure in distinguishing between two distributions given a uniform prior.

Fact 4

Given distributions $D_1, D_2$ over a domain X, for functions $f: X \rightarrow \{0,1\}$, we have:

$$ \max \limits _{f} {\text {Pr}\left[ f(x) = b:\ b\leftarrow \{0,1\}, x \leftarrow D_b\right] } = \frac{1}{2} + \frac{d(D_1, D_2)}{2} $$

2.1 Complexity Classes

We briefly define the following complexity classes that are referred to frequently in the rest of the paper. To start with, $\mathbf {P}$ (resp. $\mathbf {BPP}$) is the class of languages decidable in deterministic (resp. randomized) polynomial time and $\mathbf {L}$ is the class of languages decidable in deterministic logarithmic space. $\mathbf {NC}^k$ is the class of languages decidable by circuits of depth $O((\log {n})^k)$ (here, n denotes the input length). A language is in $\mathbf {NC}$ if it is in $\mathbf {NC}^k$ for some k.

Definition 5

( ${\mathbf {NC}}^k$ ). For any $k \in \mathbb {N} \cup \{0\}$, $\mathbf {NC}^k$ is the class of languages L for which there exists a family of boolean circuits $\{C_n\}_{n\in \mathbb {N}}$ such that:

• There is a constant c such that for all n, $C_n$ has depth at most $c (\log {n})^k$.

• For any input x of length n, $x\in L \Leftrightarrow C_n(x) = 1$

$\mathbf {DSPACE}(p(n))$ is the class of languages decidable by deterministic uring machines running with space p(n). Thus, $\mathbf {L}$ is the union of $\mathbf {DSPACE}(c \log {n})$ over all constants c.

Definition 6

(DSPACE). For any function $p:\mathbb {N} \rightarrow \mathbb {N}$, $\mathbf {DSPACE}(p(n))$ is the class of languages L for which there exists a deterministic Turing machine L such that for any input x:

• $x\in L \Leftrightarrow M(x) = 1$

• M uses at most p(|x|) cells on its work tape.

And finally, $\mathbf {SZK}$ consists of languages that have Statistical Zero Knowledge (SZK) proofs, which are interactive proofs with some additional properties, as described below.

Definition 7

(SZK). A language L is in $\mathbf {SZK}$ if there exist a tuple of Turing machines (P, V, S), where the verifier V and simulator S run in probabilistic polynomial time, satisfying the following:

• (P, V) is an interactive proof for L with negligible completeness and soundness errors.

• Let (P, V)(x) denote the distribution of transcripts of the interaction between P and V on input x. For any $x\in L$ of large enough size,

  $$ d(S(x), (P,V)(x)) \le \mathrm {negl}(|x|) $$

The above is actually a definition of honest-verifier Statistical Zero Knowledge, but we know from [28] that any language with an honest-verifier SZK proof also has an SZK proof against cheating verifiers. So this follows as a definition of $\mathbf {SZK}$ as well. We refer the reader to [31] for extensive definitions and explanations.

$\mathbf {SZK}_{\mathbf {L}}$ is the same as $\mathbf {SZK}$, but with the verifier and simulator running with logarithmic space. In this case too, the above definition is only for honest verifiers, but as this would only define a larger class, and we show positive results for this class, we will work with this definition.

2.2 Secret Sharing

Definition 8

(Access Structure). Given a set of parties $P = \{P_1, \dots , P_n\}$, an access structure $\mathcal {A}$ is a monotone collection of subsets of P. That is, if $S \in \mathcal {A}$ and $T \supseteq S$, then $T \in \mathcal {A}$.

In the context of a secret-sharing scheme, the access structure consists of all subsets of parties that are allowed to reconstruct a secret shared among them. Of course, as the access structure is monotone, it suffices to specify its minimal elements. Along the lines of [5], we associate with every language L an family of access structures $\{\mathcal {A}_{L,n}\}_{n\in \mathbb {N}}$ where $\mathcal {A}_{L,n}$ is defined for 2n parties. We will then study the efficiency of secret sharing schemes for access structures in such families as a function of n. As will be evident from the definition below, the complexity of deciding whether a set $S \in \mathcal {A}_{L,n}$ is exactly the hardness of deciding the language.

Definition 9

(Access Structure associated with Language $\varvec{L}$ ). For a language L, its associated access structure, denoted by $\mathcal {A}_{L,n}$, for a set of 2n parties $\mathcal {P}_n = \{P_{i,b}\}_{i\in [n],b\in \{0,1\}}$ is defined by the following minimal elements:

• $\forall i: \{P_{i,0}, P_{i,1}\}\in \mathcal {A}_{L,n}$

• $\forall x\in L\cap \{0,1\}^n: \{P_{1,x_1}, \dots , P_{n,x_n}\}\in \mathcal {A}_{L,n}$

We use the following definition of secret sharing schemes.

Definition 10

(Statistical Secret Sharing). An $(\epsilon , \delta )$ -Secret Sharing Scheme for n parties $\mathcal {P} = \{P_1, \dots , P_n\}$ and a domain of secrets D under access structure $\mathcal {A}\subseteq 2^{\mathcal {P}}$ is a pair of algorithms $(S, R)$, where

• $S$ is the randomized sharing algorithm that takes as input a secret $s \in D$ and outputs a sequence of shares $(s_1,s_2,\ldots ,s_n)$; and

• $R$ is the deterministic reconstruction algorithm that takes as input a subset of parties $B \subseteq [n]$ and the corresponding subset of shares $(s_i)_{i\in B}$ and outputs either a secret s or a special symbol $\bot$.

We require $(S,R)$ to satisfy the following conditions:

• 1. Correctness: For any $B \in \mathcal {A}$ and any $s\in D$, the reconstruction algorithm $R$ works: ${\text {Pr}\left[ R(B, S(s)_B) = s\right] } \ge 1 - \epsilon (n)$

• 2. Privacy: For any $B \notin \mathcal {A}$ and any $s,s' \in D$: $d(S(s)_B, S(s')_B) \le \delta (n)$.

The scheme is said to be semi-efficient if $S$ is computable in poly(n) time, and it is said to be efficient if both $S$ and $R$ are computable in poly(n) time.

Unless otherwise specified, the domain of secrets for all schemes we talk about in this work shall be $\{0,1\}$, which is without loss of generality.

Remark 11

When we talk about access structures associated with promise problems, we require no guarantees from a secret sharing scheme for sets corresponding to inputs that do not satisfy the promise (even though technically they are not part of the associated access structure, and so privacy would otherwise be expected to hold).

While much of the literature on secret sharing schemes studies the size of the shares (and call schemes that produce shares of size $\mathsf {poly}(n)$ efficient), we use a stronger interpretation of efficiency. Namely, in all our exposition, the sharing algorithm S is required to run in time polynomial in n. Thus, we will not discuss the sizes of the shares produced by the schemes, which is always $\mathrm {poly}(n)$.

2.3 Partial Randomized Encodings

We use the notion of partial randomized encodings (defined as partial garbling schemes in [18]). They are essentially randomized encodings [17] where part of the input is allowed to be public.

Definition 12

(Partial Randomized Encodings). An $(\epsilon , \delta )$ -partial randomized encoding (PRE) of a (bi-variate) function $f: \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^*$ is a pair of (randomized) functions $(E_{f}, D_{f})$, called the encoding and decoding functions, respectively, that satisfy the following conditions for all $n, n'$:

• 1. Correctness: $\forall (x, z) \in \{0,1\}^n\times \{0,1\}^{n'}$:

  $$\begin{aligned} {\text {Pr}\left[ D_{f}(x, E_{f}(x, z)) = f(x, z)\right] } \ge 1 - \epsilon (n) \end{aligned}$$

  Note that the decoder gets the first half of the input, namely the public part x, in addition to the randomized encoding $E_{f}(x,z)$.

• 2. Privacy: $\forall x\in \{0,1\}^n$ and $\forall z_1, z_2\in \{0,1\}^{n'}$:

  $$\begin{aligned} f(x, z_1) = f(x, z_2) \Rightarrow d(E_{f}(x, z_1), E_{f}(x, z_2)) \le \delta (n) \end{aligned}$$

Furthermore:

• $(E_{f}, D_{f})$ is local (or locally computable) if $E_{f}$ can be decomposed into a set of functions $\{E_{f}^{(i)}(x_i,z)\}_{i\in [|x|]}$, where $E_{f}^{(i)}$ depends only on the ith bit of x and on z.

• $(E_{f}, D_{f})$ is perfect if $\epsilon (n) = \delta (n) = 0$.

• $(E_{f}, D_{f})$ is said to be semi-efficient if $E_{f}$ is computable in poly(|x|, |z|) time, and it is said to be efficient if both $E_{f}$ and $D_{f}$ are computable in poly(|x|, |z|) time.

We can extend the above definition to PREs of randomized functions in a natural way. Namely, to construct an $(\epsilon , \delta )$-PRE for a randomized function A(x, z; r), simply construct an $(\epsilon , \delta )$-PRE $(E_{A'}, D_{A'})$ for the deterministic function $A'(x,(z,r)) = A(x,z;r)$, and take $E_{A}(x, z)$ to be the random variable $E_{A'}(x, (z,r))$ when r is chosen uniformly at random, and have $D_{A}$ be the same as $D_{A'}$. Note that in $E_{A'}$, the randomness r used by A is part of the private input. This is crucial, as revealing r along with x and A(x, b; r) could end up revealing b.

We then have the following lemma, whose proof is in Appendix A.

Lemma 13

Let A(x, z) be a randomized function, and $(E_{A}, D_{A})$ be an $(\epsilon , \delta )$-PRE of A as described above. Then, for any x and any $z_1, z_2$:

$$\begin{aligned} d(A(x, z_1), A(x, z_2)) \le \delta ' \Rightarrow d(E_{A}(x, z_1), E_{A}(x, z_2)) \le \delta (|x|) + \delta ' \end{aligned}$$

We also use the following lemma.

Lemma 14

([1, 18]). Every function $f: \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^*$ that can be computed in $\mathbf {L}/\mathrm {poly}$ has efficient perfect locally computable PREs, with encoding in $\mathbf {NC}^0$ and decoding in $\mathbf {NC}^2$.

Finally, we abuse notation slightly and define partial randomized encodings for languages (boolean functions) a bit differently, for somewhat technical reasons (instead of calling this object something different).

Definition 15

(PREs for Languages). An $(\epsilon , \delta )$ -partial randomized encoding (PRE) of a language $L \subseteq \{0,1\}^*$ is a pair of (randomized) functions $(E_{L}, D_{L})$, called the encoding and decoding functions, respectively, that satisfy the following conditions:

• 1. Correctness: $\forall x \in L$ and $b\in \{0,1\}$: ${\text {Pr}\left[ D_{L}(x, E_{L}(x, b)) = b\right] } \ge 1 - \epsilon (|x|)$.

• 2. Privacy: $\forall x\notin L$, $d(E_{L}(x, 0), E_{L}(x, 1)) \le \delta (|x|)$.

Semi-efficiency, efficiency and locality are defined as for general partial randomized encodings.

In other words, a PRE for a language L is a PRE for the following function:

$$f_L(x, b) = \left\{ \begin{array}{cc} b &{}\text{ if } x\in L \\ \bot &{}\text{ otherwise } \end{array} \right. $$

Using the above equivalence and Lemma 14, we have the following:

Lemma 16

([18]). Every language in $\mathbf {L}/\mathrm {poly}$ has efficient perfect locally computable PREs, with encoding in $\mathbf {NC}^0$ and decoding in $\mathbf {NC}^2$.

2.4 Special Interactive Proofs

We define a special type of interactive proof system with two messages. Roughly speaking, the restriction on the proof system (aside from the fact that it has two messages) is that the verifier uses a special procedure to accept or reject. In particular, the verifier V on input x and a uniformly random bit b, comes up with a message m to send to the prover. The prover wins if he can guess the bit b, given m.

Definition 17

(SIP). An $(\epsilon , \delta )$ -Special Interactive Proof (SIP) for a language L is a pair (P, V), where:

• 1. V is a PPT algorithm that takes as input an instance x and a bit b, and outputs a message m; and

• 2. P takes as input the instance x and the verifier message m, and outputs a bit $b'$.

We require (P, V) to satisfy the following conditions, when $b \leftarrow \{0,1\}$:

• 1. Completeness: $\forall x\in L$, ${\text {Pr}\left[ P(x, V(x, b)) = b\right] } \ge 1 - \epsilon (|x|)$.

• 2. Soundness: $\forall x\notin L$, and for any $P^*$, ${\text {Pr}\left[ P^*(x, V(x, b)) = b\right] } \le 1/2 + \delta (|x|)$.

While the restrictions imposed on these proofs seem rather severe, they turn out to be quite general. In fact, it follows from the work of Sahai and Vadhan [28] that the set of languages with such proofs is exactly the class $\mathbf {SZK}$. See Theorem 20.

2.5 Statistical Zero Knowledge

Recall that the class $\mathbf {SZK}$ is the set of languages that have statistical zero-knowledge proofs, and the class $\mathbf {SZK}_{\mathbf {L}}$ is set of languages that have statistical zero-knowledge proofs where the verifier and the simulator (for a statistically close simulation) both run in log-space.

Definition 18

(Promise Problems SD , $SD_L$ ). The promise problem $(\epsilon , \delta )$ -Statistical Difference (SD) is defined by the following YES and NO instances:

$$\begin{aligned} SD^{YES}&= \left\{ (M_1, M_2, 1^n) : d(M_1^n, M_2^n) > 1 - \epsilon (n)\right\} \\ SD^{NO}&= \left\{ (M_1, M_2, 1^n) : d(M_1^n, M_2^n) < \delta (n)\right\} \end{aligned}$$

where $M_1, M_2$ are deterministic Turing machines, and $M_1^n, M_2^n$ represent the random variables corresponding to their outputs when the input is distributed uniformly at random in $\{0,1\}^n$.

If $M_1$ and $M_2$ are log-space machines, then the language is called $(\epsilon , \delta )$ -Statistical Difference for Log-space Machines, or simply $SD_L$.

Theorem 19

([28]). For every $\epsilon (n), \delta (n) = 2^{-n^{O(1)}}$ such that $\delta (n) < (1-\epsilon (n))^2$, the $(\epsilon , \delta )$-SD problem is complete for $\mathbf {SZK}$, and the $(\epsilon , \delta )$-$SD_L$ problem is complete for $\mathbf {SZK}_{\mathbf {L}}$.

We will use the following theorem which is a slightly stronger version of Theorem 19. We describe the proof (which follows from the proof of Theorem 19 in [28]) in Appendix B for completeness.

Theorem 20

([28]). There exist negligible functions $\epsilon (n), \delta (n) = n^{-\omega (1)}$ such that for any language $L\in \mathbf {SZK}$, L has an $(\epsilon , \delta )$-special interactive proof system (P, V). Furthermore, if $L\in \mathbf {SZK}_{\mathbf {L}}$, then the verifier V can be computed in log-space.

Sketch of Proof

For the main statement, we observe that the complete problem for $\mathbf {SZK}$, namely $(\epsilon , \delta )$-SD, has a simple $(\epsilon /2, \delta /2)$-special interactive proof which works as follows.

• The verifier V, on input an instance $(M_0, M_1, 1^n)$ of the SD problem chooses a uniformly random bit b, and outputs a sample from $M_b^n$; and

• The prover’s goal is to guess the bit b.

By Fact 4, it follows that the best success probability of any prover in this game is $\frac{1+d(M_0^n, M_1^n)}{2}$. By the completeness of SD (Theorem 19), we get that $\mathbf {SZK}$ has $(\epsilon , \delta )$-special interactive proofs for some $\epsilon (n), \delta (n) = n^{-\omega (1)}$.

The proof for $\mathbf {SZK}_{\mathbf {L}}$ works in exactly the same way, except it is now a concern that the verifier has to first run the SZK-completeness reduction to obtain an instance of the statistical distance problem $SD_L$, since it is not guaranteed that the reduction runs in log-space. However, we show that the Sahai-Vadhan reduction indeed does. We refer the reader to Appendix B for more details.

In fact, the connection between languages with special interactive proofs and $\mathbf {SZK}$ goes both ways. Namely,

Fact 21

Let $(1 - 2\epsilon (n))^2 > 2\delta (n)$. If a language L has an $(\epsilon , \delta )$-SIP, then $L \in \mathbf {SZK}$.

This is because deciding a language L that has an $(\epsilon , \delta )$-SIP (P, V) is the same as deciding whether $(V_{(x, 0)}, V_{(x, 1)}, 1^{|r(|x|)|}) \in (2\epsilon , 2\delta )$-SD, where $V_{(x, b)}(r) = V(x, b; r)$, and $(2\epsilon , 2\delta )$-SD is in $\mathbf {SZK}$ for $\epsilon$ and $\delta$ satisfying the above property.

3 From Zero Knowledge to Secret Sharing and Back

In this section, we show tight connections between languages with special interactive proofs, partial randomized encodings (PRE), and secret sharing schemes. In particular, we show:

Theorem 22

(Main Theorem). For any language L and parameters $\epsilon (n)$ and $\delta (n)$, the following three statements are equivalent:

• 1. There are parameters $\epsilon _1 = O(\epsilon )$ and $\delta _1 = O(\delta )$ such that L has an $(\epsilon _1, \delta _1)$-special interactive proof (P, V), where the verifier V has a semi-efficient, locally computable, $(\epsilon _1,\delta _1)$-PRE.

• 2. There are parameters $\epsilon _2 = O(\epsilon )$ and $\delta _2 = O(\delta )$ such that L has a semi-efficient, locally computable, $(\epsilon _2, \delta _2)$-PRE.

• 3. There are parameters $\epsilon _3 = O(\epsilon )$ and $\delta _3 = O(\delta )$ such that for all n, there is a semi-efficient $(\epsilon _3,\delta _3)$-secret sharing scheme under the access structure $\mathcal {A}_{L,n}$.

We will prove Theorem 22 in Sect. 3.1, and here we state a number of interesting corollaries. The first two corollaries “almost” characterize the languages L whose associated access structure $\mathcal {A}_{L,n}$ (as defined in Definition 9) has a semi-efficient secret-sharing scheme. Corollary 23 shows that any language in $\mathbf {SZK}_{\mathbf {L}}$ has a semi-efficient secret-sharing scheme. Corollary 24 shows that furthermore, if $\mathbf {P}/\mathrm {poly}$ has semi-efficient, locally computable PREs, then any language in the entire class $\mathbf {SZK}$ has a semi-efficient secret-sharing scheme. Moreover, it also says that no language outside $\mathbf {SZK}$ has semi-efficient secret-sharing schemes, implying that our characterization is almost tight.

Corollary 23

Let $\epsilon (n), \delta (n) = n^{-\omega (1)}$ be negligible functions. For any language $L\in \mathbf {SZK}_{\mathbf {L}}$, and for every n, there is a semi-efficient $(\epsilon ,\delta )$-secret sharing scheme under the associated access structure $\mathcal {A}_{L,n}$.

Proof

Theorem 20 asserts that for any $L\in \mathbf {SZK}_{\mathbf {L}}$, there is an $(\epsilon , \delta )$-special interactive proof (P, V) for some $\epsilon (n),\delta (n)= n^{-\omega (1)}$, where the verifier algorithm V can be computed in log-space. Therefore, by Lemma 14, V has an efficient (and not just semi-efficient) perfect, locally computable PRE. Applying Theorem 22 (in particular, that $(1) \Rightarrow (3)$), there is a semi-efficient $(O(\epsilon ), O(\delta ))$-secret sharing scheme for $\mathcal {A}_{L,n}$.

Corollary 24

Let $\epsilon (n), \delta (n) = n^{-\omega (1)}$ be negligible functions.

• Assume that $\mathbf {P}/\mathrm {poly}$ has semi-efficient $(\epsilon , \delta )$-locally computable PREs. Then, for any language $L\in \mathbf {SZK}$, and for every n, there is a semi-efficient $(\epsilon ,\delta )$-secret sharing scheme under the associated access structure $\mathcal {A}_{L,n}$.

• Conversely, if $\mathcal {A}_{L,n}$ has a semi-efficient $(\epsilon , \delta )$-secret sharing scheme, then $L \in \mathbf {SZK}$.

This follows from the same arguments as Corollary 23, but with the absence of something like Lemma 14 to complete the argument. In fact, one may replace $\mathbf {P}/\mathrm {poly}$ in Corollary 24 with any complexity class $\mathbf {C}$ that is closed under the operations involved in the reduction used in the proof of Theorem 36 (while replacing $\mathbf {SZK}$ with the appropriate $\mathbf {SZK}_{\mathbf {C}}$). The converse is true because of Theorem 22 and Fact 21

We also have the following theorem about efficient secret sharing schemes, where both the sharing and reconstruction algorithms run in time polynomial in n. The difference from Theorem 22 is that here, we require the prover in the special interactive proof to be efficient, namely run in time polynomial in n. We view this theorem as an avenue to constructing efficient secret sharing schemes for languages L outside $\mathbf {L}$: namely, to construct a secret-sharing scheme for $\mathcal {A}_{L,n}$, it suffices to construct special interactive proofs for L wherein the verifier algorithm can be computed in $\mathbf {L}$.

The proof of Theorem 25 follows directly from that of Theorem 22.

Theorem 25

For any language L and parameters $\epsilon (n)$ and $\delta (n)$, the following three statements are equivalent:

• 1. There are parameters $\epsilon _1 = O(\epsilon )$ and $\delta _1 = O(\delta )$ such that L has an $(\epsilon _1, \delta _1)$-special interactive proof (P, V), where the prover algorithm is computable in polynomial time, and the verifier V has an efficient, locally computable, $(\epsilon _1,\delta _1)$-PRE.

• 2. There are parameters $\epsilon _2 = O(\epsilon )$ and $\delta _2 = O(\delta )$ such that L has an efficient, locally computable, $(\epsilon _2, \delta _2)$-PRE.

• 3. There are parameters $\epsilon _3 = O(\epsilon )$ and $\delta _3 = O(\delta )$ such that for all n, there is an efficient $(\epsilon _3,\delta _3)$-secret sharing scheme under the access structure $\mathcal {A}_{L,n}$.

3.1 Proof of the Main Theorem

We prove Theorem 22 by showing that $(1) \Rightarrow (2) \Rightarrow (3) \Rightarrow (1)$.

$\mathbf {(1) \Rightarrow (2)}$ . Let (P, V) be an $(\epsilon ,\delta )$-special interactive proof for the language L, and let $(E_{V}, D_{V})$ be the hypothesized semi-efficient, locally computable $(\epsilon , \delta )$-PRE for V. The PRE for the language L works as follows:

• $E_{L}(x,b) = E_{V}(x,b)$

• $D_{L}(x,y) = P(x,D_{V}(x,y))$

We first show correctness. Let $x \in L$ and $b\in \{0,1\}$. From the correctness of the PRE for the verifier algorithm V, we know that:

$$ D_{V}(x, E_{V}(x,b)) = V(x,b) $$

with probability at least $1-\epsilon$. Now, by the completeness of the special interactive proof, we know that:

$$ P(x, V(x,b)) = b $$

with probability at least $1-2\epsilon$ (because this probability is at least $1 - \epsilon$ when b is chosen at random). Putting these together, we have:

$$ D_{L}(x,E_{L}(x,b)) = P \big (x, D_{V}(x, E_{V}(x,b)) \big ) = P \big (x, V(x,b) \big ) = b $$

with probability at least $1-3\epsilon$.

Next, we turn to privacy. Let $x \notin L$. We will show that $E_{L}(x,0)$ and $E_{L}(x,1)$ are statistically close. First, note that by the $\delta$-soundness of the special interactive proof, we know that the distributions V(x, 0) and V(x, 1) are $O(\delta )$-close. Now, by Lemma 13 and using the $\delta$-privacy of the PRE scheme for V, this means that $E_{V}(x,0)$ and $E_{V}(x,1)$ are also $O(\delta )$-close. This demonstrates privacy of our PRE scheme for L.

Since $E_{L}$ is the same as $E_{V}$, it is clear that if the PRE scheme $(E_{V},D_{V})$ is locally computable, so is $(E_{L}, D_{L})$. Moreover, if $(E_{V},D_{V})$ is semi-efficient, so is $(E_{L}, D_{L})$. Finally, if $(E_{V},D_{V})$ is efficient and the prover P in the special interactive proof is computable in polynomial time, then $(E_{L}, D_{L})$ is also efficient.

$\mathbf {(2) \Rightarrow (3)}$ . This implication follows from the work of Ishai and Wee [18]. We provide a proof here for completeness.

Given a locally computable $(\epsilon , \delta )$-PRE $(E_{L}, D_{L})$ for a language L, let the set of functions $\{E_{L}^{(i)}(x_i, b)\}_{i\in [n]}$ be the local decomposition of $E_{L}(x,b)$. The following is the secret sharing scheme $(S, R)$ for the access structure $\mathcal {A}_{L,n}$:

• Sharing: Let $s\in \{0,1\}$ be the secret bit to be shared. S(s) works as follows:

  • 1. For each i, pick $s_{i,0}, s_{i,1} \in \{0,1\}$ at random such that $s_{i,0} \oplus s_{i,1} = s$, and give $s_{i,b}$ to the party $P_{i,b}$.

  • 2. Select bits $\{s_0, \dots , s_n\}$ at random such that $\bigoplus _{i=0}^n s_i = s$. For each $i\in [n]$, give $s_i$ to both $P_{i,0}$ and $P_{i,1}$.

  • 3. Choose a random string r, compute $\psi _{i,b} \leftarrow E_{L}^{(i)}(b, s_0; r)$ for every $i\in [n]$ and $b\in \{0,1\}$, and give $\psi _{i,b}$ to party $P_{i,b}$.

• Reconstruction: Any authorized set $B\in \mathcal {A}_{L,n}$ reconstructs the secret as follows:

  • If B contains $P_{i,0}$ and $P_{i,1}$ for some i, the secret s can be retrieved as $s = s_{i,0} \oplus s_{i,1}$.

  • If not, then $B = \{P_{i,x_i}\}$ for some $x\in L$. This means that between them, the parties contain $E_{L}(x, s_0; r) = \{E_{L}^{(i)}(x_i, s_0; r)\}_{i\in [n]}$. Output

    $$ D_{L}(x, E_{L}(x, s_0; r)) \oplus \bigoplus _{i\in [n]} s_i $$

    as the secret.

For correctness, note that there are two possible types of authorized sets B in $\mathcal {A}_{L,n}$. If the set B contains parties $P_{i,0}$ and $P_{i,1}$ for some i, they recover the secret as $s_{i,0} \oplus s_{i,1}$. If not, the authorized set contains the parties $P_{1,x_1},\ldots ,P_{n,x_n}$ for some $x = (x_1,x_2,\ldots ,x_n) \in L$. By the correctness of the PRE scheme for L, we know that $D_{L}(x, E_{L}(x, s_0; r)) = s_0$ with probability at least $1-\epsilon$. Thus, the recovered secret is

$$ D_{L}(x, E_{L}(x, s_0; r)) \oplus \bigoplus _{i\in [n]} s_i = \bigoplus _{i\in \{0,1,\ldots ,n\}} s_i = s $$

with probability at least $1-\epsilon$.

For privacy, there are again two types of sets B that are not present in $\mathcal {A}_{L,n}$. If there is an i such that the set of parties B does not contain either of $P_{i,0}$ and $P_{i,1}$, then B’s shares look completely random due to the absence of any information about $s_i$. The other case is when $B = \{P_{i,x_i}\}$ for some $x\notin L$. In this case, $d(S(0)_B, S(1)_B)$ is exactly the distance between $E_{L}(x, 0)$ and $E_{L}(x, 1)$ due to how the $s_i$’s are picked, which is at most $\delta$ by the privacy of the randomized encoding of L.

It is also easy to see from the definition of $S$ and $R$ that if $(E_{L}, D_{L})$ is semi-efficient, then so is $(S, R)$; and the same if it is efficient.

$\mathbf {(3) \Rightarrow (1)}$ . Given an $(\epsilon ,\delta )$-secret sharing scheme $(S, R)$ for the access structure $\mathcal {A}_{L,n}$, we construct a special interactive proof (P, V) for L, as follows:

• The verifier V, on input x and a bit b, outputs $S(b)_{B_x}$, where $B_x = \{P_{i,x_i}\}$.

• The prover P on input x and the verifier message m, outputs $R(B_x, m)$, where $B_x = \{P_{i,x_i}\}$.

For completeness, we have that for any $x\in L$, when $b\leftarrow \{0,1\}$,

$${\text {Pr}\left[ P(x, V(x, b)) = b\right] } = {\text {Pr}\left[ R(B_x, (S(b)_{B_x}) = b\right] } \ge 1 - \epsilon $$

by the correctness of secret sharing scheme, as $B_x\in \mathcal {A}_{(L.n)}$.

For privacy, we have that for any $x\notin L$, when $b\leftarrow \{0,1\}$, for any $P^*$,

$$\begin{aligned} {\text {Pr}\left[ P^*(x, V(x, b)) = b\right] }&\le \frac{1 + d(V(x, 0), V(x, 1))}{2} \le \frac{1}{2} + \frac{\delta }{2} \end{aligned}$$

by privacy of the secret sharing scheme, as $B_x\notin \mathcal {A}_{L,n}$.

V is a PPT algorithm if $(S, R)$ is semi-efficient, and P is computable in polynomial time if $(S, R)$ is efficient. Also, V is local because it can be split into the collection $\{V^{(i)}(x_i, b) = S(b)_{\{P_{i,x_i}\}}\}$, so it serves as its own semi-efficient locally computable PRE.

4 Positive Results on Efficient Secret Sharing

In this section we present efficient secret sharing schemes for access structures associated with Bounded-Degree Graph Non-Isomorphism, Lattice Closest Vector in small dimensions, and Co-Primality. These are obtained by the application of Theorem 25 (in particular, the implication $(1) \Rightarrow (2)$ in the theorem).

Useful throughout this section is the fact that arithmetic over integers (and rational numbers) may be performed in $\mathbf {NC}^1$ (see [33] for details).

4.1 Bounded-Degree Graph Non-Isomorphism

Notation. Given an upper triangular matrix $M \in \{0,1\}^{n\times n}$, denote by G(M) the undirected graph whose adjacency matrix is $(M+M^T)$, and for a symmetric matrix M, the undirected graph whose adjacency matrix is M. The degree of a graph, deg(G), is the maximum degree of any vertex in the graph. If $G_1$ and $G_2$ are isomorphic, we denote this as $G_1 \equiv G_2$.

Definition 26

$\mathbf ( {\textsf {dBDGNI}}\mathbf{).}$ d-Bounded Degree Graph Non-Isomorphism is the promise problem given by the following sets of YES and NO instances over pairs of upper triangular matrices:

$$\begin{aligned} \mathsf {dBDGNI}^{YES}&= \{ (M_0, M_1) | G(M_0) \not \equiv G(M_1); deg(G(M_0)), deg(G(M_1)) \le d \}\\ \mathsf {dBDGNI}^{NO}&= \{ (M_0, M_1) | G(M_0) \equiv G(M_1); deg(G(M_0)), deg(G(M_1)) \le d \} \end{aligned}$$

While Graph (Non-)Isomorphism is not known to be in $\mathbf {P}$, there is a classical polynomial time algorithm known for $\mathsf {dBDGNI}$ due to Luks [26]. However, it appears to be a long open question whether $\mathsf {dBDGNI}$ is in $\mathbf {NC}$ (or even in $\mathbf {RNC}$) [2].

Theorem 27

For every constant d and every n, there is an efficient (perfect) secret sharing scheme for the access structure $\mathcal {A}_{\mathsf {dBDGNI}, n}$. The complexity of the reconstruction algorithm grows as $n^{O(d)}$, whereas sharing runs in time polynomial in n.

Proof

We prove this by showing a special interactive proof for $\mathsf {dBDGNI}$ where the verifier runs in log-space (and therefore, has efficient perfect locally computable PREs) and the prover runs in polynomial time. This satisfies statement (1) in Theorem 25, and hence implies the existence of the required secret sharing scheme.

The SIP proof (P, V) works along the lines of the classical SZK proof for Graph Non-Isomorphism [15], as follows:

• The verifier $V((M_0, M_1), b)$, on input upper triangular matrices $M_0, M_1 \in \{0,1\}^{n\times n}$ and bit b, selects a random permutation matrix $P \in S_n$, and outputs $P(M_b+M_b^T)P^T$.

• The prover $P((M_0, M_1), M)$, checks whether $G(M) \equiv G(M_0)$. If so, it outputs 0, else 1.

Note that the operation $P(M+M^T)P^T$ is equivalent to permuting the vertices of the graph G(M) by the permutation P.

Perfect completeness of this protocol follows from the fact that if $M_0 \not \equiv M_1$, then the verifier’s output M will be such that G(M) is isomorphic to exactly one of $G(M_0)$ and $G(M_1)$, and P can identify which by running the algorithm for $\mathsf {dBDGNI}$ [26].

The protocol is perfectly sound because if $M_0 \equiv M_1$, then the distribution of the verifier’s output is the same whether $b = 0$ or 1, and P has probability exactly 1 / 2 of guessing b correctly.

The complexity of the verifier V in the above protocol is that of selecting a random permutation and performing two matrix multiplications, both of which can be done in log-space. Hence by Lemma 14, V has efficient perfect locally computable PREs. The prover P is computable in polynomial time because all the prover does is run the (polynomial time) algorithm for $\mathsf {dBDGNI}$.

(That the running time of reconstruction algorithm of the resulting secret sharing scheme is $n^{O(d)}$ can be seen by tracing its dependence on the running time of the algorithm for $\mathsf {dBDGNI}$ - the one in [26] runs in time $n^{O(d)}$ - in the proof of Theorem 22.)

4.2 Lattice Closest Vectors

Notation. For a full-rank (over $\mathbb {Q}$) matrix $B\in \mathbb {Z}^{d\times d}$, let $\Lambda (B)$ denote the integer lattice (of dimension d) whose basis is B, and $\mathcal {P}(B)$ denote the fundamental parallelepiped of the same lattice (the parallelepiped formed by the column vectors of B and the origin). We denote by $\mathcal {B}(y, \delta )$ the set of points in the ball of radius $\delta$ centered at the point y (note that as we work with discretised space and not with $\mathbb {R}^d$, the number of points in this set is finite).

Given full-rank matrix $B\in \mathbb {Z}^{d\times d}$, a vector $y\in \mathbb {Z}^d$, $\delta \in \mathbb {Z}^+$ and $\gamma \in [0,1]$, the (decision version of the) gap closest vector problem in d dimensions ($\mathsf {GapCVP}_{\gamma ,d}$) asks whether the Euclidean distance of y from (any point in) $\Lambda (B)$ is at most $(\gamma \delta )$ or at least $\delta$.

While classical algorithms due to Gauss, and Lenstra, Lenstra and Lovasz (from [24]) show that for any d, $\mathsf {GapCVP}_{\gamma ,d}$ is in $\mathbf {P}$ for any $\gamma$, it is not known to be (and conjectured not to be) in $\mathbf {NC}$. We are interested in the complement of this problem, as defined below.

Definition 28

( ${{{\mathbf {\mathsf{{coGapCVP}}}}}_{\gamma ,d}}{\mathbf{).}}$ For any $d\in \mathbb {Z}^+$ and $\gamma \in [0,1]$, ${{\mathbf {\mathsf{{coGapCVP}}}}}_{\gamma ,d}$ is the promise problem defined by the following YES and NO instances over triples $(B, y, \delta )$, where $B\in \mathbb {Z}^{d\times d}$ is full-rank over $\mathbb {Q}$, $y\in \mathbb {Z}^d$ and $\delta \in \mathbb {Z}^+$:

$$\begin{aligned} \mathsf {coGapCVP}_{\gamma ,d}^{YES}&= \{(B,y,\delta )\ |\ \forall x \in \Lambda (B) : ||y-x|| > \delta \}\\ \mathsf {coGapCVP}_{\gamma ,d}^{NO}&= \{(B,y,\delta )\ |\ \exists x \in \Lambda (B) : ||y-x|| \le \gamma \delta \} \end{aligned}$$

The following theorem asserts the existence of efficient secret sharing schemes under access structures associated with the above problem.

Theorem 29

For every c, d, n, and any $\gamma = \left( 1 - \varOmega (\frac{1}{n^c})\right)$, there is an efficient (o(1), o(1))-secret sharing scheme under the access structure $\mathcal {A}_{\mathsf {coGapCVP}_{\gamma ,d}, n}$.

We prove this theorem by constructing a (o(1), o(1))-Special Interactive Proof for $\mathsf {coGapCVP}_{\gamma ,d}$ with a log-space verifier and a poly time prover. As the verifier is computable in log-space, it has efficient perfect locally computable PREs, by Lemma 14. The existence of such an SIP, along with Theorem 25, implies the efficient secret sharing schemes we need. In interest of space, we defer details of the proof to the full version of this paper.

4.3 Co-primality

Efficient secret sharing schemes for non-co-primality and semi-efficient ones for quadratic non-residuosity were shown by Beimel and Ishai [5] as an illustration of the power of non-linear secret sharing schemes over linear ones. We note that these follow as implications of our Theorem 22 given the existence of SZK proofs for these languages with logspace verifiers (which are indeed known to exist).

We demonstrate here, as an example, the case of Non-Co-Primality, which is in $\mathbf {P}$, but again, as noted in [5], not known to be in $\mathbf {NC}$.

Definition 30

(NCoP) . The language Non-Co-Primality $(\mathsf {NCoP})$ consists of pairs of positive integers that are not co-prime, represented as strings, that is,

$$\begin{aligned} \mathsf {NCoP}= \{(u,v)\ |\ u,v\in \mathbb {Z}^+, gcd(u,v) > 1\} \end{aligned}$$

Theorem 31 asserts the existence of statistically correct, statistically private efficient secret sharing schemes under the access structure associated with $\mathsf {NCoP}$.

Theorem 31

For every n, there is an efficient $(\epsilon , \delta )$-secret sharing scheme under the access structure $\mathcal {A}_{\mathsf {NCoP}, n}$ from some $\epsilon (n), \delta (n) = o(1)$.

Proof

Again, we prove this by demonstrating a (o(1), o(1))-SIP for Non-co-primality where the prover is efficient and the verifier has efficient perfect locally computable PREs. This implies what we need, by Theorem 25.

We denote by |u| the length of the representation of u as a boolean string. Below, we assume $|u| \ge |v|$. The SIP proof (P, V) is roughly as follows, for some $m = \varTheta (|u|)$:

• The verifier V takes as input (u, v) and a bit b.

  • If $b = 1$, it outputs m random multiples of u modulo v; that is, it picks m random numbers $\{r_i\}_{i\in [m]} \leftarrow \{0,1\}^{|u|}$ and outputs $\{(r_i u) (mod\ v)\}$.

  • If $b = 0$, it outputs m random numbers in [v].

• The prover P takes as input (u, v) and the verifiers message, which is a set of m numbers $\{a_i\}_{i\in [m]}$. If $gcd(\{a_i\}) = 1$, the prover outptus 0, else 1.

The above SIP is complete because if $gcd(u,v) > 1$, then if $b = 1$, all multiples of u modulo v will be divisible by gcd(u, v), and the prover will always output 1, and if $b = 0$, with high probability the gcd of m random numbers in [v] will be 1 and the prover will output 0. It is sound because when $gcd(u,v) = 1$, the distribution of multiples of u (drawn from a large enough range) modulo v is negligibly close to uniform, and the cases $b = 0$ and $b = 1$ are indistinguishable.

The verifier V is computable in $\mathbf {L}$, as all it does is multiply n-bit numbers, and so has efficient perfect locally computable PREs, by Lemma 14. The prover is efficient, as all it has to do is compute the gcd of some numbers.

5 Negative Results on Universally Efficient Secret Sharing

In this section, we show that a natural strengthening of efficient secret-sharing, that we call universally efficient secret-sharing, cannot exist for all of $\mathbf {P}$, if for every polynomial t, $\mathbf {P}\not \subseteq \mathbf {DSPACE}(t(n))$.

Notation. Below, by L we denote both a language in a class $\mathcal {C}$, and its standard representation as a member of this class, say, for example, as a Turing machine that decides the language in case $\mathcal {C} = \mathbf {P}$. For a function f that takes two arguments (as f(x, y)), by $f(x,\cdot )$, we denote f curried with x, that is, the function $g(y) = f(x,y)$; this extends naturally to the case where f takes more than two arguments.

Definition 32

(Universal Secret Sharing). An $(\epsilon , \delta )$ -Universally Efficient Secret Sharing Scheme (USS), or simply a universal secret sharing scheme, for a class of languages $\mathcal {C}$ over a domain D is a pair of (randomized) algorithms $(S, R)$ such that for any $L\in \mathcal {C}$ and any n, $(S(L, 1^n, \cdot ), R(L, 1^n, \cdot , \cdot ))$ is an $(\epsilon , \delta )$-secret sharing scheme under the access structure $A_{L,n}$ over the domain D.

For any polynomial t, a universal secret sharing scheme is said to be t-semi-efficient if for any $L\in \mathcal {C}$, $S(L, 1^n, \cdot )$ is computable in time t(n). The scheme is said to be t-efficient if both $S(L, 1^n, \cdot )$ and $R(L, 1^n, \cdot , \cdot )$ are computable in time t(n).

Theorem 33

Let, for all n, $1 - \epsilon (n) > \delta (n)$. If a class of languages $\mathcal {C}$ has t-semi-efficient $(\epsilon , \delta )$-universal secret sharing (USS) schemes, then there exists $t'$ such that $t'(n) = O(t(n))$ and $\mathcal {C} \subseteq \mathbf {DSPACE}(t'(n))$.

Sketch of Proof

Suppose (S, R) is a t-semi-efficient $(\epsilon , \delta )$ USS scheme for the class $\mathcal {C}$. Theorem 33 follows from applying Lemma 34 to each language $L\in \mathcal {C}$, using the fact that by definition, $(S(L, 1^n, \cdot ), R(L, 1^n, \cdot , \cdot ))$ is an $(\epsilon , \delta )$-secret sharing scheme for $A_{L,n}$ where the sharing algorithm runs in time t(n).

In particular, Theorem 33 implies that if $\mathbf {P}$ had a t-semi-efficient USS scheme, then it would be contained in $\mathbf {DSPACE}(t(n))$ for some polynomial t(n).

Lemma 34

Let, for all n, $1 - 3\epsilon (n) > 3\delta (n)$. If, for some language L, there is an $(\epsilon , \delta )$-secret sharing scheme $(S, R)$ for $A_{L,n}$ for all n, where $S$ runs in time t(n), then $L \in \mathbf {DSPACE}(t'(n))$, where $t'(n) = O(t(n))$.

The proof below is adapted from that of a more general statement from [13].

Proof

We start by using Theorem 22 to recognize the existence of an $(\epsilon ', \delta ')$-SIP (P, V) for L where V runs in time t(n), where $\epsilon ' = 3\epsilon$ and $\delta ' = 3\delta$ (the constant 3 comes out of the proof of Theorem 22), and we have $1 - \epsilon '(n) > \delta '(n)$.

In order to decide whether $x\in L$, it is sufficient to determine whether any $P'$ can guess b given V(x, b) with probability $\ge (1-\epsilon '(|x|))$ or only $\le (1/2 + \delta '(|x|)/2)$. This is equivalent to whether d(V(x, 0), V(x, 1)) is $\ge (1 - \epsilon (|x|))$ or $\le \delta (|x|)$. But d(V(x, 0), V(x, 1)) itself can be computed in space O(t(|x|)) as follows.

First, for any v of length at most t(|x|), ${\text{ Pr }_{r}\left[ V(x,b;r) = v\right] }$ can be computed by iterating over the possible values of r – note that $|r| \le t(|x|)$– and simulating V to see if it outputs v, and counting the number of r’s for which it does. This requires only O(t(|x|)) space because V can be simulated in this much space, and the count of r’s is at most $2^{t(|x|)}$.

So for each v, we can also compute

$$p(v) := |{\text{ Pr }_{r}\left[ V(x,0;r) = v\right] } - {\text{ Pr }_{r}\left[ V(x,1;r) = v\right] }|$$

in O(t(|x|)) space. What we need is the sum $\left( \sum _{v: |v| \le t(|x|)}p(v)\right)$. To compute this, we simply iterate over all the v’s, storing at the end of each iteration only the sum $\left( \sum _{v': v'\le v} p(v)\right)$. As each $p(v) \ge 2^{-t(|x|)}$, and the cumulative sum is at most 1, this adds at most O(t(|x|)) space to what is needed for each iteration. Hence, the entire computation of d(V(x, 0), V(x, 1)) can be done in space $t'(|x|) = O(t(|x|))$, and hence $L\in \mathbf {DSPACE}(t'(n))$.

Appendices

A Proof of Lemma 13

In this section, we restate and prove Lemma 13. This essential lemma extends the privacy properties of PREs to the case of PREs of randomized functions - while the original definition of PREs (for deterministic functions) states that if for some x, $f(x, z_1) = f(x, z_2)$, then $E_{f}(x, z_1)$ and $E_{f}(x, z_2)$ are statistically close, Lemma 13 states that even for a randomized function g, if $g(x, z_1)$ and $g(x, z_2)$ are statistically close, then so are $E_{g}(x, z_1)$ and $E_{g}(x, z_2)$.

Note that PREs for randomized functions are defined as described in Sect. 2: To construct an $(\epsilon , \delta )$-PRE for a randomized function A(x, z; r), simply construct an $(\epsilon , \delta )$-PRE $(E_{A'}, D_{A'})$ for the deterministic function $A'(x,(z,r)) = A(x,z;r)$, and let $E_{A}(x, z)$ be the random variable $E_{A'}(x, (z,r))$ when r is chosen uniformly at random, and have $D_{A}$ be the same as $D_{A'}$.

Lemma 35

Let A(x, z) be a randomized function, and $(E_{A}, D_{A})$ be an $(\epsilon , \delta )$-PRE of A as described above. Then, for any x and any $z_1, z_2$:

$$\begin{aligned} d(A(x, z_1), A(x, z_2)) \le \delta ' \Rightarrow d(E_{A}(x, z_1), E_{A}(x, z_2)) \le \delta (|x|) + \delta ' \end{aligned}$$

Proof

As above, consider the deterministic function $A'(x, (z, r)) = A(x, z;r)$. By definition, $d(E_{A}(x, z_1), E_{A}(x, z_2)) = d(E_{A'}(x,(z_1,r)), E_{A'}(x,(z_2,r)))$, which is given by:

$$\begin{aligned} \sum _{\hat{v}} \left| {\text {Pr}\left[ E_{A'}(x,(z_1,r)) = \hat{v}\right] } - {\text {Pr}\left[ E_{A'}(x,(z_2,r)) = \hat{v}\right] } \right| \end{aligned}$$

where r is distributed uniformly over its domain. We wish to prove that this expression is small. From the privacy of PREs, we have promises on the behaviour of $E_{A'}$ on inputs for which $A'$ has the same output value. Towards exploiting this, we expand the above expression, conditioning on possible values of $A'$ to get:

$$\begin{aligned} \sum _{\hat{v}} \left| \sum _v {\text {Pr}\left[ A'(x,(z_1,r)) = v\right] } {\text {Pr}\left[ E_{A'}(x,(z_1,r)) = \hat{v} \Big | A'(x,(z_1,r)) = v\right] }\right. \\ \ \ \ \ \left. - \sum _v {\text {Pr}\left[ A'(x,(z_2,r)) = v\right] } {\text {Pr}\left[ E_{A'}(x,(z_2,r)) = \hat{v} \Big | A'(x,(z_2,r)) = v\right] } \right| \end{aligned}$$

For the same reason - so that we may compare $E_{A'}$ on points where $A'$ has the same output value - we add and subtract $\left( \sum _v {\text {Pr}\left[ A'(x,(z_1,r)) = v\right] }\right)$ to the factor in the second term above and use the triangle inequality to say that what we have is at most:

$$\begin{aligned}&\sum _v {\text {Pr}\left[ A'(x,(z_1,r)) = v\right] } \Big ( \sum _{\hat{v}} \left| {\text {Pr}\left[ E_{A'}(x,(z_1,r)) = \hat{v}\Big | A'(x,(z_1,r)) = v\right] } \right. \\&\left. - {\text {Pr}\left[ E_{A'}(x,(z_2,r)) = \hat{v} \Big | A'(x,(z_2,r)) = v\right] } \right| \Big ) \\&+ \sum _v \sum _{\hat{v}}{\text {Pr}\left[ E_{A}(x,(z_2,r)) = \hat{v} \Big | A(x,(z_2,r)) = v\right] } \cdot \\&\left| {\text {Pr}\left[ A(x,(z_1,r)) = v\right] } - {\text {Pr}\left[ A(x,(z_2,r)) = v\right] } \right| \\ \end{aligned}$$

The first summand above is a convex combination of several terms, each of which is at most $\delta (|x|)$ by the privacy guarantee of $E_{A'}$ (as each of these terms is some convex combination of the distance between $E_{A'}$ on input values for which $A'$ produces the same output). The second summand is simply equal to $d(A'(x, z_1), A'(x, z_2)) = \delta '$. Hence the whole thing is at most $(\delta (|x|) + \delta ')$, which is what we wanted to prove.

B A Refined Completeness Theorem for ${{\mathbf {SZK}}_{\mathbf {L}}}$

In this section, we complete the proof sketch of Theorem 20. In order to do so, we shall first demonstrate Lemma 36.

Lemma 36

([28]). There exist negligible functions $\epsilon (n), \delta (n) = n^{-\omega (1)}$ such that every language L in $\mathbf {SZK}_{\mathbf {L}}$ reduces to $(\epsilon , \delta )$-$SD_L$. Furthermore, there is a logspace program $D_L$ such that, if an instance x is mapped to the instance $(C_0, C_1)$ by the above reduction, $D_L(b,x,r) = C_b(r)$.

Given $D_L$ from Lemma 36 for a language $L\in \mathbf {SZK}_{\mathbf {L}}$, we can prove Theorem 20 by constructing a special interactive proof (P, V) for L as follows:

• $V(x, b; r) = D_L(b, x, r)$

• P(x, m) outputs 0 if ${\text {Pr}\left[ D_L(0, x, r) = m\right] } > {\text {Pr}\left[ D(1, x, r) = m\right] }$, and 1 otherwise.

Note that the above is an $(\epsilon /2, \delta /2)$-SIP proof for L where the verifier can be computed in logspace.

We shall now sketch a proof of Lemma 36, for which we shall need the following amplification lemma for statistical distance of distributions.

Lemma 37

(Polarization Lemma, [28]). Let $\alpha , \beta \in [0,1]$ be constants such that $\alpha ^2 > \beta$. Given two logspace machines $X_0, X_1: \{0,1\}^n \rightarrow \{0,1\}^m$, there are logspace machines $Y_0, Y_1: \{0,1\}^{n'} \rightarrow \{0,1\}^{m'}$ (where $n'$, $m'$ grow polynomially with n, m) that use $X_0, X_1$ only as blackboxes such that:

$$\begin{aligned} d(X_0, X_1) \ge \alpha&\Rightarrow d(Y_0, Y_1) \ge 1 - 2^{-n'}\\ d(X_0, X_1) \le \beta&\Rightarrow d(Y_0, Y_1) \le 2^{-n'}\\ \end{aligned}$$

Both the above lemmas are not stated in precisely this manner in either [28] or [31], but these extensions follow easily from the proofs of statements that are indeed made in these works.

Sketch of Proof

of Lemma 36 (The lemma follows directly from the proof of completeness of SD for SZK presented in [31], noticing that the reduction from any $L\in SZK$ to SD, outlined below, leads to logspace machines if one starts with an $L\in SZKL$, as L has a logspace simulator.)

Suppose L has an SZK proof (P, V) in which, on inputs of length n, the total communication is t(n) over v(n) messages, V uses r(n) bits of randomness, and there is a logspace simulator S that achieves deviation $\mu (n) \le 1/(Ct(n)^2)$, for some constant C to be determined. Let $S_i$ denote the distribution of the output of S (on a given input) truncated to the first i rounds. We assume, without loss of generality, that the prover speaks first, messages alternate, and that the last message of the verifier consists of all its randomness. We shall describe now distributions that witness the reduction of L to $SD_L$. Proofs and further details may be found in [31], Chap. 3.

Define the following distributions:

$$\begin{aligned} X&: S_2 \otimes S_4 \otimes \cdots \otimes S_{2v}\\ Y_1&: S_1 \otimes S_3 \otimes \cdots \otimes S_{2v-1} \otimes U_{r-7}\\ Y_2&:\text { Run } S\ 8ln(tv+2) \text { times, and if the transcript is rejecting in}\\ {}&\text {\ \ \ \ a majority of these, output }U_{tv+2}\text {, else output nothing.}\\ Y&: Y_1 \otimes Y_2 \end{aligned}$$

We may arrange, again without loss of generality, for a given input length n of L, for both X and Y to use at most $m'$ bits of randomness and have output length $n'$. Let $q = 9\,km'^2$ for some constant k to be determined later.

Let $X'' = \otimes ^q X$ and $Y'' = \otimes ^q Y$, and $m''$ and $n''$ be the (upper bound on) number of bits of randomness used and output length of $X''$ and $Y''$. Let $H = H_{m''+n'', m''}$ be a family of 2-universal hash functions from $\{0,1\}^{m''+n''} \rightarrow \{0,1\}^{m''}$. Define now the following distributions:

$$\begin{aligned} A&:\text { Choose }r\leftarrow \{0,1\}^{m''}, h\leftarrow H, y\leftarrow Y\text {, let }x = X''(r)\text {. Output }(x, h, h(r,y)).\\ B&:\text { Choose }x\leftarrow X'', h\leftarrow H, z\leftarrow \{0,1\}^{m''}\text {. Output }(x, h, z). \end{aligned}$$

As proven in [31], if $x\in L$, then $d(A,B) \ge 1 - O(2^{-k})$, and if $x\notin L$, $d(A,B) \le 2^{-\varOmega (k)}$. Note that all steps involved so far, including evaluating the hash function, may be done in logspace, meaning that there is a randomised logspace program that on input x can sample A (or B).

This lets us apply Lemma 37 to (A, B) to get distributions $(A',B')$ which are still sampleable in logspace given x (as they are logspace programs that only use the samplers for A and B as blackboxes), and are such that if $x\in L$, $d(A',B') \ge 1 - 2^{-r}$ and if $x\notin L$, $d(A',B') \le 2^{-r}$, where r (a polynomial in |x| and $\varOmega (|x|)$) is the amount of randomness used by the sampler for $A'$ (or $B'$). This gives us the reduction to $SD_L$.

We now define $D_L$ to simply emulate the above steps. On input (b, x, r), where |r| is a function of |x| resulting from above operations ($D_L$ is undefined on input lengths that do not obey this relation between |x| and |r|), if $b=0$, $D_L$ runs the logspace sampler for $A'$ with input x and randomness r, and simliarly the sampler for $B'$ if $b=1$. Note that $D_L$ is still in logspace, and that if $x\in L$, $d(D_L(0,x,r), D_L(1,x,r)) \ge 1 - 2^{-|x|}$, and if $x\notin L$, $d(D_L(0,x,r), D_L(1,x,r)) \le 2^{-|x|}$.    $\square$