Following a bunch of questions on the topic of Pohlig-Hellman encryption. I was wondering if this could be trivially adapted to be done over elliptic curves just like we create EC-DH instead of DH. surprisingly my google searches came up with no references for this, or in fact any symmetric encryption based on elliptic curves. It seems to me elliptic curves should provide the same properties of Pohlig-Hellman but allow same security with smaller keys.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Yes it can. However, it is known as the only effective approach yet it is quite naive. $\endgroup$– Arman BayatCommented Apr 6, 2018 at 19:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
I was wondering if this could be trivially adapted to be done over elliptic curves
If you don't mind the plaintexts being confined to points on the curve (as opposed to elements of $\mathbb{Z}^*_p$), then it's easy; pick a key $k$ that's relatively prime to the curve order $q$ (easy to do if you pick a curve with prime order), and then:
$$\begin{align} Enc_k(P) &= kP\\ Dec_k(P) &= (k^{-1} \bmod q)P \end{align}$$
Now, if you can't live with that restriction, one obvious possibility would be to use a curve with "twist security" (e.g. Curve25519), and so if the curve order is $q$, and the twist order is $q_T$ (note: $q$ and $q_T$ are the order of the curves, not the prime subgroups), then,
$$\begin{align} Enc_k(P) &= kP\\ Dec_k(P) &= (k^{-1} \bmod q)P&&\text{if P is on the curve}\\ Dec_k(P) &= (k^{-1} \bmod q_T)P&&\text{if P is on the twist} \end{align}$$
Curve25519 point multiplication can be done only using the $x$ coordinate, and so we can treat arbitrary values between 0 and $2^{255}-19$ as points.
Now, this construction preserves some of the properties of PH (for example, $$Enc_a(Enc_b(M)) = Enc_b(Enc_a(M))$$ but not others, for example, the question that was recently asked about combining two keys into a third that had $Dec_c(Enc_b(Enc_a(M))) = M$; that doesn't work as well; we can't define a $c$ that'll be able to decrypt both messages on the curve and messages on the twist (and giving someone both would allow them to potentially recover the values $a, b$)
-
2$\begingroup$ Also, if plaintext is on the curve, then so is ciphertext; and if plaintext is on the twist, then so is ciphertext. Thus, one bit of information leaks. This can be an issue, depending on usage context. $\endgroup$ Commented Apr 6, 2018 at 18:58
-
1$\begingroup$ @ThomasPornin: true, but a similar leakage was also inherent in the original PH scheme, which would leak whether the plaintext was a Quadratic Residue $\endgroup$– ponchoCommented Apr 6, 2018 at 19:00
-
$\begingroup$ So the trouble with merging two keys only comes from using the twist as well? (which I didn't follow). But that was only to solve the mapping problem, without that we would get the desired property, couldn't we just pad to ensure the point is on the curve? or would the padding cause a leak? $\endgroup$ Commented Apr 7, 2018 at 5:07
-
$\begingroup$ I'm trying to figure out how to use "Curve25519 point multiplication can be done only using the $x$ coordinate, and so we can treat arbitrary values between 0 and $2^{255}-19$ as points" to get that full interval as both plaintext and ciphertext space. It looks like, for decryption at least, we need to be able to recognize an $x$ giving a point on the curve from one giving a point on the twist. Is that easy? $\endgroup$– fgrieu ♦Commented Apr 7, 2018 at 6:15
-
1$\begingroup$ @fgrieu It is very easy: Is $x^3 + 486662 x^2 + x$ a quadratic residue modulo $2^{255} - 19$ or not? $\endgroup$ Commented Apr 7, 2018 at 7:00