In 2005, Nandi introduced a class of double-block-length compression functions hπ (x) := (h(x) , h( π(x) ) ), where h is a random oracle with an n-bit output and π is a non-cryptographic public permutation. Nandi demonstrated that the collision resistance of hπ is optimal if π has no fixed point in the classical setting. Our study explores the collision resistance of hπ and the Merkle-Damåard hash function using hπ in the quantum random oracle model. Firstly, we reveal that the quantum collision resistance of hπ may not be optimal even if π has no fixed point. If π is an involution, then a colliding pair of inputs can be found for hπ with only O(2n/2) queries by the Grover search. Secondly, we present a sufficient condition on π for the optimal quantum collision resistance of hπ. This condition states that any collision attack needs Ω(22n/3) queries to find a colliding pair of inputs. The proof uses the recent technique of Zhandry's compressed oracle. Thirdly, we show that the quantum collision resistance of the Merkle-Damgård hash function using hπ can be optimal even if π is an involution. Finally, we discuss the quantum collision resistance of double-block-length compression functions using a block cipher.In 2005, Nandi introduced a class of double-block-length compression functions hπ (x) := (h(x) , h( π(x) ) ), where h is a random oracle with an n-bit output and π is a non-cryptographic public permutation. Nandi demonstrated that the collision resistance of hπ is optimal if π has no fixed point in the classical setting. Our study explores the collision resistance of hπ and the Merkle-Damåard hash function using hπ in the quantum random oracle model. Firstly, we reveal that the quantum collision resistance of hπ may not be optimal even if π has no fixed point. If π is an involution, then a colliding pair of inputs can be found for hπ with only O(2n/2) queries by the Grover search. Secondly, we present a sufficient condition on π for the optimal quantum collision resistance of hπ. This condition states that any collision attack needs Ω(22n/3) queries to find a colliding pair of inputs. The proof uses the recent technique of Zhandry's compressed oracle. Thirdly, we show that the quantum collision resistance of the Merkle-Damgård hash function using hπ can be optimal even if π is an involution. Finally, we discuss the quantum collision resistance of double-block-length compression functions using a block cipher.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesMar 3, 20241 citation

Compressed Permutation Oracles Revisited

Joseph Carolan, Christian Majenz

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 compression isometry from a simple POVM on the naive purification, a technique which may find wider applications. As immediate applications, our results yield tight, concrete collision and pre-image lower bounds for the sponge hash construction underlying SHA3 and the Davies--Meyer compression function used in SHA1 and SHA2. More broadly, the improved soundness theorem provides a general-purpose tool for analyzing quantum security in settings where random permutations or ideal ciphers serve as the underlying primitive.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 compression isometry from a simple POVM on the naive purification, a technique which may find wider applications. As immediate applications, our results yield tight, concrete collision and pre-image lower bounds for the sponge hash construction underlying SHA3 and the Davies--Meyer compression function used in SHA1 and SHA2. More broadly, the improved soundness theorem provides a general-purpose tool for analyzing quantum security in settings where random permutations or ideal ciphers serve as the underlying primitive.

quant-pharXiv:2609.28469Sep 24, 20260 citations

Quantum security of Trojan message attacks on Merkle–Damgård hash construction

Ying Xu, Xiaoni Du, Jian Xiao Zou

Designs Codes and CryptographyDec 18, 20240 citations

Full quantum one‐way function for quantum cryptography

Fei Gao

Quantum EngineeringFeb 21, 20202 citations

Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications

Ritam Bhaumik, Yu-Hsuan Huang

Cryptographic security proofs often involve an adversary interacting with a larger, keyed oracle that consists of (potentially exponentially) many independent instances of a smaller, base oracle. However, showing quantum indistinguishability between two such keyed oracles can be tricky, since a single query made by an adversary may involve a superposition that covers all instances of the base oracles simultaneously. In this paper, we establish a generic indistinguishability lifting theorem of the following form: if the two base oracles are indistinguishable under quantum queries, then their corresponding keyed oracles are too, up to an O(q^2) multiplicative loss in distinguishing advantage, where q is the number of queries made by the adversary. Our lifting theorem applies to both statistical and computational settings, and to oracles that are stateful as well. It is also optimal in that it matches the obvious Grover search attack for a certain (contrived) choice of oracles. As an immediate application, we extend Carolan's compressed permutation oracle to an efficiently implementable compressed ideal cipher, and use it to prove preimage resistance of the Davies-Meyer compression function in the quantum ideal cipher model. Thanks to our lifting theorem, the soundness of our compressed ideal cipher reduces to that of Carolan's oracle, and any further improvement on the latter would automatically carry over to the former. As our second application, we give a modular construction that doubles the message length of any quantum-secure strong pseudorandom permutation. Along the way, we show that an existing two-round tweakable Feistel construction is indistinguishable from a random permutation under quantum bidirectional queries. This is done via a dedicated polynomial-method argument, which may be of independent interest.Cryptographic security proofs often involve an adversary interacting with a larger, keyed oracle that consists of (potentially exponentially) many independent instances of a smaller, base oracle. However, showing quantum indistinguishability between two such keyed oracles can be tricky, since a single query made by an adversary may involve a superposition that covers all instances of the base oracles simultaneously. In this paper, we establish a generic indistinguishability lifting theorem of the following form: if the two base oracles are indistinguishable under quantum queries, then their corresponding keyed oracles are too, up to an O(q^2) multiplicative loss in distinguishing advantage, where q is the number of queries made by the adversary. Our lifting theorem applies to both statistical and computational settings, and to oracles that are stateful as well. It is also optimal in that it matches the obvious Grover search attack for a certain (contrived) choice of oracles. As an immediate application, we extend Carolan's compressed permutation oracle to an efficiently implementable compressed ideal cipher, and use it to prove preimage resistance of the Davies-Meyer compression function in the quantum ideal cipher model. Thanks to our lifting theorem, the soundness of our compressed ideal cipher reduces to that of Carolan's oracle, and any further improvement on the latter would automatically carry over to the former. As our second application, we give a modular construction that doubles the message length of any quantum-secure strong pseudorandom permutation. Along the way, we show that an existing two-round tweakable Feistel construction is indistinguishable from a random permutation under quantum bidirectional queries. This is done via a dedicated polynomial-method argument, which may be of independent interest.

cs.CRCross-listedarXiv:2610.04674Oct 6, 20260 citations

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 compression isometry from a simple POVM on the naive purification, a technique which may find wider applications. As immediate applications, our results yield tight, concrete collision and pre-image lower bounds for the sponge hash construction underlying SHA3 and the Davies--Meyer compression function used in SHA1 and SHA2. More broadly, the improved soundness theorem provides a general-purpose tool for analyzing quantum security in settings where random permutations or ideal ciphers serve as the underlying primitive.