# Is this pairing-based signature scheme secure?

There are a number of signature schemes on small domains based on bilinear pairings which do not use random oracles. Examples are the Boneh-Boyen schemes and an interesting one from Okamoto which allows for blind, and partially blind signatures.

However all of them use some variant of the Strong Diffie Hellman assumption which (roughly) asks to compute $$e(g,g)^{1/x}$$ from $$(g, g^x, g^{x^2}, \ldots, g^{x^q})$$.

The signature scheme I have in mind is this:

Public information: $$g_1 \in \mathbb{G}_1, g_2 \in \mathbb{G}_2$$, bilinear pairing $$e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$$

Signer secret: $$x_1, x_2 \in \mathbb{Z}_p^*$$

Signer public: $$A=e(g_1, g_2)^{x_1}$$, $$B=e(g_1, g_2)^{x_2}$$

The signature algorithm takes an element of $$m \in \mathbb{Z}_p^*$$ and computes $$\sigma(m) = g_1^{x_1m+x_2}$$. The verification algorithm checks that $$e(\sigma(m), g_2) = A^m B$$

Forgery seems to require computing $$g^{m'x_1+x_2}$$ from $$(g^{m_1x_1+x_2}, g^{m_2x_1+x_2}, \ldots, g^{m_nx_1+x_2})$$ where $$m' \neq m_i$$.

Is this scheme secure and if so is it used anywhere?

• Uh, I wrote "DLP based" in the title to be more specific, but I don't think this is necessarily correct or applicable. Could you give it a try and make the title of the question more specific "Is this signature scheme secure" is very generic (gave it another try myself). – Maarten Bodewes May 6 at 12:28

Let's consider the following efficient adversary $$\mathcal{A}$$: it queries the $$\mathsf{Sign}_{sk}(\cdot)$$ oracle for the digital signatures on $$m_1,m_2$$, where $$m_2:=m_1+1$$. The received signatures are $$\sigma_1=g_1^{x_1m_1+x_2}$$ and $$\sigma_2=g_1^{x_1m_2+x_2}$$. Now, $$\mathcal{A}$$ computes $$\frac{\sigma_2}{\sigma_1}=\frac{g_1^{x_1m_2+x_2}}{g_1^{x_1m_1+x_2}}=g_1^{x_1(m_2-m_1)}=g_1^{x_1}$$. Once $$g_1^{x_1}$$ is recovered, $$\mathcal{A}$$ can also compute $$g_1^{x_2}=\frac{\sigma_1}{(g_1^{x_1})^{m_1}}$$.
The knowledge of these $$2$$ points ($$g_1^{x_1}$$ and $$g_1^{x_2}$$) enables now $$\mathcal{A}$$ to forge signatures on any message of their choice. Namely, given any message $$m$$, $$g_1^{x_1}$$ and $$g_1^{x_2}$$, the valid signature on $$m$$ can be computed as $$\sigma=(g_1^{x_1})^{m}g_1^{x_2}=g_1^{x_1m+x_2}$$. The adversary $$\mathcal{A}$$ outputs $$(m,\sigma)$$ as a valid forgery and wins the security game.
This means, that the adversary can win the existential unforgeability security game with probability $$1$$ already after $$2$$ signature queries.