Cryptographic Pseudorandom Generators Can Make Cryptosystems Problematic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2021 - 24th IACR International Conference on Practice and Theory of Public Key Cryptography, 2021, Proceedings
EditorsJuan A. Garay
PublisherSpringer Science and Business Media Deutschland GmbH
Pages441-468
Number of pages28
ISBN (Print)9783030752477
DOIs
Publication statusPublished - 2021
Event24th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2021 - Virtual, Online
Duration: May 10 2021May 13 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12711 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2021
CityVirtual, Online
Period5/10/215/13/21

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Cryptographic Pseudorandom Generators Can Make Cryptosystems Problematic'. Together they form a unique fingerprint.

Cite this