Quantum Lifting for Invertible Permutations and Ideal Ciphers

Aaram Yun; Alexandru Cojocaru; Minki Hhan; Qipeng Liu; Takashi Yamakawa

REVIEW 2 major objections 4 minor 8 references

Quantum Lifting for Invertible Permutations and Ideal Ciphers

T0 review · 2 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For any $q$-query quantum adversary against an invertible random permutation or ideal cipher, there is a $k$-query classical adversary whose success probability is at least $((1-k^2/|X|)/(8q+1)^{2k})$ of the quantum adversary's.

desk verdict Permutation lifting is solid; the ideal-cipher lifting is broken by a false uniformity lemma, and the sponge application has query-count errors. read the letter →

arxiv 2504.18188 v1 pith:V4LZXFTX submitted 2025-04-25 quant-ph cs.CCcs.CR

Alexandru Cojocaru , Minki Hhan , Qipeng Liu , Takashi Yamakawa , Aaram Yun This is my paper · ORCID

classification quant-phcs.CCcs.CR

keywords quantumliftingtheoremrandompermutationmodelidealcipherpost-quantumsecuritymeasure-and-reprogramquerycomplexityspongeconstructionDavies-Meyerhashfunctions

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves the first lifting theorems for the quantum random permutation and ideal cipher models. It shows that any quantum adversary making $q$ queries against an invertible random permutation or ideal cipher can be converted into a classical adversary making only $k$ queries, with success probability at least $((1-k^2/|X|)/(8q+1)^{2k})$ of the quantum adversary's. The point is that quantum security proofs in these models reduce to classical $k$-query bounds, at the price of a polynomial factor in $q$. The payoff is a tight bound for the double-sided zero-search game, the first non-trivial post-quantum bounds for multi-round sponge hashing, and collision resistance for the Davies-Meyer and PGV compression functions under quantum ideal ciphers.

What carries the argument

The load-bearing mechanism is a measure-and-reprogram lemma for permutations. To simulate an adversary that queries a reprogrammed permutation $\pi[x^*\to y^*]$, the simulator guesses the first query that touches the target pair: a hit query on $x^*$ (or $y^*$ for an inverse query) or a miss query on $\pi^{-1}(y^*)$ (or $\pi(x^*)$), and reprograms the permutation by swapping the two affected outputs so injectivity is preserved. In the quantum case, the algorithm's state is decomposed by inserting projections at each query into at most $(8q+1)^{2k}$ subnormalized terms, each corresponding to one choice of simulator randomness: query index, hit-versus-miss, and whether reprogramming happens before or after the query. The triangle inequality and norm bounds turn this decomposition into the stated probability ratio, and a goodness condition, violated with probability at most $k^2/|X|$, ensures that successive reprogrammings do not interfere.

What would settle it

Run the cipher simulator from Section 5 on a small domain, say two keys with $|X|=8$ and $k=2$ target pairs that share a key, and compute the exact ratio between the success probability of the reprogrammed-cipher experiment and the simulator's output. If for $q=1$ that ratio is ever smaller than $1/(8q+1)^4$, the ideal-cipher lifting theorem is refuted.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 4.1: for any search game whose challenger makes at most $k$ classical queries to an invertible random permutation $\pi$, and any adversary $\mathcal{A}$ making $q$ quantum queries to $\pi$ and $\pi^{-1}$, there exists an adversary $\mathcal{B}$ making at most $k$ classical queries whose success probability is at least $((1-k^2/|X|)/(8q+1)^{2k})$ times that of $\mathcal{A}$. Theorem 5.7 extends the same statement to ideal ciphers, with the same loss. The paper establishes that quantum query access to a permutation or cipher does not change the asymptotic difficulty of search games beyond a fixed polynomial factor in $q$: any quantum attack with success probability $p$ is matched by a $k$-query classical attack with probability at least $p/(8q+1)^{2k}$, whenever the challenger is efficient. The theorems are then applied to prove tight bounds for generalized double-sided search, the first non-trivial post-quantum security bounds for constant-round sponge (preimage, one-wayness, and multi-collision resistance), and collision resistance for Davies-Meyer and group-1 PGV compression functions.

Load-bearing premise

The ideal-cipher theorem rests on the unproven claim that the permutation measure-and-reprogram argument carries over to ciphers whose keys are repeated among the $k$ target pairs; if reprogrammings under the same key interfere with one another, the theorem and its Davies-Meyer applications fall apart.

Editorial extensions

If this is right

Any quantum query lower bound in the random permutation model now follows from the corresponding $k$-query classical bound with a $(8q+1)^{2k}$ overhead; the paper uses this to prove an $O(r_{\max} q^2 / 2^{2n})$ bound for generalized double-sided search, tight against the quadratic-speedup search algorithm.
The ideal-cipher version lifts classical collision-resistance proofs from the ICM to the quantum ideal cipher model; the paper obtains $O(q^4/2^n)$ collision resistance for Davies-Meyer and all group-1 PGV compression functions.
Constant-round sponge gains the first non-trivial post-quantum preimage, one-wayness, and multi-collision resistance bounds whenever the capacity is large enough; for the single-round case the preimage bound matches the quantum search bound up to constants.
For any classically verifiable interactive search game whose challenger uses at most $k$ classical queries, the same reduction holds, so future random-permutation or ideal-cipher proofs can be adapted to quantum adversaries without problem-specific tools.
The double-sided zero-search conjecture is confirmed with a tight $O(q^2/2^n)$ bound, improving the previous $O(r_{\max} q^3 / 2^{2n})$-type bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The constant $8$ in $(8q+1)^{2k}$ is a byproduct of the normal-form reduction from $q$ queries to $2q$ alternating forward and inverse queries; a tighter decomposition might lower it, which would sharpen every application's constant factor.
The paper's sponge bounds are meaningful only when the capacity is large relative to the squared query terms; extending the lifting to unbounded input lengths without this restriction would make the results usable for general-purpose hash functions.
If the missing proof of the cipher lifting theorem can be completed, then every classical ideal-cipher security proof for a search game automatically becomes a quantum ideal-cipher proof; Davies-Meyer collision resistance is the first beneficiary, but other block-cipher-based constructions would inherit the same reduction.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The permutation lifting theorem (Theorem 4.1) is a genuine and well-executed result, and it deserves to survive. The ideal-cipher version (Theorem 1.2 / 5.7) does not: the proof sketch rests on a uniformity claim that is false. The sponge section also has a query-count problem that needs fixing.

What's new: extending the measure-and-reprogram technique from YZ21 to the QRPM, with the hit/miss handling and the state decomposition, is a real step forward. For a permutation with inverse oracle, the proof in Section 4 is complete as far as I can tell: the decomposition into 4q+1 terms, the goodness condition, the bad-probability bound, and the reduction to a k-query classical adversary all line up. The derived bounds for double-sided search and fixed-point finding are clean and tight up to constants.

Soft spots. Section 5 is not a proof sketch; it is a place where the argument breaks. For permutations, the goodness set G[x*] is invariant under left multiplication by any sigma, which gives uniformity of the reprogrammed permutation. For ciphers, the cross-key condition E_{K_i*}(x_i*) != y_j* for all i,j couples the keys. The natural global left-action does preserve G, but the reprogrammed cipher is not uniform on G: a concrete enumeration with X of size 3 and two distinct keys gives Pr[E'_K1(1)=E'_K2(1)] = 2/3 under G, versus 1/3 for a uniform ideal cipher. So the 'duplicate of Lemma 2.11' cannot be true. Theorem 5.7 and the Davies-Meyer/PGV applications are unsupported as written. A per-key goodness condition might repair this, but that is not what the paper states or proves.

Sponge: the proof of Theorem 6.4 cites Theorem 3.1 (classical lifting) where it must use Theorem 4.1 (quantum), and the query count is off: for k sponge inputs, the challenger makes k*ell permutation queries, not k. The proof then counts B as a k-query algorithm when it should be k*ell-query. These look fixable, but the stated bounds do not follow from the argument given.

Bottom line: the permutation lifting theorem is a solid, citable contribution. The cipher half is currently a claim with a false supporting lemma, so the Davies-Meyer result should be considered open until repaired. This deserves a serious referee: a good referee can separate the two halves, accept the permutation result, and force the authors to either prove the cipher lemma properly or remove those applications.

Referee Report

2 major / 4 minor

Summary. The paper introduces lifting theorems for the quantum random permutation model (QRPM) and the quantum ideal cipher model (QICM). For the permutation case, Theorem 4.1 states that any q-quantum-query adversary against a search game with k classical challenger queries can be simulated by a k-classical-query adversary losing only a factor (8q+1)^{2k}, up to a small bad-event term. The proof is carried out through a detailed state-decomposition and measure-and-reprogram argument. The paper then presents applications to the double-sided zero-search problem, fixed-point finding, the sponge construction, and Davies-Meyer/PGV hash functions. For the ideal cipher case, Theorem 5.7 is given as a proof sketch, with the claim that it follows by duplicating the permutation proof. The central permutation lifting theorem appears technically sound, but the ideal-cipher version has a genuine gap, and the sponge application contains a citation/query-count inconsistency that needs correction.

Significance. The paper's Section 4 is a substantial technical contribution: it gives a self-contained, parameter-free derivation of a QRPM lifting theorem, avoiding fitted constants and providing explicit polynomial losses in q. If valid, the theorem is a powerful general tool that unifies several prior problem-specific analyses and yields tight bounds for double-sided zero search and fixed-point finding. The applications to multi-round sponge are also valuable, and the paper is honest about their non-tightness. However, the ideal-cipher lifting theorem is load-bearing for the Davies-Meyer/PGV results, and as written that theorem is not proven; the asserted 'duplicate proof' fails because the cipher goodness condition does not preserve uniformity of the reprogrammed oracle. The sponge proof also needs a small but real correction in its use of the lifting theorem. These issues are fixable, but they must be addressed before the paper can be accepted.

major comments (2)

[Section 5, Definitions 5.2–5.3 and Lemma 5.6] The claim that Lemma 5.6 is 'essentially a duplicate' of Lemma 4.4 is not correct, because the cipher analogue of Lemma 2.11 fails. The goodness set G[K*, x*] is not invariant under the relevant group action. Concretely, let K1 ≠ K2, X = {0,1,2}, and x1* = x2* = 1. Write a = E_{K1}(1), b = E_{K2}(1), c = E*_{K1}(1), d = E*_{K2}(1). Definition 5.2 requires a ∉ {c,d} and b ∉ {c,d}. Conditioning on (E,E*) ∈ G, one obtains Pr[c = d] = ((1/3)(2/3)^2) / ((1/3)(2/3)^2 + (2/3)(1/3)^2) = 2/3, whereas for a uniform ideal cipher the reprogrammed values E'_{K1}(1) and E'_{K2}(1) are equal with probability 1/3. Equivalently, the per-key left-multiplication action (σ_K E_K, σ_K E*_K) does not preserve G unless all σ_K are equal. Hence the distribution of the reprogrammed cipher under (E,E*) ← G is not uniform, and the step 'by Lemma 2.11' in the proof of Theorem 5.7 is unavailable. Theorem 5.7, and therefore Theorem 1.2 and the Davies-Meyer/PGV application in Section 6.3, are unproven as written. A likely repair is to define goodness per key, imposing cross conditions only among pairs sharing the same key; that variant would factor G into a product and preserve uniformity, but it is neither stated nor proved in the manuscript.
[Section 6.2, proof of Theorem 6.4] The first reduction in the proof of Theorem 6.4 is attributed to Theorem 3.1, but Theorem 3.1 is the classical lifting theorem. To reduce a q-quantum-query adversary A to a classical algorithm B, the proof must invoke the quantum lifting theorem, Theorem 4.1. Moreover, the reduced algorithm B should make kℓ classical queries, not k, because each evaluation of Sponge^π costs ℓ permutation queries; the exponent (8q+1)^{2kℓ} and the quantity N = kℓ + k in the later use of Lemma 6.11 confirm that the intended parameter is kℓ. As written, the sentence 'There exists a k-classical-query algorithm B' in the proof is inconsistent with the reduction, and the proof does not follow from the cited theorem. This is a local correction, but it is necessary for the sponge applications to be valid.

minor comments (4)

[Lemma 2.10] The statement says 'the probability that (π,π*) ∈ G[x*] is at most k^2/|X|', but the proof upper-bounds the probability that (π,π*) is not in G[x*]. The intended inequality is Pr[(π,π*) ∉ G[x*]] ≤ k^2/|X|.
[Lemma 5.4] The lemma says 'Let E be a (fixed) permutation', but in the cipher setting E should be a fixed cipher over K × X, not a permutation.
[Appendix C, proof of Lemma 4.3] Several references to the hit/miss definitions say 'Definition 6'; the correct references are Definition 2.12 for permutations and Definition 5.5 for ciphers.
[Theorem 6.4 and its proof] The statement of Theorem 6.4 defines P_R^max using k-classical-query algorithms to a random function, while the reduction in the proof produces a classical algorithm making kℓ permutation queries. The query count should be stated consistently, e.g., by renaming the lifted query count or by clarifying that the k-query bound in the theorem refers to the final sponge-evaluation algorithm after merging the kℓ direct queries.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lifting theorems are derived by a self-contained measure-and-reprogram argument, and the applications reduce to external classical results.

full rationale

The central derivation chain is not circular. Theorem 4.1 (and its classical analogue Theorem 3.1) is proved directly: the simulator S[A, pi, pi*] is constructed, the quantum state is decomposed into (8q+1)^(2k) terms by an induction on query indices, and the loss factor is obtained by Cauchy-Schwarz. No parameter is fitted to data, and the target success probability of A against a uniform permutation is recovered through Lemma 2.11, which proves that the reprogrammed permutation is uniform on the good set. The goodness condition and the bad-probability bound k^2/|X| are derived, not assumed. The sponge and Davies-Meyer applications rely on external classical results ([BDPV08] for indifferentiability and [BRS02] for PGV collision resistance), so the 'quantum lifting plus classical security' pattern is a legitimate reduction rather than a renaming of the output as the input. The only self-citations are to the authors' earlier QROM framework [YZ21], which is used as motivation and for the interactive-setting wlog; the permutation and cipher extensions are worked out in this paper, so the self-citation is not load-bearing. Section 5 does state that the ideal-cipher proof is only a sketch ('instead of providing a formal proof, we will give a brief sketch') and asserts that Lemma 5.6's proof 'is essentially a duplicate of that of Lemma 4.4'; this is an omitted-proof/correctness concern about whether the cipher uniformity argument truly carries over, but it is not circularity, because no equation of the desired theorem is fed back as an assumption. Thus the paper deserves a circularity score of 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper proves theorems from standard mathematical tools. It relies on prior classical results for the applications. No free parameters or invented entities are introduced.

assumptions (5)

domain assumption Random permutation model: pi and pi^{-1} are uniformly random and accessible as black-box oracles.
Defines the RPM used throughout (Section 1).
domain assumption Ideal cipher model: each key K gives an independent random permutation E_K, with forward and inverse oracles.
Defines ICM/QICM (Section 5).
domain assumption Quantum query model: a superposition query to a permutation costs one unit, and algorithms can be put in normal form alternating forward and inverse queries (Lemma 2.1).
Formalizes the adversary and enables the state decomposition.
domain assumption Classical indifferentiability of the sponge construction with error N(N+1)/2^c (Lemma 6.11, from BDPV08).
Used in the sponge application to pass from the lifted classical RPM adversary to a random-oracle adversary.
domain assumption Classical collision bound for group-1 PGV compression functions: at most q(q+1)/2^n (Lemma 6.14, from BRS02).
Used to bound the classical 2-query adversary in the Davies-Meyer application.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum Lifting for Invertible Permutations and Ideal Ciphers." pith.science (2026). https://pith.science/paper/V4LZXFTX

@misc{pith2026250418188,
  author       = {Pith},
  title        = {Pith review of: Quantum Lifting for Invertible Permutations and Ideal Ciphers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V4LZXFTX}},
  note         = {Machine review of arXiv:2504.18188}
}

read the original abstract

In this work, we derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries. By applying these lifting theorems, we improve previous results and obtain new quantum query complexity bounds and post-quantum security results. Notably, we derive tight bounds for the quantum hardness of the double-sided zero search game and establish the post-quantum security for the preimage resistance, one-wayness, and multi-collision resistance of constant-round sponge, as well as the collision resistance of the Davies-Meyer construction.

Figures

Figures reproduced from arXiv: 2504.18188 by the authors.

**Figure 2.** An illustration of mappings in the reprogrammed permutation 𝜋[𝑥 * → 𝜋 * (𝑥 * )] Similarly, for a backward query to 𝜋 −1 , we call a query 𝑦 “hit” (or just 𝑦 𝗁𝗂𝗍) with respect to the final outcome 𝑦 * = 𝜋 * (𝑥 * ) if 𝑦 𝗁𝗂𝗍 = 𝑦 * . We call a query 𝑦 “miss” (or just 𝑦 𝗆𝗂𝗌𝗌) if 𝑦 = 𝜋(𝑥 * ) as in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

8 extracted references · 6 canonical work pages

[1]

[𝑥* 𝑘→𝑦* 𝑘](𝑥* 𝑘) =𝑦* 𝑘

𝜋[𝑥* 1→𝑦* 1]... [𝑥* 𝑘→𝑦* 𝑘](𝑥* 𝑘) =𝑦* 𝑘

work page
[2]

[𝑥* 𝑘−1→𝑦* 𝑘−1](𝑥* 𝑘) =𝜋(𝑥* 𝑘)

𝜋[𝑥* 1→𝑦* 1]... [𝑥* 𝑘−1→𝑦* 𝑘−1](𝑥* 𝑘) =𝜋(𝑥* 𝑘)

work page
[3]

[𝑥* 𝑘−1→𝑦* 𝑘−1]−1(𝑦* 𝑘) =𝜋−1(𝑦* 𝑘)

𝜋[𝑥* 1→𝑦* 1]... [𝑥* 𝑘−1→𝑦* 𝑘−1]−1(𝑦* 𝑘) =𝜋−1(𝑦* 𝑘)

work page
[4]

[𝑥* 𝑘→𝑦* 𝑘](𝜋−1(𝑦* 𝑘)) =𝜋(𝑥* 𝑘)

𝜋[𝑥* 1→𝑦* 1]... [𝑥* 𝑘→𝑦* 𝑘](𝜋−1(𝑦* 𝑘)) =𝜋(𝑥* 𝑘). Proof. Let us prove the above statements one by one. • Statement 1: It directly follows from the definition of the permutation reprogramming. • Statement 2: It can be proved by mathematical induction. The base case is where𝑘 = 1, and in that case the equality holds trivially. Now, suppose that this statemen...

work page
[8]

Then, according to the induction hypothesis applied to 𝜋′ and (𝑝* 2,...,𝑝 * 𝑘), a tuple of length 𝑘− 1, we have 𝜋′[𝑥* 2→𝑦* 2]

(due to goodness), we get𝜋′(𝑥* 𝑖 ) = 𝜋[𝑥* 1→ 𝑦* 1](𝑥* 𝑖 ) = 𝜋(𝑥* 𝑖 )̸= 𝑦* 𝑗 by the definition of reprogramming and also by goodness. Then, according to the induction hypothesis applied to 𝜋′ and (𝑝* 2,...,𝑝 * 𝑘), a tuple of length 𝑘− 1, we have 𝜋′[𝑥* 2→𝑦* 2]... [𝑥* 𝑘−1→𝑦* 𝑘−1](𝑥* 𝑘) =𝜋′(𝑥* 𝑘). This shows that 𝜋[𝑥* 1→ 𝑦* 1]... [𝑥* 𝑘−1→ 𝑦* 𝑘−1](𝑥* 𝑘) = 𝜋′(𝑥...

work page
[2004]

Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations

Proceedings 1. Springer. 2004, pp. 40–57 (cit. on p. 2). [CP24] Joseph Carolan and Alexander Poremba. “Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations”. In: Advances in Cryptology – CRYPTO 2024: 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2024, Proceedings, Part VI. 2024, pp. 218–252. ...

work page doi:10.1007/978-3-031-68391-6_7 2025
[2008]

Sponge Functions

2008, pp. 181–197 (cit. on pp. 4, 5, 36). [BDPV11] Guidoand Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. “Sponge Functions”. In: (2011). URL: https://keccak.team/files/CSF-0.1.pdf (cit. on pp. 4, 5, 32). [BHT98] Gilles Brassard, Peter Høyer, and Alain Tapp. “Quantum Cryptanalysis of Hash and Claw-Free Functions”. In: LATIN: : Theoretical ...

2011
[2024]

Hash Functions Based on Block Ciphers: A Synthetic Approach

URL: https://eprint.iacr.org/2024/1140 (cit. on pp. 3, 5, 31, 32). [PGV93] Bart Preneel, René Govaerts, and Joos Vandewalle. “Hash Functions Based on Block Ciphers: A Synthetic Approach”. In: Advances in Cryptology - CRYPTO ’93, 13th An- nual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings. Vol. 773. 19...

arXiv 2021

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

[𝑥* 𝑘→𝑦* 𝑘](𝑥* 𝑘) =𝑦* 𝑘

𝜋[𝑥* 1→𝑦* 1]... [𝑥* 𝑘→𝑦* 𝑘](𝑥* 𝑘) =𝑦* 𝑘

work page

[2] [2]

[𝑥* 𝑘−1→𝑦* 𝑘−1](𝑥* 𝑘) =𝜋(𝑥* 𝑘)

𝜋[𝑥* 1→𝑦* 1]... [𝑥* 𝑘−1→𝑦* 𝑘−1](𝑥* 𝑘) =𝜋(𝑥* 𝑘)

work page

[3] [3]

[𝑥* 𝑘−1→𝑦* 𝑘−1]−1(𝑦* 𝑘) =𝜋−1(𝑦* 𝑘)

𝜋[𝑥* 1→𝑦* 1]... [𝑥* 𝑘−1→𝑦* 𝑘−1]−1(𝑦* 𝑘) =𝜋−1(𝑦* 𝑘)

work page

[4] [4]

[𝑥* 𝑘→𝑦* 𝑘](𝜋−1(𝑦* 𝑘)) =𝜋(𝑥* 𝑘)

𝜋[𝑥* 1→𝑦* 1]... [𝑥* 𝑘→𝑦* 𝑘](𝜋−1(𝑦* 𝑘)) =𝜋(𝑥* 𝑘). Proof. Let us prove the above statements one by one. • Statement 1: It directly follows from the definition of the permutation reprogramming. • Statement 2: It can be proved by mathematical induction. The base case is where𝑘 = 1, and in that case the equality holds trivially. Now, suppose that this statemen...

work page

[5] [8]

Then, according to the induction hypothesis applied to 𝜋′ and (𝑝* 2,...,𝑝 * 𝑘), a tuple of length 𝑘− 1, we have 𝜋′[𝑥* 2→𝑦* 2]

(due to goodness), we get𝜋′(𝑥* 𝑖 ) = 𝜋[𝑥* 1→ 𝑦* 1](𝑥* 𝑖 ) = 𝜋(𝑥* 𝑖 )̸= 𝑦* 𝑗 by the definition of reprogramming and also by goodness. Then, according to the induction hypothesis applied to 𝜋′ and (𝑝* 2,...,𝑝 * 𝑘), a tuple of length 𝑘− 1, we have 𝜋′[𝑥* 2→𝑦* 2]... [𝑥* 𝑘−1→𝑦* 𝑘−1](𝑥* 𝑘) =𝜋′(𝑥* 𝑘). This shows that 𝜋[𝑥* 1→ 𝑦* 1]... [𝑥* 𝑘−1→ 𝑦* 𝑘−1](𝑥* 𝑘) = 𝜋′(𝑥...

work page

[6] [2004]

Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations

Proceedings 1. Springer. 2004, pp. 40–57 (cit. on p. 2). [CP24] Joseph Carolan and Alexander Poremba. “Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations”. In: Advances in Cryptology – CRYPTO 2024: 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2024, Proceedings, Part VI. 2024, pp. 218–252. ...

work page doi:10.1007/978-3-031-68391-6_7 2025

[7] [2008]

Sponge Functions

2008, pp. 181–197 (cit. on pp. 4, 5, 36). [BDPV11] Guidoand Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. “Sponge Functions”. In: (2011). URL: https://keccak.team/files/CSF-0.1.pdf (cit. on pp. 4, 5, 32). [BHT98] Gilles Brassard, Peter Høyer, and Alain Tapp. “Quantum Cryptanalysis of Hash and Claw-Free Functions”. In: LATIN: : Theoretical ...

2011

[8] [2024]

Hash Functions Based on Block Ciphers: A Synthetic Approach

URL: https://eprint.iacr.org/2024/1140 (cit. on pp. 3, 5, 31, 32). [PGV93] Bart Preneel, René Govaerts, and Joos Vandewalle. “Hash Functions Based on Block Ciphers: A Synthetic Approach”. In: Advances in Cryptology - CRYPTO ’93, 13th An- nual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings. Vol. 773. 19...

arXiv 2021