# Shamir Secret Sharing - Threshold decryption implementation

I'm implementing Shamir secret sharing in C using OpenSSL.

I've split up the private key and I'm ready to start decrypting the original message using some of the shares. I set $$n = 5$$ (5 shares total) and $$t = 3$$ (3 shares required to decrypt).

The way my encrypted message is stored is in a $${\rm msg} = (c_1, c_2)$$ format, so I don't think I can just follow the example on Wikipedia, though I may be mistaken. Here is how my book tells me to do it (image). I've highlighted the particular part I'm stuck on:

"The dealer then sends $$\langle i, s_i \rangle$$ to authority $$i$$ in a secure manner.

To collectively decrypt an encrypted ballot $$c$$, where $$c = (c_1=g \bmod p, c_2 = Y^r \times m \bmod p)$$, $$t$$ such election authorities $$\{i_1, i_2, \dotsc, i_t\}$$, where $$1 \le i_j \le n$$, for $$1 \le j \le t$$, perform the following calculations (Desmedt & Frankel, 1990):

• Each entity uses its share $$s_{i_j}$$ to calculate $$\alpha_{i_j} = c_1^{i_j} \bmod p$$ and broadcasts it.
• Each entity calculates $$c_{i_j} = \displaystyle \prod_{1 \le k \le t, k \ne j} \frac{i_k}{i_k - i_j} \bmod q$$ $$\color{red}{(\Leftarrow \text{HERE})}$$ and $$\mu_1 = \displaystyle \prod_{j=1}^t \alpha_{i_j}^{c_{i_j}} \bmod p$$. Note that $$\mu_1 = c_1^s \bmod p$$.
• Each entity calculates $$\mu2 = \mu1-1 \bmod p$$ and $$m' = \mu2 \times c2 \bmod p$$, where $$m'$$ is the recovered ballot."

In this portion, I'm confused by the values $$i_k$$ and $$i_j$$. It seems to indicate that $$1 \le i_j\leq n$$ (values 1–5). Then it says $$1 \le j \le t$$ (values 1–3). Can someone straighten me out?

Let's say I'm using the following keys, just for reference:

• Key #2 | 1234
• Key #4 | 4567
• Key #5 | 5678

Final question: do I need to $$\bmod$$ each result, or just the final sum?

The index $i$ is running through the $n$ possible participants (1=Alice, 2=Bob, 3=Charlie, 4=Dave, and 5=Eve). Now to be able to easily refer to the $t$ out of $n$ persons — required by the threshold scheme — the index $i_j$ is used: $i_1$ is the first of the $t$ people taking part to the decryption, $i_2$ is the second, ..., $i_t$ is the $t$-th. (If Alice, Bob, and Charlie decrypt, this will be $i_1=1$, $i_2=2$, and $i_3=3$; if Alice, Dave, and Eve decrypt one will have $i_1=1$, $i_2=4$, and $i_3=5$.)

Now there is obviously a typo in you book as $\mu_2=\mu_1^{-1}\pmod p$ and not $\mu_1{-1}\pmod p$.

Additionally, I believe the computation of $c_{i_j}$ given in your book is incorrect: instead $\displaystyle\prod {i_k\over i_k -i_j}$ you should read the public values $\displaystyle\prod {x_{i_k}\over x_{i_k} -x_{i_j}}$ where the values $x_l$ are the public elements defining the polynomial $f$ of the secret sharing scheme.

Hence, read the source instead. The implementation given in the paper is also more efficient as it does not require any inversion mod $p$.

(For the last bit of your question, I assume you were referring to a product not a sum. And yes, you can mod $q$ whenever you want, but it's probably more efficient to keep things as small as possible.)

• Thank you so much, on all counts, bob! I knew something wasn't adding up with what i had. I really appreciate this! I will read through the original paper and go from there. Oct 19, 2012 at 14:43
• One more question! When you say "defining elements" of the polynomial, do you mean the keys themselves? (I apologize, i'm not very strong in the math department) Oct 20, 2012 at 2:08
• The polynomial $f$ underlying Shamir's $(t,n)$ secret scheme is such that it has degree $t-1$ and $f(0)$ is the key (or secret) to be shared. The share given to participant $i$ is $f(i)$. You can compute $f$ using Lagrange interpolation from $f(j)$, $j=0,...,t$. See also section 2.1 of the paper linked in the answer above.
– bob
Oct 20, 2012 at 6:02