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 2


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

  • $\begingroup$ 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^*$. $\endgroup$ Commented Apr 14, 2016 at 13:41
  • $\begingroup$ @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. $\endgroup$
    – SEJPM
    Commented Apr 14, 2016 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$.

  • $\begingroup$ 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. $\endgroup$ Commented Apr 14, 2016 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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