Paper 2012/310

A mathematical problem for security analysis of hash functions and pseudorandom generators

Koji Nuida, Takuro Abe, Shizuo Kaji, Toshiaki Maeno, and Yasuhide Numata

Abstract

In this paper, we specify a class of mathematical problems, which we refer to as ``Function Density Problems'' (FDPs, in short), and point out novel connections of FDPs to the following two cryptographic topics; theoretical security evaluations of keyless hash functions (such as SHA-1), and constructions of provably secure pseudorandom generators (PRGs) with some enhanced security property introduced by Dubrov and Ishai [STOC 2006]. Our argument aims at proposing new theoretical frameworks for these topics (especially for the former) based on FDPs, rather than providing some concrete and practical results on the topics. We also give some examples of mathematical discussions on FDPs, which would be of independent interest from mathematical viewpoints. Finally, we discuss possible directions of future research on other cryptographic applications of FDPs and on mathematical studies on FDPs themselves.

Note: A preliminary version of this paper was presented at The 6th International Workshop on Security (IWSEC 2011), November 8-10, 2011

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown status
Keywords
foundationshash functionspseudo-randomnesscryptanalysis
Contact author(s)
k nuida @ aist go jp
History
2014-08-29: revised
2012-06-03: received
See all versions
Short URL
https://ia.cr/2012/310
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/310,
      author = {Koji Nuida and Takuro Abe and Shizuo Kaji and Toshiaki Maeno and Yasuhide Numata},
      title = {A mathematical problem for security analysis of hash functions and pseudorandom generators},
      howpublished = {Cryptology ePrint Archive, Paper 2012/310},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/310}},
      url = {https://eprint.iacr.org/2012/310}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.