In order to complete the following table with asymptotic times and message expansions,

$\quad \quad \quad \quad \quad \quad \quad \quad \quad$ RSA $\quad$ McEliece $\quad$ ECC

Encryption Speed $\quad \quad \; \; N^2 \quad \quad N^2 \quad \quad \quad N^3$

Decryption Speed $\quad \quad \; \; N^3 \quad \quad N^2 \quad \quad \quad N^3$

Public Key Size $\quad \quad \quad \;\; N \quad \quad \; \ N^2 \quad \quad \quad N$


Message Expansion $\quad \; 1-1 \quad \; 2-1 \quad \quad \quad ?$

I need to find the message expansion of ECC cryptosystem, but I don't find a clear answer anywhere.

Can someone give me and explain the missing value in the table?

Thanks in advance.

  • $\begingroup$ which ECC based public key encryption scheme are you considering here? $\endgroup$ – SEJPM Jul 28 '16 at 13:45
  • $\begingroup$ Diffie-Hellman and El-Gamal $\endgroup$ – Leafar Jul 28 '16 at 13:52
  • $\begingroup$ I would say that the answer is 2-1, is it right? $\endgroup$ – Leafar Jul 28 '16 at 13:58
  • $\begingroup$ DH is not an encryption algorithm and ElGamal has 2, except for when you do hybrid encryption with ElGamal like in ECIES, where you'd get $\infty$-1, depending on your message length. $\endgroup$ – SEJPM Jul 28 '16 at 14:04
  • $\begingroup$ I was thinking about the common El-Gamal based on the discrete logarithm problem $\endgroup$ – Leafar Jul 28 '16 at 14:07

OK, a short amendment to your table, "message-expansion" only applies to messages which are quite long and not trivial one-bit messages, because they'd have a much higher message expansion.

Secondly, RSA doesn't have an expansion of "1" because of constructions such as OAEP. Also note that plain RSA has no form of semantic security and only improved variants provide IND-CPA and IND-CCA2 security.

Thirdly, McEliece can do better than "2" and usually does, depending on the details, it should have something around 1.5 at worst, also see Bernstein's Post Quantum Cryptography book and this paper (PDF). Depending on whether you want IND-CPA or IND-CCA2 security, better results may be achieved.

And now finally for ECC using ElGamal. Note first that you can't encode arbitrary messages deterministically as elliptic curve points and thus you can't easily encrypt arbitrary messages using this method.
The rest can be seen from the description in which is stated that the output effectively is two group elements and as two group elements usually are twice as large as a single group element (the message), you get a message expansion of "2". Note also that plain ElGamal is only IND-CPA and not IND-CCA2 secure.

  • $\begingroup$ It is not implicit in the question, but the constructions are the basic ones that we can learn at school... $\endgroup$ – Leafar Jul 28 '16 at 15:18

Your Answer

