Feldman's Verifiable Secret Sharing

$\newcommand{\coinheads}{\mathsf{HEADS}}$ $\newcommand{\cointails}{\mathsf{TAILS}}$ $\newcommand{\varalice}{\class{var var_Alice}{\text{Alice}}}$ $\newcommand{\varbob}{\class{var var_Bob}{\text{Bob}}}$ $\newcommand{\alicebob}[3]{#1 & \ra{#2} & #3\\[-5pt]}$ $\newcommand{\bobalice}[3]{#1 & \la{#2} & #3\\[-5pt]}$ $\newcommand{\alicework}[1]{#1 & &\\[-5pt]}$ $\newcommand{\bobwork}[1]{ & & #1\\[-5pt]}$ $\newcommand{\work}[2]{#1 & & #2\\}$ $\newcommand{\allwork}[1]{ & #1 & \\}$ $\newcommand{\dupwork}[1]{#1 & & #1\\}$ $\newcommand{\aliceseparator}{-------&&\\}$ $\newcommand{\bobseparator}{&&-------\\}$ $\newcommand{\foo}{\phantom{\text{bigarrowfitsallthis}}}$ $\newcommand{\ra}[1]{% \vphantom{\xrightarrow{asd}}% \smash{\xrightarrow[\foo]{#1}}% }$ $\newcommand{\la}[1]{% \vphantom{\xleftarrow{asd}}% \smash{\xleftarrow[\foo]{#1}}% }$ $\newcommand{\z}[1]{\mathbb{Z}_{#1}}$ $\newcommand{\zq}{\mathbb{Z}_\varq}$ $\newcommand{\zqs}{\mathbb{Z}_q^\ast}$ $\newcommand{\zps}{\mathbb{Z}_p^\ast}$ $\newcommand{\zns}[1]{\mathbb{Z}_{#1}^\ast}$ $\require{action} \newcommand{\sampleSymb}{ {\overset{\$}{\leftarrow}} }$ $\newcommand{\field}[1]{\mathbb{F}_{#1}}$ $\newcommand{\sample}[1]{#1\sampleSymb\zq}$ $\newcommand{\sampleGeneric}[2]{#1\sampleSymb#2}$ $\newcommand{\sampleInterval}[2]{#1\sampleSymb\interval{#2}}$ $\newcommand{\sampleRange}[2]{#1\sampleSymb\range{#2}}$ $\newcommand{\sampleCgroup}[1]{#1\sampleSymb\cgroup}$ $\newcommand{\samplezqs}[1]{\class{hover}{#1\sampleSymb\zqs}}$ $\newcommand{\sampleN}[2]{\class{hover}{#1\sampleSymb\z{#2}}}$ $\newcommand{\sampleNs}[2]{\class{hover}{#1\sampleSymb\z{#2}^\ast}}$ $\newcommand{\equalQ}{\overset{?}{=}}$ $\newcommand{\gQ}{\overset{?}{>}}$ $\newcommand{\inQ}{\overset{?}{\in}}$ $\newcommand{\cgroup}{\mathbb{G}}$ $\newcommand{\Hash}{\mathsf{Hash}}$ $\newcommand{\hash}[1]{\Hash({#1})}$ $\newcommand{\HashToField}{\mathsf{HashToField}}$ $\newcommand{\hashtofield}[1]{\HashToField({#1})}$ $\newcommand{\HashToGroup}{\mathsf{HashToGroup}}$ $\newcommand{\hashtogroup}[1]{\HashToGroup({#1})}$ $\newcommand{\hashbit}[2]{\mathsf{Hash}({#1})\verb+[0:#2]+}$ $\newcommand{\hmac}[2]{\mathsf{HMAC}_{#1}\left(#2\right)}$ $\newcommand{\naturals}{\mathbb{N}}$ $\newcommand{\sqfree}{L_\mathsf{square-free}}$ $\newcommand{\ceil}[1]{\lceil #1 \rceil}$ $\newcommand{\sampleSet}[2]{\class{hover}{#1\sampleSymb#2}}$ $\newcommand{\bunch}[1]{\{ #1_i\}_{i=1}^m}$ $\newcommand{\bunchi}[1]{\{ #1\}_{i=1}^m}$ $\newcommand{\forb}{\text{ for }i=1,\ldots,m}$ $\newcommand{\interval}[1]{[0, #1[}$ $\newcommand{\range}[1]{[#1]}$ $\newcommand{\rangeone}[1]{\{1, \dots,#1 -1 \}}$ $\newcommand{\vara}{\class{var var_a}{a}}$ $\newcommand{\varb}{\class{var var_b}{b}}$ $\newcommand{\varc}{\class{var var_c}{c}}$ $\newcommand{\vard}{\class{var var_d}{d}}$ $\newcommand{\varh}{\class{var var_h}{h}}$ $\newcommand{\varH}{\class{var var_H}{H}}$ $\newcommand{\varg}{\class{var var_g}{g}}$ $\newcommand{\varG}{\class{var var_G}{G}}$ $\newcommand{\vari}{\class{var var_i}{i}}$ $\newcommand{\varj}{\class{var var_j}{j}}$ $\newcommand{\vars}{\class{var var_s}{s}}$ $\newcommand{\vart}{\class{var var_t}{t}}$ $\newcommand{\varu}{\class{var var_u}{u}}$ $\newcommand{\varU}{\class{var var_U}{U}}$ $\newcommand{\varl}{\class{var var_l}{l}}$ $\newcommand{\varm}{\class{var var_m}{m}}$ $\newcommand{\varn}{\class{var var_n}{n}}$ $\newcommand{\varx}{\class{var var_x}{x}}$ $\newcommand{\varX}{\class{var var_X}{X}}$ $\newcommand{\varz}{\class{var var_z}{z}}$ $\newcommand{\varr}{\class{var var_r}{r}}$ $\newcommand{\varq}{\class{var var_q}{q}}$ $\newcommand{\varp}{\class{var var_p}{p}}$ $\newcommand{\vare}{\class{var var_e}{e}}$ $\newcommand{\vary}{\class{var var_y}{y}}$ $\newcommand{\varv}{\class{var var_v}{v}}$ $\newcommand{\varw}{\class{var var_w}{w}}$ $\newcommand{\varC}{\class{var var_C}{C}}$ $\newcommand{\varf}{\class{var var_f}{f}}$ $\newcommand{\varA}{\class{var var_A}{A}}$ $\newcommand{\varB}{\class{var var_B}{B}}$ $\newcommand{\varC}{\class{var var_C}{C}}$ $\newcommand{\varL}{\class{var var_L}{L}}$ $\newcommand{\varP}{\class{var var_P}{P}}$ $\newcommand{\varR}{\class{var var_R}{R}}$ $\newcommand{\varT}{\class{var var_T}{T}}$ $\newcommand{\varX}{\class{var var_X}{X}}$ $\newcommand{\varalpha}{\class{var var_alpha}{\alpha}}$ $\newcommand{\varprover}{\class{var var_Prover}{\text{Prover}}}$ $\newcommand{\varprover}{\class{var var_Prover}{\text{Prover}}}$ $\newcommand{\varverifier}{\class{var var_Verifier}{\text{Verifier}}}$ $\newcommand{\varN}{\class{var var_N}{N}}$ $\newcommand{\rhovar}{\class{var var_ρ}{\rho}}$ $\newcommand{\sigmavar}{\class{var var_σ}{\sigma}}$ $\newcommand{\thetavar}{\class{var var_θ}{\theta}}$ $\newcommand{\muvar}{\class{var var_μ}{\mu}}$ $\renewcommand{\vec}[1]{\mathbf{#1}}$ $\newcommand{\veca}{\vec{\class{var var_vec_a}{a}}}$ $\newcommand{\vecb}{\vec{\class{var var_vec_b}{b}}}$ $\newcommand{\vecc}{\vec{\class{var var_vec_c}{c}}}$ $\newcommand{\vecs}{\vec{\class{var var_vec_s}{s}}}$ $\newcommand{\vecG}{\vec{\class{var var_vec_G}{G}}}$ $\newcommand{\vecH}{\vec{\class{var var_vec_H}{H}}}$ $\newcommand{\vecg}{\vec{\class{var var_vec_g}{g}}}$ $\newcommand{\vech}{\vec{\class{var var_vec_h}{h}}}$ $\newcommand{\true}{\mathsf{true}}$ $\newcommand{\false}{\mathsf{false}}$ $\newcommand{\ctx}{\mathsf{ctx}}$ $\newcommand{\coloneqq}{≔}$ $\newcommand{\ip}[2]{\left\langle #1, #2 \right\rangle}$ $\newcommand{\uwork}[2]{\underline{#1} & & \underline{#2}\\}$ $\newcommand{\aliceworks}[1]{#1 & &\\[-2pt]}$ $\newcommand{\bobworks}[1]{ & & #1\\[-2pt]}$ $\newcommand{\Halving}{\text{Halving}}$ $\newcommand{\HalveProof}{\text{HalveProof}}$ $\newcommand{\HalveVerify}{\text{HalveVerify}}$ $\newcommand{\indent}{\qquad}$ $\newcommand{\append}{\mathrm{append}}$ $\newcommand{\schnorrvalidate}{\mathsf{schnorr}\_\mathsf{validate}}$

Feldman's Verifiable Secret Sharing

As Feldman first introduced, Verifiable secret sharing is an extension to Shamir’s secret sharing scheme. The idea is that, when generating shares of the secret $S$, the splitting party also generates a set of public values that shareholders can use to validate their shares.

For simplicity, we will use “Sherry” to refer to the party generating the shares of a secret $S$. We denote a share using a lower-case $s$, and a shareholder (or player) as $P$. We will assume a $\left(k, n\right)$ threshold scheme, meaning that $k$ shares are enough to recover $S$ and fewer do not obtain any information about $S$. In some protocols, the players may perform the reconstruction, independently or collaboratively.

In standard Shamir secret sharing, Sherry generates a polynomial $$ f \left( x\right) = a_{0} + a_{1} x + \cdots + a_{k-1} x^{k-1} \in \mathbb{F}\left[x\right] \enspace ,$$ where $a_{0}=S$ and $\mathbb{F}$ is a finite field of characteristic $p$, where $p$ is a suitably large prime. Shares are generated as $s_{i}=\left(x_{i},f\left(x_{i}\right)\right)$ for $i=1,\ldots,n$. Sherry then sends $s_{i}$ to $P_{i}$ over a secure channel. Shares are generated the same way in Feldman’s scheme.

Feldman’s scheme extends Shamir’s scheme by having Sherry extend the shares to include verification values, as well as publicly share an additional set of values that each player $P_{i}$ can use to verify that their share $s_{i}$ is valid.

The public values are generated by translating them into elements a commutative group $G$ for which the discrete logarithm problem is hard. For expository purposes, we’ll start with $\z{q}$, the multiplicative group of integers modulo a large prime $q$, where $q-1$ is divisible by a large prime $r$, and a generator value $g\in\z{q}$ such that $\left|g\right|=r$.

Verification Values #

Let $A_{j}=g^{a_{j}}\pmod{q}$ for $j=0,\ldots,k-1$. These are the verification values, and Sherry publishes all of them on a public broadcast channel.

Recovering any $a_{j}$ values from the corresponding $A_{j}$ would require solving a discrete logarithm problem over $\z{q}$, which is presumed to be hard. Note that $A_{0}=g^{a_{0}}=g^{S}\pmod{q}$; solving the discrete log for $A_{0}$ would recover $S$ directly.

Verification of Shares #

To verify their share $s_{i}=\left(x_{i},f\left(x_{i}\right)\right)$, player $P_{i}$ computes:

$$ V_{i}=\prod_{j=0}^{k-1}{A_{j}^{x_{i}^{j}}} \enspace . $$

For each $j$, we have $A_{j}=\left(g^{a_{j}}\right)^{x_{i}^{j}}=g^{a_{j}\cdot x_{i}^{j}}$, which means

$$ V_{i}=g^{a_{0}} g^{a_{1}\cdot x_{i}} g^{a_{2}\cdot x_{i}^{2}}\cdots g^{a_{k-1}\cdot x_{i}^{k-1}}=g^{a_{0} + a_{1}\cdot x_{i} + \cdots + a_{k-1}\cdot x_{i}^{k-1}}=g^{f\left(x_{i}\right)} $$

Since $P_{i}$ knows $f\left(x_{i}\right)$ as part of their share, they can compute $V_{i}’=g^{f\left(x_{i}\right)}$ directly from the value of $f\left(x_{i}\right)$ given in $s_{i}$. If $V_{i}’=V_{i}$, then $P_{i}$ accepts $s_{i}$ as valid; otherwise, they reject $s_{i}$.

Variations #

Feldman points out that it is not necessary to use $\z{q}$ for generating the verification values. The paper discusses using elliptic curves over finite fields. Using the more familiar point multiplication notation for an elliptic curve group $G$ with a generator point $P\in G$, we have $V_{i}=\left[a_{0}\right]P+\left[a_{1}x_{i}\right]P+\cdots +\left[a_{k-1}x_{i}^{k-1}\right]P=Y_{i}$.

Security pitfalls #

Forgery attack: Craige describes a forgery attack against Feldman’s technique when broadcast channels are incorrectly implemented. If an attacker can change each player’s view of a single $A_{j}$ value, then it is possible to forge invalid shares for each player that will pass the verification step.
Zero share attacks: All of the pitfalls of Shamir’s secret sharing scheme (e.g., generation of zero shares) still apply.
Improper parameter choice: The $p$, $q$, and $g$ values should be selected with care. While Shamir’s original paper suggested using $p=2^{16}-15=65521$, this will limit the coefficients to 16 bits; recovering the $a_{j}$ values from their corresponding $A_{j}$ values becomes trivial. Further, improper selection of $q$ or $g$ can lead to several discrete log attacks.