Proof by reduction for for digital signature scheme $S_2((sk_0,sk_1), m):=(S(sk_0,m), S(sk_1,m))$

Question

Let $(Gen,S,V)$ be a secure signature scheme (existentially unforgeable under a chosen message attack) with message space${\{0,1\}}^n$. Generate two signing/verification key pairs $(pk_0,sk_0)\gets Gen$ and $(pk_1,sk_1)\gets Gen$. Is the following a secure signature scheme? Show an attack or explain why the scheme is secure, that is, explain why an attack on the scheme leads to an attack on $(Gen,S,V)$.

The new scheme is :

$$ S_2((sk_0,sk_1), m):=(S(sk_0,m), S(sk_1,m))$$ \begin{align}&V_2((pk_0,pk_1), m,(\sigma_0,\sigma_1))= \text{'accept'}\\\iff&V(pk_0,m,\sigma_0) = \text{'accept'}\quad \text{or}\quad V(pk_1,m,\sigma_1) = \text{'accept'} \end{align}

I do not know how to give a formal proof (probably proof by reduction) that the scheme is secure. (Maybe by showing if there is an attacker for scheme $S_2$ we can use it to attack $S$ and calculating new attacker advantage and showing that it's not negligible.)

Answer 1

So this is a solution I came up with based on this chat with @Maeher.

We use proof by reduction to show if there exists an attacker $A$ with non-negligible advantage for $S_2$ we can use it to construct an attacker $B$ for $S$ with non-negligible advantage. If $$\Pr[vrfy(pk_0,m,\sigma_0) \;\; and \;\; vrfy(pk_1,m,\sigma_1)]$$ be non-negligible then easily we can construct $B$ to give us a forgery for $S$. So we assume this probability is negligible and without loss of generality assumes the above probability is equal to $0$. now suppose the non-negligible advantage of $A$ is

$$ adv2 = \Pr[vrfy(pk_0,m,\sigma_0)] + \Pr[vrfy(pk_1,m,\sigma_1)] = p_0 + p_1 $$. attacker $B$ take as input public key $pk$ and call $Gen$ algorithm to have $(pk_1,sk_1) ,( pk_0,sk_0) $ then it uniformly choose bit $b$ form $\{0,1\}$ and pass $(pk,pk_b)$ to the $A$. then $A$ return $(m,(\sigma,\sigma_b))$ and $B$ choose $(m,\sigma)$ as it's forgery. advantage of $B$ will be equal to $adv$ which $$adv \geq \frac{1}{2}(adv2 - p_0) + \frac{1}{2}(adv2 - p_1) = \frac{1}{2} adv2 $$

so $adv$ is non-negligible.