{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T18:09:51Z","timestamp":1771610991076,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,12,25]],"date-time":"2008-12-25T00:00:00Z","timestamp":1230163200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,9]]},"DOI":"10.1007\/s00453-008-9267-y","type":"journal-article","created":{"date-parts":[[2009,1,5]],"date-time":"2009-01-05T18:17:58Z","timestamp":1231179478000},"page":"113-133","source":"Crossref","is-referenced-by-count":40,"title":["Derandomized Constructions of k-Wise (Almost) Independent Permutations"],"prefix":"10.1007","volume":"55","author":[{"given":"Eyal","family":"Kaplan","sequence":"first","affiliation":[]},{"given":"Moni","family":"Naor","sequence":"additional","affiliation":[]},{"given":"Omer","family":"Reingold","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,12,25]]},"reference":[{"key":"9267_CR1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1080\/00029890.1986.11971821","volume":"93","author":"D. Aldous","year":"1986","unstructured":"Aldous, D., Diaconis, P.: Shuffling cards and stopping times. Am. Math. Mon. 93, 333\u2013348 (1986)","journal-title":"Am. Math. Mon."},{"key":"9267_CR2","unstructured":"Aldous, D., Fill, J.A.: Reversible Markov chains and random walks on graphs. http:\/\/www.stat.berkeley.edu\/users\/aldous\/RWG\/book.html"},{"key":"9267_CR3","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York (1992)"},{"issue":"2","key":"9267_CR4","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/PL00009813","volume":"18","author":"Y. Azar","year":"1998","unstructured":"Azar, Y., Motwani, R., Naor, J.: Approximating probability distributions using small sample spaces. Combinatorica 18(2), 151\u2013171 (1998)","journal-title":"Combinatorica"},{"issue":"5","key":"9267_CR5","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1023\/A:1024632031440","volume":"9","author":"A. Bar-Noy","year":"2003","unstructured":"Bar-Noy, A., Naor, J., Schieber, B.: Pushing dependent data in clients-providers-servers systems. Wirel. Netw. 9(5), 421\u2013430 (2003)","journal-title":"Wirel. Netw."},{"key":"9267_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/3-540-45760-7_9","volume-title":"Topics in Cryptology\u2014CT-RSA 2002","author":"J. Black","year":"2002","unstructured":"Black, J., Rogaway, P.: Ciphers with arbitrary finite domains. In: Topics in Cryptology\u2014CT-RSA 2002. Lecture Notes in Computer Science, vol. 2271, pp. 114\u2013130. Springer, Berlin (2002)"},{"issue":"3","key":"9267_CR7","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1006\/jcss.1999.1690","volume":"60","author":"A.Z. Broder","year":"2000","unstructured":"Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-wise independent permutations. J.\u00a0Comput. Syst. Sci. 60(3), 630\u2013659 (2000) (preliminary version STOC 2000)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9267_CR8","first-page":"1157","volume":"29","author":"A.Z. Broder","year":"1997","unstructured":"Broder, A.Z., Glassman, S.C., Manasse, M.S., Zweig, G.: Syntactic clustering of the Web. Comput. Netw. 29, 1157\u20131166 (1997)","journal-title":"Comput. Netw."},{"issue":"3","key":"9267_CR9","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1002\/rsa.20194","volume":"32","author":"A. Brodsky","year":"2007","unstructured":"Brodsky, A., Hoory, S.: Simple permutations mix even better. Random Struct. Algorithms 32(3), 274\u2013289 (2007). Arxiv:math.CO\/0411098","journal-title":"Random Struct. Algorithms"},{"key":"9267_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1112\/blms\/13.1.1","volume":"13","author":"P.J. Cameron","year":"1981","unstructured":"Cameron, P.J.: Finite permutation groups and finite simple groups. Bull. Lond. Math. Soc. 13, 1\u201322 (1981)","journal-title":"Bull. Lond. Math. Soc."},{"key":"9267_CR11","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Woelfel, P.: Almost random graphs with simple hash functions. In: Proc. of the 35th Annual ACM Symposium on Theory of Computing, pp.\u00a0629\u2013638 (2003)","DOI":"10.1145\/780542.780634"},{"key":"9267_CR12","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., Strauss, M.: Fast, small-space algorithms for approximate histogram maintenance. In: Proc. of the 34th Annual ACM Symposium on Theory of Computing, pp.\u00a0389\u2013398 (2002)","DOI":"10.1145\/509907.509966"},{"key":"9267_CR13","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Nussboim, A.: On the implementation of huge random objects. In: Proc. of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a068\u201379 (2003)","DOI":"10.1109\/SFCS.2003.1238182"},{"issue":"2","key":"9267_CR14","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1017\/S0963548300001917","volume":"5","author":"W.T. Gowers","year":"1996","unstructured":"Gowers, W.T.: An almost m-wise independent random permutation of the cube. Comb. Probab. Comput. 5(2), 119\u2013130 (1996)","journal-title":"Comb. Probab. Comput."},{"key":"9267_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1007\/978-3-540-27836-8_65","volume-title":"The 31st International Colloquium on Automata, Languages and Programming (ICALP)","author":"S. Hoory","year":"2004","unstructured":"Hoory, S., Magen, A., Myers, S., Rackoff, C.: Simple permutations mix well. In: The 31st International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 3142, pp. 770\u2013781. Springer, Berlin (2004)"},{"key":"9267_CR16","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings and data stream computation. In: Proc. of the 41st Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0189\u2013197 (2000)","DOI":"10.1109\/SFCS.2000.892082"},{"key":"9267_CR17","unstructured":"Itoh, T., Takei, Y., Tarui, J.: On permutations with limited independence. In: Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0137\u2013146 (2000)"},{"key":"9267_CR18","doi-asserted-by":"crossref","unstructured":"Itoh, T., Takei, Y., Tarui, J.: On the sample size of k-restricted min-wise independent permutations and other k-wise distributions. In: Proc. of the 35th Annual ACM Symposium on Theory of Computing, pp.\u00a0710\u2013719 (2003)","DOI":"10.1145\/780542.780645"},{"key":"9267_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/11538462_30","volume-title":"The 9th International Workshop on Randomization and Computation (RANDOM)","author":"E. Kaplan","year":"2005","unstructured":"Kaplan, E., Naor, M., Reingold, O.: Derandomized constructions of k-wise (almost) independent permutations. In: The 9th International Workshop on Randomization and Computation (RANDOM). Lecture Notes in Computer Science, vol. 3624, pp. 354\u2013365. Springer, Berlin (2005)"},{"key":"9267_CR20","unstructured":"Kassabov, M.: Symmetric groups and expanders. arXiv:math.GR\/0503204"},{"issue":"2","key":"9267_CR21","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1137\/S0895480192228140","volume":"7","author":"D. Koller","year":"1994","unstructured":"Koller, D., Megiddo, N.: Constructing small sample spaces satisfying given constraints. SIAM J. Discrete Math. 7(2), 260\u2013274 (1994)","journal-title":"SIAM J. Discrete Math."},{"key":"9267_CR22","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1137\/0217022","volume":"17","author":"M. Luby","year":"1988","unstructured":"Luby, M., Rackoff, C.: How to construct pseudorandom permutations and pseudorandom functions. SIAM J. Comput. 17, 373\u2013386 (1988)","journal-title":"SIAM J. Comput."},{"key":"9267_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1007\/3-540-39200-9_34","volume-title":"Advances in Cryptology\u2014EUROCRPYT \u20192003","author":"U.M. Maurer","year":"2003","unstructured":"Maurer, U.M., Pietrzak, K.: The security of many-round Luby\u2013Rackoff pseudo-random permutations. In: Advances in Cryptology\u2014EUROCRPYT \u20192003. Lecture Notes in Computer Science, vol. 2656, pp. 544\u2013561. Springer, Berlin (2003)"},{"key":"9267_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/978-3-540-24638-1_23","volume-title":"First Theory of Cryptography Conference, TCC 2004","author":"U.M. Maurer","year":"2004","unstructured":"Maurer, U.M., Pietrzak, K.: Composition of random systems: when two weak make one strong. In: First Theory of Cryptography Conference, TCC 2004. Lecture Notes in Computer Science, vol. 2951, pp. 410\u2013427. Springer, Berlin (2004)"},{"key":"9267_CR25","doi-asserted-by":"crossref","unstructured":"Morris, B.: On the mixing time for the Thorp shuffle. In: Proc. of the 37th Annual ACM Symposium on Theory of Computing, pp. 403\u2013412 (2005)","DOI":"10.1145\/1060590.1060651"},{"key":"9267_CR26","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"key":"9267_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/978-3-540-24676-3_12","volume-title":"Advances in Cryptology\u2014EUROCRYPT \u20192004","author":"S. Myers","year":"2004","unstructured":"Myers, S.: Black-box composition does not imply adaptive security. In: Advances in Cryptology\u2014EUROCRYPT \u20192004. Lecture Notes in Computer Science, vol. 3027, pp. 189\u2013203. Springer, Berlin (2004)"},{"issue":"1","key":"9267_CR28","doi-asserted-by":"crossref","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\u2013Rackoff revisited. J. Cryptol. 12(1), 29\u201366 (1999)","journal-title":"J. Cryptol."},{"issue":"4","key":"9267_CR29","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica 12(4), 449\u2013461 (1992)","journal-title":"Combinatorica"},{"issue":"1","key":"9267_CR30","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"N. Nisan","year":"1996","unstructured":"Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Comput. Syst. Sci. 52(1), 43\u201352 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"9267_CR31","doi-asserted-by":"crossref","unstructured":"Ostlin, A., Pagh, R.: Uniform hashing in constant time and linear space. In: Proc. of the 35th Annual ACM Symposium on Theory of Computing, pp. 622\u2013628 (2003)","DOI":"10.1145\/780542.780633"},{"key":"9267_CR32","doi-asserted-by":"crossref","unstructured":"Patarin, J.: Improved security bounds for pseudorandom permutations. In: Proc. of the 4th ACM Conference on Computer and Communications Security, pp.\u00a0142\u2013150 (1997)","DOI":"10.1145\/266420.266452"},{"key":"9267_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/978-3-540-45146-4_30","volume-title":"Advances in Cryptology\u2014CRYPTO 2003","author":"J. Patarin","year":"2003","unstructured":"Patarin, J.: Luby\u2013Rackoff: 7 rounds are enough for 2 n(1\u2212\u03b5 ) security. In: Advances in Cryptology\u2014CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729, pp. 513\u2013529. Springer, Berlin (2003)"},{"key":"9267_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/978-3-540-28628-8_7","volume-title":"Advances in Cryptology\u2014CRYPTO \u20192004","author":"J. Patarin","year":"2004","unstructured":"Patarin, J.: Security of random Feistel schemes with 5 or more rounds. In: Advances in Cryptology\u2014CRYPTO \u20192004. Lecture Notes in Computer Science, vol. 3152, pp. 106\u2013122. Springer, Berlin (2004)"},{"key":"9267_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/11535218_4","volume-title":"Advances in Cryptology\u2014CRYPTO \u20192005","author":"K. Pietrzak","year":"2005","unstructured":"Pietrzak, K.: Composition does not imply adaptive security. In: Advances in Cryptology\u2014CRYPTO \u20192005. Lecture Notes in Computer Science, vol. 3621, pp. 55\u201365. Springer, Berlin (2005)"},{"key":"9267_CR36","unstructured":"Pinkas, B.: Communication preserving cryptographic protocols. Ph.D. dissertation, Weizmann Institute of Science (1999)"},{"key":"9267_CR37","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected ST-connectivity in log-space. In: Proc. of the 37th Annual ACM Symposium on Theory of Computing, pp.\u00a0376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"},{"key":"9267_CR38","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.: Pseudorandom walks in biregular graphs and the RL vs. L\u00a0problem. In: Proc. of the 38th Annual ACM Symposium on Theory of Computing, pp.\u00a0457\u2013466 (2006)","DOI":"10.1145\/1132516.1132583"},{"key":"9267_CR39","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-8594-1","volume-title":"A Course in the Theory of Groups","author":"D.J.S. Robinson","year":"1996","unstructured":"Robinson, D.J.S.: A Course in the Theory of Groups, 2nd edn. Springer, New York (1996)","edition":"2"},{"key":"9267_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1007\/11538462_37","volume-title":"The 9th International Workshop on Randomization and Computation (RANDOM)","author":"E. Rozenman","year":"2005","unstructured":"Rozenman, E., Vadhan, S.: Derandomized squaring of graphs. In: The 9th International Workshop on Randomization and Computation (RANDOM). Lecture Notes in Computer Science, vol. 3624, pp. 436\u2013447. Springer, Berlin (2005)"},{"key":"9267_CR41","unstructured":"Rudich, S.: Limits on the provable consequences of one-way functions. Ph.D. thesis, U.C. Berkeley (1988)"},{"key":"9267_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/3-540-46035-7_9","volume-title":"Advances in Cryptology\u2014EUROCRYPT \u20192002","author":"A. Russell","year":"2002","unstructured":"Russell, A., Wang, H.: How to fool an unbounded adversary with a short key. In: Advances in Cryptology\u2014EUROCRYPT \u20192002. Lecture Notes in Computer Science, vol. 2332, pp. 133\u2013148. Springer, Berlin (2002)"},{"key":"9267_CR43","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0020-0190(99)00163-5","volume":"73","author":"M. Saks","year":"2000","unstructured":"Saks, M., Srinivasan, A., Zhou, S., Zuckerman, D.: Low discrepancy sets yield approximate min-wise independent permutation families. Inf. Process. Lett. 73, 29\u201332 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9267_CR44","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/S0097539701386216","volume":"33","author":"A. Siegel","year":"2004","unstructured":"Siegel, A.: On universal classes of extremely random constant-time hash functions. SIAM J. Comput. 33(3), 505\u2013543 (2004)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9267_CR45","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1017\/S0963548300000390","volume":"1","author":"A. Sinclair","year":"1992","unstructured":"Sinclair, A.: Improved bounds for mixing rates of Markov chains and multicommodity flow. Comb. Probab. Comput. 1(4), 351\u2013370 (1992)","journal-title":"Comb. Probab. Comput."},{"key":"9267_CR46","doi-asserted-by":"crossref","unstructured":"Sivakumar, D.: Algorithmic derandomization via complexity theory. In: Proc. of the 34th Annual ACM Symposium on Theory of Computing, pp.\u00a0619\u2013626 (2002)","DOI":"10.1145\/509907.509996"},{"key":"9267_CR47","doi-asserted-by":"crossref","first-page":"842","DOI":"10.1080\/01621459.1973.10481434","volume":"68","author":"E. Thorp","year":"1973","unstructured":"Thorp, E.: Nonrandom shuffling with applications to the game of Faro. J. Am. Stat. Assoc. 68, 842\u2013847 (1973)","journal-title":"J. Am. Stat. Assoc."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9267-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9267-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9267-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T19:32:50Z","timestamp":1738870370000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9267-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,25]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["9267"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9267-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12,25]]}}}