@EllaRose I messaged you on keybase, hope you get it

Hello

How are you?

I have a question

How could we show that the encyption of $m_1 \cdot m_2$ is $(g^{y_1+y_2}, m_1 \cdot m_2 \cdot h^{y_1+y_2})$ ?

@Evinda you have this because of the commutative property of multiplication

example: $g^3 \cdot g^2 = (g\cdot g\cdot g) \cdot (g\cdot g) = g\cdot g\cdot g\cdot g\cdot g = g^5$

sorry, the associative property

@Evinda I found a nice guide if you want: mathplanet.com/education/algebra-1/…

Yes, I understand. I hadn't understood why we take the pairwise product

@Evinda It's to allow correct decryption

The public key $h$ is produced by assigning $h = g^x$ where $x$ is the private key

So really we have $h^y = g^{x\cdot y}$

now if you write down the ElGamal encryption equation like that it might be more clear

$(g^{y}, g^{x\cdot y} \cdot m)$

We can decrypt with the private key by raising the left side chunk by $x$: $({g^{y_1}}^{x}, g^{x\cdot y_1} \cdot m_1)$

$$\frac{g^{x\cdot y_1} \cdot m_1}{g^{x\cdot y_1}} = m_1$$

You can think of the left side as the key and the right side as the encrypted message. When you multiply two messages together their keys also get multiplied.

So you must also adjust the left side to match, so that it can be decrypted later

If we were to only multiply the message side, but not the key side, we would get something like: $(g^{y_1}, g^{x y_1 y_2} m_1 m_2)$ (notice that the left side has only $y_1$), then our decryption routine above will break: $$\frac{g^{x y_1 y_2} \cdot m_1}{g^{x y_1}} = g^{y_2} m_1$$ (which can not be decrypted because $y_2$ is unknown, even if you have the private key)

@Evinda Well in this case it's no longer a public key system because you require $(y_1+y_2)$ to be able to decrypt

We want $y_1+y_2$ to be the private key, don't we?

Lets just call that the secret key in this case

yes

So we can also justify it like that, can't we?

Not if you want asymmetric encryption

It becomes symmetric encryption if you use it like that

You be Alice, I'll be Bob. Only you know the value of $x$, but we all know $h = g^x$.

Now I'll pick a random $y$, and only I know it. I'll send you $m\cdot h^y$ alone like above

You only know $x$, which doesn't help to guess $y$

Nothing helps to guess $y$, it's uniformly random, it's a strong secret key

But you want to read the message, so you need to remove the $h^y$ somehow, and without any additional information that means you must know $y$

But if I were to tell you $y$ right now, then our friend @CodesInChaos will see it and can snoop on our session

Everyone knows $h$, and so anyone who gets $y$ can easily reconstruct $h^y$ and divide it off the ciphertext

But if I were to send $g^y$ instead, nobody can obtain the original value $y$ from it.

But you, knowing $x$, have a trick up your sleeve

$(g^y)^x = (g^x)^y = h^y$

So we need $c_1$ in order to communicate just enough information about $y$ that only you can decode it

If I didn't explain very well, feel free to ping me. I'm just having Saturday relaxation today :)