--- Log opened Sat Sep 21 00:00:01 2013
16:37 < gmaxwell> http://www.smbc-comics.com/?id=3119#comic   "Use one-time signatures"
17:41 < gmaxwell> amiller: Can you help me understand why these extractability assumptions are required for 1-round and public verifier NP argument systems?  Why is it not sufficient to just argue that compromising these systems requires finding a collision for the one way hashes (for public verifyable, and PIR 1 round) or breaking the PIR privacy (for the PIR ones).
17:42 < amiller> gmaxwell, the extractibility argument is the only commonly-accepted way of defining what it means to "find" a collision
17:42 < amiller> the point is that it rules out obfuscation
17:43 < amiller> if you could obfuscate the hash function then you could do something that's "like" finding a hash collision, but the hash collision is hidden, and since it's obfuscated you can't get it out, so is it really even there
17:47 < gmaxwell> I guess I'm missing how it connects.  Say I have a PCP system for my NP language which is complete, and with X queries is exponentially unlikely to accept falsely.  I construct a hash tree over it, and I use the hashroot to select a random verifier. Which runs, checks its X points and accepts. So this should be computationally sound for some X, as the prover would have to do retries exponential in X to get false acceptance.
17:48 < gmaxwell> So I don't see where I need to invoke anything stronger than the collission resistance of the hash function to make this work.
17:51 < gmaxwell> (also, as an aside, I don't really get the focus on deletgated computation: any of these schemes have a effort blowup of far beyond 2x for the prover, if I don't trust my cloud provider I can just run my computation N times on N providers. :P   all the real applications I can think of for designated validator don't really need succinctness in the validation. ... succinctness is interesting in the publicly verified cases simply ...
17:51 < gmaxwell> ... because the verification will be done many times)
18:16 < amiller> gmaxwell, i'm pretty sure there are some pcp schemes for NP that are 1 round and only rely on collision resistance, and aren't succinct
18:17 < amiller> hm, i'm not sure actually, maybe that's not possible except with 2 rounds
18:17 < amiller> i know that a big thing in this area are the impossibility proofs that show that something like an extractibility assumption has to exist
18:18 < gmaxwell> Yes, I've seen that mentioned but don't understand why.  A bunch of stuff is also about the PIR-based 1-round systems, which I don't give a shit about because they're designated verifier. (though I think the idea of using PIR to do compression of a PCP is pretty cool)
18:19 < gmaxwell> amiller: but intutively, you have some PCP system where X random queries on it make it sound. You commit to it. Then the verifier does his X random queries checking the hashtree to make sure the prover can't adapt.  There you have a sound two round system.
18:21 < gmaxwell> If you replace the verifier's randomness with some function on the hash root, then a cheating prover can only reduce the soundness by whatever amount he can iterate, assuming the hash function is strong. And since the PCP system's soundness is exponential in the number of queries, adding a few more quries should be enough to achieve soundness against a computationally bounded prover.
18:21 < gmaxwell> So obviously I'm missing something but I'm not sure what.
18:24 < gmaxwell> Wading through papers is somewhat slow because I don't have a huge background in this field, and because I don't care about the succinct designated verifier stuff much, and it's like 3/4 of the papers. (since for bitcoin we either need public verification (e.g. for script or for bitcoin itself), or— for things like my contingent payment protocol, we can have a designated verifier, but we don't care if its succinct)
18:25 < warren> I didn't vote in the election yet.
18:25 < warren> Any thoughts?
18:33 < amiller> you really need succinct public verification don't you
18:34 < amiller> i mean, designated verifier is almost always easier
18:36 < gmaxwell> Right. We need reasonably succinct public verification (secure against verifier oracle, in particular, though if push came to shove we can do a quasi-two-round public verification) for using this stuff for script, or for validating bitcoin itself.
18:37 < gmaxwell> (quasi-two-round: in some schemes we could reduce the size for a given soundness by using future block hashes for a committed proof to throw away part of the proof)
18:39 < gmaxwell> And yea, designated verifier is easier. I was just commenting that for the applications I have for designated verifier, I don't really give a crap about succinctness, except in so far that succinctness also seems to make it easier to be confident about zero knoweldge for the cases where that matters.  I think the whole delegated computing idea is kinda dull.
18:40 < gmaxwell> warren: did you listen to / read the debate with the finalists?
18:41 < warren> gmaxwell: I missed that, searching
18:42 < amiller> gmaxwell, well this is the paper associated with that impossibility proof http://eprint.iacr.org/2010/610.pdf
18:42 < amiller> i don't understand it at any deep level though
18:43 < petertodd> gmaxwell: re: wealth: just make sure you use the right isotope
18:43 < gmaxwell> amiller: ah, thank you!
18:43 < gmaxwell> I note right away:
18:43 < gmaxwell> "The work of [Mic94] showed that such arguments can also be made fully non-interactive in the random-oracle
18:43 < gmaxwell> model. However, this leaves the question whether succinct non-interactive arguments (SNARGs) may exist in the standard
18:43 < gmaxwell> model."
18:44 < gmaxwell> Mic94 is the one that described the PCP scheme above where the commitment is the verifiers randomness. What a slog of a read that paper is.. its like 30 pages just to get to that simple system. :P
18:44 < gmaxwell> So perhaps this is all just not wanting to depend on the random-oracle model? pfft.
18:44 < amiller> yes definitely
18:44 < amiller> okay so the extractibility stuff
18:44 < amiller> is strictly weaker than a random oracle
18:45 < amiller> collision resistant hash -> extractable hash -> random oracle
18:46 < gmaxwell> Considering that pratically all digital signature algorithims in industry deployment have proofs that depend on random oracle, — though ones that don't exist— I am suddenly less concerned.
18:46 < amiller> the hope is that something like extractability is a more limited assumption and maybe somethings atisfies it
18:47 < amiller> so when it comes to building security proofs of these things
18:47 < amiller> basically if you know a thing is extractable
18:48 < gmaxwell> I've read the paper that shows that things which are sematically secure under random oracle are not necessarily secure under _any_ realizable scheme but I felt it was pretty contrived.  I guess the thing that I was missing was just that extractable was supposted to be a more limited assumption than random oracle.
18:48 < amiller> then you get to say, suppose any arbitrary adversary produces a valid proof, then i can run an extractor on that adversary that produces the actual hash collision, and that extractor is only polynomially than the original adversary itself
18:48 < amiller> for a proof with the random oracle, you basically get to look at the oracle queries directly
18:50 < amiller> so logically it's almost as good, except that the extractor can get really big if you apply extractability over and over again to work backwards
18:50 < amiller> so extractability sucks, basically
18:50 < amiller> it's the worst of both worlds
18:50 < amiller> it turns what would be simple in the random oracle world into a really frustrating counting argument that doesn't seem to even increase security
18:51 < amiller> but it's still a really strong assumption anyway and non-falsifiable etc etc
18:54 < gmaxwell> amiller: thanks. Okay, I both understand this better now, and realize that I previously understood more of it than I thought.
18:54 < amiller> np
--- Log closed Sun Sep 22 00:00:05 2013