Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.)

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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