ElGamal Threshold Cryptosystem

Question

Suppose we have a threshold ElGamal cryptosystem $(t, n)$ over an Elliptic Curve $E_p$, $p$ being a large prime, with the following parameters:

• $G$ is a generator point of $E_p$ with order $q$

• A dealer chooses a polynomial $f(x) = s + a_1x+...+a_{t-1}x \in Z_q[x]$ and $s \in Z_q$ is the secret key of the cryptosystem.

• $Y = sG$ is the public key.

• The dealer computes and distributes the secret private share $s_i$ to $P_i$ as $f(i)$, $i \in 1,2...n$.

• With Lagrange interpolation, $s = \sum_{i=1}^ts_i\prod_{j=1}^t\frac{j}{j-i}$, $i \neq j$.

• A ciphertext $(C1, C2) = (rG, M+rY)$, $r \in Z_q$, can be decrypted as $$M=-(\sum_{j=1}^tb_js_jC1) + C2$$ with $b_j = \prod_{j=1}^t\frac{j}{j-i}$, $i \neq j$.

My question is: since $s$ is an element in $Z_q$, shouldn't $b_js_j$ be also calculated $\mod q$?

$b_js_j$ can be $>q$ because it is not a field element but the number of times $C1$ is summed, right?

Answer 1

My question is: since $s$ is an element in $Z_q$, shouldn't $b_js_j$ be also calculated $\mod q$?

Doesn't really matter - the results come out the same either way.

We know that the order of $C1$ is $q$, and so we have $x C1 = (x+q)C1$ for any $x$. Hence, we have $b_js_j C1 = (b_js_j \bmod q) C1$

In practice, we generally want to reduce $b_js_j$ mod $q$ for performance reasons (or because our point multiplication routines might not handle multipliers significantly larger than $q$); however the math works out the same in either case.