# El-Gamal and Lines on Planes

I've been thinking about a geometric picture for El-Gamal. The idea is to understand the set $\{(my^{x},g^x) \mid x \in Z_p\}$ (the set of encryption of $m$ for fixed $g$ and $y$) by taking the $\log_g$ and getting $\{(\log m + x\log y, x) \mid x \in Z_p\}$, which is a line on a plane. Decryption corresponds to finding the $y$-intercept; this is possible if you know $\log y$. Re-encryption corresponds to moving a point on the line to another random point on the same line; this is possible if you know a point on the line (a ciphertext) and a vector parallel to the line (or simply another point on the line). Notice that since El-Gamal is IND-CPA, knowing two points on the line is not sufficient to determine the $y$-intercept.

Of course, one needs to determine what geometric operations are efficiently computable. Vector scaling by $\lambda$ is efficiently computable. Vector addition is efficiently computable. Vector difference is efficiently computable.

The main benefit is that it makes some sense, to me, of the homomorphic properties of El-Gamal.

Any references for this point of view? Further thought seems to show that the Computational Diffie-Hellman and Decisional Diffie-Hellman assumptions have a very elegant formulation. The Decisional Diffie-Hellman assumption is that you can't tell whether two vectors are parallel.

 This looks relevant: https://eprint.iacr.org/2013/377.pdf

• Do you want to use this for practical applications or do you want to use this to explain people how ElGamal works? – SEJPM Jun 25 '15 at 20:45
• @SEJPM to improve my own understanding. It helps me understand things like Re-Encryption and the homomorphic properties of El-Gamal. I think that other people may find this confusing. – ogogmad Jun 25 '15 at 22:00
• In fact is not really a line since you are in ${\bf Z}_p.$ You will see some points in the plane ${\bf Z}_p^2.$ – 111 Jul 20 '15 at 13:30
• @111 it's a line algebraically – ogogmad Jul 20 '15 at 15:00
• @NaN so $x\in {\bf R}$ not in ${\bf Z}_p.$ – 111 Jul 20 '15 at 21:05