0
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ This scheme falls to the same attack as your last suggestion: You can compute any $C=1/(am)\cdot P$ to forge a message. $\endgroup$
    – SEJPM
    Commented Dec 19, 2018 at 10:09
  • $\begingroup$ But in this scheme $a$ is not public - so, the attacker shouldn't be able to calculate $am$. Or am I missing something? $\endgroup$
    – irakliy
    Commented Dec 19, 2018 at 14:16
  • $\begingroup$ Attackers can just choose an $a$ themselves... $\endgroup$
    – SEJPM
    Commented Dec 19, 2018 at 14:25
  • $\begingroup$ Ah! I've updated the scheme by moving $A$ into the public key. Is it still broken? $\endgroup$
    – irakliy
    Commented Dec 19, 2018 at 15:06
  • $\begingroup$ 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$. $\endgroup$
    – Maeher
    Commented Dec 19, 2018 at 15:17

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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'$

$\endgroup$

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.