Owing to their simple and efficient design, permutation-based pseudorandom functions (PRFs) are widely adopted in modern cryptography. In the classical setting, single permutation PRFs typically provide about n/2 bit security, while double permutation variants achieve about 2n/3 bit security. This paper investigates the security of permutation-based PRFs in the Q1 model and proposes a quantum key recovery framework with improved hardware feasibility. To address the high quantum memory cost of existing Grover-meets-Simon attacks, we introduce a Grover-meets-BV approach based on Walsh spectrum sampling using the Bernstein–Vazirani procedure. Our method achieves a substantial constant factor reduction in quantum memory by reducing the qubit footprint of the core verification module from <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$u+n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>u</mi> <mo>+</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> to <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$u+1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>u</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, which nearly halves the leading qubit term in coherent parallel verifiers. It also improves robustness under incorrect Grover guesses by suppressing uninformative zero vector outputs, thereby reducing verifier repetition in the noise regime. These gains yield a more favorable multi-dimensional resource profile, with lower peak memory and improved space-time efficiency, while preserving the asymptotic time-data trade-offs of prior hybrid attacks. Concretely, our framework recovers single permutation PRF keys with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\tilde{O}(2^{n/3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi>O</mi> <mo stretchy="false">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> time and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(2^{n/3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> data complexity. For double permutation PRFs, we exploit internal linear periods and hidden shifts to achieve <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\tilde{O}(2^{2n/3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi>O</mi> <mo stretchy="false">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow> <mn>2</mn> <mi>n</mi> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> time complexity. Applications to XopEM, DS-SoEM, EDMEM, and PDMMAC illustrate improved practicality compared to prior Grover-meets-Simon approaches.

Resource-efficient Grover-meets-BV Q1 attacks on permutation-based pseudorandom functions

期刊论文
发表日期：

2026年7月2日

查看全文

Jia-Wen Zhou,
Bao-Min Zhou,
Long Zhang,
Ke-Jia Zhang

摘要

Owing to their simple and efficient design, permutation-based pseudorandom functions (PRFs) are widely adopted in modern cryptography. In the classical setting, single permutation PRFs typically provide about n/2 bit security, while double permutation variants achieve about 2n/3 bit security. This paper investigates the security of permutation-based PRFs in the Q1 model and proposes a quantum key recovery framework with improved hardware feasibility. To address the high quantum memory cost of existing Grover-meets-Simon attacks, we introduce a Grover-meets-BV approach based on Walsh spectrum sampling using the Bernstein–Vazirani procedure. Our method achieves a substantial constant factor reduction in quantum memory by reducing the qubit footprint of the core verification module from $u+n$ $u + n$ to $u+1$ $u + 1$ , which nearly halves the leading qubit term in coherent parallel verifiers. It also improves robustness under incorrect Grover guesses by suppressing uninformative zero vector outputs, thereby reducing verifier repetition in the noise regime. These gains yield a more favorable multi-dimensional resource profile, with lower peak memory and improved space-time efficiency, while preserving the asymptotic time-data trade-offs of prior hybrid attacks. Concretely, our framework recovers single permutation PRF keys with $\tilde{O}(2^{n/3})$ $\tilde{O} (2^{n / 3})$ time and $O(2^{n/3})$ $O (2^{n / 3})$ data complexity. For double permutation PRFs, we exploit internal linear periods and hidden shifts to achieve $\tilde{O}(2^{2n/3})$ $\tilde{O} (2^{2 n / 3})$ time complexity. Applications to XopEM, DS-SoEM, EDMEM, and PDMMAC illustrate improved practicality compared to prior Grover-meets-Simon approaches.