Score:2

Replacing the Hash function with messages in the BLS signature scheme, the security degenerates from EUF to SUF?

in flag

​I have been thinking about this question: if I directly replace the hash function with the message in the BLS signature, does the security of the BLS degenerate from existential unforgeability(EUF) to selective unforgeability(SUF) under the known message attack(KMA)?

The modified BLS signature scheme is defined as below. $\cdot BilinearGen\to pp:=(G_1,G_2,G_T,e,p,g_1,g_2)$ where the paring type is type-III.

$\cdot KeyGen(pp)\to(pk:=g^x_2\in G_2,sk:=x\in Z_p )$

$\cdot Sign(sk,m)\to\sigma:=m^x\in G_1$ where $m\in G_1$.

$\cdot Verify(\sigma,pk)\to(e(m,pk)?=e(\sigma,g_2) )$

The notion of selective forgery as an attack where the adversary can forge a valid signature with non-negligible probability for a particular message $m^*$, e.g., let $m^*=g^b_1$, chosen by the adversary prior to accessing the signing oracle.

Intuitively, the SUF security of the modified version can be reduced to some assumption, such as CDH assumption(An instance can be expressed as $(g^a_1,g^b_1,g_1)$). And I tried but failed as I'm not farmilar with proof without random oracle.

So, my questions are:

  1. The above modified BLS signature scheme is SUF-KMA security if CDH assumption holds?

For example, the adversary A can be given some message-signature tuples $\{(m_i,\sigma_i)\}_{i\in [n]}$. If A can forge a valid signature on the specified message $m^*=g^b_1$, then there must be another adversary B can sovle the instance of CDH assumption $(g^a_1,g^b_1,g_1)$) by the output of A.

  1. If yes, plz give me some clues or examples to continue the incomplete security proof.

  2. If no, plz tell me why.

Score:1
cn flag

Assuming your're talking about a Type-1 or Type-2 pairing it is definitely not selectively unforgeable, even under a no-message attack. Here's an attack:

Specify $m = g^b$ as the message to forge a signature for. Upon input the public key $pk = g^x$, output the signature $\sigma = pk^b$.

It is easy to see that by the bilinearity of $e$ $$e(pk,m) = e(g^x,g^b) = e(g,g^b)^x = e(g,g^{xb}) = e(g,pk^b) = e(g,\sigma)$$

It is probably universally unforgeable under a no-message attack but not under a chosen message attack.

If the pairing is Type-3, the no-message attack outlines above no longer works. Chosen message attacks exploiting the homomorphism should still apply though.

ming alex avatar
in flag
Thanks a lot, I got your idea. I re-edit my question and specify the type of pairing. Then, in this setting, can the modified BLS signature reduce to CDH assumption under SUF-KMA?
mangohost

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.