Cryptographic Pseudorandom Generators Can Make Cryptosystems Problematic

Abstract

Randomness is an essential resource for cryptography. For practical randomness generation, the security notion of pseudorandom generators (PRGs) intends to automatically preserve (computational) security of cryptosystems when used in implementation. Nevertheless, some opposite case such as in computational randomness extractors (Barak et al., CRYPTO 2011) is known (but not yet systematically studied so far) where the security can be lost even by applying secure PRGs. The present paper aims at pushing ahead the observation and understanding about such a phenomenon; we reveal such situations at layers of primitives and protocols as well, not just of building blocks like randomness extractors. We present three typical types of such cases: (1) adversaries can legally see the seed of the PRGs (including the case of randomness extractors); (2) the set of “bad” randomness may be not efficiently recognizable; (3) the formulation of a desired property implicitly involves non-uniform distinguishers for PRGs. We point out that the semi-honest security of multiparty computation also belongs to Type 1, while the correctness with negligible decryption error probability for public key encryption belongs to Types 2 and 3. We construct examples for each type where a secure PRG (against uniform distinguishers only, for Type 3) does not preserve the security/correctness of the original scheme; and discuss some countermeasures to avoid such an issue.

A A “Natural” Variant of Algorithm 1

Here we give a “natural” variant of 2PC protocol $\pi _1$ defined in Sect. 3.2 (Algorithm 1) where the inputs for two parties are not correlated and the parties have outputs in the protocol. The modified protocol is given in Algorithm 9. Here $\mathcal {F}_{\mathsf {EQ}}$ denotes an ideal functionality for two-party equality test, where the common output $\beta = 1$ (respectively, $\beta = 0$) means that the two inputs are equal (respectively, not equal).

In the part of the protocol before executing $\pi _1$, the two parties check if their inputs satisfy the required conditions in the original protocol $\pi _1$. More precisely, first, the input (p, q) for $\mathcal {P}_2$ in $\pi _1$ should satisfy that $p < q$, p and q are primes, and $p \equiv q \equiv 3 \pmod {4}$. In the protocol here, $\mathcal {P}_2$ first checks if these conditions hold, and if it fails then the protocol halts at this step. Secondly, assuming the conditions for $\mathcal {P}_2$’s input, the input N for $\mathcal {P}_1$ should satisfy that $N = pq$. This condition is checked by using $\mathcal {F}_{\mathsf {EQ}}$, and if it fails then the protocol halts at this step. Once these conditions have been verified, the parties can execute the protocol $\pi _1$ with the correct input pair. By focusing on the input pairs satisfying the conditions in $\pi _1$, the protocol here inherits from $\pi _1$ the property that the security will be lost by applying a certain secure PRG to the randomness for $\mathcal {P}_1$.

For the security against $\mathcal {P}_1$, if the output is $\iota = 2$, then $\mathcal {P}_1$ receives no message and hence the security holds trivially. If $\iota = 1$, then $\mathcal {P}_1$ just participates in the execution of $\mathcal {F}_{\mathsf {EQ}}$ and obtains the output $\beta = 0$, therefore the security follows from the security of $\mathcal {F}_{\mathsf {EQ}}$. Finally, if $\iota = 0$, then $\mathcal {P}_1$ participates in the execution of $\mathcal {F}_{\mathsf {EQ}}$ with output being always $\beta = 1$ and also participates in $\pi _1$, therefore the security also follows from the security of $\mathcal {F}_{\mathsf {EQ}}$ and $\pi _1$.

For the sake of completeness, we describe in Algorithm 10 a well-known implementation of $\mathcal {F}_{\mathsf {EQ}}$ using the lifted-ElGamal cryptosystem. Here $\boxplus$ and $\boxdot$ denote the homomorphic addition and homomorphic scalar multiplication, respectively. We analyze the behavior of the protocol as follows:

• If $x_1 = x_2$, then the ciphertext c in the protocol is a random ciphertext of plaintext $r (x_2 - r_1) = 0$ (note that the randomness in c has also been perfectly rerandomized, as a random ciphertext $\mathsf {Enc}(0)$ was homomorphically added). Hence the protocol outputs the correct value $\beta = 1$, and now the message received by $\mathcal {P}_1$ is a random ciphertext $\mathsf {Enc}(0)$ as mentioned above, which can be perfectly simulated.

• If $x_1 \ne x_2$, then $x_2 - x_1 \in (\mathbb {F}_P)^{\times }$ by the property $P > 2^{2\lambda + 1}$, while $r \leftarrow _R (\mathbb {F}_P)^{\times }$. Therefore the plaintext $r (x_2 - x_1)$ for c is also uniformly random over $(\mathbb {F}_P)^{\times }$ and hence the protocol outputs the correct value $\beta = 0$ (note that, though $r (x_2 - x_1)$ can be large and the lifted-ElGamal cryptosystem enables to efficiently decrypt small plaintexts only, the protocol just checks if the ciphertext c has plaintext 0 or not, which is still efficiently checkable). Moreover, in this case, the received message c is a random ciphertext for a uniformly random non-zero plaintext, which can be perfectly simulated.

Hence the correctness and the security (against $\mathcal {P}_1$) of the implemented $\mathcal {F}_{\mathsf {EQ}}$ have been verified. In particular, the security against $\mathcal {P}_1$ is information-theoretic. Therefore, as well as the original protocol $\pi _1$, the variant of $\pi _1$ given here also has information-theoretic security against $\mathcal {P}_1$, as desired.