2
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – X.H. Yue
    Apr 18, 2023 at 14:10

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.