Proof by reduction for for digital signature scheme $S_2((sk_0,sk_1), m):=(S(sk_0,m), S(sk_1,m))$ 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}&amp;V_2((pk_0,pk_1), m,(\sigma_0,\sigma_1))= \text{'accept'}\\\iff&amp;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.)
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.