Explain Fischlin's Fiat-Shamir like transformation I've been trying for a while to understand why this paper is correct:
ftp://ftp.inf.ethz.ch/pub/crypto/publications/Fischl05b.pdf.

The idea is a NIZK-POK where you require the hash of the commit-challenge-response to be small.
This is supposed to force the prover to make multiple hash queries for each commit, which consequently enables an extractor to extract the witness without having to rewind.
But what I can't figure out - is why not just try multiple witnesses/commits , rather than multiple challenges for a given commit?
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.