Cryptology ePrint Archive: Report 2018/718

Keeping or Losing Tiny-Error Correctness of Cryptosystems Implemented by Secure Pseudorandom Generators

Koji Nuida

Abstract: Randomness is essential but expensive resource for cryptography, and secure (and efficient) implementations of randomness using pseudorandom generators (PRGs) are much concerned in this area. On the other hand, implementations of randomness without losing the correctness of the underlying cryptosystem should be important but seem to be less concerned in the literature. The results in this paper show that the problem of the correct implementation of randomness in cryptosystems is in general non-trivial even by using secure PRGs. Namely, we construct two examples with the following properties:

- There are a secure and correct public key encryption (PKE) scheme (with negligible decryption error probability) and a secure PRG satisfying that, implementing the key generation algorithm by using the PRG makes the scheme incorrect. The reason of this phenomenon is that, the standard formulation of correctness of PKE schemes does in general not imply that erroneous keys (that yield non-negligible decryption error probability for some plaintext) are efficiently detectable.

- There are a secure and correct PKE scheme and a PRG secure against uniform distinguishers, satisfying that, implementing the encryption algorithm by using the PRG makes the scheme incorrect. The reason of this phenomenon is that, when a PKE scheme is incorrect, a plaintext that yields non-negligible decryption error probability is in general not efficiently samplable by a uniform algorithm; hence security of the PRG against non-uniform distinguishers is required. We also discuss a possibility to avoid the reliance on PRGs secure against non-uniform distinguishers.

Category / Keywords: foundations / foundations, implementation, pseudo-randomness

Date: received 1 Aug 2018

Contact author: nuida at mist i u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Version: 20180801:195336 (All versions of this report)

Short URL: ia.cr/2018/718


[ Cryptology ePrint archive ]