1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ @poncho, can you help me out with this, please? $\endgroup$
    – Fiono
    Feb 6, 2020 at 10:48

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Makes sense. Thank you so much! You are doing cryptography god's work! $\endgroup$
    – Fiono
    Feb 7, 2020 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.