João Diogo Duarte

Understanding collision resistance, quantifiers and (non-)uniformity

22 October 2026

One of the things I have always loved in cryptography is black-box separation results [RTV04]. Two classic examples are the separation of key agreement (and hence Public Key Encryption) from One-way Permutations (OWP) by Impagliazzo and Rudich [IR89], and the separation of Collision Resistant Hash Functions (CRHF) from OWPs by Simon [Sim98]. After Simon’s seminal paper, I started reading Hsiao and Reyzin’s paper on separating public-coin CRHFs from secret-coin CRHFs [HR04], which claims on the first page that

It is easy to see there is no meaningful way to formalize the notion of collision-resistance for a single fixed-output-length hash function.

As someone who works primarily in EasyCrypt [BGHZ11], I found this strange, as I thought we had a collision resistance proof for SHA3 with output length $x$ (more on this later!). Theory papers are almost always asymptotic, but they split on uniformity. For example, Goldwasser and Micali’s original definitions [GM84] are non-uniform, while Katz–Lindell [KL20] and most oracle separations [HR04] use uniform ones. Concrete security is mostly used to analyse specific constructions [BKR00, BDJR97]. EasyCrypt also works in the concrete setting, since its program logics produce explicit probability bounds rather than asymptotic statements.

Because of this and some free time on a flight, I thought this would be an interesting first blog post. It is about how quantifiers always seem to introduce irritating, nuanced pain points that, at least for me, are invisible at first sight.

Security models

We have two main flavours of security proofs, those done in the asymptotic uniform setting [KL20] and those done in the concrete setting [BKR00, BDJR97]. There is also an asymptotic non-uniform setting [GM84, Gol01], but we don’t really use it here. In my opinion, the difference between these notions lies almost entirely in the order of the quantifiers.

\begin{array}{lll} \textbf{Asymptotic Uniform:} & \forall\, \text{PPT } \mathcal{A}\ \exists \nu_{\mathcal{A}}\ \forall \ell & \Pr\big[\,G^{\mathcal{A}(1^\ell)}(1^\ell) \Rightarrow 1\,\big] \le \nu_{\mathcal{A}}(\ell) \\[6pt] \textbf{Concrete:} & \text{fix } \ell,\ \forall \mathcal{A},\ |\mathcal{A}| \le t & \Pr\big[\,G^{\mathcal{A}} \Rightarrow 1\,\big] \le \varepsilon(t) \end{array}

Here $\ell$ is the security parameter, which for now we assume to be a length, and $|\mathcal{A}|$ measures the adversary’s size and running time together, including anything hard-coded into its code. PPT means that $\mathcal{A}$ runs in probabilistic polynomial time in $\ell$ , and $\nu_{\mathcal{A}}$ is a negligible function (one that eventually drops below $1/p(\ell)$ for every polynomial $p$ ), which may depend on $\mathcal{A}$ . $G^{\mathcal{A}(\cdot)}$ denotes the game run with $\mathcal{A}$ started on the given inputs, plus whatever the game itself hands it (keys, challenges, oracle answers).

Careful, though: swapping two “for all” quantifiers on its own changes nothing, since $\forall \mathcal{A}\, \forall \ell$ and $\forall \ell\, \forall \mathcal{A}$ say exactly the same thing. What really moves is the “there exists” hiding in the bound. In the concrete setting $\varepsilon(t)$ is fixed before we pick $\mathcal{A}$ , so one bound has to hold for every adversary at once. In the uniform setting $\nu_{\mathcal{A}}$ comes after $\mathcal{A}$ , so it only has to work for that one adversary, and since being negligible only constrains large $\ell$ , it can be as bad as it likes on finitely many parameters.

In the concrete setting we fix $\ell$ first and only then quantify over the adversary, so the adversary may depend on $\ell$ . One can think of such a non-uniform adversary as a fixed machine together with an advice string $a_\ell$ that depends on $\ell$ . In the uniform setting we instead fix the adversary’s code once, and the same code then runs on every security parameter. A uniform adversary is therefore a non-uniform one whose advice does not depend on the security parameter. It still has a constant amount of advice, namely whatever is written into its code.

Notice that the definition says nothing about where the advice comes from! It could be the result of some arbitrarily long offline preprocessing phase that compresses something very useful into at most $t$ bits, such as a hard-coded collision. In the concrete setting there is only one $\ell$ , so whatever advice helps at that $\ell$ can simply be written into $\mathcal{A}$ . This is why concrete security is, in effect, non-uniform [BL13].

Side note on modelling non-uniform adversaries

Note, I prefer to think of non-uniform adversaries as Turing machines with an advice tape rather than as circuits. The two are equivalent [KL80, AB09], but the advice tape makes the possible preprocessing step much more visible, and this will matter further along.

Why fixing $\ell$ breaks a single hash function

Take a single hash function such as $H \colon \{0,1\}^{*} \to \{0,1\}^n$ . Assume, intuitively, that it is not feasible for an adversary to find a collision in $H$ . Let us try to formalize this in the following game, which is the usual collision game [RoSh04] with the key removed.

\begin{array}{l} \underline{\mathsf{Fixed}_H(\mathcal{A})} \\ (x_1, x_2) \leftarrow \mathcal{A} \\ \text{return } x_1 \ne x_2 \wedge H(x_1) = H(x_2) \end{array}

In the concrete setting we would want the following.

\forall \mathcal{A},\ |\mathcal{A}| \le t,\quad \Pr\big[\mathsf{Fixed}_H(\mathcal{A}) \Rightarrow 1\big] \le \text{small}

This statement is false! (At least once $t$ is big enough to print two short strings, and “small” means anything below $1$ .) Since $H$ maps infinitely many inputs to finitely many outputs, a collision $(c_1, c_2)$ must exist, and in fact all but at most $2^n$ inputs collide with some other input. Note that $H$ is fixed before we quantify over $\mathcal{A}$ . So there is an $\mathcal{A}$ with that collision written into it, namely the one that returns $(c_1, c_2)$ . This single and annoying $\mathcal{A}$ wins with probability $1$ . We don’t need to know $(c_1, c_2)$ , it is enough that it exists.

Adding a security parameter doesn’t help on its own. Let $H$ take $1^\ell$ as an extra input and output $\ell$ bits.

\begin{array}{l} \underline{\mathsf{Var}_H^\ell(\mathcal{A})} \\ (x_1, x_2) \leftarrow \mathcal{A}(1^\ell) \\ \text{return } x_1 \ne x_2 \wedge H(x_1, 1^\ell) = H(x_2, 1^\ell) \end{array}

In the concrete setting, where $\ell$ is fixed, we have the following.

\forall \mathcal{A},\ |\mathcal{A}| \le t,\quad \Pr\big[\mathsf{Var}_H^\ell(\mathcal{A}) \Rightarrow 1\big] \le \varepsilon(t)

Again, this is false. $\mathcal{A}$ is chosen after $\ell$ , so it can have a collision for $H(\cdot, 1^\ell)$ written into it. That collision has size $O(\ell)$ , well within the bound $t$ . This is annoying!

Finally, let us consider the asymptotic uniform case.

\forall\, \text{PPT } \mathcal{A}\ \exists \nu_{\mathcal{A}}\ \forall \ell,\quad \Pr\big[\mathsf{Var}_H^\ell(\mathcal{A}) \Rightarrow 1\big] \le \nu_{\mathcal{A}}(\ell)

This statement is potentially true! $\mathcal{A}$ is fixed before $\ell$ . To break the definition it has to win with probability at least $1/p(\ell)$ , for some polynomial $p$ , on infinitely many $\ell$ , but finitely many bits of code can only hold finitely many collisions. Its code could contain a rule for producing collisions instead of a list, but then that rule is a collision-finding algorithm, and it has to run in polynomial time. Hsiao and Reyzin make exactly this point in a footnote [HR04], noting that such a function can only be collision resistant against uniform adversaries.

The flip side is that the definition says nothing about any particular $\ell$ . Take an $\mathcal{A}$ that prints a stored collision when $\ell = 256$ and gives up otherwise. It wins with probability $1$ at $\ell = 256$ and $0$ everywhere else, which is negligible. So a family can satisfy the definition and still be completely broken at $\ell = 256$ , the one parameter we actually use; $\nu_{\mathcal{A}}$ , chosen after $\mathcal{A}$ , can simply be $1$ there.

For a fixed-output-length function like SHA-256 there is no $\ell$ to grow. So the uniform option doesn’t exist, and we are back in the first case. Every failure above has the same shape, namely that $H$ is fixed, so a collision exists, and the adversary is chosen after it.

Putting something after the adversary

The standard fix, going back to Damgård [Dam87], is to make the hash depend on something chosen after the adversary is fixed, such as a key [RoSh04]. Here “after” is about the quantifiers, not the clock: the key is sampled independently of everything written into the adversary. It is not secret, though, as the adversary gets $k$ as input.

\begin{array}{l} \underline{\mathsf{Keyed}_H(\mathcal{A})} \\ k \leftarrow \mathcal{K} \\ (x_1, x_2) \leftarrow \mathcal{A}(k) \\ \text{return } x_1 \ne x_2 \wedge H_k(x_1) = H_k(x_2) \end{array}

\forall \mathcal{A},\ |\mathcal{A}| \le t,\quad \Pr\big[\mathsf{Keyed}_H(\mathcal{A}) \Rightarrow 1\big] \le \varepsilon(t)

The adversary can still have collisions written into it, say a table of collisions for $m$ different keys, but that table only helps with probability $m/|\mathcal{K}|$ , which is tiny for a large key space. The random key turns “a collision exists” into “you need a collision for this key”. This does not make $H_k$ secure by itself: a silly family like $H_k(x) = H(x)$ , which ignores its key, is still broken by one stored collision. What the key buys us is a definition that can actually be true, so that a proof or an assumption has something to say.

This is also why the EasyCrypt SHA-3 result [ABB+19] is meaningful. The theorem says that for every adversary with oracle access to a truly random permutation $P$ and to SHA3- $x$ instantiated with $P$ , making queries of total cost at most $\sigma$ , the following holds.

\Pr\big[\mathsf{CR}^{\mathcal{A}}_{\text{SHA3-}x} = 1\big] \le \frac{\sigma^2 - \sigma}{2^{1600+1}} + \frac{\sigma^2}{2^{2x-2}} + \frac{\sigma^2 - \sigma + 2}{2^{x-1}}

The permutation $P$ is sampled inside the game, after the adversary is fixed, so it plays the role of the key. Unlike the key, though, the adversary never sees all of $P$ ; it can only query it. Of course, the real SHA3- $x$ uses one fixed permutation (Keccak- $f$ [1600]), so for the actual hash function the hard-coded adversary is back and Hsiao and Reyzin’s sentence still applies. The theorem is meaningful because it lives in the ideal permutation model; what happens when the adversary may preprocess $P$ is studied in [CDG18].

Why do we even care about these adversaries?

I argue that the hard-coded collision is a trivial attack. The adversary never finds anything, it just has the answer written in, which feels like it’s “cheating”. And the fact that a collision exists does not mean anyone knows it. It’s “collision resistance” and not “collision freeness”! For a hash function like SHA-256, what we actually care about is whether someone can find a collision, not whether one exists (in fact, one will exist for ANY compressing function). Seen this way, keys feel like a quirk of the theory that we just side-step around.

If the hard-coded adversary is the problem, why not just exclude it? The obvious attempt is to quantify only over adversaries that do not have a collision written into them. This does not work, because “has a collision written into it” is not something we can define. What if the advice is “the collision can be found between range X and range Y”? A collision can be stored encoded, split up, or reconstructed after a few steps of computation. Are those cryptographically “interesting” advice strings, or are they “cheating”? Any adversary that outputs a collision in time $t$ has, in some sense, a collision written into it. So excluding all of them means excluding every adversary that wins, and the definition becomes empty. More generally, excluding adversaries is a slippery slope that cryptography tries to avoid. It is easy to over-reach and exclude adversaries we actually care about.

IND-CCA and guards

This reminds me of how we deal with trivial wins in IND-CCA [RaSi91, BDPR98]. There, we handle them directly in the code of the game. An adversary could come preloaded with some decryption, but this is not a problem. The key, the challenge bit and the encryption randomness are all sampled after the adversary is fixed. So its code cannot be tailored to this particular key or challenge; whether it can still tell which message was encrypted is exactly what the security proof has to rule out. Two trivial wins are left, and the game guards against both: the two challenge messages must have the same length, since ciphertexts usually leak the length, and the decryption oracle refuses to decrypt the challenge ciphertext itself. So between the randomness and the guards, the game removes every trivial win.

The collision game for a fixed hash function has neither of these. Nothing is sampled after the adversary, so a preloaded collision is still valid when the game runs. And there is no guard we could write, because the game cannot tell a stored collision from a found one. Adding a key is exactly the move that gives the collision game what IND-CCA already has.

What actually works

The fixes that do work avoid excluding anyone. The first is to put something random after the adversary, such as a key or an ideal permutation, so that a stored collision is (almost certainly) useless.

The second is to weaken what counts as a win, as in multi-collision resistance [BKP18]. There the hash is keyless, though still indexed by a security parameter, so this is not SHA-256 at one fixed length. An adversary only wins by finding considerably more mutually colliding inputs than it has bits of advice. The intuition is that it cannot simply have them all written in, but this is an assumption, not a counting argument: for iterated hashes, Joux’s multicollisions [Jou04] turn a handful of stored collisions into exponentially many colliding inputs.

Rogaway, in [Rog06], observes that common hash functions are keyless, while our formal definitions of collision resistance are keyed. His fix is to stop trying to directly calculate a proper collision resistance bound for a fixed $H$ . Instead, when a cryptosystem $G$ is built from $H$ , we prove a relative bound

\forall \mathcal{A},\quad \mathsf{Adv}_G(\mathcal{A}) \le \mathsf{Adv}_H\big(\mathcal{B}(\mathcal{A})\big)

for an explicit $\mathcal{B}$ that runs $\mathcal{A}$ and is about as efficient as $\mathcal{A}$ . Crucially, $\mathcal{B}$ must be written down explicitly, since if the theorem only said “there exists a $\mathcal{B}$ ”, that $\mathcal{B}$ could simply print a collision for $H$ . It also has to be efficient, otherwise an explicit brute-force collision search would do. Any attack on $G$ becomes an attack on $H$ , and whether anyone can attack $H$ is left as an assumption, not a theorem.

The auxiliary-input line of work [Unr07, DGK17, CDG18] is another answer, as it keeps precomputation in the model but bounds the advice and counts it explicitly. Admittedly, I still need to give this work a proper read, and maybe that’ll become another blog post in the future.

Closing thoughts

I think foundations are essential and should be studied by all aspiring cryptographers. However, I also, somewhat naively, think we should ask whether they need some altering when we cannot express something as basic as “it is hard to find a collision” without a list of caveats. Keys, uniformity, ideal models and explicit reductions each fix part of the problem, but none of them says exactly what we mean by “it is hard to find a collision”. I have no good answer to this.

In my interpretation, Bernstein and Lange make the same point for concrete security as a whole in “Non-uniform cracks in the concrete” [BL13]. Concrete security usually defines $2^b$ security as the nonexistence of a good attack running in time at most $2^b$ . They give strong evidence that, under this definition, attacks well below $2^{128}$ exist against, e.g., AES-128, but these attacks rely on a huge precomputation that the definition does not account for. They are not realistic and pose no threat to anyone, since finding them in the first place would cost far more than the usual attacks. The definition only counts the cost of running an attack, so it cannot separate them from real attacks, which Bernstein and Lange see as a flaw in the definitions, not in the primitives.

Decades of work have been built on the current foundations, and changing them may not be worth it, or even possible (both in a social and a mathematical sense). What I take away is that these quirks are worth understanding. They decide what a security theorem actually says, and that is easy to lose sight of when the proof checks.

AI Usage

I used Claude Opus 5.5 on high effort to format the text and references and to proofread this. Since I am someone who thinks better by talking, I also used the chat function as a bit of a back and forth to realize my idea.

References

[AB09] S. Arora, B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Available at https://theory.cs.princeton.edu/complexity/.
[ABB+19] J. B. Almeida, C. Baritel-Ruet, M. Barbosa, G. Barthe, F. Dupressoir, B. Grégoire, V. Laporte, T. Oliveira, A. Stoughton, P.-Y. Strub. Machine-Checked Proofs for Cryptographic Standards: Indifferentiability of Sponge and Secure High-Assurance Implementations of SHA-3. ACM CCS 2019, pp. 1607–1622. Available at https://doi.org/10.1145/3319535.3363211.
[BDJR97] M. Bellare, A. Desai, E. Jokipii, P. Rogaway. A Concrete Security Treatment of Symmetric Encryption. FOCS 1997, pp. 394–403. Available at https://doi.org/10.1109/SFCS.1997.646128.
[BDPR98] M. Bellare, A. Desai, D. Pointcheval, P. Rogaway. Relations Among Notions of Security for Public-Key Encryption Schemes. CRYPTO 1998, LNCS 1462, pp. 26–45. Available at https://doi.org/10.1007/BFb0055718.
[BGHZ11] G. Barthe, B. Grégoire, S. Heraud, S. Zanella-Béguelin. Computer-Aided Security Proofs for the Working Cryptographer. CRYPTO 2011, LNCS 6841, pp. 71–90. Available at https://doi.org/10.1007/978-3-642-22792-9_5.
[BKP18] N. Bitansky, Y. T. Kalai, O. Paneth. Multi-Collision Resistance: A Paradigm for Keyless Hash Functions. STOC 2018, pp. 671–684. Available at https://doi.org/10.1145/3188745.3188870.
[BKR00] M. Bellare, J. Kilian, P. Rogaway. The Security of the Cipher Block Chaining Message Authentication Code. Journal of Computer and System Sciences 61(3), pp. 362–399, 2000. (Preliminary version at CRYPTO 1994.) Available at https://doi.org/10.1006/jcss.1999.1694.
[BL13] D. J. Bernstein, T. Lange. Non-uniform Cracks in the Concrete: The Power of Free Precomputation. ASIACRYPT 2013, LNCS 8270, pp. 321–340. Available at https://doi.org/10.1007/978-3-642-42045-0_17.
[CDG18] S. Coretti, Y. Dodis, S. Guo. Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher, and Generic-Group Models. CRYPTO 2018, LNCS 10991, pp. 693–721. Available at https://doi.org/10.1007/978-3-319-96884-1_23.
[Dam87] I. Damgård. Collision Free Hash Functions and Public Key Signature Schemes. EUROCRYPT 1987, LNCS 304, pp. 203–216. Springer, 1988.
[DGK17] Y. Dodis, S. Guo, J. Katz. Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited. EUROCRYPT 2017, LNCS 10211, pp. 473–495. Available at https://doi.org/10.1007/978-3-319-56614-6_16.
[GM84] S. Goldwasser, S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences 28(2), pp. 270–299, 1984. Available at https://doi.org/10.1016/0022-0000(84)90070-9.
[Gol01] O. Goldreich. Foundations of Cryptography, Volume 1: Basic Tools. Cambridge University Press, 2001. Available at https://doi.org/10.1017/CBO9780511546891.
[HR04] C.-Y. Hsiao, L. Reyzin. Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins? CRYPTO 2004, LNCS 3152, pp. 92–105. Available at https://doi.org/10.1007/978-3-540-28628-8_6.
[IR89] R. Impagliazzo, S. Rudich. Limits on the Provable Consequences of One-Way Permutations. STOC 1989, pp. 44–61. Available at https://doi.org/10.1145/73007.73012.
[Jou04] A. Joux. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. CRYPTO 2004, LNCS 3152, pp. 306–316. Available at https://doi.org/10.1007/978-3-540-28628-8_19.
[KL80] R. M. Karp, R. J. Lipton. Some Connections between Nonuniform and Uniform Complexity Classes. STOC 1980, pp. 302–309. Available at https://doi.org/10.1145/800141.804678.
[KL20] J. Katz, Y. Lindell. Introduction to Modern Cryptography, 3rd edition. Chapman & Hall/CRC, 2020. Available at https://www.cs.umd.edu/~jkatz/imc.html.
[RaSi91] C. Rackoff, D. R. Simon. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. CRYPTO 1991, LNCS 576, pp. 433–444. Available at https://doi.org/10.1007/3-540-46766-1_35.
[Rog06] P. Rogaway. Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys. VIETCRYPT 2006, LNCS 4341, pp. 211–228. Available at https://doi.org/10.1007/11958239_14.
[RoSh04] P. Rogaway, T. Shrimpton. Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance. FSE 2004, LNCS 3017, pp. 371–388. Available at https://doi.org/10.1007/978-3-540-25937-4_24.
[RTV04] O. Reingold, L. Trevisan, S. Vadhan. Notions of Reducibility between Cryptographic Primitives. TCC 2004, LNCS 2951, pp. 1–20. Available at https://doi.org/10.1007/978-3-540-24638-1_1.
[Sim98] D. R. Simon. Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions? EUROCRYPT 1998, LNCS 1403, pp. 334–345. Available at https://doi.org/10.1007/BFb0054137.
[Unr07] D. Unruh. Random Oracles and Auxiliary Input. CRYPTO 2007, LNCS 4622, pp. 205–223. Available at https://doi.org/10.1007/978-3-540-74143-5_12.

<< Back to all posts