# How to realize a hash function H:{0,1}* × G × {0,1}* -> Zq ？

I read papers about cloud storage data integrity audit, which needs PBC library and GMP library.

The author define encryption hash function $$H:\{0,1\}^* \times G \times \{0,1\}^* \to \Bbb Z_q$$, used as $$H(ID,R,RN) \bmod q$$, $$G$$ is a cyclic multiplicative group with order $$q$$ ,$$q$$ is a large prime, $$R, ID,RN$$ are elements of $$G$$.

I don't know how to compute $$H(ID,R,RN) \bmod q$$ ,they may multiply or do exponent arithmetic ?or use hash function like SHA1 ? How can I construct this function?

• Welcome to Cryptography.SE. When someone asked about some read papers, usually we want the links and maybe a little summary of them so that your question can be correctly answerable. Also, in our site we have $\LaTeX / MathJax$ is enables. I've edited some. Note hash functions are not encryption. Maybe you want to say. cryptographic hash function? Sep 6 '20 at 10:18

If elements $$R$$ of $$G$$ can uniquely be expressed as a bitstring $$\overline R$$ (e.g. by taking the two components in a finite field of the affine coordinates of $$R$$, each uniquely representable as a fixed-size bitstring, and these are concatenated to form $$\overline R$$), then it is easy to construct a generic hash $$H:\{0,1\}^* \times G \times \{0,1\}^* \to \mathbb Z_q$$ from a standard $$b$$-bit hash $$F:\{0,1\}^* \to \{0,1\}^b$$, say SHA-512 with $$b=512$$, as follows:

• $$h\gets F\big(F(\text{ID})\mathbin\|F(\overline R)\mathbin\|F(\text{RN})\big)$$, which is a hash of $$(\text{ID},R,\text{RN})$$ in the set $$\{0,1\}^b$$
• if $$\log_2q>b/2\,$$, expand $$h$$ as follows:
• $$g\gets h$$
• for $$i$$ from $$1$$ to $$\big\lceil(\log_2q-b/2)/b\big\rceil\,$$
• $$h\gets h\mathbin\|F(g\mathbin\|\overline i)\,$$, where $$\overline i$$ is a bitstring uniquely representing the integer $$i\,$$ (e.g. encoding $$i$$ in big-endian base 256 as a minimal number of bytes, then converted to binary)
• $$r\gets \underline h\bmod q\,$$, where $$\underline h$$ is the integer coded by the bitstring $$h$$ per big-endian binary

The result $$r$$ is the desired hash of $$(\text{ID},R,\text{RN})$$ in the set $$\mathbb Z_q$$.

This hash has nearly the same security as $$F$$ or an ideal hash in $$\mathbb Z_q$$, whichever is lower. Argument (or lack of a reference), under a model of the hash $$F$$ as a random oracle (and any security reduction is is with respect to that):

• The step "$$h\gets F\big(F(\text{ID})\mathbin\|F(\overline R)\mathbin\|F(\text{RN})\big)$$" is a generic composition of hashes, in order to hash multiple inputs of variable size (while maintaining collision resistance contrary to mere concatenation), and allowing a security reduction.
• The step "if $$\log_2q>b/2\,$$, expand $$h$$" does that essentially as in MGF1, again allowing a security reduction.
• The step "$$r\gets \underline h\bmod q\,$$" insures the output is in the desired range. It create a bias towards low values, but since at least $$b/2$$ bits are discarded this bias is low, and it's possible to upper-bound the advantage a distinguisher can obtain.
• Can you please link a paper that estimates the security of H? Mar 18 '21 at 15:06
• @Mikhail Kudinov: sorry I don't have a reference. I have added a security argument, and will think about making it more rigorous; but don't hold your breath.
– fgrieu
Mar 19 '21 at 10:33
• That last step makes assumptions about F beyond collision resistance. Mar 19 '21 at 11:04
• @Maeher: Agreed in full. I put myself "under a model of the hash $F$ as a random oracle", and any later "security reduction" is w.r.t. that [update: added that to the answer]. My "while maintaining collision resistance" is not meant as an intermediary step in a proof (rather, as a rationale for multiple hashes), and the whole thing is not intended to be a proper proof.
– fgrieu
Mar 19 '21 at 11:28
• Sure, for a random oracle that should work. Mar 19 '21 at 12:10