{"id":"e0a179dd-0d0d-4649-bb1d-a5a14d5d2d28","arxiv_id":"2510.14475","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"By separating XOR-type functions into secret and public halves, quantum key-recovery on TPP-PRF block cipher constructions becomes offline and reduces Q2 oracle queries from O(2^{(n+t)/2}(n-t)) to O(2^t(n-t)).","lead":"An offline quantum attack is proposed that breaks several block-cipher constructions built from two parallel permutations (SoEM22, XopEM, SUMPIP, DS-SoEM) using far fewer queries to the encryption oracle than previous dedicated attacks. The trick is to split each periodic function into a secret part and a public part, so most of the quantum search runs after the online queries are done.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Generic TPP-PRF claim in Theorem 4/Eq.(8) assumes l_{ij} maps preserve the high/low bit split; for arbitrary GF(2)-linear maps F_L is aperiodic, so only identity-map instantiations (XopEM/SoEM22/SUMPIP/DS-SoEM) are supported.","rationale":"The paper's headline result is an offline dedicated attack on constructions based on TPP-PRFs, culminating in Theorem 4 and Eq. (8). The load-bearing step is the truncation argument: after summing over the low subspace L, the claimed hidden period s^l must survive in the high bits. For the concrete instantiations XopEM, SoEM22, SUMPIP, and DS-SoEM, the relevant linear maps are identity (or simple domain separation), and the period does survive because low-bit shifts can be absorbed by reindexing the sum over L. However, the paper states the result for generic TPP-PRFs, where l_{ij} are arbitrary nonzero linear maps. In that setting, the periodicity of the truncated F_L requires l23(s^l∥0^t)∈l23(L) (and analogously for l13); for any invertible l23 that mixes high and low bits this forces s^l=0, so the attack's central test oracle would not detect the correct key. This is not a mere technical gap in the proof: it is a concrete failure of the claimed period property for a generic linear map. The reader's weakest_assumption identifies exactly this truncation/linear-map compatibility issue, and I agree that it is the most load-bearing concern. A second, smaller concern is the Q1 full-key-recovery statement: recovering the remaining t bits by an additional offline Simon step would add O(2^n) classical queries, which is not accounted for in the balanced O~(2^{(2n-t)/3}) complexity if full key recovery is meant. The paper should either restrict the generic claim to l_{ij} that act blockwise on the high/low split, or prove the affine-subspace condition and state the resulting restricted class. With that restriction, the concrete attacks on SoEM22/XopEM/SUMPIP/DS-SoEM remain plausible and the query-complexity improvement over Shi et al. is real. Therefore the verdict should remain CONDITIONAL rather than ACCEPT or REJECT: the broad claim needs revision, but the central technique is not invalidated for the named instantiations.","tokens_in":18182,"tokens_out":24811,"duration_ms":185522,"concrete_test":"Take n=4, t=2. Let l23 be the invertible 4×4 binary matrix swapping coordinates 1 and 3 (so l23(L)≠L), and set l13=l33=l34=identity, l14=identity. Pick random permutations P1,P2 and keys k1,k2 with s=k1 and s^l≠0. Compute F_L(i0^l,x^l)=⊕_{u∈L} [P1((x^l∥00⊕u)⊕k1)⊕P1(x^l∥00⊕u)⊕P2((x^l⊕k2^l)∥00⊕u)⊕P2((x^l∥00⊕u)⊕k2)] for both x^l values and compare F_L(x^l) with F_L(x^l⊕s^l). Eq. (8)/Theorem 4 predicts equality; the affine-subspace calculation predicts inequality for generic P2. Repeat for 10 random P2; any inequality falsifies the generic claim.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Eq. (6) defines TPP-PRFs with nonzero linear maps l_{ij}; Eq. (7) then sets p(i,x)=l34P2(l23(x⊕i)). The truncation in Section III-B1 sums over L={0^{n-t}∥*}. For the claimed period s^l to survive, one needs, for B(x^l)=⊕_{u∈L} P2(l23(x^l∥u)), B(x^l⊕s^l)=B(x^l) under the correct key. Since P2 is a random permutation, this holds only if the affine subspaces l23((x^l∥L)) and l23((x^l⊕s^l)∥L) coincide, i.e. l23(s^l∥0^t)∈l23(L). For invertible l23 this forces s^l=0. The same condition arises for l13 in the P1 terms. Thus Eq. (8)'s derivation silently assumes l23(s^l∥0^t)∈L, i.e. that l_{ij} act blockwise (scaled identity) on the high/low split. Without this, F_L has no nonzero period, Algorithm 4 cannot recover i^l_0, and Theorem 4 is unsupported for generic TPP-PRFs. The concrete XopEM/SoEM22/SUMPIP/DS-SoEM instantiations use identity maps and remain plausible; the broad claim does not. Separately, the Q1 full-key-recovery remark would add O(2^n) classical queries for the remaining t bits, conflicting with the balanced O~(2^{(2n-t)/3}) figure if a full key recovery is claimed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes offline dedicated quantum key-recovery attacks on block cipher constructions built from two parallel permutation-based pseudorandom functions (TPP-PRFs). It first identifies PolyMAC as a new instance vulnerable to the online dedicated attack of Shi et al., then introduces a 'decoupled' p-XOR-type function and presents Algorithm 4, an offline dedicated attack that uses truncation. The claimed results are: in the Q2 model, encryption-oracle query complexity O(2^t(n-t)) instead of O(2^{(n+t)/2}(n-t)); in the Q1 model, a query/time tradeoff T^2 D = 2^{2n-t} balancing at O~(2^{(2n-t)/3}). Concrete instantiations XopEM, SoEM22, SUMPIP, and DS-SoEM are treated, and Theorem 4 is stated for generic decoupled XOR-type functions.","tokens_in":18707,"tokens_out":40996,"duration_ms":290022,"significance":"If the generic claim were fully established, the paper would answer an open question of Shi et al. and improve on both the online dedicated attack and the Q1 results of Sun et al. The offline-separation idea and the concrete identity-map instantiations are genuinely interesting, and the reported Q2 query reduction for SoEM22 and related schemes is plausible. However, the paper's central generic derivation for TPP-PRFs rests on an unstated blockwise-linearity assumption, and the full-key Q1 complexity claim is not supported by the stated algorithms. These issues are load-bearing and need correction before the contribution can be evaluated as claimed.","major_comments":[{"comment":"The derivation of the period of F^L assumes that the n-bit linear maps l13, l23, l14, l24 act blockwise on the p/(n-t-p)/t decomposition. Expressions such as '(l13 y ⊕ l14 k^{l1}_1)∥l14 k^{l2}_1∥0^t' and 'j^{l2} = l13^{-1}l14 k^{l2}_1' are only meaningful if these maps are block-diagonal; for an arbitrary invertible GF(2)-linear map, applying it to a split input mixes the components, and the displayed equality in the lines following Eq. (8) does not follow. In particular, the period condition requires the middle part of the vector s = l13^{-1}l14(k1), which equals l13^{-1}l14(k1^{l2}) only under a blockwise assumption. The same issue affects i^l = l23^{-1}l24 k^l_2. Thus Theorem 4 is not established for generic TPP-PRFs; the supported cases are those where the l maps are identity or at least blockwise on the chosen split.","section":"Section III-B1, Eq. (8)"},{"comment":"The paper claims that the remaining t-bit key can be recovered by applying the offline Simon algorithm, and the abstract/conclusion state a balanced O~(2^{(2n-t)/3}) classical-query complexity. In the Q1 model, however, running offline Simon on the full n-bit function would require O(2^n) classical queries to prepare the necessary superposition, which dominates O~(2^{(2n-t)/3}). Theorem 4's bound is only for recovering the high (kappa-t) bits (and the period). If the authors intend only partial-key recovery, the abstract and conclusion should say so; if they claim full-key recovery, the stated complexity is incorrect.","section":"Section III-B2, after Theorem 4"},{"comment":"The PolyMAC formula uses undefined notation 'k2_1' and 'k2_3', and the claimed period relation s=(k1⊕k3)(β0⊕β1) with α_i=k1(β0⊕β1) or k3(β0⊕β1) is not derivable from the displayed equation as written. Since PolyMAC is presented as the first new instance answering Shi et al.'s open question, this is a load-bearing part of the paper and must be corrected and expanded with a clear definition of the scheme.","section":"Section III-A1, Eq. (3)"}],"minor_comments":[{"comment":"The domain of F^L is given as {0,1}^{n-t} × {0,1}^{n-t-p} × {0,1}^p, but the first argument is written as i^l∥j^{l2}, which has length 2n-2t-p. The types should be made consistent.","section":"Eq. (8)"},{"comment":"The notation l=l1∥l2 is used both for the index in Eq. (8) and for the original key l; this is confusing. Also, 'l1' and 'l2' are used as both bit lengths and strings.","section":"Section III-B1"},{"comment":"If 'k2_1' and 'k2_3' are intended to be k1^2 and k3^2, this should be written unambiguously with a definition of the finite-field multiplication.","section":"Eq. (3)"},{"comment":"The prepared state notation is missing parentheses: it should clearly indicate tensor products over c' copies of the superposition. The line breaks in the description also make the algorithm harder to read.","section":"Algorithm 4"},{"comment":"The condition 'l_ij ≠ 0' should be supplemented by invertibility or a precise blockwise condition; the paper's later truncation arguments rely on such structure.","section":"Eq. (6)"}],"recommendation":"major_revision","confidential_remarks":"The paper has a promising core: the offline separation for identity-map instantiations such as SoEM22 and XopEM is plausible and the Q2 query reduction is meaningful. The main problem is that Section III-B1 overgeneralizes: the algebra in Eq. (8) is only valid under a blockwise-linearity assumption that is never stated. The full-key Q1 complexity claim also appears inconsistent with the offline Simon cost for the remaining t bits. These are fixable by narrowing the generic claim and clarifying the partial-key scope, but they must be addressed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does two useful things. It identifies new targets for Shi et al.'s dedicated quantum attack—PolyMAC and the TPP-PRF constructions XopEM, SoEM22, SUMPIP, DS-SoEM—and it adapts that attack to an offline setting by introducing decoupled p-XOR-type functions. For the concrete instantiations, the periodicity and truncation arguments check out, and the Q2 query improvement from O(2^{(n+t)/2}(n−t)) to O(2^t(n−t)) for SoEM22 is real. That part is a solid contribution to quantum symmetric cryptanalysis.\n\nThe soft spot is the generic TPP-PRF claim. In Section III-B1, the derivation of the periodic F_L silently assumes the linear maps l_ij respect the high/low bit split used for truncation. For arbitrary GF(2)-linear maps, that is false: the affine subspace l23((x^l||L)) is not generally invariant under adding s^l||0^t, so the summed function F_L has no nonzero period and Algorithm 4 cannot recover i_0^l. Theorem 4 as stated is therefore unsupported for generic TPP-PRFs; it holds for the listed instantiations because their linear maps are essentially identity. This is not a minor typo—it is a missing hypothesis in the central theorem. The fix is either to restrict the theorem to instantiations where the maps act blockwise or to add explicit conditions and prove the periodicity under those conditions.\n\nA second, smaller issue: the Q1 full-key-recovery remark does not account for the leftover t key bits. Recovering those via offline Simon would add O(2^n) classical queries, which breaks the balanced O~(2^{(2n-t)/3}) claim if a full key recovery is intended. The tradeoff T^2D=2^{2n-t} appears correct only for the high-bit portion.\n\nWho is this for? Researchers working on quantum attacks against symmetric constructions, especially those following the Grover-meets-Simon line. The concrete attacks are worth knowing and the offline adaptation is a genuine step forward. But the paper overclaims in its abstract and Theorem 4. It deserves a serious referee—yes, send it to review—but the referee should require the generic claim to be corrected or explicitly scoped before publication. The underlying idea is good; the presentation needs to be honest about its actual range of validity.","headline":"Offline dedicated attack is a real advance for the identity-map instantiations, but the generic TPP-PRF claim rests on an unflagged truncation/linear-map assumption.","tokens_in":19132,"tokens_out":1685,"would_cite":true,"duration_ms":16762,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P94","94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that block-cipher constructions built from two parallel permutation-based pseudorandom functions can be key-recovered by an offline quantum attack that needs far fewer oracle queries than previous ones.","keywords":["offline quantum attack","XOR-type function","truncation technique","permutation-based pseudorandom function","Even-Mansour construction","SoEM22","PolyMAC","quantum cryptanalysis"],"falsifier":"Take a concrete TPP-PRF with a non-identity linear map l13 that mixes high and low bit positions, choose small n (e.g., n=6) and t=2, compute F_L of Eq. (8) by exhaustive enumeration, and test whether F_L(i_0^l,x^l)=F_L(i_0^l,x^l XOR s^l) holds for all x^l; if it does not, the central claim for generic TPP-PRFs fails. The same experiment with identity maps should reproduce the period, confirming the split is the load-bearing condition.","tokens_in":18114,"feed_emoji":"🔐","tokens_out":5954,"duration_ms":48752,"temperature":0.7,"pith_summary":"This paper claims that four block-cipher constructions built from two parallel public permutations—XopEM, SoEM22, SUMPIP, and DS-SoEM—hide a periodic structure that a quantum attacker can exploit without needing continuous access to the encryption oracle. The trick is to rewrite the construction as a decoupled XOR-type function, in which the key-dependent part is public, so the attacker can prepare a useful quantum state from one branch and then do the expensive search offline. The claimed payoff is quantitative: in the quantum-query model the number of queries to the encryption oracle drops from O(2^((n+t)/2) (n-t)) to O(2^t (n-t)), and in the classical-query model both query and time complexity fall from O~(2^(2n/3)) to O~(2^((2n-t)/3)). The paper also shows that the MAC scheme PolyMAC falls to the earlier online version of the attack, answering an open question about which structures are vulnerable.","feed_headline":"Offline quantum attack cracks four paired-permutation ciphers","feed_subtitle":"A decoupling trick cuts oracle queries from 2^((n+t)/2) to 2^t and lowers offline time to O~(2^((2n-t)/3)).","key_machinery":"The central object is the decoupled (public) XOR-type function, f(i,x)=g1(x) XOR p(x XOR i), with p public. Combined with the truncation technique—summing over a t-dimensional subspace L of low bits—it produces F_L(i^l,x^l) whose period in the high (n-t) bits is the secret period s^l, while the low key bits cancel out. Because the public branch can be evaluated offline, the algorithm separates an online preparation phase for the g1 superposition from an offline search phase, which is what converts the attack from online to offline.","core_discovery":"For any decoupled XOR-type function f(i,x)=g1(x) XOR p(x XOR i) coming from a TPP-PRF, summing f over the low t-bit subspace L yields a function F_L(i^l,x^l) that has an (n-t)-bit period s^l exactly when the high bits of the secret state i equal i_0^l. Since p is public, the only part that needs the encryption oracle is g1, and the attack (Algorithm 4) prepares the state for G_L^1 once and then runs amplitude-amplification search offline over candidate i^l, recovering i_0^l and s^l. The paper claims Theorem 4: O(2^t (n-t)) quantum queries in the Q2 model, or O(2^(p+t)) classical queries with O(2^((2n-2t-p)/2) n^3) offline time in Q1, with a balanced optimum at O~(2^((2n-t)/3)). The same meth","pith_inferences":["If the linear maps inside a TPP-PRF mix high and low bit positions instead of acting independently on the split, the truncated function is unlikely to have the claimed period; a designer could immunize the construction by ensuring such mixing.","The same decoupling idea may convert attacks on other two-branch public-permutation constructions (e.g., EDM/EDMD-style functions) into offline attacks whenever one branch is public.","The tunable truncation parameter t gives a knob that trades recovered key bits against query cost, which could be exploited to fit the attack on resource-constrained quantum devices."],"forward_implications":["XopEM, SoEM22, SUMPIP, and DS-SoEM can be key-recovered by the offline attack.","In the Q2 model the oracle-query count is reduced from O(2^((n+t)/2) (n-t)) to O(2^t (n-t)); in Q1 both queries and time drop from O~(2^(2n/3)) to O~(2^((2n-t)/3)).","The attack produces the tradeoff T^2 D = 2^(2n-t) between classical queries D and offline quantum time T, so an attacker can choose a resource profile.","After recovering the high bits, the remaining t low key bits can be found with an offline period-finding step, giving full key recovery.","PolyMAC is a new target for the online XOR-type attack, extending the class of vulnerable constructions."],"fun_headline_variants":["Decoupled XOR functions enable offline quantum attack on TPP-PRF ciphers","Quantum offline attack slashes queries on PolyMAC and four TPP-PRF ciphers","New quantum attack goes offline on paired-permutation constructions","Offline quantum attack on TPP-PRF ciphers with reduced query complexity","Decoupling trick enables offline attack on four TPP-PRF ciphers"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole truncated-function argument assumes the linear maps used inside the TPP-PRF respect the decomposition into high and low bits, so that summing over the low subspace cancels the low key bits and leaves the high period; for arbitrary n-bit linear maps this is false, and for SoEM22/XopEM it holds only because those maps are identities.","fun_headline_variants_meta":{"raw":{"variants":["Decoupled XOR functions enable offline quantum attack on TPP-PRF ciphers","Quantum offline attack slashes queries on PolyMAC and four TPP-PRF ciphers","New quantum attack goes offline on paired-permutation constructions","Offline quantum attack on TPP-PRF ciphers with reduced query complexity","Decoupling trick enables offline attack on four TPP-PRF ciphers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000848,"raw_usage":{"total_tokens":3623,"prompt_tokens":937,"completion_tokens":2686,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":681,"completion_tokens_details":{"reasoning_tokens":2584}},"tokens_in":681,"tokens_out":2686,"duration_ms":16590,"temperature":1.0,"reasoning_tokens":2584,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T09:36:51.489683+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a concrete TPP-PRF with a non-identity linear map l13 that mixes high and low bit positions, choose small n (e.g., n=6) and t=2, compute F_L of Eq. (8) by exhaustive enumeration, and test whether F_L(i_0^l,x^l)=F_L(i_0^l,x^l XOR s^l) holds for all x^l; if it does not, the central claim for generic TPP-PRFs fails. The same experiment with identity maps should reproduce the period, confirming the split is the load-bearing condition.","supporting_citations":[],"review_version":1}