--- Day changed Mon Sep 28 2015
01:09 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
01:39 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has joined #secp256k1
02:05 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has quit [Quit: Leaving.]
02:08 -!- arubi [~ese168@unaffiliated/arubi] has quit [Quit: Leaving]
02:25 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has joined #secp256k1
02:28 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has quit [Client Quit]
02:35 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has joined #secp256k1
02:35 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has quit [Client Quit]
02:58 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has joined #secp256k1
03:30 -!- arubi [~ese168@unaffiliated/arubi] has joined #secp256k1
03:49 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]
03:57 -!- adam3us1 [~Adium@host-92-19-5-4.as13285.net] has joined #secp256k1
03:59 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has quit [Ping timeout: 250 seconds]
04:12 -!- jtimon [~quassel@160.28.134.37.dynamic.jazztel.es] has joined #secp256k1
04:20 -!- adam3us1 [~Adium@host-92-19-5-4.as13285.net] has quit [Quit: Leaving.]
04:48 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has joined #secp256k1
05:07 -!- jtimon [~quassel@160.28.134.37.dynamic.jazztel.es] has quit [Ping timeout: 255 seconds]
05:13 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has quit [Quit: Leaving.]
05:42 -!- jtimon [~quassel@160.28.134.37.dynamic.jazztel.es] has joined #secp256k1
05:50 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has joined #secp256k1
05:50 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has quit [Remote host closed the connection]
06:08 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has joined #secp256k1
06:35 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has quit [Quit: Leaving.]
07:21 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has joined #secp256k1
07:50 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has quit [Quit: Leaving.]
07:51 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has joined #secp256k1
08:20 -!- arubi [~ese168@unaffiliated/arubi] has quit [Quit: Leaving]
08:46 -!- andytoshi [~andytoshi@wpsoftware.net] has quit [Ping timeout: 256 seconds]
08:46 -!- andytoshi [~andytoshi@wpsoftware.net] has joined #secp256k1
08:56 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has quit [Quit: Leaving.]
09:15 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has joined #secp256k1
09:34 -!- GAit [~GAit@2-228-102-98.ip191.fastwebnet.it] has quit [Quit: Leaving.]
09:48 -!- arubi [~ese168@unaffiliated/arubi] has joined #secp256k1
09:52 -!- arubi [~ese168@unaffiliated/arubi] has quit [Client Quit]
09:54 -!- arubi [~ese168@unaffiliated/arubi] has joined #secp256k1
10:22 -!- jtimon [~quassel@160.28.134.37.dynamic.jazztel.es] has quit [Remote host closed the connection]
10:39 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
11:10 -!- nullbyte [NSA@gateway/vpn/mullvad/x-riakichncsbshzxn] has joined #secp256k1
11:27 <@sipa> Apocalyptic: does that help with a formal argument why my assumption is correct, then?
11:33 < andytoshi> so Apocalyptic says that A -> H(A)*A is a groupelem-to-groupelem random oracle, which isn't quite right because if you know the DL of A then you know the DL of H(A)
11:33 <@sipa> we can assume that H(A) is a random oracle that returns a number in the range [1...n-1], i guess
11:45 <@sipa> it can't be a random oracle... because with infinite compute power you can obviously solve the equation
11:51 < andytoshi> if it's a groupelem->number random oracle i think that's an ok assumption, tho i'm unsure what it gains us as far as analysis. i'm not sure what equation you are worried about being computationally solvable?
11:53 <@sipa> solve A + H(X)*X = y*G for x, Y given A
11:54 <@sipa> information theoretical arguments don't really help, because there is obviously 1 solution for y given whatever X and A
11:55 < andytoshi> well usually you say "H is a random oracle" then you do some sort of argument where a simulator programs the random oracle with statistically uniform values and solve DL with it
12:36 -!- nullbyte [NSA@gateway/vpn/mullvad/x-riakichncsbshzxn] has quit [Read error: Connection reset by peer]
12:39 -!- nullbyte [~NSA@193.138.219.233] has joined #secp256k1
12:48 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]
12:50 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
13:39 <@sipa> andytoshi: i have some intuition that a solution if it exists would involve an X that is a linear combination of A and Y... nothing else would maintain the "known DL" property; so if X = p*A + q*y*G, then A + p*A*H(p*A+q*yG) + q*y*G*H(p*A+q*y*G) = y*G, or (1 + p*h)*A = (1 - q*h)*y*G, either yiu need to know the DL of A, or (1-p*h) needs to be zero
13:44 <@sipa> hmm, i guess it could be a linear combination of A Y and G
13:45 <@sipa> but that doesn't change things
13:49 -!- adam3us [~Adium@213.193.165.20] has joined #secp256k1
13:51 < Apocalyptic> "<sipa> it can't be a random oracle... because with infinite compute power you can obviously solve the equation" // I don't get that statement, this would translate to "a hash function can't be a random oracle because with infinite computer power you can solve the preimage equation", maybe i'm missing something
13:52 < Apocalyptic> andytoshi, "if you know the DL of A then you know the DL of H(A)", how so ? there is no simple relationship between A and H(A) is there ?
14:02 < Apocalyptic> also I thought H(A) is actually a scalar since you multiply a point by it, so i'm not even sure what the DL of H(A) means in this context
14:07 <@sipa> Apocalyptic: my argument is that reasoning about random oracles won't help decide whether this equation is computationally hard to solve
14:08 < Apocalyptic> sipa, I think it does in the sense that we can argue that an attacker can't choose X so that H(X)*X maps to a value B such that he knows how to solve the DLOG for A+B
14:10 < Apocalyptic> maybe it's not even needed here, but I find it more convincing with this extra assumption
14:10 <@sipa> i think the distinction that andytoshi made there is that it isn't a random oracle to someone who knows H
14:14 < Apocalyptic> I don't see why it wouldn't, you're telling me that you have a distinguisher between X \mapsto H(X)*X and a function that returns a random point from the group ? If so I would like to see it
14:15 <@sipa> yes, i just test a few points X and see if it returns H(X)*X
14:15 <@sipa> for the first it will, for the second it won't
14:15 < Apocalyptic> right...
14:17 <@sipa> i have another distinguisher: the total domaon of X*H(X) is presumably in the order of n/e rather than n points
14:17 < Apocalyptic> I guess what I meant is that H(X)*X is quite uniformly distributed, but yeah "random oracle" was definitely wrong
14:17 <@sipa> domaim
14:17 <@sipa> domaiN
14:18 < Apocalyptic> sipa, what is n and e ?
14:18 <@sipa> n is the order of the curve, e is the base of the natural logarithm
14:18 <@sipa> because of collisions in the hash function
14:19 <@sipa> well, because of collisions in the function
14:20 <@sipa> it may n*(1-1/e)
14:20 <@sipa> i think that's the right value
14:22 < Apocalyptic> that sounds plausible
14:22 <@sipa> Apocalyptic: i think the interesting property is that X -> H(X)*X is irreversible, even to someone who knows the DL.of X
14:24 <@sipa> eh, that doesn't make sense; i mean x -> H(x*G)*x is computationally infeasible to reverse
14:24 <@sipa> invert
14:25 < Apocalyptic> yeah, even with just H(x)
14:27 < Apocalyptic> just to be sure, when talking about DL in this context, we're always assuming it's with G as a base, right
14:28 <@sipa> yes
14:30 -!- adam3us [~Adium@213.193.165.20] has quit [Quit: Leaving.]
14:35 -!- adam3us [~Adium@213.193.165.20] has joined #secp256k1
14:36 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]
14:36 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
14:41 < Apocalyptic> so my reasoning for the formal argument was the following, suppose it is easy to solve A + H(X)*X = y*G for X, Y given A, and let (X,Y) be a solution that the method yields. If X=0, then it resulted in computing Y such that A = Y*G, which is solving DL_G(A). If not, then it involved computing DL_G(A+B), where B is a point whose value can't be chosen by the attacker by your irreversibility property, so it would involve having a generic
14:41 < Apocalyptic> computationally easy DL solver
14:46 <@sipa> sounds reasonable to me, but i'm no expert :)
14:47 -!- adam3us [~Adium@213.193.165.20] has quit [Quit: Leaving.]
14:54 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]
14:55 <@sipa> andytoshi: how formal does that sound to you? ^
15:11 <@gmaxwell> This is actually the same hardness argument as for the unforgability of pay-to-contract, I think.
15:13 <@sipa> without loss of generality you can say it's solving for X and z, where z = y/H(X)
15:14 <@sipa> so it becomes X = Z - A/H(X)
15:15 <@sipa> not sure if useful
15:21 <@sipa> Apocalyptic: oh, X cannot be chosen to be 0 even, in practice here
15:21 <@sipa> because that is not a valid public key
15:26 < Apocalyptic> this would mean that even knowing DL_G(A) doesn't help in solving the equation
15:26 <@sipa> it does
15:27 <@sipa> there is an obvious y = a + H(x*G)*x solution, for every x and a
15:28 < Apocalyptic> oh X = x*g ?
15:28 <@sipa> yes
15:30 <@sipa> note: there isn't a requirement that the DL of X is known
15:30 < Apocalyptic> I thought X was just a point and DL_G(X) was unknown
15:30 <@sipa> it isn't
15:30 <@sipa> i just give an algorithm to construct a solution
15:30 <@sipa> pick number z
15:30 <@sipa> pick number x
15:31 <@sipa> and X=x*G and y=a+H(x*G)*x is a solution to the problem
15:31 <@sipa> IF you know a
15:31 < Apocalyptic> indeed
15:33 <@sipa> gmaxwell: is there a proof for that?
15:33 <@sipa> gmaxwell: i assume timo wrote a paper about pay to contract?
15:34 <@gmaxwell> sipa: yea, thats why I broke it up.
15:34 <@gmaxwell> I vaguely recall it was based on the one more discrete log stuff.
15:34 <@sipa> brought it up?
15:35 <@gmaxwell> yes. oops
16:02 <@sipa> oh!
16:02 <@sipa> i think i got it
16:02 < Apocalyptic> do tell :)
16:03 <@sipa> with substitutiins you can rewrite the equation as X + A*H(X) y*G
16:03 <@sipa> if you can solve that for arbitrary A, you can forge Schnorr signatures
16:03 <@sipa> with X = R and y=s
16:04 <@sipa> and public key A
16:04 <@sipa> in Schnorr it is H(X.x || msg)
16:04 <@sipa> but this is not harder
16:04 <@gmaxwell> Hah. I tried that earlier but got stuck on having to have P in the e hash, which isn't part of the normal schnorr definition. :P
16:05 <@sipa> what is P?
16:07 <@gmaxwell> pubkey. I was trying to show that  you couldn'd find  P + H(P)G == target for arbritary targets unless you can forge schnorr, pick arbritary R  and R == sG + eP  with e=H(R||P)
16:09 <@gmaxwell> So I'm trying to get the build clean without -Wno-unused-functions   mostly no big deal, though   secp256k1_ecmult_const is only used in tests unless module ECDH is used.
16:11 <@sipa> gmaxwell: not sure if you agree with my argument or not?
16:12 -!- nullbyte [~NSA@193.138.219.233] has quit [Ping timeout: 240 seconds]
16:13 <@gmaxwell> Maybe?  How did you end up with y == a + H(xG)x?   I thought the proposed linearity breaker was P + H(P)G?
16:14 <@sipa> gmaxwell: my suggested solution is instead of signing with key p, sign with key p*H(P)
16:14 <@sipa> if you have two parties, a*H(A) + b*H(B)
16:15 <@sipa> the question is whether b, having seen A, can choose B such that the secret key a disappears
16:15 <@gmaxwell> I caught that but why?   Why not  P + H(P)G?
16:15 <@sipa> that won't work
16:15 <@gmaxwell> Show me the break?
16:16 <@sipa> i think
16:16 <@sipa> so the sum pubkey becomes A + B + H(A)*G + H(B)*G
16:17 <@gmaxwell> okay now replace A with A+-B  okay, its independant of B's secret. Gotcha.
16:17 <@sipa> if i choose B as B'-A, that becomes B' + H(A)*G + H(B'-A)*G
16:17 <@sipa> right
16:18 <@gmaxwell> (but not indpendant of B, which is why I didn't instantly see it)
16:19 <@sipa> but do you see how using a multiplicative tweak solves it, to the point that if you can break it, yoi can break Schnor
16:19 <@sipa> r?
16:19 <@gmaxwell> Almost, just need to complete the rewrite.
16:20 <@sipa> so if party 2 has seen A, the question is if he can make A*H(A) + X*H(X) be something with known DL
16:21 <@sipa> without losimg generality, substitute A*H(A) by A... A + X*H(X) has known DL
16:22 <@sipa> replace the hash function with something that returns the scalar inverse of H(X)
16:22 <@sipa> then you have A + X/H(X) has known DL
16:24 <@sipa> multiply both sides by H(X), A*H(X) + X has known DL
16:25 <@sipa> if you can do that, you can also do A*H(X.x || msg) + X = y*G
16:25 <@sipa> that's exactly our schnorr scheme
16:26 <@sipa> with y = -s, A = Q, X = R
16:33 <@gmaxwell> Maybe I'd be more convinced if you stated it the other way around, e.g. start with a statement of a  R == sG + H(R)P    where you use control of r/R and/or s  and convert that back into  making A + X*H(X) have a known discrete log?
16:34 <@sipa> ok
16:35 <@sipa> R == sG + h(R)P
16:35 <@sipa> R + h(R)P
16:35 <@sipa> == sG
16:36 <@sipa> substitute h(X) with 1/h'(X)
16:36 <@sipa> R + (1/h(R))P == sG
16:36 <@sipa> multiply both sides with h(R)
16:37 <@sipa> h(R)*R + P == (s*h(R))G
16:40 <@sipa> so given P (equal to the sum of the other participants' h(X)*X values), i can construct a point R, and h(R)*R + otherkeys has a known DL to me: s*h(R)
16:41 <@sipa> errata: i lost the ' along the way, and i moved h(R)P to the other side with negating the sign
16:43 <@gmaxwell> I guess I'm getting hung up on the 1/h() substution (did in the forward direction too).
16:44 <@sipa> oh
16:44 <@sipa> the way to see it: if you have a means of forging Schnorr with hash function H, you can also forge an alternative Schnorr with hash function 1/H
16:45 <@sipa> agree?
16:46 <@sipa> because H is a random oracle, you can presumably forge it with _any_ function as hash function
16:47 <@gmaxwell> Right.
16:51 <@gmaxwell> So perhaps another way to present that, is assume you have a  blackbox that takes P and gives you s,R such that sG == P + R/H(R)
16:52 <@gmaxwell> and thats very clearly a schnorr cracker box.
17:04 <@sipa> gmaxwell: you need to do the argument in the other direction i think
17:05 -!- CodeShark [~CodeShark@cpe-76-167-237-202.san.res.rr.com] has joined #secp256k1
17:05 <@sipa> "assume I can cancel out any public key in A*H(A) + B*H(B) + ... scheme, for any hash function H"
17:06 <@sipa> and then conclude from that that you can use this algorithm to forge Schnorr signatures
17:06 <@sipa> which would make the assumption invalid
17:13 <@sipa> gmaxwell: https://gist.github.com/sipa/ac328e05dda213e66874
18:19 < andytoshi> Apocalyptic: sorry, i was overloading H. let H'(A) = H(A)*A. then what i meant to say was that the DL of H'(A) is known to anyone who knows the DL of A. so H' is not a random oracle
18:20 -!- maaku [~quassel@173-228-107-141.dsl.static.fusionbroadband.com] has quit [Remote host closed the connection]
18:21 < andytoshi> sipa: Apocalyptic: i did not mean that knowing H makes it a random oracle; this is true of all "random oracles"
18:21 -!- maaku [~quassel@173-228-107-141.dsl.static.fusionbroadband.com] has joined #secp256k1
18:21 -!- maaku is now known as Guest56346
18:21 < andytoshi> oh, but i did mean that anyone with oracle access to H can distinguish H' from random
18:25 < andytoshi> Apocalyptic: ok, so your argument goes: let H' be a random oracle. then simulate it by returning bG for known random b; now if the attacker can give you the DL of a' of A + H'(X), it is (a + b) where a is the DL of A. so you've successfully extracted a.
18:25 < andytoshi> Apocalyptic: so your argument is solid *assuming* H' is an RO. but in practice the attacker will have oracle access to H (cuz it's just SHA256, which we can reasonably model as a random oracle but this still gives oracle access) so H' is *not* a random oracle
18:26 < andytoshi> (still reading scrollback, i apologize if you are responding at the bottom of my buffer)
18:26 <@sipa> andytoshi: seen my gist link above?
18:28 -!- Guest56346 is now known as maaku
18:31 < andytoshi> ttr
18:33 <@sipa> time to relax?
18:34 < andytoshi> :) my screen connection dropped and i must've accidentally hit enter after pounding the keyboard
18:34 < andytoshi> but no, i'm not down to your gist link yet. i'm thinking about this "if you can solve this you can break schnorr" stuff
18:35 <@sipa> my gist contains a proof of that :)
18:36 < andytoshi> oh, ok :)
20:58 <@gmaxwell> sipa: you cannot split a pre-existing secret with this scheme... a surprising property.
20:59 <@gmaxwell> andytoshi: can sipas scheme work with interactive multiparty threshold key generation?  I suspect it cannot because ^
22:02 < andytoshi> sipa: i just got into austin from mountain view, i checked your proof on the plane and think it's solid
22:03 < andytoshi> gmaxwell: i share your intuition but don't have the cycles to think carefully about it tonight