Message Expansion / Encryption Blowup Factor / Ciphertext Expansion of ECC

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$

Private 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.


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.

Category: encryption Time: 2016-07-28 Views: 0

Related post

  • Efficiency of McEliece cryptography (ciphertext expansion) 2015-09-07

    Most of the sources say McEliece has never gained acceptance because of its large size of private and public keys. However I have never heard about the size (or length) of its ciphertext. ("Ciphertext expansion".) For example, McEliece offers th

  • When should I use Message layer encryption vs transport layer encryption 2011-07-08

    Basically I will be having to secure a connection between different hops. Therefore even if TLS is widely known to be the best in class, I am wondering that in such a case message based encryption wouldn't be worth more than transport layer based enc

  • How large should a Diffie-Hellman p be if the messages are encrypted? 2013-03-18

    How large should the prime $p$ and generator $g$ values be in a Diffie-Hellman handshake if the messages are encrypted. If the key that encrypted the Diffie-Hellman messages becomes compromised, then does that compromise the key generated using Diffi

  • Enterprise message bus encryption 2015-08-03

    I'm contemplating using Amazon's Simple Queue System as the basis of an enterprise message bus. According to Amazon, the contents are not encrypted, which means the application(s) will have to handle encryption / decryption. It seems likely that this

  • Is it secure to send the hash along the message without encryption? 2016-02-24

    Lets suppose Alice send to Bob a message $M$ along with its hash value say $H$ which is calculated using SHA3 algorithm. It is sent on the network where it got read by Eve and she does not make any changes to the message $M$, she will just read the m

  • Public key encryption without ciphertext expansion 2014-10-30

    Say I have a database column that is defined as VARCHAR(255) that stores names. I can assume that names can be up to 255 chars. I need a public key encryption so that I can replace names with their ciphertexts. However the DB structure cannot be chan

  • Can we decrypt in this order when the message is encrypted twice? 2013-10-16

    If we encrypt a message twice with symmetric key $k_1$ first and then $k_2$ like $E_{k2}\{E_{k1}\{m\}\}$ , ideally we should decrypt with $k_2$ first and then $k_1$ but is it possible to decrypt with $k_1$ and then with $k_2$ ? Using any of the AES M

  • Encryption in which ciphertext is bigger than plaintext? 2014-11-11

    Is there an encryption which would produce a ciphertext longer than the plaintext? (please ignore block-chaining IV stuff, which would result in a data being generated from the plaintext). The point in question is that a ciphertext generated $\{0,1\}

  • Should private messages be encrypted? 2013-03-11

    I want to implement a private messaging system to my website, but I'm wondering if the content of the -supposedly private- message between Alice and Bob should be stored in plain text in the database or it should be encrypted prior to that, so that e

  • Is signing a message just encrypting it with private key? 2014-05-04

    It is often said that RSA encryption with a private key is the same as signing (signature generation). Will RSA encryption with a private key over a cryptographic hash give the same result as performing a signature generation operation? -------------

  • Verification of signed message with encryption 2014-08-11

    I have a question about the message that is being encrypted and signed. Say, two users called Tom and Mary, both have a pair of private key and public key. Tom sends a message through a system that will encrypt and sign the message. 2 kinds of messag

  • CCA security of a system that splits messages and encrypts each packet 2014-11-14

    Propose a symmetric key based crypto-system for implementing a secure email system. This system is based on AES and CCA secure. Suppose that you have to encrypt a large message and that this message is split in several small packets and the crypto-sy

  • How to get rid of "Authenticated with partial success" message when using two factor authentication 2016-07-04

    On my linux machine I am writing a PAM module for two factor authentication ( It works on an opt in basis so if a user doesn't have a .signal_authenticator file the module just returns success. When sshi

  • Symmetric encryption mode where ciphertext size is plain text size 2013-02-22

    I've had many questions on Stackoverflow on how to minimize the output of a cipher - during encryption of course - to the same size as the input. Obviously this is possible for a single block of plaintext, but it gets harder when the plaintext size i

  • How to find out if my IM messages are encrypted? 2013-03-25

    I'm a Yahoo Messenger addict and I use it extensively with Pidgin on Debian. Unfortunately I moved to a place where I have to share a privately operated network connection with a lot of people I'm not really familiar with. Without having details abou

  • Message signing/encryption with Thunderbird and Kleopatra 2009-10-27

    How do I make Thunderbird use my certificates stored in Kleopatra (KDE)? When I try to import certificates it says it's looking for PKCS12 files, but I can't find any. I'm not sure where Kleopatra stores keys, but I assume it takes them from gnupg's

  • Message expansion in NTRU: why is it $\log_p(q)$-to-$1$? 2016-07-27

    Suppose that we are working with the original version of NTRU with parameters $(N,p,q,k,d_f,d_g,d_\phi)$. In this case we are working with the original NTRU with the digital envelope and the parameter $k$ is described below. Suppose that we encrypt a

  • Impacts of not using RSA exponent of 65537 2012-07-01

    This RFC says the RSA Exponent should be 65537. Why is that number recommended and what are the theoretical and practical impacts & risks of making that number higher or lower? What are the impacts of making that value a non-Fermat number, or simply

  • Is RSA-OAEP secure when e=3? 2012-07-01

    This RFC says the RSA Exponent should be 65537. Why is that number recommended and what are the theoretical and practical impacts & risks of making that number higher or lower? What are the impacts of making that value a non-Fermat number, or simply

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development


Front-end development


development tools

Open Platform

Javascript development

.NET development

cloud computing


Copyright (C), All Rights Reserved.

processed in 0.471 (s). 13 q(s)