--- Log opened Fri Aug 30 00:00:28 2013
--- Day changed Fri Aug 30 2013
00:00 < gmaxwell> amiller: so what you're doing will break the signature of knoweldge proof, right, because you won't know how to build an extractor?
00:02 < amiller> if i only use "standard" knowledge assumptions, then i can build an extractor but it might be exponential sized, which is vacuous
00:03 < gmaxwell> right if the extractor is exponential sized then it just tries all inputs. :P
00:04 < gmaxwell> amiller: having a weak proof of knoweldge would kinda suck. well, there are lots of cases where weak security is okay...
00:05 < gmaxwell> I'm still annoyed about 3/4 of MPC papers using this "semi-honest" model, and not even all that obviously from their text.
00:05 < amiller> the thing is, these knowledge assumptions are on really shaky ground anyway
00:05 < amiller> they're "non falsifiable" assumptions
00:05 < amiller> they reguire "non black box" access to the adversary
00:06 < amiller> they are basically non-constructive reductions about obfuscation being hard
00:06 < gmaxwell> I know, right, if you have a prover who produce a valid proof, and you have full open access to his state, you can extract a witness with realistic work.
00:09 < amiller> so basically i think i should just use the recursive extractor and leave worrying about it to future owrk
00:09 < amiller> it's sound in any 'oracle' model
00:09 < amiller> it's more plausible that this is a problem with the knowledge definition than a problem with using snarks this way
00:10 < amiller> it's a weird situation
00:10 < amiller> it's not even clear what an "attack" on this knowledge assumption would be
00:10 < amiller> to do something without knowing it
00:16 < amiller> the more cool stuff i can do "conditionally secure" on the definition working out, the easier it will be to justify working on the definition?
00:17 < amiller> i mean it feels unhealthy to say i'm going to go off and assume i can use all these things that aren't justified yet
00:17 < amiller> but whatever, #yolocrypto
00:21 < gmaxwell> yea, well, I think it's helpful to think about how this stuff would be used. e.g. the proof of knoweldge being strong is important for the CoinWitness type usage.
00:23 < amiller> yeah, i'd be really interested to come up with a more satisfying definition than the extractor
00:23 < amiller> what are some important implications of 'knowledge of a witness'
00:23 < amiller> certainly if you could 'know' a witness and no such witness existed it wouldn't make sense
00:24 < amiller> when witnesses vacuously exist like in the hash preimage case it's stranger because "knowing it exists" isn't as good as "knowing it"
00:28 < gmaxwell> I think a lot of this stuff is going to remain dumb and unknown until it gets into actual use with actual stakes.
00:28 < gmaxwell> Too much academic output works itself into little useless ruts with definitions which are mathmatically fun but meaningless in practice.
00:30 < amiller> it's an especially difficult balance with security/crypto
00:31 < amiller> since the actual attackers are invisible/untestable
00:32 < gmaxwell> not quite, I mean— set things up so there are bitcoin which can only be moved if the system is compromised. (may require keeping a victim to interact with online)
00:33 < amiller> yeah that sort of helps
00:33 < amiller> it would have to be pretty big to actually motivate serious effort from cryptanalysts
00:33 < gmaxwell> thats what secures my laptop. :P  I dunno, people take things where there is no reward simply because they can publish on it.
00:33 < amiller> also it's just as likely it would reveal a minor implementation error rather than the fundamental failure of a concept
00:34 < amiller> so i think the most productive thing to do is take snarks and run with them.
00:34 < gmaxwell> and yea, thats a problem... I'd like to get the tresor hardware wallet people to embed a private key of theirs in every device... and have the wallet willing to signmessage for the key to prove its in there. ... with some bounty coin assigned to the key.
00:34 < gmaxwell> so that when someone has compromised the hardware security, people know about it.. but unfortunately that doesn't give you much information...
00:35 < gmaxwell> and you'd find that it was compromised with a really hard attack, thats not all that interesting.
00:39 < amiller> recursive snarks are just so damn sexy, it will have instant practical appeal
00:39 < amiller> this ben-sasson character is nuts if he thinks we're actually going to recompile the whole verifier for every possible batch-size of blocks :p
00:40 < gmaxwell> amiller: oh, you know their forumulation fixes the UPPER size, right?
00:41 < gmaxwell> you can just pad out the computation to make it meet the upper size.
00:41 < amiller> yeah
00:41 < amiller> ok every "possible" batch size is an exagerration
00:41 < gmaxwell> so then with log2() extra calculations for sizes you have only a worst case ~2x overhead in prover work.
00:42 < amiller> yes but it's still a big circuit to compile eacch time
00:43 < amiller> bootstrapping etc
00:46 < amiller> also all the proving would have to be redone for each different block size
00:46 < gmaxwell> I thought the bootstraping version of Eli's stuff didn't require any preprocessing anymore.
00:47 < amiller> the thing i want to do is just a simpler form of bootstrapping
00:47 < gmaxwell> the downsides of it is that the proofs are larger for equal security, and they don't have a strong zero-knoweldge property... but they eliminate the generator and in particular the need for the generator to have a strongly secret random string.
00:47 < amiller> the papers that advocate bootstrapping and do it without incurring the extractor-blowup problem bend over backwards to have only 'constant depth' bootstrapping
00:48 < amiller> they haven't implemented the bootstrapping, rihgt?
00:51 < gmaxwell> I don't know where their implementation stands, I know they have running the generator based version and have all kinds of benchmarks on it. They certantly have _plans_ for the bootstrapping version.
00:52 < gmaxwell> The generator version kinda sucks because if the prover is in cahoots with the generator he can easily generate fake proofs. Plus the prover keys are enormous. Plus the generation is, like the proving, slow.
00:55 < amiller> lets ask how the bootstrap version is coming along :o
03:50 < gmaxwell> So, that idea I had for making lamport signatures smaller by using a tree structured CSPRNG to build your secrets.  I came up with another thing to apply it to where it is way more powerful.
03:51 < gmaxwell> Say you want to produce an encrypted card deck for someone, which is correct with high probablity and randomly shuffled with high probablity.
03:52 < gmaxwell> First you build a set of — say, 65536— secret values, using a tree structured CSPRNG.
03:52 < gmaxwell> Then you build a hash tree over them, and tell Bob (you are alice) the root hash of your secrets.
03:53 < gmaxwell> Bob them picks a random value and tells it to you.
03:54 < gmaxwell> You generate 65536 regular card decks in order. And you take half of each of your secrets and encrypt each card deck.  You then take the other half of each secret hash it with bob's random value and use it to run a PRNG to shuffle each deck.
03:54 < gmaxwell> You now have 65536 encrypted, shuffled decks. You build a hash tree over them. and tell bob the root of the hash tree.
03:55 < gmaxwell> Bob picks 65535 out of the 65536 decks for you to reveal.
03:56 < gmaxwell> So you then find the minimal number of nodes in your secret value tree such that when you reveal them bob learns all your secrets except for the excluded result.
03:56 < gmaxwell> you also give bob the excluded result deck but not its secret and bob can compute all the decks except the excluded one, and verify the root.
03:57 < gmaxwell> Bob is now convinced that he knows an encrypted fairly sorted deck.
03:57 < gmaxwell> and you only had to transmit to him one deck and log2(65536)=16 plus a few hashes.
05:22 < gmaxwell> petertodd: so, if you combine all my recent ideas you can do guy fawkes signatures in a blockchain cryptosystem in one stage, and elimiate the announce/commit crud.
05:24 < gmaxwell> petertodd: the idea is that you create a tree compressed lamport signature in your transactions and flood to the network, with everything but the signature hashroot external to the transaction. When it gets mined, the block hash is used as the source of random selection to reduce the proof size.
05:24 < gmaxwell> once sufficiently burried the signature is pruned down to nothing and it's effectively just a guy fawkes signature.
06:55 < petertodd> gmaxwell: nice!
11:02  * Luke-Jr wonders if GCC can be compiled with SCIP to make gitian obsolete
21:51 < jorash> I think I may have found a channel open to the project I'm part of...
21:51 < jorash> We're a bunch of quantum information scientists working on the problem of efficient classical emulation of universal computation (answer the question of does P = BQP in the positive)
21:52 < jorash> One of the implications is that miner can be developed which runs a quantum search algorithm (such as Grover's square root speedup, or Gross-Pitaevskii's constant time speedup) and yields mined coin much faster than current hardware brute force methods
--- Log closed Sat Aug 31 00:00:58 2013