

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

Can someone clarify what is meant by the terms cryptosystem bandwidth and block size for public key cryptosystems; The context is the Paillier cryptosystem and its Damgard-Jurik generalisation. My intuition is that they refer to the modulus. Since the modulus is $n^2$ and $n^s$ respectively does it apply that they have more bandwidth/block size than ElGamal which computes $mod \;\; q$; Is this intuition correct;

share|improve this question
Bandwith is normally related to time. So without some kind of performance metric, it would be tricky to say something about it. With asymmetric crypto-systems you do have overhead because the size of the ciphertext produced is normally larger than the plaintext. Also note that asymmetric cryptosystems almost always are paired with a symmetric hash or encryption algorithm, making the overhead less of an issue. – Maarten Bodewes Sep 22 '13 at 14:24
up vote 2 down vote accepted

Let $c$ denote a ciphertext and let $m$ denote a plaintext. To my best knowledge, researchers in cryptography employ "bandwidth" as different meanings, say, ciphertext expansion ($|c|/|m|$) or a number of bits of plaintexts contained in a ciphertext ($|m|$). @owlstead refers "overhead," which is $|c| - |m|$. For example,

I think you mean the latter, i.e., $|m|$ and "block size" seems to be $|c|$.

Let us calculate $|m|/|c|$.

  • Paillier: The plaintext space is $\mathbb{Z}_n$ and the ciphertext space is $\mathbb{Z}_{n^2}$. Hence, the ratio of bandwidth/blocksize is $1/2$.
  • DJ with $s\geq 1$: The plaintext space is $\mathbb{Z}_{n^{s}}$ and the ciphertext space is $\mathbb{Z}_{n^{s+1}}$. Hence, the ratio is $s/(s+1)$.
  • ElGamal: The plaintext space is $\mathbb{G}$ and the ciphertext space is $\mathbb{G}^2$. Hence the ratio is $1/2$.
share|improve this answer
Hi curious. The ciphertext length is log n^2 and that of plaintext is log n. Hence we got 1/2. – xagawa Feb 2 '14 at 12:16

Your Answer


