I'm not sure I fully understand how A works: when it's asking for the signatures for the t messages, does the state change (for each signature)?

You should distinguish between the forger and the legitimate signer. Since this is a state based signature scheme, the state of the signer will indeed change as it signs additional messages.

For the forger, we do not know how its computations are carried out. It can ask (adaptively) to signatures of up to t messages. But it does not have direct access to any secret information on the

signer's side.

I'll rephrase:

What is the public key for the stateful signatures? Is it vk_i (after signing the i-th message), or is it all the chain (messages, public keys, signatures)?

Either way, sounds too me like it doesn't match the definition for the experiment of Existential Forgery under Chose Plaintext Attack- in our experiment, we said that A gets the public verification key, vk. In this case, the public verification key will change with each oracle request by A, so its given public key isn't relevant anymore.

Another difficulty with the definitions is what exactly does the t-epsilon rival output?

We know it forges a signature according to the chain-based schema. But the signature is dependent on previous messages:

{pk_j, m_j, sigma_j} for all j <= i

So do the t messages that A got their signatures from the oracle are the messages in its forged signature?

Mainly, what is the format of the forged signature of A?

I will be glad for a response. The hw is due date is in 3 days.

I'll try to help-

Uri:

There is one main verification key, namely that of the first layer. This one is published and "known to all" as in forgery under chosen plaintext attack. Since it is stateful, the state, or more verification keys, are published on the fly and given to the adversary, to create the "chain of trust". If it bothers you that there are verification keys in the algorithm that arn't published at the beginning - think of them as a "verified state", and only the original key is the published verification key, and that the verification function uses the published key, and the "verified state" to test the signature. I hope I didnt confuse you even more…

Watson:

The adversary tries to output some chain that has not been seen before. This might be taking some of the previous chains and appending onto it a new entry, or it might mean changing the order of a chain, or even forging something totally unseen before.

Or more formally, it outputs $\{pk_j,m_j,\sigma_j\}_{j\in [k]}$ for some k (bound polynomially of course, since the adversary is PPT). Where the exact same chain was not given to A at any point by the oracle (but perhaps some subset of the chain was).

And of course, the chain passes the verification test.

That greatly helped, thanks Very Fire.

It is still unclear in what way A interacts with the oracle.

Each time A queries the oracle for a signature for some m_t with verification key vk_t then it receives a signature {pkj,mj,σj}j∈[k]

where the last message in the the signature is m_t signed with verification key vk_t, is this correct?

More or less, but note that we both slightly messed up the notation. The verification keys are $vk_j$ and there is no $pk_j$ (that is, the signature itself is $\{vk_j,m_j,\sigma_j\}_{j\in[k]}$).

When A queries for $m_t$, it receives a signature $\{vk_j,m_j,\sigma_j\}_{j\in[t]}$ which is signed using the secret key $sk_{t-1}$ and verified using the verification key $vk_{t-1}$, which A already has.

excatly- the chain is the signature itself. A queries with messages, receives chains from the oracle, and must fake a chain and message pair (just like in the regular signature scheme, you fake $(m',\sigma')$)

But shouldn't the verification keys of the forged signature be the same as v_0, … , v_t used in the oracle queries?

Again this is all regarding the definition of adversary A to the chain-based scheme. Not part of the solution…