00:04:48	gmaxwell:	kanzure: if we want to be all secret decoder ring about it, here is what we do.
00:05:25	kanzure:	i don't know which it we're talking about, but i'm listening
00:05:31	zooko:	me neither and me too!
00:05:32	gmaxwell:	the tweet.
00:05:44	kanzure:	oh that's way less interesting than what i was hoping we were talking about
00:05:50	kanzure:	i am going to proceed with my prior assumptions then
00:06:33	nsh:	there was a paper that suggested you can do ECC in 400 bytes of RAM but it's in Springerjail
00:06:38	gmaxwell:	You generate your secret and a second random value. By hand you sum your secret and the random value. Now take your secret+random and your random value to seperate computers and compute x*G for each. then do the single point addition by hand to get your pubkey. :P
00:06:58	nsh:	(bytes of RAM being roughly commensurate to 'moving parts' in some mechanical system)
00:07:09	zooko:	gmaxwell: huh!
00:07:26	gmaxwell:	the first addition is plain integer addition mod order, which is trivial. The point addition requires something like 8 field operations, so it's going to take you a while by hand. :P
00:07:55	gmaxwell:	but its completely reasonable and I assume you could do it in under an hour.
00:07:57	nsh:	* nsh would like to see some abacus pros doing ECC
00:08:05	kanzure:	nsh: you mean springerkink
00:08:43	nsh:	* nsh nods
00:08:59	kanzure:	why isn't the tor onion routing stuff a separate library? i don't see why it has to be tor-only code.
00:09:24	nsh:	.title http://crypto.stackexchange.com/questions/8747/how-to-build-an-electro-mechanical-public-key-cipher-machine
00:09:24	yoleaux:	historic - How to build an electro-mechanical public key cipher machine? - Cryptography Stack Exchange
00:09:26	gmaxwell:	kanzure: it's not usefully abstractable.
00:09:28	kanzure:	this stuff over here: https://gitweb.torproject.org/tor.git/blob_plain/HEAD:/src/or/circuitbuild.c
00:10:17	sipa:	8 field operations? how fast does a human do a 512-bit by 256-bit division...?
00:10:40	sipa:	oh; field; if it's secp256k1 there's an easier way to do a modulus
00:10:53	gmaxwell:	yea.
00:11:11	gmaxwell:	well you can use repeated subtraction to do the reduction instead of division in any case.
00:11:15	nsh:	" I wonder if you could implement ECC in hardware? Have a flexible line defined by the equation to serve as a cam surface, then place a straightedge at points P and Q to find the intersecting point. It could be a great illustrative tool, but I doubt it could be made accurate enough to provide the security required. – John Deters Jun 17 '13 at 16:50 "
00:11:42	nsh:	that's zooko-worthy crazebition :)
00:11:51	zooko:	Haha
00:11:57	kanzure:	cc kragenjaviersitaker
00:12:06	gmaxwell:	nsh: lol thats goofy, ECC over Fp^n is only conceptually related to ec over reals... in particular discrete log for ec on reals is not hard.
00:12:15	nsh:	right
00:12:47	nsh:	but perhaps you can shift the quantization?
00:13:09	nsh:	not sure that makes any sense
00:13:24	sipa:	nsh: http://bitcoin.stackexchange.com/questions/21907/what-does-the-curve-used-in-bitcoin-secp256k1-look-like
00:13:28	gmaxwell:	sipa: also you can get a pubkey in jacobian, and just have a computer reduce it to affine, as thats easy to check.
00:19:37	zooko:	So, FWIW, I was imagining a hash function instead of "public key". :-)
00:20:20	sipa:	nsh: heh, i wonder how much ram my implementation of secp256k1 uses at most (excluding the precomputed tables)
00:20:22	gmaxwell:	ah people have done sha256 by hand. (sha256^2 in fact)
00:20:43	nsh:	hmm
00:21:16	nsh:	is there a limit to processing/ram tradeoff particular to a given algorithm/calculation?
00:21:41	nsh:	ie, generally you can use less state at the expense of longer processing but only to a point
00:21:57	nsh:	how does that point depend on the intrinsics of the calculation?
00:22:21	sipa:	oh, for verification some factors are converted to wNAF form, which takes 4*129 bytes
00:25:22	gmaxwell:	nsh: there really is no limit for the s*G task, though obviously you run out of fast ram at some point. For the a*G + b*P multiexp, where only G is a constant base that you use over and over again and P you only use once, there is a small optimal amount of table to use.
00:25:55	nsh:	hmm
00:25:57	gmaxwell:	(the multiexp is what signature verification is doing; P is the pubkey)
00:26:08	nsh:	* nsh nods
00:26:37	gmaxwell:	For the multiply with a generator case, it basically always gets faster with a bigger table if you're assuming memory bandwidth is infinite.
00:26:59	sipa:	latency you mean
00:27:12	sipa:	ah, for signing; never mind
00:27:42	gmaxwell:	on i4770r which has a 128mb L4 cache. I get the best performance for multiply with a constant point using a 70mbyte-ish table.
00:27:45	nsh:	if we're aiming for something like an abacus that can be used by a trained human with good manual dexterity at 'reasonable' speed
00:28:00	nsh:	there will be some optimum degree of mechanical/state complexity
00:28:25	gmaxwell:	well for e.g. generate a pubkey, if you're allowed a book you want the most precomputation possible.
00:29:02	nsh:	* nsh nods
00:29:15	gmaxwell:	e.g. a book with 65536 entries lets you do the whole multiply yourself with only 16 point additions.
00:29:23	nsh:	* nsh wonders about an ECC precomp slide-rule type device
00:29:42	nsh:	books are suboptimal for hand-based look-up, really
00:29:56	gmaxwell:	they can have tabs.
00:29:58	fanquake:	fanquake has left #bitcoin-wizards
00:30:06	nsh:	* nsh nods
00:35:06	zooko:	sorry -- I'm playing Thunderstone in real life with my brother Nathan and my 10yo son. :-)
00:40:07	rusty:	gmaxwell: is there a canonical writeup on UTXO commitments somewhere? I can only find scattered references...
00:59:10	phantomcircuit:	gmaxwell, i have done the first 3 and the last 3 stages of sha256 by hand
00:59:16	phantomcircuit:	0/10 would not recommend
01:00:19	gmaxwell:	rusty: no, sprawling discussions, maaku's work is probably the most sophicated.
01:00:34	gmaxwell:	I think maaku is not around today or I'd ping him for links.
02:24:47	maaku:	maaku is now known as Guest76468
02:37:14	zooko:	phantomcircuit: haha
02:42:48	wallet42:	wallet42 is now known as Guest67358
02:42:48	wallet421:	wallet421 is now known as wallet42
02:52:48	amiller:	rusty, i have a paper and an ocaml library that makes authenticated data structure protocols for any data structure https://amiller.github.io/lambda-auth/
02:57:58	amiller:	rusty, i have a forum post, https://bitcointalk.org/index.php?topic=101734.0 etotheipi has one https://bitcointalk.org/index.php?topic=88208.0 maaku has one https://bitcointalk.org/index.php?topic=204283.0 petertodd has an implementation too https://github.com/petertodd/python-merbinnertree
02:58:46	amiller:	i think all of those are the best references... not *too* scattered
03:23:39	rusty:	amiller: thanks! Reading now...
09:05:18	asimov.freenode.net:	topic is: This channel is not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
09:05:18	asimov.freenode.net:	Users on #bitcoin-wizards: andy-logbot cbeams Guyver2 nuke1989 webdeli waxwing berndj-blackout grandmaster2 Baz____ coiner aburan28 bitbumper TheSeven c0rw|sle_ FBI-AGENT maaku__ op_null rusty epscy dgenr8 zibbo rfreeman_w hashtag_ tromp Emcy koshii mkarrer_ Luke-Jr null_radix Aquent spinza jaekwon_ go1111111 Graftec fenn Starduster Nightwolf postpre ryanxcharles iddo Hunger- HaltingState d4de luny nubbins` SDCDev Pan0ram1x adlai arowser jaekwon samson_ lclc_bnc K1773R
09:05:18	asimov.freenode.net:	Users on #bitcoin-wizards: s1w Eliel_ kanzure bobke LaptopZZ warptangent Shiftos isis btcdrak iambernie sneak harrigan michagogo hguux_ gavinandresen SubCreative JonTitor devrandom ebfull phantomcircuit sl01 Cory Grishnakh sipa mortale DoctorBTC Flyer33 Alanius jbenet HM dansmith_btc artifexd btc__ kumavis mappum Muis azariah4 nanotube orw MRL-Relay fluffypony jgarzik PaulCapestany BlueMatt a5m0 kgk LarsLarsen gazab AdrianG yoleaux gwillen livegnik BananaLotus Myagui
09:05:18	asimov.freenode.net:	Users on #bitcoin-wizards: @ChanServ burcin coutts wizkid057 Dyaheon bbrittain NikolaiToryzin forrestv nickler mr_burdell Logicwax Meeh tromp_ Krellan poggy pi07r_ comboy mmozeiko lnovy Taek optimator_ [\\\] Apocalyptic throughnothing petertodd crescendo CryptOprah cfields-away Fistful_of_Coins gmaxwell kinlo ahmed_ so Anduck [d__d] espes BigBitz otoburb wumpus EasyAt starsoccer hollandais jaromil helo Keefe Iriez huseby phedny midnightmagic nsh coryfields andytoshi
09:05:18	asimov.freenode.net:	Users on #bitcoin-wizards: BrainOverfl0w warren asoltys gribble Graet smooth amiller danneu catcow TD-Linux [Tristan] ryan-c roasbeef harrow lechuga_ pigeons
09:33:53	c0rw|sle_:	c0rw|sle_ is now known as c0rw|away
10:03:24	berndj-blackout:	berndj-blackout is now known as berndj
14:49:31	adam3us:	so petertodd gengix and gwern discussed and then petertodd implemented a scheme for time-lock encryption https://github.com/petertodd/timelock and peter mentions gengix and links to gwern. http://www.gwern.net/Self-decrypting%20files
14:51:18	adam3us:	and if i am understanding it correctly, the idea is to farm out a say 1000 1hr hashchains to 1000 nodes starting from 1000 independent IVs, then encrypt the second IV with the k1=H^k(iv1) so you have E_k1( iv2 ) and so on.
14:51:37	adam3us:	the idea being setup is parallel but decrypt is serial
14:52:15	adam3us:	now this has a problem firstly it takes as much aggregate work to setup as decrypt. secondly the nodes you farm the setup to could remember the solutions and collude to decrypt with no additional work.
14:52:15	kanzure:	sounds right
14:52:44	kanzure:	oh, which nodes are you expecting to farm out to?
14:53:25	adam3us:	it doesnt say.. i was guessing other people? as they were talking long time-frames for decryption and presuming the person doesnt have a personal supercomputer.
14:53:39	adam3us:	(eg like month per parallel thread so it could take years to decrypt)
14:56:07	adam3us:	anyway i think its missing several solutions which are more efficient and private/secure against collusion. if you choose random key k encrypt m the message with it c=E_k(m) and and then publish c, and truncate k to delete 64-bits you get instant no work setup of a 2^64 decryption challenge. tune as you wish to get more or less work.
14:58:32	adam3us:	now that is random and the searcher could get lucky, but you can apply it multiple times to reduce the variance to negligible. eg iv1000=E_k1000(m), iv999=E_k999(iv1000) … iv1=E_k1(iv2) and omit the desired number of bits eg 56 bits missing from each of 1024 challenges gives the 64-bit work factor low variance, no trust, negligible cost during setup
14:58:34	op_null:	kanzure: the point is that you can parallelize generation. on a GPU you can do lots of concurrent threads, if you're limited to just one there's not much you can do but get an intel CPU and overclock the shit out of it.
14:59:08	kanzure:	my question was actually about the upfront setup collusion actually
14:59:22	kanzure:	but anyway, key truncation.. hm.
14:59:35	adam3us:	op_null: yeah but my point is you can generate KDFs with arbitrary iterations/work and your choice variance with negligible work
15:00:38	adam3us:	this could be done with PBKDF2 or such things. eg you could setup a high work KDF from a cell phone processor in a fraction of a second that'd take as long as you want on a desktop.
15:01:09	op_null:	right, I was just talking about "now this has a problem firstly it takes as much aggregate work to setup as decrypt." in particular. I don't think it's a real problem that the amount of work is the same, really.
15:02:31	op_null:	I'm attracted to the idea just because there's not all that many problems you have to solve by using liquid nitrogen CPU cooling.
15:02:53	adam3us:	op_null: well it is because work has cost, and also you cant securely outsource this work. say you need to at short notice send a very secure/time-locked message from a cell phone using a panic button. now-what. and you dont trust the network at large not to cache the parallel setup parts.
15:03:24	adam3us:	(they could be sold when the actual decryptors come back and pay people to decrypt things at a profit because the worker gets paid twice for the same work)
15:03:52	op_null:	oh yeah, of course then you're toast. alternatives are great.
15:06:07	adam3us:	there is work you can securely outsource.. i made an intentionally parallelizable KDF that is blind and so securely outsourceable … not time-lock but work-locked. you can get it solved in a fraction of a second using litecoin miners (people who want to sell gpu-work at litecoin $/CPU KHrates) securely from a smart-phone
15:06:39	adam3us:	there is a non-parallelizable version of that (had to do extra things to make it parallelizable)
15:07:26	adam3us:	https://bitcointalk.org/index.php?topic=311000.0
15:08:02	adam3us:	(thats a different use-case really. cost-locked vs time-locked)
15:08:47	adam3us:	if it costs $5 per password guess that is protecting $100,000 even a weakish password will be net loss to attack (using a KDF with those properties)
15:12:32	adam3us:	an outsourceable non-parallel KDF could be useful also if the encrypted message is public, and the person paying for the work doesnt trust them to not decrypt the document he paid to decrypt.
15:19:23	mkarrer_:	mkarrer_ is now known as mkarrer
16:24:43	antanst:	antanst has left #bitcoin-wizards
16:58:27	lclc_bnc:	lclc_bnc is now known as lclc
17:25:21	lclc:	lclc is now known as lclc_bnc
18:51:02	lclc_bnc:	lclc_bnc is now known as lclc
19:02:29	lclc:	lclc is now known as lclc_bnc
19:08:48	kanzure:	http://underhandedcrypto.com/rules/ "The Underhanded Crypto contest was inspired by the famous Underhanded C Contest, which is a contest for producing C programs that look correct, yet are flawed in some subtle way that makes them behave inappropriately. This is a great model for demonstrating how hard code review is, and how easy it is to slip in a backdoor even when smart people are paying attention. We’d like to do the same for ...
19:08:54	kanzure:	... cryptography. We want to see if you can design a cryptosystem that looks secure to experts, yet is backdoored or vulnerable in a subtle barely-noticable way. Can you design an encrypted chat protocol that looks secure to everyone who reviews it, but in reality lets anyone who knows some fixed key decrypt the messages? We’re also interested in clever ways to weaken existing crypto programs. Can you make a change to the OpenSSL ...
19:09:00	kanzure:	... library that looks like you’re improving the random number generator, but actually breaks it and makes it produce predictable output?"
19:28:50	gwillen:	kanzure: I propose taking the current openssl source and submitting it, alleging that you have made it subtly vulnerable
19:28:53	gwillen:	and see what they find
19:29:14	nsh:	hah
19:29:38	kanzure:	they accept existing code only if you have modified it
19:29:56	kanzure:	which is pretty easy to check (diffs)
19:30:16	kanzure:	and i think they have you submit and make your changes obvious
19:30:40	gwillen:	heh, darn
20:09:58	FBI-AGENT:	FBI-AGENT is now known as Dr-G
20:31:44	adam3us:	submit ekr's patches? ;) ooh politically insensitive
20:32:57	c0rw|away:	c0rw|away is now known as c0rw1n
20:33:02	adam3us:	eg the one that broadcasts extra randomness to amplify the ec drbg breakage
20:33:06	adam3us:	adam3us has left #bitcoin-wizards
20:36:10	sipa:	?
20:36:19	sipa:	ah
22:35:15	tacotime:	someone wrote a paper about using a paillier cryptosystem to enhance blockchain privacy in conjunction with utxo-bearing spvs
22:35:21	tacotime:	https://drive.google.com/file/d/0B21vncLoIlIyaVpGVFN5c1VFdmM/view
22:41:35	kanzure:	wasn't there something recent about xss vulnerabilities in google drive.. hrm.
22:42:40	tacotime:	kanzure: if you are afraid i will dl the pdf and email it to you
22:42:46	tacotime:	not that pdfs are much safer
22:47:59	kanzure:	i feel like my options are one terrible javascript execution environment for another terrible javascript execution environment
22:48:08	tacotime:	and good discussion from gmaxwell/adam3us here: https://bitcointalk.org/index.php?topic=872377.0
22:48:11	adam3us:	see https://bitcointalk.org/index.php?topic=872377.msg9647318#msg9647318 they seem to be confused about the need for
22:49:51	adam3us:	tacotime: ah yes. that :) the need for paillier at all. its avoids introducing another crypto-assumption, is more compact to use EC DLOG than paillier (256-bit ciphertext vs 6kbit) plus they did not seem to realise that you need to prevent wrapping mod n. or misread the paper they got one of the parts from to assume it implied wrapping prevention, which afaik it does not.
22:51:54	tacotime:	yeah i was reading about paillier and saw it was using RSA keys and became afraid. i will read over your homomorphic value scheme, must have missed it before. :)
22:52:42	adam3us:	the homomorphic value is not doing anything exciting.. all standard zkp & EC dlog. 1kbit for encrypted value vs 64-bit for unencrypted.
22:57:21	gmaxwell:	oh I was just typing what adam3us already typed.
22:57:52	adam3us:	uh 1kbyte not 1kbit. i think the effect is quite exciting though :) hide the values while still validating that they add up. (though you can still tell that the person who sent it to you had at least that value). i talked about it a bit some video and slides https://bitcointalk.org/index.php?topic=509674.0
22:58:00	gmaxwell:	It needs proofs to prevent the wrap and I don't know how to construct those compactly (while staying with just boring cryptographic assumptions)
22:59:34	adam3us:	skip to 49m on the video for the encrypted value part https://www.youtube.com/watch?v=3dAdI3Gzodo&feature=youtu.be
22:59:56	tacotime:	cool, ty.
23:02:24	adam3us:	i wonder.. you could probably improve the hiding of where the money came from by proving that the sum of the inputs is the value, without revealing to the recipient the allocation of value across those inputs. didnt think of that before.
23:03:45	nsh:	gmaxwell, what's the security effect of wrapping around n?
23:03:57	nsh:	or cryptopathogenesis
23:05:43	gmaxwell:	nsh: it's a total break. It only shows your outputs are congruent to your inputs mod n.
23:06:12	nsh:	hmm
23:06:18	kanzure:	andy-logbot: what about non-interactive proofs where the proof isn't about some specific data, but rather just something like "the value is greater than or equal to n" or "the value is less than n"? does this exist
23:06:18	kanzure:	I'm logging. I don't understand 'what about non-interactive proofs where the proof isn't about some specific data, but rather just something like "the value is greater than or equal to n" or "the value is less than n"? does this exist', kanzure. Try /msg andy-logbot help
23:06:18	gmaxwell:	so e.g. you can create enormous value outputs when you only have a few coins.
23:06:22	kanzure:	oops
23:06:28	kanzure:	andytoshi: what about non-interactive proofs where the proof isn't about some specific data, but rather just something like "the value is greater than or equal to n" or "the value is less than n"? does this exist
23:06:51	gmaxwell:	kanzure: there are proofs for this, seem adam3us' writeup, but they are not tiny.
23:07:11	nsh:	oh god, the logbots are starting giving academic interjections now. skynet dawns
23:07:17	kanzure:	hmm okay then
23:07:22	nsh:	*have started
23:09:10	gmaxwell:	really, the problem is that expanding values to a kilo-bit for encryption would be bad enough that it would be hard to tolerate. ... having to go to several times that for all the proofs is ... considerable overhead.
23:09:20	adam3us:	kanzure: yes its a research area for "zk range proofs" the one i focussed on optimizing is one by berry schoenmakers which is simple & convenient for EC dlog. this kind of proof is useful in many protocols because most zkps are all modulo n so you either need to prove n is >> the values so it couldnt wrap, or that it doesnt wrap
23:15:43	nsh:	still hard to intuit why proving nonwrap would require extra stronger assumptions
23:17:48	nsh:	* nsh reads more
23:18:38	nsh:	(or is that just within efficiency tolerances)
23:21:24	adam3us:	gmaxwell: yes i am disappointed about the size. annoying range proofs.
23:22:42	adam3us:	gmaxwell: about the only thing you could say in defence is that without hiding the value, if you actually cared about privacy to that degree you'd be sending multiple standard-sized values or something. ie these hidden value spends would be providing more privacy per transaction.
23:28:16	petertodd:	adam3us: you're misunderstanding the design space of timelock in a whole variety of ways - anything other than highly optimized algorithms with existing excellent scalar implementations is a bad idea.
23:28:31	petertodd:	adam3us: (I'll probably switch it to AES when I get around to it)
23:29:04	andytoshi:	off channel i mentioned to kanzure that i believe you cannot form a NIZK without either CRS and RO (and that i would not trust an RO SNARK, or any "cryptography of programs" that assumed that a big chunk of its own code was ethereal and could not be fed into itself)
23:29:05	petertodd:	adam3us: secondly the "farm it out" part of the problem is pretty trivial - think of how little parallelism you need to make it practical
23:29:18	andytoshi:	kanzure: the proofs that adam3us is talking about are in the RO model
23:29:45	adam3us:	petertodd: yeah but then you need to trust the people you farmed it out to to forget
23:29:58	petertodd:	adam3us: e.g "I want to lock for 5 years, and I want to setup the proof in a month" -> 60 cores, not a big deal at all to just go out and buy, or if someone writes me a GPU implementation
23:30:25	adam3us:	petertodd: i do agree that its preferable to use sym key, thats why i rejected pubkey variants, for hashcash
23:31:28	adam3us:	petertodd: anyway my symkey argument stands: you can do that without oursourcing. just delete keybits.
23:32:45	nsh:	andytoshi, "ethereal.. fed into itself"?
23:33:31	nsh:	are there any actually analytically-enlightening papers on how systems break down under various departures from random oracle?
23:34:10	adam3us:	petertodd: but also the even optimized things get toasted if someone makes an asic for it. probably your best bet would be to use sha256 and find a way to construct it out of repurposing bitcoin miners.
23:34:51	rusty2:	petertodd: my problem with all timelock schemes is more meta: someone has to care about your specific time-lock. AFAICT that introduces the most variance, as valuable timelocks get attacked first. If someone produces timelocks which can be solved via merge-mining, *that* would open far more uses.
23:35:22	petertodd:	rusty2: my timelock scheme incentivises everyone to crack it because cracking it gets you bitcoins
23:35:28	gmaxwell:	andytoshi: I am moving my eyebrows at your dismissal of RO assumptions.
23:35:32	rusty2:	rusty2 is now known as rusty
23:35:42	nsh:	(constraining algorithms and protocols in the interests of maintaining the utility of legacy hardware is definitely not something that's going to cause later regret)
23:35:53	nsh:	(not this time!)
23:35:53	petertodd:	rusty2: solves that problem, *and* gives solid proof of what's the fastest scalar implementation out there (by people willing to use it publicly)
23:36:09	andytoshi:	gmaxwell: specifically for SNARKs, things like KDM-secure encryption, obfuscation
23:36:23	andytoshi:	gmaxwell: anything that treats code as executable code (as opposed to blindly treating its input as data)
23:36:32	petertodd:	rusty: tech is such that that scalar implementation is very likely close to the best possible (<10x)
23:37:04	andytoshi:	nsh: one sec, i have an example of a broken RO-secure system for KDM-secure encryption..
23:37:13	gmaxwell:	andytoshi: the only RO assunption _required_ for a SNARK is a fiat shamir transform to make the protocol non-interactive.
23:37:34	adam3us:	petertodd: dont forget people may have an interest to crack lots of time-lock in parallel if they got used much at vastly lower J/crack
23:37:38	andytoshi:	gmaxwell: oh, FS i think is ok
23:37:55	andytoshi:	but i don't really trust that feeling because i can't tell why exactly i'm ok with fs
23:38:08	nsh:	+1 economy of scale cracking
23:38:24	rusty:	petertodd: If I understand correctly, you don't scale. How do I make my timelocked will-and-testament, for example? Do I hook onto your current puzzles somehow?
23:38:55	andytoshi:	nsh: bottom of page 19 https://eprint.iacr.org/2007/315.pdf
23:39:14	nsh:	ty
23:39:20	andytoshi:	oh, i'm OK with FS because it treats its input as raw data
23:39:42	andytoshi:	to contrast, the example i just gave to nsh (which is pretty jargonny, sorry) is using the RO in a pretty integral way
23:40:51	nsh:	i still suspect there might be something interest, analogous to andytoshi's impossibility conjecture, if the self-referential part were clearer
23:40:55	andytoshi:	KDM security is where the attacker can request encryptions of arbitrary functions of the secret key material ... and the "security proof" of one such system assumes that RO output is uniformly random and in particular totally independent of these ciphertexts
23:41:05	petertodd:	rusty: you spend 1core * T computer power and make it yourself; scales linearly
23:41:28	andytoshi:	and obviously, in a real system this assumption is false because your RO is instantiated with an actual function you can give to the ciphertext oracle
23:41:41	petertodd:	rusty: it's meant to actually work, right now, because I had a client who actually needed it...
23:41:55	nsh:	but really it's would be nice to quantify the weakness in terms of the dependency in terms of some notion of algorithmic-information-theoretical proximity of inputs and outputs
23:42:01	nsh:	*unmangle()
23:42:13	andytoshi:	nsh: welll, the way "zero knowledge" is defined in cryptography is in terms of a simulator, so you need an oracle ... this means a CRS ("trusted setup oracle"), an RO, or interaction
23:42:30	andytoshi:	nsh: but maybe there is a better definition of ZK that'd give us what we want without such a requirement
23:42:44	petertodd:	adam3us: what's the relevance of what "people might have an interest in cracking in parallel" - I just want a solution that works and is maximally predictable - anything parallel isn't
23:42:47	rusty:	petertodd: and what would motivate someone to solve it? The cost of that setup seems to be the ~ cost to solve it, since I have to offer a reward. But that seems redundant: is there a system where unrelated parties can share a timelock?
23:43:15	nsh:	i think we're grasping at a informational theoretical conservation law but it's a bit beyond my conceptual horizons at least
23:43:20	petertodd:	rusty: the motiviation is there exist Bitcoins on the bitcoin blockchain that by cracking the timelock you get to take the bitcoins...
23:43:24	andytoshi:	nsh: i hope not :)
23:43:28	andytoshi:	but maybe, i get that feeling too
23:43:46	petertodd:	rusty: no such "ulrelated parties" systems exist without adding huge amounts of complexity and/or handwaving
23:43:54	nsh:	just doesn't sit so well, aesthetically, that the assumptions can't be made less discrete/binary
23:44:50	rusty:	petertodd: Thanks, I thought that might be the case :( Unfortunately that constrains usage significantly, since the locker has to pay the solving cost.
23:45:06	petertodd:	adam3us: so, AFAICT your symkey arrangement basically makes it a semi-parallelizable problem?
23:45:08	andytoshi:	nsh: one thing my team at UT is working on is "universal parameters" which means a single CRS which can then generate other CRS's without additional trust http://eprint.iacr.org/2014/507
23:45:27	nsh:	very theological :)
23:45:32	andytoshi:	:P
23:45:47	petertodd:	rusty: meh, solve problems that actually exist first - like I said, I had a client who actually needed a working timelock crypto application! (and hell, I found another person who needed one after)
23:46:02	andytoshi:	nsh: using obfuscation they have a selectively secure candidate ... one discouraging theoretical result they have is that adaptive security is impossible even in the RO model
23:46:26	andytoshi:	which is much stronger than my impossibility result...plus they actually finished it instead of handwaving the way i did :P
23:46:29	nsh:	((iacr.org should apply some sort of latex.js for abstracts))
23:47:02	nsh:	hmm
23:47:14	andytoshi:	so an open problem is, well, maybe there is a security definition between selectively secure and fully adaptively secure which evades the impossibility result ... how strong a claim do we need to make before it becomes impossible?
23:47:34	andytoshi:	i dunno, i will spend some time thinking about it over the next months
23:47:44	nsh:	petertodd, you should be able to solve 5 impossible things for pre-delivery client invoicing before breakfast
23:47:56	nsh:	you're not thinking MBA-dimensionally, Marty!
23:48:21	nsh:	andytoshi, a fine question to ponder
23:48:56	rusty:	petertodd: It's nice work, for sure.
23:48:58	andytoshi:	nsh: right, right. I have a real problem with that.
23:49:10	andytoshi:	(re "not thinking MBA-dimensionally")
23:49:18	petertodd:	rusty: thanks!
23:49:21	andytoshi:	i had to look up marty's response :P
23:49:24	nsh:	well, a lot of people have the opposite problem
23:49:25	kanzure:	consequences of that could be disastrous and destroy the entire universe
23:50:28	nsh:	i don't mind disaster OR eschaton. it's both at once that really messes up your weekend
23:50:40	kanzure:	(context: ) (not worth your time)
23:51:44	petertodd:	adam3us: so the interesting thing re adding a bit of varience back, is it may make cracking timelocks more interesting to the casual observer, becaues even though the guy with a fancy liquid nitrogen cooled rig still has a big edge, it's not a 100% guaranteed edge - helps ensure there's diversity in the community of timelock crackers
23:52:13	kanzure:	andytoshi: what was the problem again you had with the random oracle model for zero knowledge proofs of knowledge? something about forged or faulty transcripts?
23:52:35	kanzure:	or, in particular, the forged or faulty transcripts are the thing i'm trying to place
23:53:48	andytoshi:	kanzure: in the CRS model, the party generating the common reference string has access to secret data which allows them to create "proofs" of false statements
23:54:09	nsh:	petertodd, can you synopsize what adding variance means? you can make it so the expected time to crack timelock has a higher variance through parameter adjustment?
23:54:15	andytoshi:	kanzure: in the RO model, my problem was that certain ways of using ROs block attacks by sleight-of-hand assuming they cannot happen
23:54:30	andytoshi:	kanzure: but if the RO is only used in a fiat-shamir transform, this is not the case (as gmaxwell observers)
23:54:39	nsh:	(i don't know to what extent you can reliably project statistical distributions onto human cracking motivation)
23:55:47	petertodd:	nsh: so, if I understand adam's proposal, by dropping bits only some fraction of attempts to crack a given key will actually succeed, e.g. drop 1 bit, half succeed
23:55:57	nsh:	hm
23:56:37	petertodd:	nsh: though, actually, thinking about it more, that's probably not going to give us what we want, because the guy who can afford 1024 dewars full of boiling LN still wins...
23:57:08	kanzure:	jokes on you i'm holding out until the LN market falls through
23:57:12	petertodd:	nsh: (or in adam's example, 2^56 dewars)
23:57:43	nsh:	just think of the scrap metal value of those cannisters though; practically pays for itself
23:58:08	andytoshi:	metallurgy to #bitcoin-alchemists pls
23:58:09	petertodd:	nsh: which is bad, because we *want* people to invent in small scale but utterly pushing the limits exotic tech to crack this stuff, as that gets you as close as possible to physical limits, and in turn that gives everyone predictability
23:58:30	nsh:	* nsh smiles, nods