Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question


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

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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