I know that the normal construction for Ajtai hash functions is as follows:

Pick $n, m, q \in \mathbb{Z}^+$ such that $n \log q < m < \frac{q}{2n^4}$ and $q = O(n^c)$ for some $c>0$, and some random matrix $A \in {\mathbb{Z}_q}^{n \times m}$. Then the Ajtai hash function $f_A: \{ 0,1 \}^m \to \mathbb{Z}_q^n$ is defined as $$f_A(\vec{x}) = A \vec{x} \mod q.$$

I notice that $\mathsf{dom}(f_A) = \{ 0,1 \}^m$ but my question is what happens when $\mathsf{dom}(f_A) = D^m$ for any arbitrary $D \subset \mathbb{Z}_q$? What are the limitations on the kinds of $D$ I can pick such that the function retains all the useful properties of being a hash function, and how would the choice of $D$ impact the security constraints I mentioned above (i.e. $n \log q < m < \frac{q}{2n^4}$).

Like for example, what if instead of the input being a bitstring, I want it to be a byte array, so $D = \{ 0, 1, \dots, 255 \}$ (for some $q \gg 255$), or similar.

Is there any way to easily find these constraints and parameters? Rules of thumb and so on. Or any literature around this? Or is it a situation where you have to do mathematical analysis on a case-by-case basis?

And if you do find the new security constraints for a given $D$, and pick valid parameters $n, m, q$, how do you then go on to measure how many bits of security you get against collision attacks? (i.e 256 bits of security against collision attacks)


1 Answer 1


Micciancio studies precisely this question (for an "algebraically structured" version of the Ajtai hash) in Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. See Section 4 in particular.

  • 1
    $\begingroup$ Thankyou so much. Reading through this paper is like a blessing $\endgroup$ Commented Mar 22 at 5:47

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.