Notes on Leakage Resilient Secret Sharing 1

Posted on 2021-10-25 In Course Note Disqus:

All the info comes from [BDIR19] and [MPSW20]

Let $\mathbb{F}$ be a finite field, a linear code $C$ over $\mathbb{F}$ of length $n+1$ and rank $k + 1$ is a $(k+1)$-dimension vector subspace of $\mathbb{F}^{n+1}$, referred to as $[n+1,k+1]_{\mathbb{F}}$ code.

Generator matrix $G\in \mathbb{F}^{(k+1)\times (n+1)}$ of $[n+1,k+1]_\mathbb{F}$ linear code $C$ ensures that $\forall c \in C$ exists $\vec{\boldsymbol{a}}\in \mathbb{F}^{k+1}$ such that $c \equiv\vec{\boldsymbol{a}}\cdot G$.

The rowspan of $G$ is represented as $\langle G \rangle$, it is also the code generated by $G$. In standard form $G = [I_{k+1}|P]$ where $P$ is the parity check matrix.

Write $C \subseteq \mathbb{F}^{n+1}$ be the linear code generated by $G$, the dual code of $C$ is written as $C^\bot \subseteq \mathbb{F}^{n+1}$, which is the set of elements in $\mathbb{F}^{n+1}$ that are orthogonal to every element in $C$. $\forall c’ \in C^\bot, \langle c’, c\rangle \equiv \boldsymbol{0}$.

The dual code of a $[n+1, k+1]_\mathbb{F}$ code is a $[n+1,n-k]_\mathbb{F}$ code. The generator matrix $H$ for dual code of $[n+1,k+1]_\mathbb{F}$ code $C$ satisfies $H=[-P^\top | I_{n-k}]$.

Consider $GH^\top = [I_{k+1} | P] \cdot [-P^\top | I_{n-k}]^\top = -P + P = \boldsymbol{0}$.

Maximum Distance Separable Code

The weight of a codeword is the number of non-zero element in a non-zero codeword.

The distance of a linear code is the minimum weight of a non-zero codeword.

A $[n,k]_\mathbb{F}$ code is a maximum distance separable (MDS) code if its distance is $n-k+1$.

The dual code of $[n,k]_\mathbb{F}$ MDS code is a $[n,n-k]_\mathbb{F}$ MDS code.

For a MDS code generated by $G \in \mathbb{F}^{k \times n}$, if $G = [I_k | R]$ where $R$ is a random matrix of $k \times (n-k)$ size over $\mathbb{F}$. Let row indices and column indices be $\set{1,\ldots,k}$ and $\set{1,\ldots,n}$.

For $i \in \set{k, \ldots,n}$ and define $\mathcal{E}_i$ be the event that $G_{\ast,\set{1,\ldots,i}}$ is full rank, and let $\neg \mathcal{E}_i$ be the complement. Then we have $\Pr[\neg \mathcal{E}_i | \mathcal{E}_{i - 1}] \le \binom{i - 1}{k - 1} / p$.

Given $G_{\ast,\set{1,\ldots,i - 1}}$ is full rank, then $G_{\ast,\set{1,\ldots,i}}$ is full rank if and only if $\forall S \subseteq \set{1,\ldots,i - 1}$ of $|S| = k - 1$, we have $G_{\ast,S\cup\set{i}}$ is full rank, which also means $G_{\ast,i}$ do not fall in column span of $G_{\ast,S}$.

The chance of $G_{\ast,i}$ fall into column span of $G_{\ast,S}$ is $p^{k - 1} / p^k = 1 / p$. Given choice of $|S| = \binom{i - 1}{k - 1}$, by union bound we have $\Pr[\neg \mathcal{E}_i | \mathcal{E}_{i - 1}] \le \binom{i - 1}{k - 1} / p$.

For $\Pr[\neg\mathcal{E}_n]$, we have
$$
\begin{aligned}
\Pr[\neg \mathcal{E}_n] &= \Pr[\neg \mathcal{E}_{k + 1} | \mathcal{E}_k] + \Pr[\neg \mathcal{E}_{k + 2} | \mathcal{E}_{k+1}] + \cdots + \Pr[\neg \mathcal{E}_{n} | \mathcal{E}_{n-1}]\newline
&\le \binom{k}{k - 1} / p + \binom{k + 1}{k - 1} / p + \cdots + \binom{n}{k - 1} / p\newline
&\le \binom{k}{n} / p
\end{aligned}
$$

Let $C \subseteq \mathbb{F}^{n+1}$ be a code, and $s \in \mathbb{F}$ be a secret. Let generator matrix be $G^+ \in \mathbb{F}^{(k+1)\times (n+1)}$ and we have
$$
\lbrace\vec{\boldsymbol{y}}: \vec{\boldsymbol{x}} \in \mathbb{F}^{k+1}, \vec{\boldsymbol{y}} := \vec{\boldsymbol{x}} \cdot G^+ \rbrace\subseteq \mathbb{F}^{n+1}
$$
The secret sharing scheme picks independent and uniformly random $r_1,\ldots,r_k \in \mathbb{F}$ and let
$$
(y_0,\ldots,y_n) := (s,r_1, \ldots,r_k)\cdot G^+
$$
We write $G \in \mathbb{F}^{k\times n}$ as $G^+_{\set{1 \ldots k} \times \set{1 \ldots n}}$, and $\langle G \rangle$ forms a $[n,k]_\mathbb{F}$ code.

Realizing that secret $s$ forms the affine space $s \cdot \vec{\boldsymbol{v}} + \langle G \rangle$, where $\vec{\boldsymbol{v}} = G^+_{0,\set{1 \ldots n}}$.

Suppose parties $i_1,\ldots,i_t \in \set{1,\ldots,n}$ reconstruct the secret themselves with the share $s_1,\ldots,s_t$.

Let $G^+_{\ast,i_1},\ldots,G^+_{\ast,i_t} \in \mathbb{F}^{(k+1)\times 1}$ representing the columns indexed by $i_1,\ldots,i_t \in \set{1,\ldots,n}$ respectively.

If $G^+_{\ast,i_0}$ does not lie in the span of $\set{G^+_{\ast,i_1},\ldots,G^+_{\ast, i_t}}$, then the secret is perfectly hidden. Otherwise, then the secret can be reconstructed.

The (punctured) Reed-Solomon code of rank $(k+1)$ and evaluation places $\vec{X} = (X_1,\ldots,X_n) \in (\mathbb{F}^\ast)^n$, where $i \neq j$ implies $X_i \neq X_j$.

Let $f(X)$ be the unique polynomial with degree $\leq k$ such that $f(0) = y_0$ and $\forall i \in \set{1, \ldots, k}, f(X_i) = y_i$ for $y_0, \ldots,y_k \in \mathbb{F}$, define $c_{k+1} = f(X_{k + 1}),\ldots,c_n = f(X_n)$.

Then the set of all codeword $(y_0,y_1,\ldots,y_k,c_{k+1},\ldots,c_n)\in \mathbb{F}^n$ is a $[n+1,k+1]_{\mathbb{F}}$ code.

Furthermore, the mapping
$$
(y_0,y_1,\ldots,y_k)\mapsto(y_0,y_1,\ldots,y_k,c_{k+1},\ldots,c_n)
$$
is linear and a generator matrix in standard form establishes the mapping.

We can first consider passing coefficients of polynomial $\vec{f}: (f_0,\ldots,f_k)$ into a matrix $H$ of form
$$
H = \left[ \begin{matrix}1 &\ldots& 1 \newline X_0 & \ldots & X_k \newline \vdots & \ddots & \vdots \newline X_0^k & \ldots & X_k^{k} \end{matrix} \right]
$$
such that we can have $(y_0,\ldots,y_k) \gets \vec{f}\cdot H$. Then we prepare $H’$ to be the evaluation point matrix with degree precomputed as follows
$$
H’ = \left[ \begin{matrix}1 &\ldots& 1 &\ldots &1 \newline X_0 & \ldots & X_k & \ldots & X_n \newline \vdots & \ddots & \vdots & \ddots & \vdots \newline X_0^k & \ldots & X_k^k & \ldots & X_n^k \end{matrix} \right]
$$
and compute $G = H^{-1} \cdot H’$, in this way the left side of $G$ is $I_{k+1}$ and right side is a parity-check matrix.

Shamir secret sharing is the Massey SS corresponding to (punctured) RS code.

Suppose $f(0) = s = y_0, \forall i \in \set{1,\ldots,k}, f(X_i) = r_i$. Define secret shares $\set{s_i}_{i \in \set{1,\ldots,n}}$ where $s_i = f(X_i)$.

Fourier Series and Tricks

Let $\mathbb{F}$ be a field of order prime $p$, let $z \in \mathbb{C}$ where $\mathbb{C}$ be complex field, and let $\overline{z}$ be the complex conjugate of $z$. For function $f,g:\mathbb{F} \to \mathbb{C}$, the inner product is defined as
$$
\langle f, g\rangle = \frac{1}{p}\sum_{x \in \mathbb{F}} f(x) \overline{g(x)}
$$
Define $\omega := e^{2\pi i / p}$ and let function $\chi_\alpha(x) := \omega^{\alpha x}$. For $\alpha\in \mathbb{F}$ we define Fourier coefficient $\hat{f}(\alpha) := \langle f, \chi_\alpha\rangle$. Define $\ell^2$ norm of $\hat{f}$ as
$$
|| \hat{f} ||_2 := \sqrt{\sum_{\alpha \in \mathbb{F}} |\hat{f}(\alpha)|^2}
$$

Fourier Inversion Formula

$$
\begin{aligned}
\sum_{\alpha \in \mathbb{F}} \hat{f}(\alpha) \cdot \omega^{\alpha x} &= \sum_{\alpha \in \mathbb{F}} \Big( \frac{1}{p} \sum_{x’ \in \mathbb{F}} f(x’)\cdot \omega^{-\alpha x’}\Big)\cdot \omega^{\alpha x}\newline
&= \frac{1}{p} \sum_{\alpha \in \mathbb{F}}\Big( \sum_{x’\in\mathbb{F}} f(x’) \cdot \omega^{\alpha(x - x’)} \Big)\newline
&= \frac{1}{p} \sum_{x’\in\mathbb{F}}\Big( \sum_{\alpha \in \mathbb{F}} f(x’) \cdot \omega^{\alpha(x - x’)} \Big)\newline
&= \frac{1}{p}\cdot p \cdot f(x) = f(x)
\end{aligned}
$$

Parseval’s Identity

$$
\begin{aligned}
\frac{1}{p}\sum_{x \in \mathbb{F}} |f(x)|^2 &= \frac{1}{p}\sum_{x \in \mathbb{F}} \Big( \sum_{\alpha \in \mathbb{F}} \hat{f}(\alpha) \cdot \omega^{\alpha x} \Big) \cdot \Big( \overline{\sum_{\alpha \in \mathbb{F}} \hat{f}(\alpha) \cdot \omega^{\alpha x}} \Big)\newline
&= \frac{1}{p}\sum_{x \in \mathbb{F}} \Big( \sum_{\alpha \in \mathbb{F}} \hat{f}(\alpha) \cdot \omega^{\alpha x} \Big) \cdot \Big( \sum_{\alpha \in \mathbb{F}} \overline{\hat{f}(\alpha)} \cdot \omega^{-\alpha x} \Big)\newline
&= \frac{1}{p} \sum_{x \in \mathbb{F}}\Big( \sum_{\alpha \in \mathbb{F}} \hat{f}(\alpha)\cdot \overline{\hat{f}(\alpha)} \Big)\newline
&= \sum_{\alpha\in \mathbb{F}}|\hat{f}(\alpha)|^2
\end{aligned}
$$

Poisson Summation Formula

Let $C \subseteq \mathbb{F}^n$ be a linear code with dual code $C^\bot \in \mathbb{F}^n$. $\forall i \in \set{1,\ldots,n}$, $f_i:\mathbb{F}\to\mathbb{C}$ be an arbitrary function. Then we have
$$
\underset{\vec{\boldsymbol{x}} \gets C}{\mathbb{E}} \left[\prod^n_{i = 1} f_i(x_i)\right] = \underset{\vec{\boldsymbol{x}} \gets C}{\mathbb{E}} \left[\prod^n_{i = 1} \left(\sum_{\alpha_i \in \mathbb{F}} \hat{f_i}(\alpha_i) \cdot \omega^{\alpha_i x_i}\right)\right]
$$
Then consider multiplication of $\prod^n_{i = 1} \left(\sum_{\alpha_i \in \mathbb{F}} \hat{f_i}(\alpha_i) \cdot \omega^{\alpha_i x_i}\right)$, which is the sum of products of permutations of $\left( \hat{f_1}(\sigma_1)\cdot \omega^{\sigma_1 x}, \ldots, \hat{f_n}(\sigma_n)\cdot \omega^{\sigma_n x} \right)$, then
$$
\begin{aligned}
\underset{\vec{\boldsymbol{x}} \gets C}{\mathbb{E}} \left[\prod^n_{i = 1} \left(\sum_{\alpha_i \in \mathbb{F}} \hat{f_i}(\alpha_i) \cdot \omega^{\alpha_i x_i}\right)\right] &= \underset{\vec{\boldsymbol{x}} \gets C}{\mathbb{E}} \left[\sum_{\vec{\boldsymbol{\alpha}} \in \mathbb{F}^n} \left( \prod^n_{i = 1} \hat{f_i}(\alpha_i) \cdot \omega^{\alpha_i x_i}\right)\right]\newline
&= \underset{\vec{\boldsymbol{x}} \gets C}{\mathbb{E}} \left[\sum_{\vec{\boldsymbol{\alpha}} \in \mathbb{F}^n} \left( \prod^n_{i = 1} \hat{f_i}(\alpha_i) \right) \cdot \omega^{\langle\vec{\boldsymbol{\alpha}}, \vec{\boldsymbol{x}} \rangle} \right]\newline
&= \sum_{\vec{\boldsymbol{\alpha}} \in \mathbb{F}^n} \left( \prod^n_{i = 1} \hat{f_i}(\alpha_i) \right) \cdot\underset{\vec{\boldsymbol{x}} \gets C}{\mathbb{E}} \left[ \omega^{\langle\vec{\boldsymbol{\alpha}}, \vec{\boldsymbol{x}} \rangle} \right]
\end{aligned}
$$
Since $\langle \vec{\boldsymbol{a}}, \vec{\boldsymbol{x}} \rangle \equiv 0$ when $\vec{\boldsymbol{x}} \in C^\bot$, and $\langle \vec{\boldsymbol{a}}, \vec{\boldsymbol{x}}\rangle$ is uniformly random when $\vec{\boldsymbol{x}} \notin C^\bot$. Thus
$$
\underset{\vec{\boldsymbol{x}} \gets C}{\mathbb{E}} \left[\prod^n_{i = 1} f_i(x_i)\right] = \sum_{\vec{\boldsymbol{\alpha}} \in C^\bot} \prod^n_{i = 1} \hat{f_i}(\alpha_i)
$$

Claim 4.18.1 from BDIR18

First we can use Parseval’s Identity
$$
\begin{aligned}
\sum_{u \in \set{0,1}^m} ||{\hat{\boldsymbol{1}_u}}||_2 &= \sum_{u \in \set{0,1}^m} \sqrt{\sum_{\alpha\in\mathbb{F}}|{\hat{\boldsymbol{1}_u}(\alpha)}|^2} \newline
&= \sum_{u \in \set{0,1}^m} \sqrt{\frac{1}{p}\sum_{x\in\mathbb{F}}|{\boldsymbol{1}_u(x)}|^2}
\end{aligned}
$$
Then we notice that $\frac{1}{p}\sum_{x\in\mathbb{F}}|{\boldsymbol{1}_u(x)}|^2 \equiv \frac{1}{p} \sum_{x \in \mathbb{F}} \boldsymbol{1}_u(x)$, thus we have
$$
\begin{aligned}
\sum_{u \in \set{0,1}^m} ||{\hat{\boldsymbol{1}_u}}||_2 &= \sum_{u \in \set{0,1}^m} \sqrt{\frac{1}{p}\sum_{x\in\mathbb{F}}|{\boldsymbol{1}_u(x)}^2|}\newline
&= \sum_{u\in\set{0,1}^m}\sqrt{\frac{1}{p} \sum_{x\in\mathbb{F}} \boldsymbol{1}_u(x)}\newline
&= \sum_{u\in\set{0,1}^m}\sqrt{\Pr_{x \in \mathbb{F}} \left[f(x) \equiv u\right]}
\end{aligned}
$$
Observing that $\sum_{u \in \set{0,1}^m} \Pr_{x\in\mathbb{F}}\left[ f(x) \equiv u\right] = 1$, we have Cauchy inequality that
$$
\begin{aligned}
\left(\sum_{u \in \set{0,1}^m} ||{\hat{\boldsymbol{1}_u}}||_2\right)^2 &= \left(\sum_{u\in\set{0,1}^m}\sqrt{\Pr_{x \in \mathbb{F}} \left[f(x) \equiv u\right]}\right)^2\newline
&\le \left( \sum_{u\in\set{0,1}^m}\Pr_{x \in \mathbb{F}} \left[f(x) \equiv u\right] \right)^2\cdot 2^m = 2^m
\end{aligned}
$$
Thus we have
$$
\sum_{u \in \set{0,1}^m} ||{\hat{\boldsymbol{1}_u}||}_2 \le 2^{m / 2}
$$

Lemma 4.17.1 from BDIR19

Consider $\sum_{u \in \set{0,1}^m} |\hat{\boldsymbol{1}}_u(0)| = 1$:
$$
\begin{aligned}
\sum_{u \in \set{0,1}^m} |\hat{\boldsymbol{1}}_u(0)| &= \sum_{u \in \set{0,1}^m}|\langle \boldsymbol{1}_u,\chi_0\rangle|\newline
&= \sum_{u\in\set{0,1}^m} \left|\frac{1}{p} \sum_{x\in\mathbb{F}} \boldsymbol{1}_u(x) \right|\newline
&= \sum_{u\in\set{0,1}^m} \Pr_{x \in \mathbb{F}} \left[ f(x) \equiv u \right] = 1
\end{aligned}
$$

Lemma 3.11 from BDIR19

Let $k\in \mathbb{N}$ and let $\zeta_k:[0,k]\to\mathbb{R}_{\ge 0}$ be defined as $\zeta_k = \frac{\sin(x \pi / k)}{\sin(\pi / k)}$ with $\zeta_k(0) = 0$. Let $A \subseteq \mathbb{Z}_k$ of size $t$, and let $\omega = e^{2\pi i / p}$. Let $A^\ast = \set{0,1\ldots,t-1}$, then
$$
\left|\sum_{x\in A} \omega^x\right| \le \left|\sum_{x \in A^\ast} \omega^x\right| = \frac{\sin(\pi t / k)}{\sin(\pi/k)} = \zeta_k(t)
$$
First we show the latter part of the inequality is derived from trigonometry calculation
$$
\left| \sum_{x \in A^\ast} \omega^x \right| = \left| \frac{\omega^t - 1}{\omega - 1} \right| = \left| \frac{2i \cdot \sin(\pi t / k) \cdot e^{i\pi t / k}}{2i \cdot \sin(\pi / k) \cdot e^{i\pi / k}} \right| = \left|\frac{\sin(\pi t / k)}{\sin(\pi / k)}\right|
$$
Then we want to show that the sum is maximum when $A = A^\ast$ for some $A \subseteq Z_k$.

Noticing that for interval $A, B \subseteq Z_k$, if there exists $c \in \mathbb{Z}_k$, we have $\sum_{x \in A} \omega^x = \omega^c \cdot \sum_{x \in B} \omega^x$, then $\left|\sum_{x \in A}\omega^x\right| = \left|\sum_{x \in B}\omega^x\right|$.

For a set $A\subseteq \mathbb{Z}_k$, we can denote $\sum_{x \in A} \omega^x$ to be $\omega^A$ for simplicity.

The inequality is vacuously true when $|A| = 0$ or $|A| = k$. For general case, it is a extremal argument, and we can try to prove with contradiction.

Suppose for a set $A \subseteq \mathbb{Z}_k$ such that $|A| = t$ leads to $\gamma^A$ has the maximum magnitude. Then $|\gamma^A| \ge |\gamma^{A^\ast}| > 0$.

We consider $A’$ be a subset of size $t$ and consisting all the roots of unity most aligned with $\gamma^A$. That is, $\forall a \in A’, b \in \mathbb{Z}_k\backslash A’$, we have $\omega^\alpha\circ \gamma^A \ge \omega^b \circ \gamma^A$.

where $\circ$ is defined as vector dot product on complex (consider $z_1 \circ z_2 = |z_1| |z_2| \cos \theta$ where $\theta$ is the angle between $z_1,z_2$).

If $A = A’$, then the proof is established. Otherwise, pick $a \in A’ \backslash A$ and $b \in A \backslash A’$, and conclude $A’’ = (A \backslash \set{b}) \cup \set{a}$.

Realizing that $|\gamma^{A’’}| = |\gamma^A + (\gamma^a - \gamma^b)|$, also by previous conclusion, $\gamma^a \circ \gamma^A \ge \gamma^b \circ \gamma^A$. Thus $\gamma^A \circ (\gamma^a - \gamma^b) \ge 0$, and thus $|\gamma^{A’’}| \ge |\gamma^A| + |\gamma^a - \gamma^b|$.

In this way, if $A$ is not an interval and $\gamma^A$ is maximum in magnitude leads to a contradiction. Thus $\gamma^A$ is maximum when $A$ is an interval.

Lemma 4.17.2 from BDIR19

For a more general case where $\alpha \neq 0$, consider $\sum_{u \in \set{0,1}^m}|\hat{\boldsymbol{1}}_u(\alpha)|$, we have
$$
\begin{aligned}
\sum_{u\in\set{0,1}^m}|\hat{\boldsymbol{1}}_u(\alpha)| &= \sum_{u\in\set{0,1}^m}\left| \frac{1}{p} \sum_{x \in \mathbb{F}} \boldsymbol{1}_u(x)\cdot \omega^{\alpha x} \right|\newline
&= \frac{1}{p}\sum_{u\in\set{0,1}^m}\left| \omega^{\alpha A_u} \right|\newline
&\le \frac{1}{p} \sum_{u\in\set{0,1}^m}\frac{\sin(\pi t_u / p)}{\sin(\pi / p)}\newline
&\le \frac{1}{p} \frac{2^m \sin(\pi / 2^m)}{\sin(\pi/p)} = \frac{2^m\sin(\pi/2^m)}{p\sin(\pi / p)}
\end{aligned}
$$

Massey Secret-Sharing Scheme