{"id":"arxiv/2609.28469","url":"https://arxiv.org/abs/2609.28469","tags":["quant-ph"],"score":0,"title":"Compressed Permutation Oracles Revisited","domain":"quant-ph","source":"arxiv","authors":["Joseph Carolan","Christian Majenz"],"reviews":0,"subject":"quant-ph","summary":"The compressed permutation oracle has been used to analyze the quantum security of a number of cryptographic constructions which resisted prior techniques. However, these analyses were fundamentally limited by the poor soundness of the method: the technique was proven sound only up to $O(N^{1/12})$ queries to permutations on $N$ elements. We revisit this analysis, improving the soundness bound to a tight $Ω(N^{1/2})$. In addition to being tighter, our proof is conceptually simpler and more direct, and gives the same bound in the ideal cipher model. The main technical idea is to construct the…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{}}