RSA offers the functionality of encrypting (short messages, or symmetric keys) with a public key, and decrypting with a private key. However, RSA key generation is extremely expensive, especially for 2048-bit+ keys. Is there an algorithm which employs elliptic curve cryptography, fast asymmetric encryption, fast key generation, and small keys sizes?
$\begingroup$
$\endgroup$
6
-
5$\begingroup$ ECIES $\endgroup$– DrLecterApr 14, 2014 at 20:58
-
$\begingroup$ @DrLecter - From what I understand, ECIES uses symmetric encryption (albeit with a shared secret, derived by means of asymmetric cryptography), does it not? I'm looking for asymmetric encryption. I did say scheme, so perhaps I should have been more explicit. I want to know whether there's an algorithm that employs ECC that is similar to RSA in that a short message can be encrypted with a public key, and decrypted with a private key. $\endgroup$– hunterApr 14, 2014 at 23:38
-
$\begingroup$ @hunter Why? What do you gain from encrypting the message itself with ECC instead of hybrid encryption? ECIES has a standard asymmetric encryption API. There are a few situations where RSA works but ECIES does not, but they're relatively exotic. $\endgroup$– CodesInChaosApr 15, 2014 at 9:35
-
$\begingroup$ @CodesInChaos - Why? Curiosity... nothing more. I'm not researching this for a practical application. $\endgroup$– hunterApr 15, 2014 at 12:40
-
1$\begingroup$ @hunter: ElGamal, Cramer-Shoup, Linear encryption. First two are under the DH assumption, where the second is in IND-CCA secure version of the first (IND-CPA). Thrid one is IND-CPA secure under the linear assumption (DLIN) which can be used in groups where the DHP may be easy (there is also a Cramer-Shoup like IND-CCA version of the last, but not really practical). ElGamal is the most efficient one. $\endgroup$– DrLecterApr 15, 2014 at 12:53
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
4
As already mentioned in a previous comment, ECIES (a hybrid encryption scheme) is typically the way to go when implementing asymmetric encryption on elliptic curves, as it is standardized. It provides chosen ciphertext security (IND-CCA).
But as you are looking for "pure" public key encryption schemes, here we go:
ElGamal can not only be implemented in (prime order $q$ subgroups of) $\mathbb{Z}_p^*$ for prime $p$, but equally on elliptic curve groups. It provides chosen plaintext security (IND-CPA).
Furthermore, there are various ElGamal-type schemes I want to mention:
- Cramer-Shoup is an ElGamal variant that provides IND-CCA security.
- If you work in a pairing friendly elliptic curve setting, it may be the case that in the group in which you are using the encryption scheme the decisional Diffie-Hellman (DDH) problem is easy. In such a case ElGamal is insecure as it's security relies on the DDH. Here, you can use Linear-encryption, which in contrast to ElGamal relies on the decision linear (DLIN) assumption and stays secure even if the DDH is easy and is also IND-CPA secure.
- There is also a IND-CCA secure Cramer-Shoup version of linear encryption (but that's rather of theoretical interest).
- Furthermore, recently I encountered another variant of linear encryption, denoted as linear combination encryption (unfortunately, behind a paywall) which provides IND-CPA security and relies on the decision linear combination (DLC) assumption. It can also be used in groups where the DDH may be easy (however, this scheme is rather esoteric and seems to be tailored to the constructed group signature scheme and the proofs respectively).
The most efficient one of these schemes is the standard ElGamal version.
-
1$\begingroup$ Those are all good schemes, but doesn't the question ask for encryption to be fast like in RSA? Do any of these schemes support encryption that is as fast as RSA's encryption? As far as I can tell, none of them are -- have I misunderstood? I think there's a tradeoff: RSA encryption will be faster than the ECC schemes; the ECC schemes will be faster for everything else, and will have shorter keys. $\endgroup$– D.W.Apr 16, 2014 at 5:23
-
$\begingroup$ @D.W. Actually, the title asks for existence and the question for fast keygen enc and small keys in comp to RSA 2048+. And the OP asked to post my comment as answer ;) But I agree with your remarks on efficiency and key sizes. $\endgroup$– DrLecterApr 16, 2014 at 5:31
-
$\begingroup$ Thanks, DrLecter! Makes sense! On re-reading the question, the question is not as clear as I initially thought. The question says "Is there an algorithm which employs elliptic curve cryptography, fast asymmetric encryption, [...]" - I took that to mean it wants the encryption operation to be fast, like in RSA, but it's entirely possible that might not be the right reading. Perhaps the original author will take a moment to edit the question and make what he/she is looking for clearer. $\endgroup$– D.W.Apr 16, 2014 at 5:33
-
$\begingroup$ @D.W. yes you are right, thats not fully clear. But from a comment of the OP on the question I assumed that he is just curious if there are schemes and then I just named some that came to my mind :) But after rethinking I will come back and edit efficiency aspects into my answer. $\endgroup$– DrLecterApr 16, 2014 at 5:37
$\begingroup$
$\endgroup$
1
The ElGamal encryption scheme works in any finite cyclic group $G$, so in particular in the group generated by a $\mathbb{F}_q$-point $P$ on an elliptic curve. Key sizes tend to be a lot smaller over elliptic curves.
-
1$\begingroup$ crypto.stackexchange.com/questions/9987/… addresses ElGamal over elliptic curves. $\endgroup$– archieApr 15, 2014 at 2:52