--- Day changed Wed Jan 24 2018 02:47 -!- jtimon [~quassel@41.31.134.37.dynamic.jazztel.es] has joined #secp256k1 05:17 < nickler> I think the biggest pain point in the aggsig signing API at the moment is the required seed parameter for the nonce ("oh crap, I thought the seed should've been the same for all parties", etc). 05:17 < nickler> You can't use RFC6979 because you don't know the challenge prehash yet because it includes the sum of nonces. Someone could change their nonce and then you'd sign a different challenge with the same nonce. 05:17 < nickler> It doesn't seem to be possible to publicly derive nonces from just the pubkeys and the message for each participant. 05:18 < nickler> What seems possible is to derive your nonce with RFC6979 (including the list of pubkeys) and require a zero knowledge proof from each participant that they generated their nonce the same way, but that's .... ugly. 09:39 -!- hdevalence [~hdevalenc@2600:380:c02c:2474:382a:c918:5091:c5d3] has joined #secp256k1 09:43 -!- hdevalence [~hdevalenc@2600:380:c02c:2474:382a:c918:5091:c5d3] has quit [Ping timeout: 246 seconds] 09:44 < gmaxwell> At least some version of our musig paper discussed that problem some. 09:45 < gmaxwell> I seem to think that I'd decided even the ZKP wouldn't work but now I'm not sure why. 09:48 < sipa> it's in the paper 09:49 < sipa> but i agree that the zkp approach seems like it solves it 09:51 < gmaxwell> maybe I'd just been thinking the ZKP is too hard to do but with bullet proofs it's not actually that big of a deal. 09:52 < gmaxwell> the you'd sha256 the message and pubkeys, resulting in a single value, and give a bullet proof that your nonce is a pedersen commitment to the bits of that single value and your private key. 09:53 < gmaxwell> the circuit would basically be a single ZKP-efficient hash. like 1500 multiply gates. 09:54 < gmaxwell> inputs mh, kG, xG; prove k = commit(mh||x). 09:57 < sipa> is it even that much? 09:58 < sipa> it seems that you should be able to use bulletproofs' pederson inputs 09:58 < gmaxwell> I'm assuming you are. 09:58 < sipa> *pedersen 09:58 < gmaxwell> you still need a ZKP friendly hash inside. 09:58 < sipa> i mean: don't use a hash function 09:58 < gmaxwell> I dont see how you aren't going to create a vulnerablity without some kind of hash. 09:58 < sipa> say k = (msg*G + privkey*H).x 09:59 < gmaxwell> it's not like you can set kG = xG + mhG 09:59 < sipa> which is effectively what a ZKP friendly hash would do anyway 10:00 < sipa> but instead you reveal the whole msg*G + privkey*H point 10:01 < sipa> oh, nvm 10:01 < sipa> you don't reveal k 10:04 < gmaxwell> so the trick of using a pedersen commitment as a hash isn't ideal for nonce generation, because the resulting value is pretty structured, not uniform. 10:05 < andytoshi> i think we could even use a 128-bit input to the ZKP-efficient hash .. but even at 256, it's only 750 gates i believe 10:06 < andytoshi> yeah satisfying the curve equation means that the x coord has a bit of bias .. not sure if it's a usable bit for e.g. lattice attacks, but i wouldn't bet that it's not 10:09 < sipa> do it twice, add them up 10:09 < sipa> :) 10:13 < andytoshi> i'd be more comfortable with mimc than something EC-based .. cuz the jubjub/pedersen commit stuff is designed with collision resistance in mind but literally no other properties .. whereas here we really want a random oracle 10:13 < andytoshi> and mimc is designed to be a general-purpose hash 10:18 < sipa> MiMC uses x^3, claiming it is a permutation 10:18 < sipa> but i believe they 10:18 < sipa> but i believe they're working only in GF(2^n) fields, where n is odd 10:41 < nsh> you can do MiMC PRF with x^3 over a GF(p) if the condition gcd(3,p-1) = 1 holds, per the paper 10:41 < sipa> which is not true for the secp256k1 field or group 10:41 < nsh> ah 10:42 < nsh> perhaps a higher exponent x^n 10:42 < sipa> however, x^3-3x is a polynomial in every field 10:42 < sipa> eh, is a permutation 10:43 < gmaxwell> Feels kinda yucky to cook up a new hash function for this. 10:44 < sipa> yes 10:44 < gmaxwell> (I would count MiMC as that too) 10:44 < gmaxwell> 10,000-ish gates for a sha2 wouldn't be that awful. :P 10:44 < sipa> interesting: "Over a finite field, every function, so in particular every permutation of the elements of that field, can be written as a polynomial function." 10:45 < nsh> neat 10:46 < gmaxwell> yes, but the polynominal need not be small. 10:46 < sipa> sure 10:46 < gmaxwell> e.g. as we were talking about sqrt the other day. 10:46 < sipa> but yesterday i was concerned that just using an exponentiation in a hash function iteration wouldn't be enough to make the function hard to invert 10:48 < sipa> and surprised that MiMC used something "as simple" as iterated x^3 and addition 10:49 < sipa> but if every function can be written as a polynomial (which from an information theoretic perspective isn't surprising at all), then perhaps that was a stupid concern 10:52 < sipa> (x^2 - 2) is also a permutation in every field 11:00 < sipa> oh, nevermind 11:08 < sipa> ok, x^5 is a permutation in the secp256k1 field 11:09 < gmaxwell> sipa: if x^2-2 was a permutation so would x^2 be. 11:10 < sipa> yes, x^2 - 2 is a permutation only when gcd(2, field_size^2 - 1) = 1 11:10 < sipa> x^3 - 3x is a permuation only when gcd(3, field_size^2 - 1) = 1 11:10 < sipa> which is not true for any of our fields 11:11 < sipa> x^5 is a permutation in both the secp256k1 field and the integers modulo its group size 11:11 < gmaxwell> five multiplies... kinda yuck. 11:11 < sipa> 4 11:11 < sipa> no, 3 11:11 < sipa> y = x^2 11:11 < sipa> z = y^2 11:11 < sipa> result = x*z 11:12 < gmaxwell> oh ladder, sure. 11:12 < sipa> i believe x^5 may also be the simplest permutation polynomial, actually 11:12 < sipa> https://en.wikipedia.org/wiki/Permutation_polynomial#Small_degree 11:16 < sipa> that list is exhaustive for up to degree 5 13:17 -!- droark [~droark@c-24-22-123-27.hsd1.or.comcast.net] has quit [Quit: Later.] 13:23 -!- ryan-c [~ryan@znc.rya.nc] has quit [Ping timeout: 248 seconds] 13:24 -!- ryan-c [~ryan@znc.rya.nc] has joined #secp256k1 14:23 -!- droark [~droark@c-24-22-123-27.hsd1.or.comcast.net] has joined #secp256k1 14:28 -!- phantomcircuit [~phantomci@192.241.205.97] has quit [Quit: ZNC 1.6.3 - http://znc.in] 14:28 -!- phantomcircuit [~phantomci@192.241.205.97] has joined #secp256k1 14:30 -!- phantomcircuit [~phantomci@192.241.205.97] has quit [Remote host closed the connection] 14:30 -!- phantomcircuit [~phantomci@192.241.205.97] has joined #secp256k1 14:37 -!- phantomcircuit [~phantomci@192.241.205.97] has left #secp256k1 [] 22:36 -!- maaku [~maaku@173.234.25.100] has quit [Quit: ZNC - http://znc.in] 22:39 -!- maaku [~maaku@173.234.25.100] has joined #secp256k1