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?

  • $\begingroup$ 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). $\endgroup$ – Maarten Bodewes May 6 at 12:28

The proposed digital signature scheme is not secure! More precisely, it is not existentially unforgeable under an adaptive chosen-message attack.

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.

  • $\begingroup$ Very clever! Thank for your answer. $\endgroup$ – user82867 May 6 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.