# How to construct a hash function that maps any binary string into a multiplicative group element? [duplicate]

Pairing based cryptography schemes such as identity-based encryption or different attribute-based encryption schemes (CP-ABE, KP-ABE etc.) often make use of a hash function defined as $H_1:\{0,1\}^* \rightarrow \mathbb{G}_1$. Where, $\mathbb{G}_1$ is a multiplicative group of some large prime order $p$. Then, the function $e:\mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ is called a bilinear pairing if it has bilinearity, non-degeneracy and computability properties. Here, $\mathbb{G}_2$ and $\mathbb{G}_T$ are also groups. Now, my question is, how such a hash function $H_1$ is constructed?

• Probably you'd first apply a standard hash to reduce the length of the input to $N$ bits (say 256, 512, 1024 bits), and then map the resulting number $h \in \{0, \dots, 2^{N} - 1\}$ to $(h \mod{p}) \in \{0, \dots, p-1\}$. This mapping is not entirely uniform, but assuming $2^N \gg p$, it is "almost" uniform.
– TMM
Feb 20 '17 at 1:01
• Details on how this particular hash function is to be implemented is given in the Boneh-Franklin paper (eprint.iacr.org/2001/090.pdf, §4.3,§5.2). Feb 20 '17 at 11:14