Why do we need to convert hashes to points on an elliptic curve?

tn flag

In order to sign message m, m must be mapped to a point in G.1

However, Point can be multiplied. Why can't I simply do $mG$?


  • $pk = [sk]G_1$
  • $m = hash(message)$
  • Signing: $s = m [sk] G_2$
  • Verify: $e(G_1, s) == e(pk, m G_2)$

Oh, if it is possible to convert G1 to G2, it seems possible to multiply the public key by m. then,

  • Signing: $k = random, r = kG_2, s = [sk] (m + k)$
  • Verify: $e(G_1, sG_2) == e(pk, r + mG_2) $
  • ($[sk](m + k) == [sk](k + m)$)
ru flag

Because under such a scheme possession of a single valid signature allows an adversary to forge arbitrary messages.

Suppose I have a signature $S=m[sk]G_2$ for the message $m$ and wish to forge a signature for a message $m'$. Using the Euclidean algorithm I compute $x=\frac{m'}m$ modulo the order of $G_2$ and then create the new signature $S'=xS=m'[sk]G_2$. Verifier could confirm that $e(G_1,S')=e(PK,mG_2)$, but this signature was produced without knowledge of the private key.

my flag

In order to sign message m, m must be mapped to a point in G

In BLS, we do (not that's all that difficult) - other EC based signature algorithms, such as ECDSA and EdDSA, have no such need.

To answer the specific BLS-type proposals you made:

Why can't I simply do $mG$?

Well, your first suggestion would allow anyone to perform a forgery; it had:

  • Signing: $s = m [sk] G_2$

Then, suppose someone had a valid signature $s$ for a known message $m$. Then, they could compute $m^{-1} s = [sk] G_2$; with that, they can sign any message they wanted.

Your second suggestion would also allow forgeries (given a valid signature of a known message); if the attacker had a valid $(r, s)$ pair for a message $m$, then to sign a message $m'$, he can construct $r' = (r + (m - m')G_2, s' = s$; on the rhs, the validator would compute $e(pk, r' + m'G_2) = e(pk, r + mG_2)$, which would match the lhs (because the attacker used the same $s$).

I sit in a Tesla and translated this thread with Ai:


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.