These are hash functions, but I don't understand their notations, can anyone tell me what's the difference between H, H1 and H2? $\mathbb{G}_1$ is an additive group and $\mathbb{G}_2$ is a multiplicative group. Both groups have the same prime order p and their bilinear mapping is $e: \mathbb{G}_1 \times \mathbb{G}_1 \to \mathbb{G}_2$ Source:https://www.cs.nmsu.edu/~misra/papers/T-ITS-2011.pdf

\begin{align} H&: \mathbb G_1\to\{0,1\}^n\\ H_1&: \mathbb G_2\to\{0,1\}^n\\ H_2&: \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n \end{align}

  • $\begingroup$ @kelalaka I edited now , thank u for telling me $\endgroup$
    – Chai Ma
    Nov 22, 2020 at 10:58
  • $\begingroup$ It from an article , should i post it too ? $\endgroup$
    – Chai Ma
    Nov 22, 2020 at 11:01
  • $\begingroup$ I added it now. $\endgroup$
    – Chai Ma
    Nov 22, 2020 at 11:11
  • $\begingroup$ There is nothing special there. If you search the hash in the paper you will see that thy used SHA-1! $\endgroup$
    – kelalaka
    Nov 22, 2020 at 11:15
  • $\begingroup$ I know it's SHA-1, but what's the difference in using just one of them and why they have different notations? $\endgroup$
    – Chai Ma
    Nov 22, 2020 at 11:16

1 Answer 1


The notation $H:\mathbb G_1\to\{0,1\}^n$ means that $H$ takes as input an element of $\mathbb G_1$, and produces as output an $n$-bit bistring.

The notation $H_1:\mathbb G_2\to\{0,1\}^n$ similarly means that $H_1$ takes as input an element of $\mathbb G_2$, and produces as output an $n$-bit bistring.

The notation $H_2:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ means that $H_2$ takes as input a pair of $n$-bit bistrings, and produces as output an $n$-bit bistring.

If you ask me, the names are not well chosen. It would be more mnemonic to use $H_1$ (resp. $H_2$, $H$) where there's $H$ (resp $H_1$, $H_2$).

But that's far from the worse there is in this paper. Things like

The ECDLP had been proved to be a hard problem [19].

are wrong (what's cited to support this falsehood actually makes ECDLP tractable on some curves). I hope studying this paper was not recommended as part of a course in cryptography. If so, I fear there's something deeply flawed in this recommendation process.

Addition per comment: I do not see that the authors explain how they build their hashes, except for a mention of SHA-1 in section VI. A reasonable implementation with $n=160$ based on SHA-1 could use

$$\begin{align} H(g)&\underset{\text{def}}=\operatorname{SHA-1}(c_0\mathbin\|\hat g)\\ H_1(g)&\underset{\text{def}}=\operatorname{SHA-1}(c_1\mathbin\|\hat g)\\ H_2(u,v)&\underset{\text{def}}=\operatorname{SHA-1}(c_2\mathbin\|u\mathbin\|v)\end{align}$$ where $\hat g$ is a bitstring uniquely representing (as a fixed number of bits) an element $g$ of $\mathbb G_1$ or $\mathbb G_2$, and $c_0$, $c_1$, $c_2$ are public distinct 32-bit bitstrings tasked with making the three hash functions somewhat independent from the perspective of security analysys.

Note: SHA-256 or better should be used rather than SHA-1, which is obsolete and quite practically broken as a collision-resistant hash when operating on messages sizably larger than 768-bit. But as far as we know, SHA-1 remains 80-bit secure in the above constructions, because what's hashed is short.

Note: This shall not be construed as an endorsement of the article. I do not understand enough about functional requirements of a Pseudonymous Authentication-Based Conditional Privacy Protocol for VANETs to tell if they are met by the cryptography outlined; and only understand some of the crypto involved. The article does not tell enough to convince a cryptographer about the security of the implementation. In particular, I have doubt that the BLS signature based on "the Type-A curve defined in the PBC library with the default parameters" could be fast, 154-bit as suggested (the exact size is not stated), and secure to the 80-bit security level targeted.

  • $\begingroup$ Thank you. Actually, this paper wasn't recommended as part of a course in cryptography but I was given the task of searching for a Cryptographic solution for VANETs to implement. Honestly, I have no experience in cryptography and I don't know much so I can't tell if there are wrong things. I assumed that scientific articles are proved to be true. $\endgroup$
    – Chai Ma
    Nov 22, 2020 at 12:20
  • $\begingroup$ @Chai Ma: cryptography articles in reputable peer-reviewed cryptographic journals can generally be trusted as mostly correct. For cryptography, that includes IACR publications. Here the publication's theme is intelligent transportation systems. This is applied science, and not cryptography, thus it can't be blindly assumed that the material is correct from a cryptographic standpoint. $\endgroup$
    – fgrieu
    Nov 22, 2020 at 12:57
  • $\begingroup$ I see now, thank you for sharing that with me. I was wondering about something in this article, they're using the BLS short signature scheme the one proposed by Boneh et al and ECDLP, how can I implement these concepts? Is a trusted library for them that I should implement or something else? $\endgroup$
    – Chai Ma
    Nov 22, 2020 at 13:09
  • $\begingroup$ BLS is hard to implement, especialy the choice of pairing. Here's a list of libraries. I can't make a first-hand recommendation of any. $\endgroup$
    – fgrieu
    Nov 22, 2020 at 13:32
  • $\begingroup$ Thank you for the advice. How can $H_2$(which is a SHA1 hash function) take a pair of n-bit bistrings as input? I mean hash functions take only one parameter as input right? $\endgroup$
    – Chai Ma
    Nov 22, 2020 at 23:13

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.