1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Paillier is asymmetric encryption. Stream / block encryption is symmetric encryption . More to read : en.wikipedia.org/wiki/Paillier_cryptosystem $\endgroup$ – hardyrama Feb 5 at 5:36
  • $\begingroup$ Stream ciphers have the defining property that changing a bit of the plaintext changes a single bit of the ciphertext (or vice versa on decryption). By that test, is Pailler encryption a stream cipher? Hint for the second part: what is the maximum value that Pailler encryption can encipher while keeping it's distinguishing (homomorphic) property? What's the corresponding block size in bits? Can any plaintext of that size in bit be reversibly encrypted? $\endgroup$ – fgrieu Feb 5 at 6:49
  • $\begingroup$ @frgrieu According to your first statement, then yes it is a stream cipher. As far as I know the maximum number of bits you can encrypt or decrypt is equal to N. Ao if N is 1024 bits then I can encrypt 1024 bits of plaintext at a time. By this can we conclude that the size of bits to be encrypted at a time depends on the security key length? $\endgroup$ – Mimi Feb 5 at 9:17
  • $\begingroup$ @Hardyrama if its neither stream nor block then how is the encryption and decryption of data handled, abstractly speaking. $\endgroup$ – Mimi Feb 5 at 9:19
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – SEJPM Feb 6 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.