0
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\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, 2014 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, 2014 at 21:27
  • $\begingroup$ So, $\epsilon_3 \le max(\epsilon,\epsilon',\epsilon'')$. Is that right ? $\endgroup$
    – Dingo13
    Sep 3, 2014 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, 2014 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, 2014 at 8:56

Your Answer

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

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