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;
-
$\begingroup$ 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. $\endgroup$– Maarten Bodewes ♦Sep 22, 2013 at 14:24
1 Answer
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$.
-
1$\begingroup$ Hi curious. The ciphertext length is log n^2 and that of plaintext is log n. Hence we got 1/2. $\endgroup$– xagawaFeb 2, 2014 at 12:16