# Signature scheme doesn't seem to hold

I can't seem to verify the signature scheme described below.

Key Generation

Public Key: $$y_1=g^{a_1}y^{a_2} \pmod p$$ $$y_2=g^{b_1}y^{b_2} \pmod p$$ $g$ denotes a generator of $Z_p^*$ and $y$ is a random element from $Z_p^*$. The private key is $(a_1,a_2,b_1,b_2)$.

Signing $$\sigma_1=a_1m+b_1 \pmod q$$ $$\sigma_2=a_2m+b_2 \pmod q$$ where $q\mid p-1$. The signature on $m$ is $(\sigma_1,\sigma_2)$.

Verification. To verify $(m,\sigma_1,\sigma_2)$ one does the following. $$y_1^my_2 \overset{?}{=} g^{\sigma_1}y^{\sigma_2}\pmod p$$

Taking this as an example: $p = 23$, $g = 7$, Private Key : $(12$, $20$, $3$, $18)$, $y = 16$ and $q = 2$

This will give me:

$$y_1 = 7^{12} \cdot 16^{20} = 13 \pmod{23}$$ $$y_2 = 7^{3}\cdot 16^{18} = 10 \pmod{23}$$

Now signing a message $m = 13$:

$$\text{output}_1 = 12(13) + 3 = 1 \pmod 2$$ $$\text{output}_2 = 20(13) + 18 = 0 \pmod 2$$

Verifying gives me:

Equation 1 = $13^{13} \cdot 10 = 11 \pmod {23}$

Equation 2 = $7^1\cdot 16^0 = 7 \pmod {23}$

As you can see from the above equation, 11 is not equal to 7 and I cannot verify it.

I suspect the problem lies with using the wrong $q$. Should the value of q exclude 1 and 2?

Any idea at which step I go wrong?

-

The text you quoted appears to be incorrect; as specified, it doesn't always work (as you found out).

$y_1^m y_2 = g^{\sigma_1} y^{\sigma_2}$ will hold in general if both of the following are true:

$$a_1 m + b_1 \equiv \sigma_1 \pmod{p-1}$$

$$a_2 m + b_2 \equiv \sigma_2 \pmod{Order(y)}$$

Note: it is possible for the equation to hold in other conditions, but because $y$ has no known relationship with $g$, it would be infeasible to find other solutions for non-toy instances of this problem, even for the valid signer.

However, the text specifies that $\sigma_1$ and $\sigma_2$ are computed modulo $q$; if $q < p-1$, then neither of these equations are guaranteed to hold.

I can see two obvious ways to fix up this method:

• Specify $q = p-1$; then both $\sigma_1$ and $\sigma_2$ will satistfy the above conditions (N.B.: all possible values of $y$ have an order that is a divisor of $p-1$)

• Allow any $q | p-1$; however, specify that both $g$ and $y$ must be of order q.

Also, as specified, this scheme would appear to be insecure as a signature scheme; with two valid signatures, an attacker should be able to recover $a_1, a_2, b_1, b_2$, which is the private key.

-
Thanks for the clarification!! May I know what does it mean by $g$ and $y$ must be of order $q$? Any examples? –  Calvin Peh Nov 8 '14 at 16:27
$g$ is of order $q$ if $g^q \equiv 1$ (and if there is no smaller $q > 0$ where this holds; although that's actually not important in this case). In your example, $g$ is of order 22. An alternative value with order 11 would be $g=2$ –  poncho Nov 8 '14 at 17:10