In BLS short signatures paper, the authors describe a hash function $H\colon\ \{0, 1\}^∗ → G^∗$, where $G$ is a Gap-Diffie-Hellman group.
They present a structure where a standard hash is used on a field element, and then mapped to a subgroup of $G$, later to be used in the security proof as a random oracle.
How would the security proof change (or break) if we'll simply use an exponentiation of some generator of $G$?
i.e., to have $H(m) := g^m$ for some generator $g$.

  • $\begingroup$ see here: crypto.stackexchange.com/questions/11358/… $\endgroup$ – DrLecter Jul 5 '18 at 21:38
  • $\begingroup$ Thanks @DrLecter. In your answer you demonstrated an insecure hash using $H: \{0, 1\}^* \rightarrow G$ as $H(M) = H'(M)P$, using the same generator $P$ used to create the public key $X = xP$. Wouldn't breaking it be avoided if instead we'll define $H(M) = H'(M)Q$ where the discrete log from $Q$ to $P$ is unknown? Or is the problem is to find such a $Q$ in the first place?... $\endgroup$ – oleiba Jul 6 '18 at 9:10
  • $\begingroup$ Finding such a Q is not a problem in this setting. Yes this would make the attack outlined ineffective. But the proof strategy breaks down. $\endgroup$ – DrLecter Jul 6 '18 at 10:55

It is not a secure hash function. For example, one can easily break the collision resistance property: let $q$ be the order of $g$, then $m$ and $m+q$ have the same hash value, $H(m+q)=g^{m+q}=g^m=H(m)$.

  • $\begingroup$ Thanks! What if I'll change that to $H(m) = g^{H'(m)}$ for some CRH $H'$ ? $\endgroup$ – oleiba Jul 6 '18 at 9:19
  • $\begingroup$ You can restrict the domain of H to $\mathbb{Z}_q$, which solves this problem. And yes, you could use a CRH H' tonmap to this domain first. $\endgroup$ – DrLecter Jul 6 '18 at 10:52
  • $\begingroup$ It should be $\mathbb{Z}_q$. $\endgroup$ – DrLecter Jul 6 '18 at 10:59
  • $\begingroup$ So if I understand you correctly, it solves this specific attack but renders BLS' security proof useless?... $\endgroup$ – oleiba Jul 6 '18 at 11:05
  • $\begingroup$ Are you refering to the comment under your question? Then yes. $\endgroup$ – DrLecter Jul 6 '18 at 11:34

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.