Can the PPT adversary ask for a signature of a specific message? Or does it get some message's input and has to deal with it?
כמו כן, האם הוא צריך לזייף הודעה m'>m כלשהי, או את כל ההודעות m'>m?
Prove that any PPT that is given a message $m$ and its signature $s$ (this is equivalent to the PPT asking for a signature on $m$ from its oracle)
is not able to compute a signature $s'$ of a message $m' > m$ (for any such m')
You can prove one of the two:
1. the adversary is given m and a signature on m, and he cannot choose them ==> then, given that he cannot forge a signature on any m'>m
2. the adversary requests for a signature on some m ==> then, given that he cannot forge a signature on any m'>m
But these two are equivalent because it holds for any m and for any m'>m
I would like to join the question and ask, what should we prove:
1) there is no A(m,m') such that m'>m and :
for every x : A(m, f^(n-m) (x) ) = (m' , f^(n-m') (x))
or:
2) there is no A(m) such that:
for every x, there is m' , such that m'> m and:
A(m, f^(n-m) (x) ) = (m' , f^(n-m') (x))
these are 2 different questions, the second seems to be much more difficult to prove
thank you
I'll go for the proof itself, as it is easier:
Assume that a PPT adversary $A$ is given a message $m$ and its signature $s$ is able to compute a signature $s'$ of some message $m’ > m$. Then, prove that in fact $A$ inverts $f^k$ for some $k$ (which depends on $m'$). This in contradiction to section b.