Score:1

Alternative definition of secret sharing using entropy

hm flag

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.

Marc Ilunga avatar
tr flag
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.
lamontap avatar
cn flag
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)$.
Score:0
tr flag

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$.

Correctness: A conditional entropy of zero means $Y$ fully defines $X$. For a correct secret sharing schemes, authorized sets should be able to reconstruct the secret (with probability 1). Which also means, the secret is fully defined by shares.

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

Cristie avatar
hm flag
Thank you for your answer. I got the idea of the proof but cannot prove it formally
Marc Ilunga avatar
tr flag
@Cristie, I will try and flesh out the details some more soon.
Marc Ilunga avatar
tr flag
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.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.