{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:58:03Z","timestamp":1781031483740,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["DE-SC0020264"],"award-info":[{"award-number":["DE-SC0020264"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800736","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"150-161","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Compressed Permutation Oracles"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2891-9436","authenticated-orcid":false,"given":"Joseph","family":"Carolan","sequence":"first","affiliation":[{"name":"University of Maryland at College Park, College Park, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Gorjan Alagic Chen Bai Alexander Poremba and Kaiyan Shi. 2023. On the Two-sided Permutation Inversion Problem. arxiv:2306.13729.","DOI":"10.62056\/a0qj89n4e"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Gorjan Alagic Joseph Carolan Christian Majenz and Saliha Tokat. 2025. The Sponge is Quantum Indifferentiable. Cryptology ePrint Archive Paper 2025\/731. https:\/\/eprint.iacr.org\/2025\/731","DOI":"10.1109\/FOCS63196.2025.00135"},{"key":"e_1_3_2_1_3_1","series-title":"Round 3","volume-title":"Cryptographic sponge functions. Submission to NIST","author":"Bertoni G.","unstructured":"G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche. 2011. Cryptographic sponge functions. Submission to NIST (Round 3). http:\/\/sponge.noekeon.org\/CSF-0.1.pdf"},{"key":"e_1_3_2_1_4_1","series-title":"Round 3","volume-title":"The Keccak SHA-3 submission. Submission to NIST","author":"Bertoni G.","unstructured":"G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche. 2011. The Keccak SHA-3 submission. Submission to NIST (Round 3). http:\/\/keccak.noekeon.org\/Keccak-submission-3.pdf"},{"key":"e_1_3_2_1_5_1","unstructured":"Guido Bertoni Joan Daemen Micha\u00ebl Peeters and Gilles van Assche. 2007. Sponge functions. In ECRYPT Hash Workhsop."},{"key":"e_1_3_2_1_6_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT","author":"Bertoni Guido","year":"2008","unstructured":"Guido Bertoni, Joan Daemen, Micha\u00ebl Peeters, and Gilles Van Assche. 2008. On the Indifferentiability of the Sponge Construction. In Advances in Cryptology \u2013 EUROCRYPT 2008, Nigel Smart (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 181\u2013197. isbn:978-3-540-78967-3"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-96-0947-5_8"},{"key":"e_1_3_2_1_8_1","volume-title":"Advances in Cryptology \u2013 ASIACRYPT","author":"Boneh Dan","year":"2011","unstructured":"Dan Boneh, \u00d6zg\u00fcr Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. 2011. Random Oracles in a Quantum World. In Advances in Cryptology \u2013 ASIACRYPT 2011, Dong Hoon Lee and Xiaoyun Wang (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 41\u201369. isbn:978-3-642-25385-0"},{"key":"e_1_3_2_1_9_1","volume-title":"Advances in Cryptology \u2013 CRYPTO","author":"Carolan Joseph","year":"2024","unstructured":"Joseph Carolan and Alexander Poremba. 2024. Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations. In Advances in Cryptology \u2013 CRYPTO 2024, Leonid Reyzin and Douglas Stebila (Eds.). Springer Nature Switzerland, Cham. 218\u2013252. isbn:978-3-031-68391-6"},{"key":"e_1_3_2_1_10_1","unstructured":"Joseph Carolan Alexander Poremba and Mark Zhandry. 2024. (Quantum) Indifferentiability and Pre-Computation. Cryptology ePrint Archive Paper 2024\/1727. https:\/\/eprint.iacr.org\/2024\/1727"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77886-6_21"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Alexandru Cojocaru Minki Hhan Qipeng Liu Takashi Yamakawa and Aaram Yun. 2025. Quantum Lifting for Invertible Permutations and Ideal Ciphers. Cryptology ePrint Archive Paper 2025\/738. https:\/\/eprint.iacr.org\/2025\/738","DOI":"10.1007\/978-3-032-01878-6_16"},{"key":"e_1_3_2_1_13_1","volume-title":"Andreas H\u00fclsing, Christian Schaffner, and Dominique Unruh.","author":"Czajkowski Jan","year":"2017","unstructured":"Jan Czajkowski, Leon Groot Bruinderink, Andreas H\u00fclsing, Christian Schaffner, and Dominique Unruh. 2017. Post-quantum security of the sponge construction. Cryptology ePrint Archive, Paper 2017\/771. https:\/\/eprint.iacr.org\/2017\/771"},{"key":"e_1_3_2_1_14_1","unstructured":"Jan Czajkowski Christian Majenz Christian Schaffner and Sebastian Zur. 2019. Quantum Lazy Sampling and Game-Playing Proofs for Quantum Indifferentiability. Cryptology ePrint Archive Paper 2019\/428. https:\/\/eprint.iacr.org\/2019\/428"},{"key":"e_1_3_2_1_15_1","unstructured":"Jelle Don Serge Fehr Christian Majenz and Christian Schaffner. 2021. Online-Extractability in the Quantum Random-Oracle Model. Cryptology ePrint Archive Paper 2021\/280. https:\/\/eprint.iacr.org\/2021\/280"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589986"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34578-5_6"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Akinori Hosoyamada and Kan Yasuda. 2018. Building Quantum-One-Way Functions from Block Ciphers: Davies-Meyer and Merkle-Damg\u00e5rd Constructions. Cryptology ePrint Archive Paper 2018\/841. https:\/\/eprint.iacr.org\/2018\/841","DOI":"10.1007\/978-3-030-03326-2_10"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-12612-4_20"},{"key":"e_1_3_2_1_20_1","volume-title":"Proc. IEEE International Symposium on Information Theory. IEEE, 2682\u20132685","author":"Kuwakado Hidenori","year":"2010","unstructured":"Hidenori Kuwakado and Masakatu Morii. 2010. Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In Proc. IEEE International Symposium on Information Theory. IEEE, 2682\u20132685."},{"key":"e_1_3_2_1_21_1","volume-title":"Advances in Cryptology \u2013 CRYPTO","author":"Lefevre Charlotte","year":"2022","unstructured":"Charlotte Lefevre and Bart Mennink. 2022. Tight Preimage Resistance of\u00a0the\u00a0Sponge Construction. In Advances in Cryptology \u2013 CRYPTO 2022, Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer Nature Switzerland, Cham. 185\u2013204. isbn:978-3-031-15985-5"},{"key":"e_1_3_2_1_22_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT","author":"Liu Qipeng","year":"2019","unstructured":"Qipeng Liu and Mark Zhandry. 2019. On Finding Quantum Multi-collisions. In Advances in Cryptology \u2013 EUROCRYPT 2019, Yuval Ishai and Vincent Rijmen (Eds.). Springer International Publishing, Cham. 189\u2013218. isbn:978-3-030-17659-4"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217022"},{"key":"e_1_3_2_1_24_1","unstructured":"Christian Majenz Giulio Malavolta and Michael Walter. 2024. Permutation Superposition Oracles for Quantum Query Lower Bounds. Cryptology ePrint Archive Paper 2024\/1140. https:\/\/eprint.iacr.org\/2024\/1140"},{"key":"e_1_3_2_1_25_1","volume-title":"Data Encryption Standard (DES)","author":"U.S. Department of Commerce National Institute of Standards. 1977.","unstructured":"U.S. Department of Commerce National Institute of Standards. 1977. Data Encryption Standard (DES). National Bureau of Standards, Washington, D.C.. https:\/\/csrc.nist.gov\/pubs\/fips\/46\/final"},{"key":"e_1_3_2_1_26_1","unstructured":"Ansis Rosmanis. 2022. Tight Bounds for Inverting Permutations via Compressed Oracle Arguments. arxiv:2103.08975."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58108-1_24"},{"key":"e_1_3_2_1_28_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT","author":"Unruh Dominique","year":"2014","unstructured":"Dominique Unruh. 2014. Revocable Quantum Timed-Release Encryption. In Advances in Cryptology \u2013 EUROCRYPT 2014, Phong Q. Nguyen and Elisabeth Oswald (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 129\u2013146. isbn:978-3-642-55220-5"},{"key":"e_1_3_2_1_29_1","unstructured":"Dominique Unruh. 2021. Compressed Permutation Oracles (And the Collision-Resistance of Sponge\/SHA3). Cryptology ePrint Archive Paper 2021\/062. https:\/\/eprint.iacr.org\/2021\/062"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-99-8730-6_12"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.1984.10027"},{"key":"e_1_3_2_1_32_1","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques. 568\u2013597","author":"Yamakawa Takashi","year":"2021","unstructured":"Takashi Yamakawa and Mark Zhandry. 2021. Classical vs quantum random oracles. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. 568\u2013597."},{"key":"e_1_3_2_1_33_1","unstructured":"Henry Yuen. 2013. A quantum lower bound for distinguishing random functions from random permutations. arxiv:1310.2885. arxiv:1310.2885"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.37"},{"key":"e_1_3_2_1_35_1","first-page":"7","article-title":"A Note on the Quantum Collision and Set Equality Problems. Quantum Info","volume":"15","author":"Zhandry Mark","year":"2015","unstructured":"Mark Zhandry. 2015. A Note on the Quantum Collision and Set Equality Problems. Quantum Info. Comput., 15, 7-8 (2015), May, 557\u2013567.","journal-title":"Comput."},{"key":"e_1_3_2_1_36_1","unstructured":"Mark Zhandry. 2016. A Note on Quantum-Secure PRPs. arxiv:1611.05564. arxiv:1611.05564"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26951-7_9"},{"key":"e_1_3_2_1_38_1","volume-title":"Advances in Cryptology \u2013 ASIACRYPT","author":"Zhandry Mark","year":"2021","unstructured":"Mark Zhandry. 2021. Redeeming Reset Indifferentiability and Applications to Post-quantum Security. In Advances in Cryptology \u2013 ASIACRYPT 2021, Mehdi Tibouchi and Huaxiong Wang (Eds.). Springer International Publishing, Cham. 518\u2013548. isbn:978-3-030-92062-3"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800736","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800736","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:06Z","timestamp":1781028306000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800736"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":38,"alternative-id":["10.1145\/3798129.3800736","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800736","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}