Proof for composed signatures

Question

Assumes that we have 3 signature algorithms, $S^A$ with key pair $(sk^A,pk^A)$, $S^B$ with key pair $(sk^B,pk^B)$,$S^C$ with key pair $(sk^C,pk^C)$. We denote by $\epsilon$, $\epsilon'$ and $\epsilon''$ the advantages for breaking $S^A$, $S^B$ and $S^C$ respectively, in the sense of weak unforgeability.

I have a composed signature algorithm which works as follows : First we sign a message with $S^A$, then the result is signed with $S^B$, and finally the result of $S^B$ is signed with $S^C$. An adversary can plays to the game in which he can make queries to a composed signing oracle for the signature of messages of his choices. At the end, the adversay has to find a composed signature for a message which was never queried at the oracle.

Is the adversary advantage bounded by $\epsilon+\epsilon'+\epsilon''+\epsilon \epsilon'+\epsilon \epsilon''+\epsilon' \epsilon''+\epsilon \epsilon'\epsilon''$ ?

I try to construct the proof.. This could be a nice example for me to understand well provable security.

Thank you.

Answer 1

Sketch.

Suppose you have an adversary against the composed scheme with advantage $\epsilon_3$. Observe that whenever you have a signature for the composed system, you have a signature for each of the three component signature schemes.

It should then follow that a forger for the composed signature scheme can be turned into a forger for each of the three signature schemes, and it will have advantage $\epsilon_3$. (This involves a few easy technicalities.)

With that proved, it follows that we can bound the adversary's advantage $\epsilon_3$ by the advantages $\epsilon$, $\epsilon'$ and $\epsilon''$.