Understanding Hash function notations

Question

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?

Answer 1

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

Answer 2

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