# 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. – Chris C Oct 19 '12 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) – Chris C Oct 20 '12 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 '12 at 6:02