2
$\begingroup$

I'm trying to implement Private Set Intersection using the additive ElGamal public key encryption system. The code I've written can encrypt and decrypt numbers using the ElGamal system, so far so good. Adding and multiplying the cipher also works. Or at least, it works with positive numbers.

As I understand modulo arithmetics negative numbers can be think of by the following: $x + a = 0 \mod q$ where $a$ is a negative number. So if I have the group order set to 8009 minus one can is 8008, because $1 + 8008 = 0 \mod 8009$.

Now I noticed that no matter which generator I use, when I use power-mod such that $g^{q-1} \mod q$ the result always 1. I didn't dig much in the math of encryption yet, but it seems to a consistent result. $2^6 = 1 \mod 7$, $1151^{8008} = 1 \mod 8009$ and so on. Which then brings me to a problem. The whole 'additive' part comes in due because of using exponentials, such that $g^x g^y = g^{x+y}$ But would this be true in modulo arithmetic here? $g^{-1} g^{+1} \mod q$ should evaluate to 1 to have the $x + y = -1 + 1 = 0$, yet if $g^{-1} \mod q$ is always 1 then the result of $1 * g$ will be just $g$, so I would be off by one. In fact, the $g^{-1} \mod q$ is always one, but then $g^0 \mod q$ is also 1. What's going on here? I'm really confused.

$\endgroup$
4
$\begingroup$

Now I noticed that no matter which generator I use, when I use power-mod such that g^(q-1) mod q the result always 1

Congratulations, you just rediscovered Fermat's Little Theorem which says that for all primes $p$ and all non-zero integers $a$ which are not multiples of $p$, it holds that $a^{p-1}\bmod p=1$.

So if I have the group order set to 8009 minus one can is 8008, because 1 + 8008 mod 8009 = 0.

Indeed, this is how it works for plain addition $\bmod 8009$, however it seems you're not actually doing that and are actually using lifted ElGamal, i.e. encrypting as $(g^k \bmod p,g^m\cdot y^k\bmod p)$ (because standard ElGamal only has a multiplicative homomorphism).

But at that point you're no longer adding $m+m'$ but you're instead adding $g^m\cdot g^{m'}=g^{m+m'}$ and as it turns out, these exponents don't operate in the group $\mathbb Z_p$ (i.e. $\bmod p$) but instead in the group $\mathbb Z_{\operatorname{ord}(g)}$, where $\operatorname{ord}(g)$ is the smallest non-zero integer $q$ such that $g^q\bmod p=1$. If you are using a safe prime $p$, i.e. a prime $p$ such that $(p-1)/2=q$ is also prime, then $\operatorname{ord}(g)$ can take exactly 4 values: $1,2,q,2q$ (by Lagrange's theorem and the multiplicative order being $p-1$ for a prime).

| improve this answer | |
$\endgroup$
  • $\begingroup$ This should be included too. $g^{-1} \bmod q$ this part is missing from the OP's Q. It should not be 1. It is the inverse of $g$ and $g^{-1}\cdot g^1 \bmod q = g^{-1} \cdot g \bmod q$ $\endgroup$ – kelalaka Jun 21 at 17:31
  • $\begingroup$ Also, negative numbers: $g^{-x} = (g^{x})^{-1}$ $\endgroup$ – kelalaka Jun 21 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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