# Secure hash function into $\mathbb{Z}_q$

Given the existence of a secure hash function $h: \{ 0,1 \}^* \rightarrow \{0,1\}^k$, how can I construct a secure hash function $h': \{ 0,1 \}^* \rightarrow \mathbb{Z}_q$ ?

Of course this is easy for $q=2^k$, as we can always see $\{ 0,1 \}^k$ as the set $\mathbb{Z}_{2^k}$, but what if $q$ is an arbitrary integer?

• Does this Q&A answer your question? – SEJPM May 13 '17 at 16:46

You can define $h'$ as $h'(m) := h(m) \mod q$.

As long as $2^k$ is larger than $q$ by e.g. 128 bits, the resulting function $h'$ is (almost) equally distributed in $\mathbb Z_q$.

For a suitable hashfunction $h$ you might pick a SHA-3 with variable output size, like SHAKE256.

• I think we discussed something similar before. If you want a well distributed result you can use the output of SHAKE256 as input for a function that extract such numbers from a bit stream, the simplest being compare and redo if too large (this is of course non-deterministic, which can be an issue as you don't know the required output size of SHAKE256 in advance). – Maarten Bodewes May 14 '17 at 12:48
• Well the error is extremely small when compared to the ideal distribution, as long $2^k$ is significately larger than $q$ (e.g. $k=2176$ for a 2048 bit value of $q$). – raisyn May 14 '17 at 13:02