Paper 2018/718

Cryptographic Pseudorandom Generators Can Make Cryptosystems Problematic

Koji Nuida


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.

Note: Merged with the content of Report 2016/1040; the original title was "Keeping or Losing Tiny-Error Correctness of Cryptosystems Implemented by Secure Pseudorandom Generators"

Available format(s)
Publication info
Published by the IACR in PKC 2021
Contact author(s)
nuida @ mist i u-tokyo ac jp
2021-02-24: revised
2018-08-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Koji Nuida},
      title = {Cryptographic Pseudorandom Generators Can Make Cryptosystems Problematic},
      howpublished = {Cryptology ePrint Archive, Paper 2018/718},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.