Is Paillier a stream or block encryption

Question

Does Paillier follow a stream encryption or block encryption technique. If it’s a block encryption then what is the size of the block in bits or bytes.

Answer 1

Stream Ciphers

A stream cipher produces key streams usually small sizes as bits (or bytes or words,...) that are x-ored with the message bits to produce the encrypted stream ( or call it the ciphertext). A stream cipher stores an internal state and updates it for the next output. They are also called state ciphers since the encryption depends on not only key and plaintext but also the state.

More formally; let $s$ be the state, $f$ is the next state function, $g$ is the function that produces the keystream $z_i$, and $h$ is the function that produce encryption of $m_i$ with the key stream $c_i$.

\begin{align} s_i &= f(s_i,k)\\ z_i &= f(s_i,k)\\ c_i &= h(z_i,m_i) \end{align}

Block Ciphers

A block cipher operates on blocks and more formally it is a family of permutations. We need a mode of operation to operate on data; CBC, CTR, GCM, etc... There is no stored information inside the block cipher and they are called memoryless ciphers.

More formally: A block cipher with $b$-bit block size is a family of permutations;

$$E:\{0,1\}^b \times \{0,1\}^k \to \{0,1\}^b$$ where each key $k\in \mathcal K$ selects a permutation form all permutations of $\{0,1\}^b$

We expect that this family of permutations forms a Pseudo-Random Permutation (PRP).

Block vs Stream

The distinction is not clear when a mode of operation like CTR mode turns a block cipher into a stream cipher (normally CTR mode is designed for PRF, not for PRP). One, however, can see the real distinction is that if a cipher designed as a stream cipher then it has internal states.

Paillier

Pailler is neither a block cipher nor a stream cipher, it is a public key system in which you need two keys; the public key and private key.

In the Paillier cryptosystem, the encryption of $m$, $0 \leq m < n$ is performed with a public key $(n,g)$ as $c=g^m r^n \bmod n$, where $r \stackrel{R}{\leftarrow}\mathbb{Z}_n^*$.

The message is recovered wiht the private key ($\lambda,\mu$) as $m = L(c^\lambda \bmod n^2) \cdot \mu \bmod n$ where $L = \dfrac{x-1}{n}$.

Long messages with Paillier

If you want to encrypt long messages for a target $A$ with Paillier, then you can divide it into parts where each has at most length $<n$ end encrypt each target with the public key of $A$ with a new random $\lambda$ per block. The problem is tracking the order of the parts. It can be achieved either externally or internally. Externally is clear, internally you must leave some space for the tacking. Still, I will not call this block cipher. Can CBC like encryption be performed, yes and keep in mind to not reuse the $\lambda$

Turning into a stream cipher is also possible but has dangerous paths. Consider using as CTR mode. You need to select a nonce and a counter and encrypt it and then x-or the block with the output. If you omit the generate a new $\lambda$ for each block, this is going to be a catastrophic failure.

Lack of

Still, there is no integrity and authenticity. The Paillier cryptosystem is malleable by design, remember public key encryption is free and the Paillier cryptosystem has additive and multiplicative properties. Therefore one needs at least HMAC.

Forget it

Remember, we don't use public-key cryptography for encryption, we prefer/advise using hybrid-cryptosystem like DHKE/AES-GCM. Public-key cryptography is slow compared to symmetric encryption. AES has tremendous speed with the hardware support and even GCM has, too. ChaCha20 is very fast even without hardware support. Stick to advice and use a hybrid cryptosystem.