# Unable to understand hash function representations

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

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

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

• 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! – Hitsugaya Jan 28 '16 at 15:09