Ex5Q1c

Ex5Q1c

Uri Berger (guest) 08 Jan 2017 17:33

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?

Wondering Wanderer (guest) 09 Jan 2017 08:16

כמו כן, האם הוא צריך לזייף הודעה m'>m כלשהי, או את כל ההודעות m'>m?

oritmosk 09 Jan 2017 17:32

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')

Uri Berger (guest) 11 Jan 2017 12:28

Still didn't get it. Can the adversary choose m? Or is it given m by the outside player, and then it can ask for its signature?

oritmosk 14 Jan 2017 06:34

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

matan (guest) 14 Jan 2017 11:27

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

oritmosk 14 Jan 2017 16:44

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.