# Proof for composed signatures

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.

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''$.

• Thanks @K.G. $\epsilon_3$ is bounded by the "sum" of $\epsilon$, $\epsilon'$ and $\epsilon''$ ? Or by the "maximum" of the 3 advantages ? I understand that when I have a forgery fo a composed signature, then I have a forgery for one of the 3 signatures systems... – Dingo13 Aug 29 '14 at 15:06
• Recall that a scheme is $\epsilon$-secure if any adversary has advantage at most $\epsilon$. For any $\epsilon_3$-forger (adversary with advantage $\epsilon_3$) against the composed system, we get an $\epsilon_3$-forger against any of the three systems. Now we apply the definition of secure. – K.G. Aug 30 '14 at 21:27
• So, $\epsilon_3 \le max(\epsilon,\epsilon',\epsilon'')$. Is that right ? – Dingo13 Sep 3 '14 at 6:51
• You have $\epsilon_3 \leq \epsilon$, $\epsilon_3 \leq \epsilon'$ and $\epsilon_3 \leq \epsilon''$. Can you find a smaller bound? – K.G. Sep 4 '14 at 12:49
• Thank you. I can't. Can we fing such a bound with a max(...) in proofs of security ? – Dingo13 Sep 11 '14 at 8:56