{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:58:23Z","timestamp":1778065103706,"version":"3.51.4"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2015,12,10]],"date-time":"2015-12-10T00:00:00Z","timestamp":1449705600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0845003"],"award-info":[{"award-number":["CCF-0845003"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,12,10]]},"abstract":"<jats:p>This article takes a new step towards closing the gap between pseudorandom functions (PRF) and their popular, bounded-input-length counterparts. This gap is both quantitative, because these counterparts are more efficient than PRF in various ways, and methodological, because these counterparts usually fit in the substitution-permutation network paradigm (SPN), which has not been used to construct PRF.<\/jats:p>\n          <jats:p>\n            We give several candidate PRF\n            <jats:italic>\n              F\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            that are inspired by the SPN paradigm. Most of our candidates are more efficient than previous ones. Our main candidates are as follows.\n          <\/jats:p>\n          <jats:p>\n            \u2014\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            : {0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u2192 {0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            is an SPN whose S-box is a random function on\n            <jats:italic>b<\/jats:italic>\n            bits given as part of the seed. We prove that\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            resists attacks that run in time \u2264 2\n            <jats:italic>\n              <jats:sup>\u03f5b<\/jats:sup>\n            <\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            \u2014\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            : {0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u2192 {0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            is an SPN where the S-box is (patched) field inversion, a common choice in practical constructions. We show that\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            is computable with boolean circuits of size\n            <jats:italic>n<\/jats:italic>\n            \u22c5 log\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            and that it has exponential security 2\n            <jats:sup>\n              \u03a9(\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            against linear and differential cryptanalysis.\n          <\/jats:p>\n          <jats:p>\n            \u2014\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>3<\/jats:sub>\n            : {0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u2192 {0,1} is a nonstandard variant on the SPN paradigm, where \u201cstates\u201d grow in length. We show that\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>3<\/jats:sub>\n            is computable with TC\n            <jats:sup>0<\/jats:sup>\n            circuits of size\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1 + \u03f5<\/jats:sup>\n            , for any \u03f5 &gt; 0, and that it is almost 3-wise independent.\n          <\/jats:p>\n          <jats:p>\n            \u2014\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>4<\/jats:sub>\n            : {0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u2192 {0,1} uses an extreme setting of the SPN parameters (one round, one S-box, no diffusion matrix). The S-box is again (patched) field inversion. We show that\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>4<\/jats:sub>\n            is computable by circuits of size\n            <jats:italic>n<\/jats:italic>\n            \u22c5 log\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            and that it fools all parity tests on \u22642\n            <jats:sup>\n              0.9\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            outputs.\n          <\/jats:p>\n          <jats:p>\n            Assuming the security of our candidates, our work narrows the gap between the Natural Proofs barrier and existing lower bounds in three models: circuits, TC\n            <jats:sup>0<\/jats:sup>\n            circuits, and Turing machines.\n          <\/jats:p>","DOI":"10.1145\/2792978","type":"journal-article","created":{"date-parts":[[2015,12,14]],"date-time":"2015-12-14T14:19:41Z","timestamp":1450102781000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs"],"prefix":"10.1145","volume":"62","author":[{"given":"Eric","family":"Miles","sequence":"first","affiliation":[{"name":"Northeastern University, Los Angeles, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,12,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554821"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706594"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040109"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00359-4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44371-2_20"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_42"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/070691954"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1694"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00630563"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.35"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v32:3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496618_4"},{"key":"e_1_2_1_15_1","unstructured":"Joan Daemen. 1995. Cipher and hash function design strategies based on linear and differential cryptanalysis. Ph.D. Dissertation K.U. Leuven Leuven Flanders Belgium.  Joan Daemen. 1995. Cipher and hash function design strategies based on linear and differential cryptanalysis. Ph.D. Dissertation K.U. Leuven Leuven Flanders Belgium."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Joan Daemen and Vincent Rijmen. 2002. The Design of Rijndael: AES - The Advanced Encryption Standard. Springer Verlag New York Inc. Secaucus NJ.   Joan Daemen and Vincent Rijmen. 2002. The Design of Rijndael: AES - The Advanced Encryption Standard. Springer Verlag New York Inc. Secaucus NJ.","DOI":"10.1007\/978-3-662-04722-4_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900025"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2270275"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1999.0309"},{"key":"e_1_2_1_20_1","unstructured":"Praveen Gauravaram Lars R. Knudsen Krystian Matusiewicz Florian Mendel Christian Rechberger Martin Schl\u00e4ffer and S\u00f8ren S. Thomsen. 2011. Gr\u00f8stl: A SHA-3 candidate. http:\/\/www.groestl.info.  Praveen Gauravaram Lars R. Knudsen Krystian Matusiewicz Florian Mendel Christian Rechberger Martin Schl\u00e4ffer and S\u00f8ren S. Thomsen. 2011. Gr\u00f8stl: A SHA-3 candidate. http:\/\/www.groestl.info."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30539-2_3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1988-0917825-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Oded Goldreich. 2001. Foundations of Cryptography: Volume 1. Cambridge University Press New York NY.   Oded Goldreich. 2001. Foundations of Cryptography: Volume 1. Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511546891"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001917"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806750"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_55"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00025-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.016"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-001-0003-x"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4218\/etrij.01.0101.0402"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology (EUROCRYPT'01)","author":"Keliher Liam"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 2nd Internatinal Workshop on Fast Software Encryption (FSE). 196--211","author":"Knudsen Lars R.","year":"1994"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993702"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press New York NY.   Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217022"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/188307.188366"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_5"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00003817"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972643"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389257"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology (EUROCRYPT'93)","author":"Nyberg Kaisa","year":"1993"},{"key":"e_1_2_1_46_1","series-title":"Lecture Notes in Pure and Applied Math","volume-title":"Proceedings of the International Conference on Finite Fields, Coding Theory, and Advances in Communications and Computing","author":"Pieprzyk Josef"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/646765.704113"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490273"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057113"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb00928.x"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214051"},{"key":"e_1_2_1_53_1","unstructured":"Joachim von zur Gathen and J\u00fcrgen Gerhard. 2003. Modern Computer Algebra (2nd ed.). Cambridge University Press New York NY.   Joachim von zur Gathen and J\u00fcrgen Gerhard. 2003. Modern Computer Algebra (2nd ed.). Cambridge University Press New York NY."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.36"},{"key":"e_1_2_1_55_1","unstructured":"Hongjun Wu. 2011. The hash function JH. http:\/\/www3.ntu.edu.sg\/home\/wuhj\/research\/jh\/index.html.  Hongjun Wu. 2011. The hash function JH. http:\/\/www3.ntu.edu.sg\/home\/wuhj\/research\/jh\/index.html."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2792978","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2792978","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2792978","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:34Z","timestamp":1750223254000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2792978"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,10]]},"references-count":55,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,12,10]]}},"alternative-id":["10.1145\/2792978"],"URL":"https:\/\/doi.org\/10.1145\/2792978","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,10]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}