4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ My advice is, try not too hard to understand a security proof. It is often not worth the effort. $\endgroup$
    – user27950
    Aug 16, 2017 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, 2017 at 3:33
  • $\begingroup$ @floorcat: I could tell you a lot about the benefits of being a vegetarian . $\endgroup$
    – user27950
    Aug 19, 2017 at 11:39

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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