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?

  • $\begingroup$ My advice is, try not too hard to understand a security proof. It is often not worth the effort. $\endgroup$ – user27950 Aug 16 '17 at 11:38
  • $\begingroup$ @Cryptostasis Where's the fun in that? You need meat with your veggies...you can't have any pudding if you don't eat your meat... $\endgroup$ – floor cat Aug 19 '17 at 3:33
  • $\begingroup$ @floorcat: I could tell you a lot about the benefits of being a vegetarian . $\endgroup$ – user27950 Aug 19 '17 at 11:39

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.