2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Aug 20, 2023 at 19:17
  • $\begingroup$ 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)$. $\endgroup$
    – lamontap
    Aug 25, 2023 at 19:49

1 Answer 1

0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. I got the idea of the proof but cannot prove it formally $\endgroup$
    – Cristie
    Aug 22, 2023 at 15:35
  • $\begingroup$ @Cristie, I will try and flesh out the details some more soon. $\endgroup$ Aug 22, 2023 at 15:38
  • $\begingroup$ 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. $\endgroup$ Aug 22, 2023 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.