In this article https://www.mdpi.com/2073-8994/12/10/1687/htm, specifically in the section 4.1 of the initialization phase,the following cryptographic hash functions have been chosen: \begin{align} h_1&: \mathbb G\to\mathbb Z_q^*\\ h_2&: \{0,1\}^*\times\{0,1\}^*\times\mathbb G\to\mathbb Z_q^*\\ h_3&: \{0,1\}^*\to\mathbb Z_q^* \end{align} where G is an additive group with order q. Can anyone explain to me what's the meaning of their notations and how to use them for example in SHA algortihm? Or maybe give me a simple example with real inputs?

  • $\begingroup$ The paper is fascinating. It dutifully cites 36 earlier papers on the same vein, including the one in this related question. $\endgroup$ – fgrieu Dec 18 '20 at 22:22
  • $\begingroup$ You can also upvote the answers, too. $\endgroup$ – kelalaka Dec 23 '20 at 22:02

The $q$ is defined as the order of the ECC is used. Therefore we need to use a hash function that has at least 256-bit output since the secure curves use at least around that. Let choose SHA256.

  1. $h_1 : \mathbb G\to\mathbb Z_q^*$

    Given $g \in \mathbb G$ represent it in binary and hash with SHA256. Note that the $Z_q^*$ means $Z_q - \{0\}$ so you need to discard if the hash value is zero. Wait, if you luckily hit zero, publish a short paper.

  2. $h_2: \{0,1\}^*\times\{0,1\}^*\times\mathbb G\to\mathbb Z_q^*$

    The $\times$ is used as the function takes input from 3 spaces. You can concatenate the inputs from them, however, two distinct delimiters are required since the first two spaces are not bound (Kleine star). This unboundedness can cause simple collisions, like $aab||ba$ and $aa||bba$ are two distinct inputs from two different input spaces, however, both have the same hash, and this is a collision since the inputs are from different spaces.

    You may need to use 3 inputs like $$String1||\text{delimeter1} || String2 || \text{delimeter1} || g$$ where $String1$ from the first space, $String2$ from the second space and $g \in \mathbb G$.

  3. $h_3: \{0,1\}^*\to\mathbb Z_q^*$

    Nothing special from the above cases.

They say you need 3 distinct hash functions. It is not clear that you may benefit from domain separation like below.

\begin{align} h_1(x)&: \operatorname{SHA256}(\texttt{"Hash-one"}||x)\\ h_2(x)&: \operatorname{SHA256}(\texttt{"Hash-two"}||x)\\ h_3(x)&: \operatorname{SHA256}(\texttt{"Hash-threee"}||x) \end{align}

If it is not this case you may need 3 different hash functions.

Also note that, if the $q > 256$ you cannot use SHA256 directly then use SHA512, Blake2, etc. and trim the result whenever needed.

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Maarten Bodewes Dec 23 '20 at 17:15

The other answer does not detail how to make the result in $\mathbb Z_q^*$, and that was unclear to the OP.

Since $q$ is prime, $\mathbb Z_q^*$ is the integers in the interval $[1,q)$. In the paper's example, $q$ is a 192-bit integer¹. We can use a much larger hash function such as SHA‑512 (or even SHA‑256), reduce the result modulo $q-1$, and add $1$. The result will be reasonably uniform on $[1,q)$. That is$$h(x)=(\operatorname{SHA‑512}(x)\bmod(q-1))+1$$

¹ Specifically $q=2^{192}-2^{64}-1$, which is prime. That's a strange value for the order of an elliptic curve group on a non-singular curve. More generally the paper is riddled with serious issues², I have little confidence in it and some of its references [1…36], and I suggest to question the motivation of any advice to use them as reference, or cite them.

² A few problems:

  • In 4.1 it is not made explicit that prime $q$ is the order of the group $\mathbb G$ of the non-singular Elliptic Curve $E$ on $\mathbb F_p$ of equation $y\equiv x^3+a\,x+b\pmod p$.
  • In table 3 giving $q$, it is the same as $p$, which won't hold for a non-singular curve. Given the values of $p$ and $b$, if $a$ was $-4$, the curve would be secp192r1 aka NIST Curve P-192, which order is 6277101735386680763835789423176059013767194773182842284081 and would be $q$. That's difficult to compute (the standard method is the SEA, which is not for the faint hearted).
  • But $a=-3$ instead! Perhaps it's a typo, but it's one consistent with the (non-standard) coordinates of $P$ given. I have not verified if it results in a curve of prime order.
  • Table 3 states $a$ and $b$ are large primes; however this does not hold in the example (and indeed there is not reason to use primes).
  • It's mentioned symmetric encryption and decryption functions $E_\pi(\cdot)/D_\pi(\cdot)$, but no criteria is given to choose them. On the other hand, I've not spotted they are used ($E$ is used only as the name of the Elliptic Curve, and $\pi$ is one of the less used Greek letters in the article).
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – fgrieu Dec 23 '20 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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