Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose that the only public key cryptography schemes that we knew were Diffie Hellman, RSA and ElGamal. How much would this set civilization back? Are there important applications of elliptic curve cryptography [specifically] without viable substitutes?

[Edit: I came across this question which gives some information, but I'm looking for more. Specifically, I would like to know how much better elliptic curve cryptography is/(would be) than more classical encryption schemes for the applications where elliptic curve cryptography is superior.

share|improve this question

If you are restricted to Diffie-Helman, RSA, and ElGamal, I believe you cannot do pairing based cryptography which has applications to attributed based encryption and identity based encryption. These applications are not used heavily in practice, but could be in the next decade or two.

For more information on speed benefits of ECC, see this question and answers. Based on my own testing comparing the elliptic curve variant of exponential ElGamal (which is additively homomorphic) with Paillier (also additively homomorphic and similar-ish to RSA), the elliptic curve cipher was 2 orders of magnitude faster for both encryption and decryption (with a few realistic assumptions as decrypting exponential ElGamal can be tricky). Thus I believe encryption was something like 100ms on one device for Paillier vs 1ms on EC-ElGamal. Decryption was similar.

share|improve this answer

ECC allows the use of way smaller keys than necessary in traditional public key cyptography. According to this paper, these are just a fraction of the size of the keys with comparable strength of traditional RSA.

the computional effort for an equivalent level of security ranks from 1:3 (ECC vs DH, 80 bit) to 1:60 (ECC vs DH, 256 bit)

This also means, that public key cryptography is faster, and thus allows good security for systems that require a good chunk of security, but also can not provide the amount of computing power to process the traditional RSA in a reasonable amount of time. Examples for this are almost all smart card applications. Most people would not want to wait a minute until their RSA is done, if they could do it in a second using ECC, just to pick up some money (banking, used in Austria), or board a plane/cross a border (german "Personalausweis" (ID), most passports in europe).

As you see, not using ECC would not take us back into the stoneage, but they improve the way we can use our recources (time, or computional power) for its everyday use.

share|improve this answer

My understanding is that ECC is mostly lighter-weight than RSA. That is to say, for similar key strengths, the ECC key is significantly smaller. For example, a 2048-bit RSA key is believed to be about as strong as a 224-bit ECC key.

share|improve this answer
Thanks Jeff. Do you have a sense for what this difference means in practice? – Jonah Sinick Apr 22 '13 at 3:47
Well I would think it would mean less data transmitted during negotiation or other transactions. But other that that no, I don't have a good sense for what it translates to. – Jeff Apr 22 '13 at 15:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.