2
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ see here: crypto.stackexchange.com/questions/11358/… $\endgroup$
    – DrLecter
    Jul 5, 2018 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, 2018 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, 2018 at 10:55

1 Answer 1

3
$\begingroup$

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)$.

$\endgroup$
12
  • $\begingroup$ Thanks! What if I'll change that to $H(m) = g^{H'(m)}$ for some CRH $H'$ ? $\endgroup$
    – oleiba
    Jul 6, 2018 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, 2018 at 10:52
  • $\begingroup$ It should be $\mathbb{Z}_q$. $\endgroup$
    – DrLecter
    Jul 6, 2018 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, 2018 at 11:05
  • $\begingroup$ Are you refering to the comment under your question? Then yes. $\endgroup$
    – DrLecter
    Jul 6, 2018 at 11:34

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.