Alternative definition of secret sharing using entropy

Question

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.

Answer 1

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. :)