# Understanding Hash function notations

I am implementing a Certificateless Cryptography Algorithm by referencing the paper An Efficient Certificateless Encryption for Secure Data Sharing in Public Clouds. In this paper on page no. 4 during setup phase they have mentioned to choose hash functions (in my case it's SHA-256). But some of the notations are confusing me.

Choose Cryptographic Hash functions :

$H_1 : \{0,1\}^* \times Z_p^* {\rightarrow} Z_q^*\\ H_2 : \{0,1\}^* \times Z_p^* \times Z_p^* {\rightarrow} Z_q^*\\ H_3 : \{0,1\}^* {\rightarrow} Z_q^*\\ H_4 : Z_p^* {\rightarrow} \{0,1\}^{n + k_0}\\ H_5 : Z_p^* {\rightarrow} \{0,1\}^{n + k_0}\\ H_6 : Z_p^* \times \{0,1\}^{n + k_0} \times Z_p^* {\rightarrow} Z_q^*$

where $n$, $k_0$ are the bit-length of a plaintext and a random bit string, respectively.

Can any one please explain me how do I interpret above hash functions. I have one more doubts in this algorithm,

Correct me if I am wrong $x$$H_1 (ID_A,w_0) means x \times H_1(ID_A) \oplus H_1(w_0) where x \in Z_q^* Or it has another meaning? ## 2 Answers So let's start with the hash functions:$$H_n:A\times B\times C \rightarrow D$$is the mathematican's notion for a function called H_n that takes arguments from the sets A,B,C (in this order) and maps it to D, where B,C are optional. You're facing three types of sets for this: • \{0,1\}^* is the set of binary bit-strings of arbitrary size, e.g. any data that can be represented as a sequence of bits • \{0,1\}^{n+k_0} is the set of binary bit-strings of length n+k_0, e.g. any data that is exactly n+k_0 bits long. • \mathbb Z_q^* and \mathbb Z^*_p are the sets of all natural numbers smaller than q and p respectively. The tricky part is instantiating these functions now. You can instantiante them using KDF2 (combined with optional concatenation) and / or using HKDF or HMAC which can all be based off SHA-256. The input is quite simple: You just feed the data (in the appropriate representation) into the KDFs and you're done. The binary output is also simple: The KDFs can produce arbitrary-sized outputs and you truncate what is too much (they usually run in some sort of CTR-mode internally). The really tricky part is converting the binary hash string to an integer. The best you can do is to generate a string a little bit longer (a few bits) than what is needed for the modular reduction and then apply the modular reduction (e.g. \bmod q) to the converted integers. This should give a "good-enough" distribution Correct me if I am wrong x$$H_1$ $(ID_A,w_0)$ means $x \times H_1(ID_A) \oplus H_1(w_0)$ where $x \in Z_q^*$

No, you're supposed to take it literally. You call $H_1(ID_A,w_0)$ and multiply the result (which is in $\mathbb Z^*_q$ by definition) with $x$ which is also chosen from $\mathbb Z^*_q$, e.g. $x\times H_1(ID_A,w_0) \bmod q$.

• I understood some of the part you explained in answer by what about multiply cyclic group with Hash, do I need to take any value from cyclic group i.e. $a$ ∈ $Z_q^*$. – Vighanesh Gursale Apr 14 '16 at 13:41
• @VighaneshGursale, I guess you refer to the lower part? The "hash" should output an integer of the cyclic group and you can multiply that one normally with $x$ and if you're asking how to convert the hash output into such an integer, just look at the paragraph directly above. – SEJPM Apr 14 '16 at 17:11

Correct me if I am wrong $xH_1$ $(ID_A,w_0)$ means $x \times H_1(ID_A) \oplus H_1(w_0)$ where $x \in Z_q^*$

It is hard to formally respond because I don't have access to the paper you mention but with common sense, just by reading the $H_1$ definition, $xH_1$ $(ID_A,w_0)$ means $x \times H_1(ID_A, w_0)$ where $ID_A \in \{0,1\}^*$ and $w_0 \in Z_p^*$. But this notation does not imply antyhing on the set of $x$ so I don't know why do you suppose that $x \in Z^*_q$.

• The actual statement in base paper is $d_0 : s_0 + xH_1(ID_A,w_0)$ where $s_0$ is any random value of $Z_q^*$, this part is in the phase of Key-Generation where they are trying to generate some parameters. – Vighanesh Gursale Apr 14 '16 at 13:36