# ElGamal Threshold Cryptosystem

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?

• @poncho, can you help me out with this, please? – Fiono Feb 6 at 10:48

My question is: since $$s$$ is an element in $$Z_q$$, shouldn't $$b_js_j$$ be also calculated $$\mod q$$?
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.