CSE5313 Coding and information theory for data science (Lecture 18)

Secret sharing

The president and the vice president must both consent to a nuclear missile launch.

We would like to share the nuclear code such that:

• $Share1, Share2 \mapsto Nuclear Code$
• $Share1 \not\mapsto Nuclear Code$
• $Share2 \not\mapsto Nuclear Code$
• $Share1 \not\mapsto Share2$
• $Share2 \not\mapsto Share1$

In other words:

• The two shares are everything.
• One share is nothing.

Formalize the notion of secret sharing

Problem setting

A dealer is given a secret $m$ chosen from an arbitrary distribution $M$.

The dealer creates $n$ shares $s_1, s_2, \cdots, s_n$ and send to $n$ parties.

Two privacy parameters: $t,z\in \mathbb{N}$ $z<t$.

Requirements:

For $\mathcal{A}\subseteq[n]$ denote $S_\mathcal{A} = \{s_i:i\in \mathcal{A}\}$.

• Decodability: Any set of $t$ shares can reconstruct the secret.
  • $H(M|S_\mathcal{T}) = 0$ for all $\mathcal{T}\subseteq[n]$ with $|\mathcal{T}|\geq t$.
• Security: Any set of $z$ shares reveals no information about the secret.
  • $I(M;S_\mathcal{Z}) = 0$ for all $\mathcal{Z}\subseteq[n]$ with $|\mathcal{Z}|\leq z$.

This is called $(n,z,t)$-secret sharing scheme.

Interpretation

• $\mathcal{Z} \subseteq [n]$, $|\mathcal{Z}| \leq z$ is a corrupted set of parties.
• An adversary which corrupts at most $z$ parties cannot infer anything about the secret.

Applications

• Secure distributed storage.
  • Any $\leq z$ hacked servers reveal nothing about the data.
• Secure distributed computing with a central server (e.g., federated learning).
  • Any $\leq z$ corrupted computation nodes know nothing about the data.
• Secure multiparty computing (decentralized).
  • Any $\leq z$ corrupted parties cannot know the inputs of other parties.

Scheme 1: Shamir secret sharing scheme

Parameters $n,t$, and $z=t-1$.

Fix $\mathbb{F}_q$, $q>n$ and distinct points $\alpha_1, \alpha_2, \cdots, \alpha_n \in \mathbb{F}_q\setminus \{0\}$. (public, known to all).

Given $m\sim M$ the dealer:

• Choose $r_1, r_2, \cdots, r_z \sim U_1, U_2, \cdots, U_z$ (uniformly random from $\mathbb{F}_q$).
• Defines $p\in \mathbb{F}_q[x]$ by $p(x) = m + r_1x + r_2x^2 + \cdots + r_zx^z$.
• Send share $s_i = p(\alpha_i)$ to party $i$.

Theorem valid encoding scheme

This is an $(n,t-1,t)$-secret sharing scheme.

Decodability:

• $\deg p=t-1$, any $t$ shares can reconstruct $p$ by Lagrange interpolation.

Privacy:

Need to show that $I(M;S_\mathcal{Z})=0$ for all $\mathcal{Z}\subseteq[n]$ with $|\mathcal{Z}|=z$.

that is equivalent to show that $M$ and $s_\mathcal{Z}$ are independent for all $\mathcal{Z}\subseteq[n]$ with $|\mathcal{Z}|=z$.

Scheme 2: Ramp secret sharing scheme (McEliece-Sarwate scheme)

• Any $z$ know nothing
• Any $t$ knows everything
• Partial knowledge for $z<s<t$

Parameters $n,t$, and $z<t$.

Fix $\mathbb{F}_q$, $q>n$ and distinct points $\alpha_1, \alpha_2, \cdots, \alpha_n \in \mathbb{F}_q\setminus \{0\}$. (public, known to all)

Given $m_1, m_2, \cdots, m_n \sim M$, the dealer:

• Choose $r_1, r_2, \cdots, r_z \sim U_1, U_2, \cdots, U_z$ (uniformly random from $\mathbb{F}_q$).
• Defines $p(x) = m_1+m_2x + \cdots + m_{t-z}x^{t-z-1} + r_1x^{t-z} + r_2x^{t-z+1} + \cdots + r_zx^{t-1}$.
• Send share $s_i = p(\alpha_i)$ to party $i$.

Decodability

Similar to Shamir scheme, any $t$ shares can reconstruct $p$ by Lagrange interpolation.

Privacy

Similar to the proof of Shamir, exactly one value of $U_1, \cdots, U_z$ is possible!

$\operatorname{Pr}(s_\mathcal{Z}|m_1, \cdots, m_{t-z}) = \operatorname{Pr}(U_1, \cdots, U_z) = the above = 1/q^z$

($U_i$‘s are uniform and independent).

Conclude similarly by the law of total probability.

$\operatorname{Pr}(s_\mathcal{Z}|m_1, \cdots, m_{t-z}) = \operatorname{Pr}(s_\mathcal{Z}) \implies I(S_\mathcal{Z}; M_1, \cdots, M_{t-z}) = 0$.

Conditional mutual information

The dealer needs to communicate the shares to the parties.

Assumed: There exists a noiseless communication channel between the dealer and every party.

From previous lecture:

• The optimal number of bits for communicating $s_i$ (i’th share) to the i’th party is $H(s_i)$.
• Q: What is $H(s_i|M)$?

Tools:

• Conditional mutual information.
• Chain rule for mutual information.

Definition of conditional mutual information

The conditional mutual information $I(X;Y|Z)$ of $X$ and $Y$ given $Z$ is defined as:

where $H(X|Y,Z)$ is the conditional entropy of $X$ given $Y$ and $Z$.

The chain rule of mutual information

Conditioning reduces entropy.

Lower bound for communicating secret

Consider the Shamir scheme ($z = t - 1$, one message).

Q: What is $H(s_i)$ with respect to $H(M)$ ? A: Fix any $\mathcal{T} = \{i_1, \cdots, i_t\} \subseteq [n]$ of size $t$, and let $\mathcal{Z} = \{i_1, \cdots, i_{t-1}\}$.

So the bits used for sharing the secret is at least the bits of actual secret.

In Shamir we saw: $H(s_i) \geq H(M)$.

• If $M$ is uniform (standard assumption), then Shamir achieves this bound with equality.
• In ramp secret sharing we have $H(s_i) \geq \frac{1}{t-z}H(M_1, \cdots, M_{t-z})$ (similar proof).
• Also optimal if $M$ is uniform.

Downloading file with lower bandwidth from more servers

link to paper