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 &lt; 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.