$\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}}$
Alternative versions of Shamir's Secret Sharing scheme

Alternative Secret Sharing Solutions #

There are multiple ways to prevent inadvertently sharing the secret value by evaluating the polynomial at zero. In Shamir Secret Sharing, we described defense strategies to solve that problem in classical Shamir’s Secret Sharing scheme. Here, we describe alternative implementations of Shamir’s scheme, which ensure that evaluating $f\left(0\right)$ does not reveal $S$.

These alternative schemes are certainly harder to implement (and to review), and their added complexity might not be worth the ability to mistakenly leak $f(0)$, since they can still leak the secret value by leaking other points of the polynomial.

Transforming the Inputs Using a Nonzero Function #

Suppose we are working over $\z{p}$, where $p=2^{255}-19$. Consider the multiplicative group $\zns{p}$ of integers less than $p$ and relatively prime to $p$. We can define $h\left(m\right)=2^{m}\pmod{p}$. Since $0\not\in \zns{p}$, we know that $h\left(m\right)\neq 0$ for any integer $m$. Since $2$ is a generator of $\zns{p}$, we know that $h\left(m\right)$ has maximal order in $\zns{p}$.

During share generation, given an integer input $x$, define $x’=h\left(x\right)$. Then, generate the corresponding share according to $\left(x’,f\left(x’\right)\right)$. Because $x’\neq 0$, counters and external inputs can be used without the risk of generating a zero share.

This technique is compatible with the secret reconstruction using Lagrange interpolation: as far as the Lagrange interpolating polynomial goes, a share formed from the transformed values works the same as any other shares.

Avoiding the $y$-intercept #

It is possible to encode the secret $S$ into a polynomial such that $f\left(t\right)=S$ for a value $t\neq 0$. The process is only a little more complicated than the standard Shamir scheme:

  • Select a non-zero $t\in\field{p}$
  • Select a random degree-$(k-1)$ polynomial $g\left(x\right)\in\field{p}\left[x\right]$
  • Compute $S’=S-g\left(t\right)$
  • Set the final polynomial to $f\left(x\right)=g\left(x\right)+S'$

We now have $f\left(t\right)=g\left(t\right)+S’=g\left(t\right)+S-g\left(t\right)=S$. The Lagrange interpolating polynomial can compute $f\left(x\right)$ at $x=t$ just as easily as at $x=0$.

If shares are generated sequentially, selecting a value of $t$ larger than any reasonable number of shares $n$ (e.g., $t\gg 2^{64}$) can prevent creating an insecure share of the form $\left(t,f\left(t\right)\right)$.

If shares are generated randomly, it’s still possible to wind up with an insecure share by randomly selecting $t$. However, generating this value at random is significantly less likely than accidentally “generating” a zero share from a blocked read.

Moving Away from the Constant Term #

There is no requirement that $S$ be encoded into $f\left(x\right)$ through the manipulation of the constant coefficient. It’s possible to encode $S$ into, say, the linear coefficient of $f\left(x\right)$. Recovering the linear coefficient is straightforward, once you realize that the linear term of $f\left(x\right)$ is the constant term of $f’\left(x \right)$, the derivative of $f\left(x\right)$.

The process for generating a polynomial becomes:

  • Generate a random, degree-$(k-3)$ polynomial $g\left(x\right)$
  • Select a random $c\in\field{p}$
  • Set $f\left(x\right)=g\left(x\right)x^2+Sx+c$

The Lagrange interpolating polynomial can be adapted to evaluate derivatives of polynomials; the equation used to compute the first derivative is below. The equation is slightly more complicated than before but certainly within the capability of a good programmer.

$$f’\left(t\right)=\displaystyle\sum_{j=1}^{k}{y_{j}\left(\displaystyle\sum_{\begin{smallmatrix}i=1\\ i\neq j\end{smallmatrix}}^{k}{\left[\frac{1}{x_{j}-x_{i}}\displaystyle\prod_{\begin{smallmatrix}m=1\\ m\neq i,j\end{smallmatrix}}^{k}{\frac{t-x_{m}}{x_{j}-x_{m}}}\right]}\right)}$$

Evaluating $f’\left(0\right)$ gives the linear coefficient of $f\left(x\right)$, recovering $S$.

Requiring Recovery of the Full Polynomial #

Finally, it’s possible to encode the secret across all coefficients of $f\left(x\right)$. Take $g\left(x\right)=\displaystyle\sum_{i=0}^{k-1}{a_{i}x^{i}}$ , where each $a_{i}$ is chosen uniformly at random (except that $a_{k-1}\neq 0$), then we can set $M=\displaystyle\sum_{i=0}^{k-1}{a_{i}}$ and $R=S - M$. We then select a random $0\leq i\leq k-1$ and set $f\left(x\right)=g\left(x\right)+Rx^i$. Then the sum of the coefficients is equal to $S$.

Going back to the original Lagrange interpolating polynomial equation, if $t$ is replaced with a symbol $x$, the Lagrange interpolating polynomial recovers $f\left(x\right)$ exactly. $S$ can then be recovered from the reconstructed polynomial. Symbolic computations are more expensive and slightly more complex, but for, say, $k<30$, the algorithm works just fine.