# Alternative definition of secret sharing using entropy

I ame reading the paper "Secret-Sharing schemes: A survey" by Amos Beimel. Here there are two definitions of secret sharing. The first one states:\ A distribution scheme $$\langle \Pi,\mu \rangle$$ with domain of secrets $$S$$ is a secret-sharing scheme realizing an access structure $$\mathscr{A}$$ if the following holds:

• Correctness: the secret $$s$$ can be reconstructed by any authorized set of parties. That is, $$\forall B \in \mathscr{A}$$ there exists a $$Recon_B$$ algorithm such that $$\Pr[Recon_B(\Pi(s,r)_B) = s] = 1 \qquad \forall s \in S$$ where $$\Pi(s,r)_B$$ denotes a restriction of $$\Pi(s,r)$$ to its $$B$$ entries.
• Perfect Privacy: every unauthorized set cannot learn anything about the secret from their shares. Formally, $$\forall\,T \notin \mathscr{A}, \forall\,a,b \in S$$ and for every vector of shares $$\langle s_j\rangle_{P_j \in T}$$: $$\Pr[\,\Pi(a,r)_T = \langle s_j\rangle_{P_j \in T}\,] = \Pr[\,\Pi(b,r)_T = \langle s_j\rangle_{P_j \in T}\,].$$

The second definition uses the notion of entropy and states: A distribution scheme $$\langle \Pi,\mu \rangle$$ is a secret-sharing scheme realizing an access structure $$\mathscr{A}$$ if the following conditions hold:

• Correctness: For every set $$B \in \mathscr{A}$$, $$\begin{equation*} H(S|S_B) = 0. \end{equation*}$$
• Perfect Privacy: For every unauthorized set $$T \notin \mathscr{A}$$, $$\begin{equation*} H(S|S_T) = H(S). \end{equation*}$$

What I am trying to do is prove that the two definitions are equivalent.

• To help better understand the question, it will be helpful to fix the notation a bit. Currently, the same symbols are used to denote sets and random variables. Aug 20 at 19:17
• Here are a couple of pointers to get you started. Every probability distribution that has entropy 0 must satisfy $\Pr[S=s]=1$ for some $s$ and $\Pr[S=s']=0$ for $s\neq s'$. If $A$ and $B$ are two random variables such that $H(A|B)=0$, then when we condition on $B$, $A$ becomes deterministic, so there exists a function that computes $A$ given $B$. If two random variables $A$ and $B$ are independent, then $H(A|B)=H(A)$. Aug 25 at 19:49

Work in progress...

Intuitively, the definitions are equivalent, given that entropy is a measure of uncertainty or knowledge we have about something. Conditional entropy $$H(X|Y)$$ measures how much we know about $$X$$ after we know $$Y$$.

Notation: $$\Pr^X[\cdot]$$ denotes a probability expression over the random choices of the random variable $$X$$. An alternative formulation of entropy $$H(X) = \mathbb E[-\log \Pr^X[X=x]]$$.

Let's now show the equivalence of the two definitions.

Correctness: Intuitively, if the conditional entropy is zero, then $$Y$$ completely determines $$X$$. For a correct secret-sharing scheme, authorized sets should be able to reconstruct the secret (with probability 1). Which also means shares fully define the secret. Concretely, let $$s \in \mathcal{S}$$ be a secret value and $$r \in \mathcal{R}$$ be some randomness; $$s_B = \Pi_B(s,r)$$ be the share associated with the set $$B$$. We know that $$Pr^R[Recon_B(\Pi(s,r)_B) = s] = 1 \qquad \forall s \in S.$$

The probability is over the random choices of the random variable $$R$$ corresponding to the randomness. To link the two definitions, we'll need to introduce a random variable $$S$$ capturing the distribution of secret values (note that the first definition isn't concerned with the distribution of the secret values). So if we defined as the random variable $$S_B = (\Pi(S,R)_B)$$; Then we have: $$\Pr^{R,S}[Recon_B(\Pi(s,r)_B) = s] = \begin{cases} 1 & \text{if } S = s \\ 0 & \text{otherwise} \end{cases}.$$ In the expression above, the probability distribution is over the choice of $$R$$ and $$S$$; which can also be simply stated as $$S = Recon_B(S_B)$$. We can now show the result.

$$H(S|S_B) = \mathbb{E} [-\log\Pr^{S,R}[S | S_B]] = \\ \mathbb{E} [-\log\Pr^{S,R}[Recon_B(S_B) | S_B]] = \mathbb{E} [-\log 1] = 0.$$

Privacy: Unauthorized sets should not reconstruct the secret. This can also be stated as shares from unauthorized sets are statically independent of the secret; alternatively, the entropy expression in the definition. :)

• Thank you for your answer. I got the idea of the proof but cannot prove it formally Aug 22 at 15:35
• @Cristie, I will try and flesh out the details some more soon. Aug 22 at 15:38
• Actually @Cristie, it would be helpful to know where in the formalization of the proof you're stuck to help make the answer as relevant as possible, i.e., : avoid talking about things you know already. Aug 22 at 19:26