# 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?

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