1 2013-03-19 00:00:39 <muhoo> um, no, it's not there after all. that was a block with a similar hash
 2 2013-03-19 00:00:57 <gmaxwell> jrmithdobbs: apparently their formulation preserves the DLP problem difficulty (as presumably a solution in one translates to the other through some trivial operation), but IIRC their paper didn't actually cite anything for that claim, and my ECC number theory isn't strong enough for the reason to have been instantly obvious to me.
 3 2013-03-19 00:02:25 <jrmithdobbs> gmaxwell: ya, there's some craziness to make it into a usable signing scheme, why we actually saw saw WIP code from djb for the first time in ever with that version that's in nacl that he abandoned
 4 2013-03-19 00:03:46 <jrmithdobbs> speaking of curve25519 (the dh function) if anyone wants a js implementation i got a guy that wrote one and released it gpl to liberate it via mit this weekend for a project i'm working on
 5 2013-03-19 00:03:50 <jrmithdobbs> https://github.com/rev22/curve255js/blob/master/curve25519.html
 6 2013-03-19 00:03:52 <jrmithdobbs> enjoy ;p
 7 2013-03-19 00:04:07 <Diablo-D3> hrm
 8 2013-03-19 00:04:07 <Diablo-D3> so
 9 2013-03-19 00:04:11 <Diablo-D3> what Im thinking is this
10 2013-03-19 00:04:22 <Diablo-D3> I bet I can make a QC-proof hash.
11 2013-03-19 00:04:30 <Diablo-D3> but one thats still crypto secure
12 2013-03-19 00:04:37 <jrmithdobbs> gmaxwell: I'm *kind* of starting to understand the math but sounds like we're pretty much at the same point there :)
13 2013-03-19 00:04:51 <nimdAHK_> how do I list connected nodes in bitcoind?
14 2013-03-19 00:04:59 <sipa> nimdAHK_: getpeerinfo
15 2013-03-19 00:05:16 <jrmithdobbs> did it get merged as listconnections or getpeerinfo i don't remember
16 2013-03-19 00:06:00 <nimdAHK_> sipa: thanks
17 2013-03-19 00:06:14 <Diablo-D3> 
ACTION ponders

18 2013-03-19 00:06:28 <Diablo-D3> why aren't more cryptos hard but highly parallel?
19 2013-03-19 00:06:51 <Diablo-D3> like, I expected SHA3 to feature more instruction level parallelism than it did
20 2013-03-19 00:07:14 <Diablo-D3> and EC signing schemes seem to be stuck in the dark ages too
21 2013-03-19 00:08:02 <sipa> ECDSA signing can certainly be parallellized, but these are such tight loops that depend on fitting everything in small amounts of cache, that breaking them up will hurt performance a lot
22 2013-03-19 00:08:32 <sipa> so you're generally better off just doing several signatures over multiple threads
23 2013-03-19 00:08:53 <sipa> oh, and instruction level parallellism... that's one thing they do considered a lot for Ed25519
24 2013-03-19 00:09:03 <sipa> * did consider
25 2013-03-19 00:10:43 <Diablo-D3> well, what Im thinking of doing is gluing the innards of SHA3 into a LDPC algo
26 2013-03-19 00:10:55 <Diablo-D3> and then somehow throwing EC math in there somehow
27 2013-03-19 00:11:06 <sipa> to obtain... what?
28 2013-03-19 00:11:11 <gmaxwell> Diablo-D3: I think you need a spolier.
29 2013-03-19 00:11:12 <Diablo-D3> QC hard.
30 2013-03-19 00:11:40 <MC-Droid> cup holders
31 2013-03-19 00:12:03 <sipa> Diablo-D3: do you understand shor's algorithm?
32 2013-03-19 00:12:23 <sipa> gmaxwell: and blue leds
33 2013-03-19 00:12:27 <Diablo-D3> sipa: I think so.
34 2013-03-19 00:12:37 <sipa> Diablo-D3: i don't
35 2013-03-19 00:12:47 <Diablo-D3> sipa: I dont blame you
36 2013-03-19 00:13:18 <Diablo-D3> sipa: but I think anything thats not a symmetric cipher is going to be difficult on QC
37 2013-03-19 00:13:24 <btc123_> http://en.wikipedia.org/wiki/Shor%27s_algorithm
38 2013-03-19 00:13:32 <btc123_> Diablo-D3: explain in detail.
39 2013-03-19 00:14:13 <Diablo-D3> btc123_: I dont have to, wikipedia does it for me
40 2013-03-19 00:14:19 <gmaxwell> sipa: I think it's actually easier to understand it (at least non-concretely) as applied to the DLP.  If you imagine a search for the DLP solution you keep stepping around the field until you collide with yourself. Effectively your search for the solution is an infinite series of steps which is periodic.
41 2013-03-19 00:14:50 <gmaxwell> sipa: shor effectively allows you to find the cycle length of that search without actually evaulating it. Then you step directly.
42 2013-03-19 00:14:53 <Diablo-D3> btc123_: its grover's algo I'm worried about
43 2013-03-19 00:15:07 <Diablo-D3> gmaxwell: yeah, but then you have to explain what a cycle length is
44 2013-03-19 00:15:27 <gmaxwell> Though I do not quite understand how this is accomplished??? though I can look at the math and each step follows.
45 2013-03-19 00:15:50 <btc123_> TIL that bitcoin devs are QC experts
46 2013-03-19 00:16:04 <Diablo-D3> gmaxwell: well, as far as I can tell, the math is just generating accurate probabilities
47 2013-03-19 00:16:20 <Diablo-D3> so you can just skip all the low probability parts of the search space
48 2013-03-19 00:16:22 <sipa> Diablo-D3: what type of crypto do you want to design that is crypto-hard? a hashing function?
49 2013-03-19 00:16:27 <sipa> a signature scheme?
50 2013-03-19 00:16:29 <sipa> encryption?
51 2013-03-19 00:16:32 <Diablo-D3> sipa: hashing function
52 2013-03-19 00:16:48 <sipa> Diablo-D3: you do understand the implications of Grover's algorithm?
53 2013-03-19 00:17:14 <Diablo-D3> sipa: I think so
54 2013-03-19 00:17:18 <gmaxwell> standard hashing functions are generally believed to be QC hard (at least upto what grovers does)??? though it may turn out some structures have particular weaknesses.
55 2013-03-19 00:17:23 <Diablo-D3> sipa: it makes symmetric cipher cracking much faster
56 2013-03-19 00:17:43 <sipa> Diablo-D3: yes, but up to a limit
57 2013-03-19 00:17:45 <gmaxwell> Diablo-D3: not just that, its unescapable. The bound is tight.
58 2013-03-19 00:17:58 <sipa> Diablo-D3: and there is no way around it
59 2013-03-19 00:18:10 <gmaxwell> Grover gives up a speedup for _all_ non-linear search. But the speedup is only a sqrt speedup.
60 2013-03-19 00:18:20 <sipa> sha256 is as good a QC-hard hash function as any
61 2013-03-19 00:18:27 <Diablo-D3> heh, can you use grover's algo on non-qc hardware?
62 2013-03-19 00:18:27 <gmaxwell> So just increasing your state by 2x makes it go away as a concern.
63 2013-03-19 00:18:37 <gmaxwell> Diablo-D3: you can simulate it.
64 2013-03-19 00:18:44 <sipa> yes, but not with the same speed :D
65 2013-03-19 00:18:45 <Diablo-D3> but the simulation is slower than just doing it?
66 2013-03-19 00:18:46 <gmaxwell> But it doesn't give you a speedup. :P
67 2013-03-19 00:19:15 <Diablo-D3> increasing your state 2x doesnt fix it
68 2013-03-19 00:19:22 <gmaxwell> Diablo-D3: more like an impossibly large slowdown. :P
69 2013-03-19 00:19:23 <Diablo-D3> because then they just make faster QCs
70 2013-03-19 00:19:28 <gmaxwell> Diablo-D3: it really does.
71 2013-03-19 00:19:45 <Diablo-D3> okay so wait, 2x in which direction? like sha3 has a 1600 bit internal state
72 2013-03-19 00:19:48 <Diablo-D3> going to 3200 fixes it?
73 2013-03-19 00:20:07 <Diablo-D3> because I imagine going to 3200 fixes _a lot of things_
74 2013-03-19 00:20:23 <k9quaint> anyone read the guidance that the US treasury just issues regarding virtual currencies?