Explain Fischlin's Fiat-Shamir like transformation
I think I got it.
The point, in short, is that you require multiple proofs (commit_i,challenge_i,response_i), where each proof's validity depends on all the first messages commit; i.e., on COMMIT=(commit_1,..,commit_k).
So if the probability of a good proof is 1/l,
if you try to get a good sequence (proof_1,..,proof_k) by complete random sampling (from the space of l-tuples of correct proofs), it will take you in expectation 1/l^k.
But if you fix COMMIT, and try different values of challenge_i,response_i,
it will take you in expectation lk tries.
Taking l to be polynomial and k super-constrant, you can get the first to be super polynomial but not the second.