Bandwidth and block size for Paillier cryptosystem

Question

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;

Answer 1

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,

• Joye and Libert (EUROCRYPT 2013, ePrint 2013/435) wrote that "the scheme is computationally efficient but somewhat wasteful in bandwidth as $k \cdot \log_2{N}$ bits are needed to encrypt a $k$-bit message." Here, the scheme is the Goldwasser-Micali scheme and it encrypts a bit into a ciphertext of length $\log_2{N}$ and "bandwidth" seems to be $|c|/|m|$.
• Chevallier-Mames, Naccache, and Stern (SCN 2008, ePrint 2008/119) defined "bandwidth" as the number of bits contained in a ciphertext, that is, $|m|$.

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