Shamir Secret Sharing - Threshold decryption implementation

Question

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?

Answer 1

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.)