# Does this pairing-based signature scheme work?

Suppose $$g$$ is a pairing-friendly elliptic curve with subgroup generators $$G_1$$ and $$G_2$$. Suppose also that $$M$$ is the message I want to sign.

Setup

1. Compute $$A = a \cdot G_1$$ and $$P = p \cdot G_2$$, where $$a$$ and $$p$$ are some secret values.
2. The public key is then defined as a tuple $$(A, P)$$.

Signature

1. Hash message $$M$$ to a number using a hash function: $$m=Hash(M)$$.
2. Compute $$C = \frac{p}{a \cdot m} \cdot G_2$$.
3. The signature is then defined as $$C$$.

Verification

1. Compute $$m = Hash(M)$$.
2. Verify that $$e(A, C)^m = e(G_1, P)$$.

Are there any holes in this scheme?

• This scheme falls to the same attack as your last suggestion: You can compute any $C=1/(am)\cdot P$ to forge a message. – SEJPM Dec 19 '18 at 10:09
• But in this scheme $a$ is not public - so, the attacker shouldn't be able to calculate $am$. Or am I missing something? – irakliy Dec 19 '18 at 14:16
• Attackers can just choose an $a$ themselves... – SEJPM Dec 19 '18 at 14:25
• Ah! I've updated the scheme by moving $A$ into the public key. Is it still broken? – irakliy Dec 19 '18 at 15:06
• Let $C$ be a signature for $M$. We compute a signature for $M'$ by computing $x=H(M')/H(M)$ and $C' = \frac{1}{x}\cdot C$. – Maeher Dec 19 '18 at 15:17

## 2 Answers

Your proposed signature scheme falls to universal forgeries under a known message attack (UF-KMA).

The adversary $$\mathcal{A}$$ receives the public key $$(A,P)$$, a single message signature pair $$(M,C)$$ and the challenge message $$M^*$$. It outputs $$C' := \frac{H(M)}{H(M^*)} \cdot C.$$

The adversary described above is succesful with probability $$1$$. To see this, consider that $$C$$ is by definition $$C = \frac{p}{a\cdot H(M)} \cdot G_2.$$ We now have \begin{align} C' &= \frac{H(M)}{H(M^*)} \cdot C\\ &= \frac{H(M)}{H(M^*)}\cdot\frac{p}{a\cdot H(M)} \cdot G_2\\ &=\frac{p\cdot H(M)}{a\cdot H(M) H(M^*)} \cdot G_2\\ &=\frac{p}{a\cdot H(M^*)} \cdot G_2, \end{align} which is exactly the signature of $$M^*$$ and will therefore be accepted by the verification equation.

No, it doesn't work; forgeries are still easy.

Suppose the attacker has a valid signature $$C$$ for a message $$M$$ with $$e(A, C)^m = e(G_1, P)$$

Now, the attacker has a second message $$M'$$ with $$m' = \text{Hash}(M')$$.

Then, the attacker computes $$C' = (m'^{-1} \cdot m)C$$

Then, we have $$e(A, C')^{m'} = e(A, m' C') = e(A, mC) = e(A, C)^m$$, which agrees with the constant (for a public key) $$e(G_1, P)$$, and so $$C'$$ is a valid forgery for $$M'$$