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.)

  • $\begingroup$ 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? $\endgroup$
    – Maeher
    Commented Jul 10, 2020 at 11:16
  • $\begingroup$ @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 $\endgroup$
    – mike
    Commented Jul 10, 2020 at 11:24
  • $\begingroup$ @Maeher sorry for my mistake . i think now i corrected the question. $\endgroup$
    – mike
    Commented Jul 10, 2020 at 11:31
  • $\begingroup$ Makes more sense now. So, any thoughts on the modified scheme I mentioned? $\endgroup$
    – Maeher
    Commented Jul 10, 2020 at 11:54
  • $\begingroup$ @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 $\endgroup$
    – mike
    Commented Jul 10, 2020 at 12:02

1 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.

  • $\begingroup$ In Latex \Pr is available. Please check my edits. $\endgroup$
    – kelalaka
    Commented Oct 6, 2020 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.