{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T13:05:53Z","timestamp":1765112753604},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642320088"},{"type":"electronic","value":"9783642320095"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32009-5_5","type":"book-chapter","created":{"date-parts":[[2012,8,6]],"date-time":"2012-08-06T02:40:28Z","timestamp":1344220828000},"page":"68-85","source":"Crossref","is-referenced-by-count":14,"title":["Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs"],"prefix":"10.1007","author":[{"given":"Eric","family":"Miles","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Wigderson, A.: Algebrization: a new barrier in complexity theory. In: 40th ACM Symp. on the Theory of Computing, STOC, pp. 731\u2013740 (2008)","DOI":"10.1145\/1374376.1374481"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Allender, E., Kouck\u00fd, M.: Amplifying lower bounds by means of self-reducibility. J. of the ACM 57(3) (2010)","DOI":"10.1145\/1706591.1706594"},{"issue":"3","key":"5_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple constructions of almost \n                  \n                    \n                  \n                  $$k$$\n                -wise independent random variables. Random Structures & Algorithms 3(3), 289\u2013304 (1992)","journal-title":"Random Structures & Algorithms"},{"key":"5_CR4","unstructured":"Baker, T., Gill, J., Solovay, R.: Relativizations of the P=? NP question. SIAM J. Comput. 4(4), 431\u2013442 (1975)"},{"issue":"6","key":"5_CR5","doi-asserted-by":"publisher","first-page":"2220","DOI":"10.1137\/070691954","volume":"38","author":"LMJ Bazzi","year":"2009","unstructured":"Bazzi, L.M.J.: Polylogarithmic independence can fool DNF formulas. SIAM J. Comput. 38(6), 2220\u20132272 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF00630563","volume":"4","author":"E Biham","year":"1991","unstructured":"Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology 4(1), 3\u201372 (1991)","journal-title":"Journal of Cryptology"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Braverman, M.: Poly-logarithmic independence fools \n                  \n                    \n                  \n                  $$AC^0$$\n                 circuits. In: 24th IEEE Conf. on Computational Complexity, CCC. IEEE (2009)","DOI":"10.1109\/CCC.2009.35"},{"issue":"3","key":"5_CR8","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1002\/rsa.20194","volume":"32","author":"A Brodsky","year":"2008","unstructured":"Brodsky, A., Hoory, S.: Simple permutations mix even better. Random Struct. Algorithms 32(3), 274\u2013289 (2008)","journal-title":"Random Struct. Algorithms"},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/11496618_4","volume-title":"Information Security and Cryptology \u2013 ICISC 2004","author":"H.-S. Cho","year":"2005","unstructured":"Cho, H.-S., Sung, S.H., Kwon, D., Lee, J.-K., Song, J.H., Lim, J.: New Method for Bounding the Maximum Differential Probability for SPNs and ARIA. In: Park, C., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 21\u201332. Springer, Heidelberg (2005)"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer (2002)","DOI":"10.1007\/978-3-662-04722-4"},{"issue":"3","key":"5_CR11","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s001459900025","volume":"10","author":"S Even","year":"1997","unstructured":"Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptology 10(3), 151\u2013162 (1997)","journal-title":"J. Cryptology"},{"key":"5_CR12","unstructured":"Gao, S., von zur Gathen, J., Panario, D., Shoup, V.: Algorithms for exponentiation in finite fields. J. Symb. Comput. 29(6), 879\u2013889 (2000)"},{"key":"5_CR13","unstructured":"Gauravaram, P., Knudsen, L.R., Matusiewicz, K., Mendel, F., Rechberger, C., Schl\u00e4ffer, M., Thomsen, S.S.: Gr\u00f8stl: a SHA-3 candidate (2011), \n                  http:\/\/www.groestl.info"},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-540-30539-2_3","volume-title":"Advances in Cryptology - ASIACRYPT 2004","author":"C. Gentry","year":"2004","unstructured":"Gentry, C., Ramzan, Z.: Eliminating Random Permutation Oracles in the Even-Mansour Cipher. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 32\u201347. Springer, Heidelberg (2004)"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1090\/S0025-5718-1988-0917825-9","volume":"50","author":"A Gerasoulis","year":"1988","unstructured":"Gerasoulis, A.: A fast algorithm for the multiplication of generalized Hilbert matrices with vectors. Mathematics of Computation 50, 179\u2013188 (1988)","journal-title":"Mathematics of Computation"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press (2001)","DOI":"10.1017\/CBO9780511546891"},{"issue":"4","key":"5_CR17","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. of the ACM 33(4), 792\u2013807 (1986)","journal-title":"J. of the ACM"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.: A hard-core predicate for all one-way functions. In: 21st ACM Symp. on the Theory of Computing, STOC, pp. 25\u201332 (1989)","DOI":"10.1145\/73007.73010"},{"issue":"2","key":"5_CR19","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1017\/S0963548300001917","volume":"5","author":"W Gowers","year":"1996","unstructured":"Gowers, W.: An almost \n                  \n                    \n                  \n                  $$m$$\n                -wise independent random permutation of the cube. Combinatorics, Probability and Computing 5(2), 119\u2013130 (1996)","journal-title":"Combinatorics, Probability and Computing"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Haitner, I., Reingold, O., Vadhan, S.P.: Efficiency improvements in constructing pseudorandom generators from one-way functions. In: 42nd ACM Symp. on the Theory of Computing, STOC, pp. 437\u2013446 (2010)","DOI":"10.1145\/1806689.1806750"},{"issue":"4","key":"5_CR21","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"5_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1007\/11672142_55","volume-title":"STACS 2006","author":"A. Healy","year":"2006","unstructured":"Healy, A., Viola, E.: Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 672\u2013683. Springer, Heidelberg (2006)"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. System Sci. 65(4), 695\u2013716 (2002); Special issue on complexity, 2001 (Chicago, IL)","DOI":"10.1016\/S0022-0000(02)00025-9"},{"issue":"2-3","key":"5_CR24","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.tcs.2005.09.016","volume":"348","author":"S Hoory","year":"2005","unstructured":"Hoory, S., Magen, A., Myers, S., Rackoff, C.: Simple permutations mix well. Theor. Comput. Sci. 348(2-3), 251\u2013261 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/s00145-001-0003-x","volume":"14","author":"T Jakobsen","year":"2001","unstructured":"Jakobsen, T., Knudsen, L.: Attacks on block ciphers of low algebraic degree. Journal of Cryptology 14, 197\u2013210 (2001)","journal-title":"Journal of Cryptology"},{"issue":"4","key":"5_CR26","doi-asserted-by":"publisher","first-page":"158","DOI":"10.4218\/etrij.01.0101.0402","volume":"23","author":"JS Kang","year":"2001","unstructured":"Kang, J.S., Hong, S., Lee, S., Yi, O., Park, C., Lim, J.: Practical and provable security against differential and linear cryptanalysis for substitution-permutation networks. ETRI Journal 23(4), 158\u2013167 (2001)","journal-title":"ETRI Journal"},{"key":"5_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/3-540-44987-6_26","volume-title":"Advances in Cryptology - EUROCRYPT 2001","author":"L. Keliher","year":"2001","unstructured":"Keliher, L., Meijer, H., Tavares, S.: New Method for Upper Bounding the Maximum Average Linear Hull Probability for SPNs. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 420\u2013436. Springer, Heidelberg (2001)"},{"key":"5_CR28","series-title":"LNCS","first-page":"196","volume-title":"FSE 1994","author":"LR Knudsen","year":"1995","unstructured":"Knudsen, L.R.: Truncated and Higher Order Differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196\u2013211. Springer, Heidelberg (1995)"},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"Kopparty, S.: On the complexity of powering in finite fields. In: ACM Symp. on the Theory of Computing, STOC (2011)","DOI":"10.1145\/1993636.1993702"},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"issue":"2","key":"5_CR31","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0217022","volume":"17","author":"M Luby","year":"1988","unstructured":"Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373\u2013386 (1988)","journal-title":"SIAM J. Comput."},{"key":"5_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/3-540-48285-7_33","volume-title":"Advances in Cryptology - EUROCRYPT \u201993","author":"M. Matsui","year":"1994","unstructured":"Matsui, M.: Linear Cryptanalysis Method for DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386\u2013397. Springer, Heidelberg (1994)"},{"issue":"4","key":"5_CR33","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput. 22(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5_CR34","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/PL00003817","volume":"12","author":"M Naor","year":"1999","unstructured":"Naor, M., Reingold, O.: On the construction of pseudorandom permutations: Luby-Rackoff revisited. J. Cryptology 12(1), 29\u201366 (1999)","journal-title":"J. Cryptology"},{"issue":"2","key":"5_CR35","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/972639.972643","volume":"51","author":"M Naor","year":"2004","unstructured":"Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. J. of the ACM 51(2), 231\u2013262 (2004)","journal-title":"J. of the ACM"},{"key":"5_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-48285-7_6","volume-title":"Advances in Cryptology - EUROCRYPT \u201993","author":"K. Nyberg","year":"1994","unstructured":"Nyberg, K.: Differentially Uniform Mappings for Cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55\u201364. Springer, Heidelberg (1994)"},{"key":"5_CR37","unstructured":"Pieprzyk, J.: On bent permutations. In: Proceedings of the International Conference on Finite Fields, Coding Theory, and Advances in Communications and Computing, Las Vegas (August 1991)"},{"key":"5_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/3-540-44598-6_24","volume-title":"Advances in Cryptology - CRYPTO 2000","author":"Z. Ramzan","year":"2000","unstructured":"Ramzan, Z., Reyzin, L.: On the Round Security of Symmetric-Key Cryptographic Primitives. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 376\u2013393. Springer, Heidelberg (2000)"},{"issue":"1","key":"5_CR39","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A Razborov","year":"1997","unstructured":"Razborov, A., Rudich, S.: Natural proofs. J. of Computer and System Sciences 55(1), 24\u201335 (1997)","journal-title":"J. of Computer and System Sciences"},{"key":"5_CR40","doi-asserted-by":"crossref","unstructured":"Razborov, A.A.: A simple proof of Bazzi\u2019s theorem. ACM Transactions on Computation Theory (TOCT) 1(1) (2009)","DOI":"10.1145\/1490270.1490273"},{"key":"5_CR41","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1109\/TIT.1985.1057113","volume":"31","author":"RM Roth","year":"1985","unstructured":"Roth, R.M., Seroussi, G.: On generator matrices of MDS codes. IEEE Transactions on Information Theory 31, 826\u2013830 (1985)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"4","key":"5_CR42","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1002\/j.1538-7305.1949.tb00928.x","volume":"28","author":"C Shannon","year":"1949","unstructured":"Shannon, C.: Communication theory of secrecy systems. Bell Systems Technical Journal 28(4), 656\u2013715 (1949)","journal-title":"Bell Systems Technical Journal"},{"key":"5_CR43","doi-asserted-by":"crossref","unstructured":"Vadhan, S.P., Zheng, C.J.: Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In: ACM Symp. on the Theory of Computing, STOC  (2012)","DOI":"10.1145\/2213977.2214051"},{"key":"5_CR44","doi-asserted-by":"crossref","unstructured":"Williams, R.: Non-uniform ACC lower bounds. In: IEEE Conf. on Computational Complexity, CCC (2011)","DOI":"10.1109\/CCC.2011.36"},{"key":"5_CR45","unstructured":"Wu, H.: The hash function JH (2011), \n                  http:\/\/www3.ntu.edu.sg\/home\/wuhj\/research\/jh\/index.html"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32009-5_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T18:48:06Z","timestamp":1557168486000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32009-5_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642320088","9783642320095"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32009-5_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}