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.



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

  • $\begingroup$ 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... $\endgroup$ – Dingo13 Aug 29 '14 at 15:06
  • $\begingroup$ 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. $\endgroup$ – K.G. Aug 30 '14 at 21:27
  • $\begingroup$ So, $\epsilon_3 \le max(\epsilon,\epsilon',\epsilon'')$. Is that right ? $\endgroup$ – Dingo13 Sep 3 '14 at 6:51
  • $\begingroup$ You have $\epsilon_3 \leq \epsilon$, $\epsilon_3 \leq \epsilon'$ and $\epsilon_3 \leq \epsilon''$. Can you find a smaller bound? $\endgroup$ – K.G. Sep 4 '14 at 12:49
  • $\begingroup$ Thank you. I can't. Can we fing such a bound with a max(...) in proofs of security ? $\endgroup$ – Dingo13 Sep 11 '14 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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