I'm reading Collision-Resistant Hashing: Towards Making UOWHFs Practical, and they
say that its formalization is non-asymptotic. Why is the formalization non-asymptotic?
What is an example of hash function with an asymptotic formlization?


1 Answer 1


An asymptotic formalization cares only about what happens when the security parameter becomes "large enough". Since we use (essentially) one fixed security parameter, it is certainly possible to construct cryptosystems that would be insecure for some fixed security parameters, but secure in an asymptotic formalization.

This means that a non-asymptotic formalization is to be preferred over an asymptotic formalization (although the latter may be "cleaner").

A silly example is the following construction of a compression function (which should exist under reasonable number-theoretic assumptions):

For $n \leq 10000$, let $p_n = 10^n$. For $n > 10000$, let $u_n$ be the integer made up of the first $n$ decimal digits of $\pi$, and let $p_n$ be the smallest safe prime larger than $u_n$. Let $g=4$ and $h_n$ be the integer we get from the first $n$ decimal digits of $e$.

Let $f_n:\{0,1,\dots,\lfloor (p_n-1)/2 \rfloor\}^2 \rightarrow \{0,1,\dots,p_n-1\}$ be defined by $$f_n(x,y) = g^x h_n^{2y} \bmod p_n .$$

Under reasonable number-theoretic assumptions (that it is asymptotically hard to compute the logarithm of $h_n^2$ to the base $g$ modulo $p_n$), this is asymptotically collision resistant. But for any security parameter $n$ that we would like to use, it is easy to find collisions.

(Note that we can flip this construction around to get a compression function family that is (under reasonable assumptions) collision resistant for any security parameter we care to use, but asymptotically insecure.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.