I don't understand how is this possible- by my understanding, Lamport's scheme is determinstic (after the keys are chosen), and therefore, given (m,sigma), we can't output (m',sigma') where m=m', sigma' is a valid signature of m' and sigma != sigma'.

And if so, it must be for some different message (that is, m != m'). But in that case, for the same OWF, Lamport's scheme isn't one time NORMAL (not strong) signature scheme, which condradicts what we talked about in class.

What am I missing?

Ex5Q2