# Hashing functions - How to define them?

Let $$\mathcal{G}$$ be a cyclic additive group for an elliptic curve $$E\, / \ \,\mathbb{F}_p$$, and let $$p, n$$ be two large prime numbers (e.g., we can consider $$\texttt{secp160r1}$$ with $$p = 160$$ bit and the reasonably even $$n$$ is $$160$$ bit long).

I have read several papers in which hashing functions were defined, but I do not understand how the definitions were reached. Let me give you an example:

$$H_1:\{0,1\}^* \times \mathcal{G} \times \mathcal{G} \rightarrow \mathbb{Z}_n^*$$

$$H_2:\{0,1\}^* \times \{0,1\}^* \times \mathcal{G} \times \mathcal{G} \times \mathcal{G} \times \mathcal{G} \rightarrow \mathbb{Z}_p^*$$

My questions are:

1. Why do the authors multiply the value $$\{0,1\}^*$$ by $$\mathcal{G}$$ more than once ? One time is not enough?
2. Why, in the second function $$H_2$$, do they multiply the value $$\{0,1\}^*$$ two times with itself? What changes?
3. If I want to define a third hashing function $$H_3$$, do I need a third prime number or can I leverage $$p$$ or $$n$$ (in $$H_1$$ the output is in $$\mathbb{Z}_n^*$$, and in the second in $$\mathbb{Z}_p^*$$)?
4. What is in practice the difference between $$H_1$$ and $$H_2$$?
5. Supposing that $$n = p = 160$$ bit, may I estimate the output length for each hashing function? Is this long $$160$$ bit right (e.g., could be SHA-1)?
6. Why not simply define a hashing function as $$H:\{0,1\}^* \rightarrow \{0,1\}^l$$?
• It's hard to say without knowing which authors you're talking about, but often it is convenient to use a uniform random function on some prescribed domain and codomain; you can always get something very close to that using a hash function on bit strings by encoding the structured input into a bit string and then projecting the output into some structured output space. E.g., for a map $H\colon\mathbb Z/p\mathbb Z\to\mathbb Z/q\mathbb Z$ when $q\ll2^{2048}$, define $H(x)=\operatorname{SHAKE128-2048}(\underline x)\bmod q$, where $\underline x$ is the little-endian bit encoding of the integer. – Squeamish Ossifrage May 18 '19 at 19:35

1. They are not. First of all, $$\{0,1\}^*$$ and $$\mathcal{G}$$ are not "values", they are sets. $$\times$$ does not mean multiplication, but the Cartesian product of those sets. Second of all, those are not definitions of functions. All that's specified there is the domain and range of the hash functions. Specifically $$H_1$$ maps tuples $$(a,b,c)$$, where $$a\in\{0,1\}^*$$ and $$b,c\in\mathcal{G}$$ to an element of $$\mathbb{Z}_n^*$$.
2. See above. $$H_2$$ maps tuples consisting of two elements of $$\{0,1\}^*$$ and four elements of $$\mathcal{G}$$ to an element of $$\mathbb{Z}_p^*$$.
5. The output of those functions is not a bitstring. It's an element of $$\mathbb{Z}_n^*$$ and $$\mathbb{Z}_p^*$$ respectively. The values may be encoded as a bitstring, where the canonical encoding would indeed have length at most 160 bits.