# Bandwidth and block size for Paillier cryptosystem

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 Damgård-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;

• 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

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