I have some hash function representations, which I find it hard to understand.

I have searched a lot but didn't found anything helpful. Please help me understand the hash function representations given below:

Choose cryptographic hash functions
$H_1:\{0, 1\}^*\times\mathbb Z^∗_p\to\mathbb Z^∗_q$
$H_2:\{0, 1\}^*\times\mathbb Z^*_p\times\mathbb Z^*_p\to\mathbb Z^*_q$
$H_3:\{0, 1\}^*\to\mathbb Z^*_q$
$H_4:\mathbb Z^*_p\to\{0, 1\}^{n+k_0}$
$H_5:\mathbb Z^*_p\to\{0, 1\}^{n+k_0}$
$H_6:\mathbb Z^*_p\times\{0, 1\}^{n+k_0}\times\mathbb Z^*_p\times\{0, 1\}^{n+k_0}\to\mathbb Z^∗_q$

I saw this from this paper An Efficient Certificateless Encryption for Secure Data Sharing in Public Clouds (pdf, see section 2.3).


1 Answer 1


I'll review the standard mathematical notations used for $H_1:\{0,1\}^*\times\mathbb Z_p^∗\to\mathbb Z_q^∗$ , going from the bottom up. Hopefully, that will make the rest evident.

$\{0,1\}$ is the set with the two elements $0$ and $1$, known as Booleans.

$\{0,1\}^k$ (for some non-negative integer $k$ ) is the set of tuples with $k$ Booleans, or equivalently of $k$-bit bitstrings; it has $2^k$ elements. For example $\{0, 1\}^3$ (or equivalently, $\{0, 1\}\times\{0, 1\}\times\{0, 1\}$ ) is the set of all three-bit bitstrings: $\{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)\}$.

$\{0,1\}^*$ is the union of all $\{0, 1\}^k$ for all non-negative integers $k$, or equivalently the (infinite) set of all finite bitstrings. This set usually also includes the empty string.

$\mathbb Z$ is the set of (signed) integers. $(\mathbb Z,+,\cdot)$ is the (infinite) ring of integers.

$\mathbb Z_p$ (also denoted $\mathbb Z/p\mathbb Z$, especially in number theory which uses the notation $\mathbb Z_p$ for $p$-adic numbers) is the set of the equivalence classes of the equivalence relation "congruent modulo $p$" over $\mathbb Z$; that is, an element of $\mathbb Z_p$ is a maximal subset of $\mathbb Z$ such that the difference of any two elements in that subset is a multiple of $p$. By taking the smallest non-negative integer in each such subset (which also is the remainder of the Euclidean division by $p$ of any element of such subset), we can assimilate $\mathbb Z_p$ to the set of the $p$ non-negative integers less than $p$. $(\mathbb Z_p,+,\cdot)$ is the (finite) ring of integers modulo $p$.

$\mathbb Z_p^*$ is the subset of elements of $\mathbb Z_p$ (containing elements) having a multiplicative inverse in the ring $(\mathbb Z_p,+,\cdot)$, or equivalently coprime with $p$. An alternative definition is that $\mathbb Z_p^*$ is the maximal subset of $\mathbb Z_p$ making $(\mathbb Z_p^*,\cdot)$ a (finite) group. When $p$ is prime, $\mathbb Z_p^*$ is (assimilable to) the set of the $p-1$ positive integers less than $p$, and $(\mathbb Z_p,+,\cdot)$ is the (finite) field of integers modulo $p$.

$\{0,1\}^*\times\mathbb Z_p^∗$ is the set of (ordered) pairs with the first element of the pair in $\{0,1\}^*$ and the second element in $Z_p^∗$.

$H_1:\{0,1\}^*\times\mathbb Z_p^∗\to\mathbb Z_q^∗$ is a notation stating that $H_1$ is a function from the set $\{0,1\}^*\times\mathbb Z_p^∗$ to the set $\mathbb Z_q^∗$. That is, $H_1$ takes as input a bitstring $b$ of unspecified (but finite) length (possibly the empty bitstring), and an integer $i$ coprime with $p$ and defined modulo $p$ (that is, $i$ and $i+z\cdot p$ are assimilated and will produce the same result for all $z$ in $\mathbb Z$ ), and produces $j=H_1(b,i)$ coprime with $q$ and defined modulo $q$ (we can think of $j$ as a positive integer less than $q$ and coprime with $q$, or as the set of all integers having that remainder by the Euclidean division by $q$ ).

  • 1
    $\begingroup$ Thank you so much! It took me quite a while to finally understand how it works, but thank you that it finally clears up some of my doubts especially on the {0,1}3 is equivalent to , {0,1}×{0,1}×{0,1}{0,1}×{0,1}×{0,1}. Thank you! $\endgroup$
    – Hitsugaya
    Commented Jan 28, 2016 at 15:09

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.