×

A mathematical problem for security analysis of hash functions and pseudorandom generators. (English) Zbl 1344.94067

Iwata, Tetsu (ed.) et al., Advances in information and computer security. 6th international workshop, IWSEC 2011, Tokyo, Japan, November 8–10, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25140-5/pbk). Lecture Notes in Computer Science 7038, 144-160 (2011).
Summary: The aim of this paper is to emphasize the significance of a certain mathematical problem in research on information security. We point out that the mathematical problem, which we refer to as “Function Density Problem,” has connections to the following two major cryptographic topics; security analysis of hash functions in the real world (like SHA-1), and construction of pseudorandom generators with some enhanced security property. We also provide a first example to show how a study of Function Density Problem can contribute to the progress of the above-mentioned two topics. Other potential applications of Function Density Problem to information security are also discussed.
For the entire collection see [Zbl 1225.68019].

MSC:

94A60 Cryptography
65C10 Random number generation in numerical analysis
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Blum, L., Blum, M., Shub, M.: A simple unpredictable pseudo-random number generator. SIAM J. Comput. 15, 364–383 (1986) · Zbl 0602.65002 · doi:10.1137/0215025
[2] Carter, J.L., Wegman, M.N.: Universal classes of hash functions (extended abstract). In: Proc. STOC 1977, pp. 106–112 (1977) · doi:10.1145/800105.803400
[3] Dubrov, B., Ishai, Y.: On the randomness complexity of efficient sampling. In: Proc. STOC 2006, pp. 711–720 (2006) · Zbl 1301.68261 · doi:10.1145/1132516.1132615
[4] Farashahi, R.R., Schoenmakers, B., Sidorenko, A.: Efficient Pseudorandom Generators Based on the DDH Assumption. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 426–441. Springer, Heidelberg (2007) · Zbl 1161.65305 · doi:10.1007/978-3-540-71677-8_28
[5] Matsumoto, T., Imai, H.: Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988) · Zbl 0655.94013 · doi:10.1007/3-540-45961-8_39
[6] Nuida, K., Hanaoka, G.: On the Security of Pseudorandomized Information-Theoretically Secure Schemes. In: Kurosawa, K. (ed.) ICITS 2009. LNCS, vol. 5973, pp. 56–73. Springer, Heidelberg (2010) · Zbl 1282.94061 · doi:10.1007/978-3-642-14496-7_6
[7] Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978) · Zbl 0368.94005 · doi:10.1145/359340.359342
[8] Rogaway, P.: Formalizing human ignorance – collision-resistant hashing without the keys. In: Nguyên, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 211–228. Springer, Heidelberg (2006) · Zbl 1295.94138 · doi:10.1007/11958239_14
[9] Wang, X., Yin, Y.L., Yu, H.: Finding Collisions in the Full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005) · Zbl 1145.94454 · doi:10.1007/11535218_2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.