3
$\begingroup$

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.

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

Improve this question
$\endgroup$
5
  • $\begingroup$ Do you want to use this for practical applications or do you want to use this to explain people how ElGamal works? $\endgroup$
    – SEJPM
    Commented Jun 25, 2015 at 20:45
  • 1
    $\begingroup$ @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. $\endgroup$
    – wlad
    Commented Jun 25, 2015 at 22:00
  • $\begingroup$ 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.$ $\endgroup$
    – 111
    Commented Jul 20, 2015 at 13:30
  • $\begingroup$ @111 it's a line algebraically $\endgroup$
    – wlad
    Commented Jul 20, 2015 at 15:00
  • $\begingroup$ @NaN so $x\in {\bf R}$ not in ${\bf Z}_p.$ $\endgroup$
    – 111
    Commented Jul 20, 2015 at 21:05

0

Reset to default

Your Answer

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