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?

Thank you in advance.

  • $\begingroup$ Does this Q&A answer your question? $\endgroup$
    – 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.

  • 1
    $\begingroup$ 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). $\endgroup$
    – Maarten Bodewes
    May 14 '17 at 12:48
  • $\begingroup$ 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 $). $\endgroup$
    – raisyn
    May 14 '17 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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