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, 2020 at 22:22
-
$\begingroup$ You can also upvote the answers, too. $\endgroup$– kelalakaDec 23, 2020 at 22:02
2 Answers
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.
$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.
$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$.
$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, 2020 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, 2020 at 13:03