On the Security of Pseudorandomized Information-Theoretically Secure Schemes

Koji Nuida; Goichiro Hanaoka

Paper 2010/329

On the Security of Pseudorandomized Information-Theoretically Secure Schemes

Koji Nuida and Goichiro Hanaoka

Abstract

In this article, we discuss a naive method of randomness reduction for cryptographic schemes, which replaces the required perfect randomness with output distribution of a computationally secure pseudorandom generator (PRG). We propose novel ideas and techniques for evaluating the indistinguishability between the random and pseudorandom cases, even against an adversary with computationally unbounded attack algorithm. Hence the PRG-based randomness reduction can be effective even for information-theoretically secure cryptographic schemes, especially when the amount of information received by the adversary is small. In comparison to a preceding result of Dubrov and Ishai (STOC 2006), our result removes the requirement of generalized notion of ``nb-PRGs'' and is effective for more general kinds of protocols. We give some numerical examples to show the effectiveness of our result in practical situations, and we also propose a further idea for improving the effect of the PRG-based randomness reduction.

Note: This article is the mergence of two preliminary versions of this work presented at The 4th International Conference on Information Theoretic Security (ICITS 2009), Shizuoka, Japan, December 3--6, 2009. (version 2) The overall organization of the paper is revised

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. IEEE Transactions on Information Theory, vol.59, no.1 (2013) 635-652
Keywords: foundations pseudo-randomness information-theoretic security
Contact author(s): k nuida @ aist go jp
History: 2013-01-21: last of 2 revisions; 2010-06-04: received; See all versions
Short URL: https://ia.cr/2010/329
License: CC BY

BibTeX

@misc{cryptoeprint:2010/329,
      author = {Koji Nuida and Goichiro Hanaoka},
      title = {On the Security of Pseudorandomized Information-Theoretically Secure Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2010/329},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/329}},
      url = {https://eprint.iacr.org/2010/329}
}