{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:24:13Z","timestamp":1760235853897,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T00:00:00Z","timestamp":1632960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61632013","61972370"],"award-info":[{"award-number":["61632013","61972370"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fundamental Research Funds for Central Universities in China","award":["WK3480000007"],"award-info":[{"award-number":["WK3480000007"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In CRYPTO 2019, Chen et al. showed how to construct pseudorandom functions (PRFs) from random permutations (RPs), and they gave one beyond-birthday secure construction from sum of Even-Mansour, namely SoEM22 in the single-key setting. In this paper, we improve their work by proving the multi-key security of SoEM22, and further tweaking SoEM22 but still preserving beyond birthday bound (BBB) security. Furthermore, we use only one random permutation to construct parallelizable and succinct beyond-birthday secure PRFs in the multi-key setting, and then tweak this new construction. Moreover, with a slight modification of our constructions of tweakable PRFs, two parallelizable nonce based MACs for variable length messages are obtained.<\/jats:p>","DOI":"10.3390\/e23101296","type":"journal-article","created":{"date-parts":[[2021,10,1]],"date-time":"2021-10-01T10:55:40Z","timestamp":1633085740000},"page":"1296","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Constructions of Beyond-Birthday Secure PRFs from Random Permutations, Revisited"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7630-6802","authenticated-orcid":false,"given":"Jiehui","family":"Nan","sequence":"first","affiliation":[{"name":"Key Laboratory of Electromagnetic Space Information, Chinese Academy of Sciences, School of Information Science and Technology, University of Science and Technology of China, Hefei 230027, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ping","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Honggang","family":"Hu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Electromagnetic Space Information, Chinese Academy of Sciences, School of Information Science and Technology, University of Science and Technology of China, Hefei 230027, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,9,30]]},"reference":[{"key":"ref_1","first-page":"191","article-title":"Chaos-based true random number generators","volume":"7","author":"Bonilla","year":"2016","journal-title":"J. Math. Ind."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.tcs.2020.08.014","article-title":"A new quantum random number generator certified by value indefiniteness","volume":"862","author":"Trejo","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","article-title":"How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits","volume":"13","author":"Blum","year":"1984","journal-title":"SIAM J. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C. (1982, January 3\u20135). Theory and Applications of Trapdoor Functions. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), Chicago, IL, USA.","DOI":"10.1109\/SFCS.1982.45"},{"key":"ref_5","unstructured":"Goldreich, O., Goldwasser, S., and Micali, S. (1984, January 24\u201326). How to Construct Random Functions. Proceedings of the 25th Annual Symposium onFoundations of Computer Science, Singer Island, FL, USA."},{"key":"ref_6","first-page":"12","article-title":"Construction of a Pseudo-Random Generator From Any One-Way Function","volume":"28","author":"Impagliazzo","year":"1993","journal-title":"SIAM J. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1383","DOI":"10.1137\/S0097539701389257","article-title":"Pseudorandom Functions and Factoring","volume":"31","author":"Naor","year":"2002","journal-title":"SIAM J. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1145\/972639.972643","article-title":"Number-theoretic constructions of efficient pseudo-random functions","volume":"51","author":"Naor","year":"2004","journal-title":"J. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1007\/978-3-642-29011-4_42","article-title":"Pseudorandom Functions and Lattices","volume":"Volume 7237","author":"Pointcheval","year":"2012","journal-title":"Advances in Cryptology\u2014EUROCRYPT 2012"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/978-3-642-40041-4_23","article-title":"Key Homomorphic PRFs and Their Applications","volume":"Volume 8042","author":"Canetti","year":"2013","journal-title":"Advances in Cryptology\u2014CRYPTO 2013, Part I"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/978-3-662-44371-2_20","article-title":"New and Improved Key-Homomorphic Pseudorandom Functions","volume":"Volume 8616","author":"Garay","year":"2014","journal-title":"Advances in Cryptology\u2014CRYPTO 2014, Part I"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/BFb0054132","article-title":"Luby-Rackoff Backwards: Increasing Security by Making Block Ciphers Non-invertible","volume":"Volume 1403","author":"Nyberg","year":"1998","journal-title":"Advances in Cryptology\u2014EUROCRYPT\u201998"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-3-662-53018-4_5","article-title":"EWCDM: An Efficient, Beyond-Birthday Secure, Nonce-Misuse Resistant MAC","volume":"Volume 9814","author":"Robshaw","year":"2016","journal-title":"Advances in Cryptology\u2014CRYPTO 2016, Part I"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1007\/978-3-319-63697-9_19","article-title":"Encrypted Davies-Meyer and Its Dual: Towards Optimal Security Using Mirror Theory","volume":"Volume 10403","author":"Katz","year":"2017","journal-title":"Advances in Cryptology\u2014CRYPTO 2017, Part III"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/978-3-030-26948-7_10","article-title":"How to Build Pseudorandom Functions from Public Random Permutations","volume":"Volume 11692","author":"Boldyreva","year":"2019","journal-title":"Advances in Cryptology\u2014CRYPTO 2019, Part I"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/978-3-662-47989-6_9","article-title":"Tweaking Even-Mansour Ciphers","volume":"Volume 9215","author":"Gennaro","year":"2015","journal-title":"Advances in Cryptology\u2014CRYPTO 2015, Part I"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1007\/978-3-030-64837-4_20","article-title":"Minimizing the Two-Round Tweakable Even-Mansour Cipher","volume":"Volume 12491","author":"Moriai","year":"2020","journal-title":"Advances in Cryptology\u2014ASIACRYPT 2020, Part I"},{"key":"ref_18","first-page":"1","article-title":"On the Composition of Single-Keyed Tweakable Even-Mansour for Achieving BBB Security","volume":"2020","author":"Chakraborti","year":"2020","journal-title":"IACR Trans. Symm. Cryptol."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"31","DOI":"10.46586\/tosc.v2021.i2.31-70","article-title":"Permutation Based EDM: An Inverse Free BBB Secure PRF","volume":"2021","author":"Dutta","year":"2021","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/978-3-642-55220-5_19","article-title":"Tight Security Bounds for Key-Alternating Ciphers","volume":"Volume 8441","author":"Nguyen","year":"2014","journal-title":"Advances in Cryptology\u2014EUROCRYPT 2014"},{"key":"ref_21","first-page":"328","article-title":"The \u201cCoefficients H\u201d Technique (Invited Talk)","volume":"Volume 5381","author":"Avanzi","year":"2009","journal-title":"Selected Areas in Cryptography. SAC 2008"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/978-3-662-44371-2_3","article-title":"Minimizing the Two-Round Even-Mansour Cipher","volume":"Volume 8616","author":"Garay","year":"2014","journal-title":"Advances in Cryptology\u2014CRYPTO 2014, Part I"},{"key":"ref_23","first-page":"391","article-title":"Building Blockcipher from Tweakable Blockcipher: Extending FSE 2009 Proposal","volume":"Volume 7089","author":"Chen","year":"2011","journal-title":"Processings of 13th IMA International Conference on Cryptography and Coding (IMACC 2011)"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/10\/1296\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:08:14Z","timestamp":1760166494000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/10\/1296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,30]]},"references-count":23,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2021,10]]}},"alternative-id":["e23101296"],"URL":"https:\/\/doi.org\/10.3390\/e23101296","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,9,30]]}}}