{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T09:29:57Z","timestamp":1768901397354,"version":"3.49.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032018540","type":"print"},{"value":"9783032018557","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-032-01855-7_21","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T19:41:35Z","timestamp":1755373295000},"page":"651-678","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Pseudorandomness Properties of\u00a0Random Reversible Circuits"],"prefix":"10.1007","author":[{"given":"William","family":"Gay","sequence":"first","affiliation":[]},{"given":"William","family":"He","sequence":"additional","affiliation":[]},{"given":"Nicholas","family":"Kocurek","sequence":"additional","affiliation":[]},{"given":"Ryan","family":"O\u2019Donnell","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Arad, I., Landau, Z., Vazirani, U.: The Detectability Lemma and Quantum Gap Amplification. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. pp. 417\u2013426 (2009)","DOI":"10.1145\/1536414.1536472"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s00220-016-2706-8","volume":"346","author":"FG Brandao","year":"2016","unstructured":"Brandao, F.G., Harrow, A.W., Horodecki, M.: Local random quantum circuits are approximate polynomial-designs. Commun. Math. Phys. 346, 397\u2013434 (2016)","journal-title":"Commun. Math. Phys."},{"issue":"3","key":"21_CR3","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":"21_CR4","doi-asserted-by":"crossref","unstructured":"Chen, C.F., Docter, J., Xu, M., Bouland, A., Hayden, P.: Efficient Unitary T-designs from Random Sums. arXiv preprint arXiv:2402.09335 (2024)","DOI":"10.1109\/FOCS61266.2024.00037"},{"key":"21_CR5","unstructured":"Chen, C.F., Haah, J., Haferkamp, J., Liu, Y., Metger, T., Tan, X.: Incompressibility and spectral gaps of random circuits. arXiv preprint arXiv:2406.07478 (2024)"},{"issue":"1","key":"21_CR6","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.80.012304","volume":"80","author":"C Dankert","year":"2009","unstructured":"Dankert, C., Cleve, R., Emerson, J., Livine, E.: Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A-Atomic, Molecul. Opt. Phys. 80(1), 012304 (2009)","journal-title":"Phys. Rev. A-Atomic, Molecul. Opt. Phys."},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Feng, X., Ippoliti, M.: Dynamics of pseudoentanglement. arXiv preprint arXiv:2403.09619 (2024)","DOI":"10.1007\/JHEP02(2025)128"},{"issue":"2","key":"21_CR8","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1017\/S0963548300001917","volume":"5","author":"W Gowers","year":"1996","unstructured":"Gowers, W.: An almost m-wise independent random permutation of the cube. Combinatorics, Probability Comput. 5(2), 119\u2013130 (1996)","journal-title":"Combinatorics, Probability Comput."},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Gretta, L., He, W., Pelecanos, A.: More efficient approximate $$ k $$-wise independent permutations from random reversible circuits via log-sobolev inequalities. Cryptology ePrint Archive (2024)","DOI":"10.1137\/1.9781611978322.191"},{"issue":"2","key":"21_CR10","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.104.022417","volume":"104","author":"J Haferkamp","year":"2021","unstructured":"Haferkamp, J., Hunter-Jones, N.: Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions. Phys. Rev. A 104(2), 022417 (2021)","journal-title":"Phys. Rev. A"},{"issue":"3","key":"21_CR11","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1007\/s00220-022-04507-6","volume":"397","author":"J Haferkamp","year":"2023","unstructured":"Haferkamp, J., Montealegre-Mora, F., Heinrich, M., Eisert, J., Gross, D., Roth, I.: Efficient unitary designs with a system-size independent number of non-clifford gates. Commun. Math. Phys. 397(3), 995\u20131041 (2023)","journal-title":"Commun. Math. Phys."},{"issue":"2","key":"21_CR12","doi-asserted-by":"publisher","first-page":"1531","DOI":"10.1007\/s00220-023-04675-z","volume":"401","author":"AW Harrow","year":"2023","unstructured":"Harrow, A.W., Mehraban, S.: Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates. Commun. Math. Phys. 401(2), 1531\u20131626 (2023)","journal-title":"Commun. Math. Phys."},{"issue":"09","key":"21_CR13","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1088\/1126-6708\/2007\/09\/120","volume":"2007","author":"P Hayden","year":"2007","unstructured":"Hayden, P., Preskill, J.: Black holes as mirrors: quantum information in random subsystems. J. High Energy Phys. 2007(09), 120 (2007)","journal-title":"J. High Energy Phys."},{"issue":"2\u20133","key":"21_CR14","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. Theoret. Comput. Sci. 348(2\u20133), 251\u2013261 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"10","key":"21_CR15","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1038\/s41567-020-0932-7","volume":"16","author":"HY Huang","year":"2020","unstructured":"Huang, H.Y., Kueng, R., Preskill, J.: Predicting many properties of a quantum system from very few measurements. Nat. Phys. 16(10), 1050\u20131057 (2020)","journal-title":"Nat. Phys."},{"key":"21_CR16","unstructured":"Hunter-Jones, N.: Unitary Designs from Statistical Mechanics in Random Quantum Circuits. arXiv preprint arXiv:1905.12053 (2019)"},{"issue":"1","key":"21_CR17","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00453-008-9267-y","volume":"55","author":"E Kaplan","year":"2009","unstructured":"Kaplan, E., Naor, M., Reingold, O.: Derandomized constructions of k-wise (almost) independent permutations. Algorithmica 55(1), 113\u2013133 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"21_CR18","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00222-007-0065-y","volume":"170","author":"M Kassabov","year":"2007","unstructured":"Kassabov, M.: Symmetric groups and expander graphs. Invent. Math. 170(2), 327\u2013354 (2007)","journal-title":"Invent. Math."},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Liu, T., Pelecanos, A., Tessaro, S., Vaikuntanathan, V.: Layout graphs, random walks and the t-wise independence of SPN block ciphers. In: Annual International Cryptology Conference, pp. 694\u2013726. Springer (2023)","DOI":"10.1007\/978-3-031-38548-3_23"},{"key":"21_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/978-3-030-84259-8_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"T Liu","year":"2021","unstructured":"Liu, T., Tessaro, S., Vaikuntanathan, V.: The t-wise independence of\u00a0substitution-permutation networks. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 454\u2013483. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84259-8_16"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Ma, F., Huang, H.Y.: How to construct random unitaries. arXiv preprint arXiv:2410.10116 (2024)","DOI":"10.1145\/3717823.3718254"},{"key":"21_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/978-3-540-24638-1_23","volume-title":"Theory of Cryptography","author":"U Maurer","year":"2004","unstructured":"Maurer, U., Pietrzak, K.: Composition of random systems: when two weak make one strong. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 410\u2013427. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24638-1_23"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Metger, T., Poremba, A., Sinha, M., Yuen, H.: Simple constructions of linear-depth t-designs and pseudorandom unitaries. arXiv preprint arXiv:2404.12647 (2024)","DOI":"10.1109\/FOCS61266.2024.00038"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Mohanty, S., O\u2019Donnell, R., Paredes, P.: Explicit near-ramanujan graphs of every degree. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 510\u2013523 (2020)","DOI":"10.1145\/3357713.3384231"},{"key":"21_CR25","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/BF02099509","volume":"175","author":"B Nachtergaele","year":"1996","unstructured":"Nachtergaele, B.: The spectral gap for some spin chains with discrete symmetry breaking. Commun. Math. Phys. 175, 565\u2013606 (1996)","journal-title":"Commun. Math. Phys."},{"key":"21_CR26","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press (2014)"},{"key":"21_CR27","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Servedio, R.A., Paredes, P.: Explicit orthogonal and unitary designs. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1240\u20131260. IEEE (2023)","DOI":"10.1109\/FOCS57990.2023.00073"},{"issue":"5","key":"21_CR28","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/41\/5\/055308","volume":"41","author":"AJ Scott","year":"2008","unstructured":"Scott, A.J.: Optimizing quantum process tomography with unitary 2-designs. J. Phys. A: Math. Theoret. 41(5), 055308 (2008)","journal-title":"J. Phys. A: Math. Theoret."},{"key":"21_CR29","unstructured":"Wilmer, E., Levin, D.A., Peres, Y.: Markov Chains and Mixing Times. American Mathematical Soc., Providence (2009)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-01855-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T19:21:44Z","timestamp":1768850504000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01855-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783032018540","9783032018557"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01855-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"17 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}