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$?
  • $\begingroup$ 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. $\endgroup$ May 18, 2019 at 19:35

1 Answer 1

  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^*$.
  3. You don't need any prime numbers to define a hash function. But also there are no definitions of hash function anywhere in your question.
  4. They have a different domain. Meaning that they accept different inputs.
  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.
  • $\begingroup$ Thank you very much for this detailed answer. But in practice what do you mean with the answers 1. and 2.? Can you put an example in order to describe it? It is very useful for me. And finally in 4. what do you mean about "different inputs"? Could you provide an example? $\endgroup$
    – CipherX
    May 18, 2019 at 6:46
  • $\begingroup$ Furthermore, what is the difference to choice an element that belongs to G or {0,1}^*? $\endgroup$
    – CipherX
    May 18, 2019 at 6:50

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.