# 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}&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.)

• Maybe, to get an intuition, first consider the modified scheme, that verifies both signatures. (i.e. replace "or" with "and" in the definition of verification) Is that modified scheme secure? Does the same proof work for the original scheme from the question? If not, is it fixable? – Maeher Jul 10 '20 at 11:16
• @Maeher what i meant by last sentence was to show if there is an attacker for scheme s2 we can use it as subroutine to attack scheme s – mike Jul 10 '20 at 11:24
• @Maeher sorry for my mistake . i think now i corrected the question. – mike Jul 10 '20 at 11:31
• Makes more sense now. So, any thoughts on the modified scheme I mentioned? – Maeher Jul 10 '20 at 11:54
• @Maeher in the case of modified scheme it would be easy to forge,but in case of 'or' the problem is i cant tell for which key (sk0 or sk1) attacker could forge a signature – mike Jul 10 '20 at 12:02

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.