{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T04:24:10Z","timestamp":1691641450822},"reference-count":12,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2015,2]]},"abstract":"<jats:p>In this paper, we specify a class of mathematical problems, which we refer to as \u201cFunction Density Problems\u201d (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 crypto-graphic applications of FDPs and on mathematical studies on FDPs themselves.<\/jats:p>","DOI":"10.1142\/s0129054115500100","type":"journal-article","created":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T04:05:36Z","timestamp":1430885136000},"page":"169-194","source":"Crossref","is-referenced-by-count":1,"title":["A Mathematical Problem for Security Analysis of Hash Functions and Pseudorandom Generators"],"prefix":"10.1142","volume":"26","author":[{"given":"Koji","family":"Nuida","sequence":"first","affiliation":[{"name":"Research Institute for Secure Systems (RISEC), National Institute of Advanced Industrial Science and Technology (AIST), AIST Tsukuba Central 2, 1-1-1 Umezono, Tsukuba, Ibaraki 305-8568, Japan"}]},{"given":"Takuro","family":"Abe","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering and Science, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501, Japan"}]},{"given":"Shizuo","family":"Kaji","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Faculty of Science, Yamaguchi University, 1677-1 Yoshida, Yamaguchi-shi, Yamaguchi 753-8512, Japan"}]},{"given":"Toshiaki","family":"Maeno","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Meijo University, 1-501 Shiogama-guchi, Tenpaku-ku, Nagoya 468-8502, Japan"}]},{"given":"Yasuhide","family":"Numata","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Shinshu University, 3-1-1 Asahi, Matsumoto-shi, Nagano 390-8621, Japan"}]}],"member":"219","published-online":{"date-parts":[[2015,5,5]]},"reference":[{"key":"p_1","first-page":"235","author":"Blais E.","year":"2014","journal-title":"Part"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215025"},{"key":"p_3","first-page":"106","volume":"1977","author":"Carter J. L.","year":"1977","journal-title":"Proc. STOC"},{"key":"p_4","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1145\/1132516.1132615","volume":"2006","author":"Dubrov B.","year":"2006","journal-title":"Proc. STOC"},{"key":"p_5","first-page":"426","volume":"2007","author":"Farashahi R. R.","year":"2007","journal-title":"Proc. PKC"},{"key":"p_6","first-page":"1","volume":"11","author":"Henshall K.","journal-title":"Article"},{"key":"p_7","first-page":"419","volume":"1988","author":"Matsumoto T.","year":"1988","journal-title":"Proc. EUROCRYPT"},{"key":"p_8","first-page":"144","volume":"2011","author":"Nuida K.","year":"2011","journal-title":"Proc. IWSEC"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2216978"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"p_11","first-page":"211","volume":"2006","author":"Rogaway P.","year":"2006","journal-title":"Proc. VIETCRYPT"},{"key":"p_12","first-page":"17","volume":"2005","author":"Wang X.","year":"2005","journal-title":"Proc. CRYPTO"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/s0129054115500100","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T03:47:37Z","timestamp":1691639257000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/s0129054115500100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2]]},"references-count":12,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2015,5,5]]},"published-print":{"date-parts":[[2015,2]]}},"alternative-id":["10.1142\/s0129054115500100"],"URL":"https:\/\/doi.org\/10.1142\/s0129054115500100","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2]]}}}