12019-11-09T00:47:32  *** pinheadmz has joined ##taproot-bip-review
 22019-11-09T02:15:44  *** HighOnBtc has quit IRC
 32019-11-09T02:29:18  *** nick_freeman has joined ##taproot-bip-review
 42019-11-09T02:32:27  *** nick_fre_ has quit IRC
 52019-11-09T03:51:12  *** nick_freeman has quit IRC
 62019-11-09T04:01:54  *** mryandao has joined ##taproot-bip-review
 72019-11-09T05:16:02  *** andytoshi has quit IRC
 82019-11-09T05:45:10  *** michaelfolkson has joined ##taproot-bip-review
 92019-11-09T06:00:13  *** michaelfolkson has quit IRC
102019-11-09T06:13:47  <raj_149> paraphrasing from Bip-Schnorr: implicite Y coordinate are not reduction in security if they are thought of from number of "curve operation to get priv key" perspective, as getting the right Y is just an negation operation in field element.
112019-11-09T06:13:47  <raj_149> But this necessarily reduces the total space of valid pubkeys into half. Does that have any security consequences for DLP?
122019-11-09T06:13:47  <raj_149> let me know if my question is not clear enough.
132019-11-09T06:30:34  <sipa> raj_149: no, it does.not reduce security at all, not even 1 bit
142019-11-09T06:30:38  <sipa> https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7
152019-11-09T06:31:22  <sipa> raj_149: the intuition is that the fact that negation of public keys is so cheap to compute, will *already* reduce security... even for full public keys with y coordinate
162019-11-09T06:59:46  <raj_149> Okay, thanks for the reference.
172019-11-09T07:04:51  <sipa> raj_149: another way to look at it (which is in the bip draft, i think) is this: imagime you had an algorithm X that given an x-only pubkey computed its discrete logarithm
182019-11-09T07:05:35  <sipa> you can write an algorithm Y that breaks the DL for full pubkeys, by simply giving it to X, and then depending on whether the sign is right, either return its result directly or negate ot
192019-11-09T07:06:00  <sipa> so Y is not slower than X
202019-11-09T07:12:38  <raj_149> That does make sense.
212019-11-09T07:12:38  <raj_149> In another words, the total privkey space is unchanged.
222019-11-09T07:12:39  <raj_149> So assuming DLP is hard, its gonna take same effort to scour privkey for pubkeys with/without the tie breaker. Will that be a valid arguement?
232019-11-09T07:13:22  <sipa> raj_149: no, the privkey space is halved
242019-11-09T07:13:39  <sipa> but it's removing a half that already didn't add any security
252019-11-09T07:18:57  *** r251d has quit IRC
262019-11-09T07:19:37  <raj_149> Oh right. privkeys are negated depending on the y of pubkeys.
272019-11-09T07:19:37  <raj_149> What do you mean by "didn't add security"?
282019-11-09T07:19:38  <raj_149> Isn't the computational hardness depends on the total size of the haystack in which your have to hit the niddle? If you have smaller haystack then it becomes easier to find the niddle.
292019-11-09T07:21:06  <sipa> raj_149: the most efficient DLP solver algorithms scale with the square root of largest prime factor of the group size divided by the size of the efficiently computable endomorphism on the group
302019-11-09T07:21:34  <sipa> negating a group element is an efficiently computable endomorphism
312019-11-09T07:28:49  <raj_149> I guess i need to study more on DLP. It felt counterintuitive at first glance.
322019-11-09T07:29:43  <raj_149> Thanks for clarifying. Is the any reference i can study up on this topic??
332019-11-09T07:34:31  <sipa> start with pollard's rho for discrete logarithms
342019-11-09T09:00:45  *** michaelfolkson has joined ##taproot-bip-review
352019-11-09T10:56:57  *** b10c has joined ##taproot-bip-review
362019-11-09T11:31:26  *** sergei-t has joined ##taproot-bip-review
372019-11-09T12:03:32  <waxwing> where can i check current status on threshold with musig? i have this vague memory that someone said it wasn't currently clear that it could be done ..?
382019-11-09T12:10:30  *** sergei-t has left ##taproot-bip-review
392019-11-09T12:21:24  *** michaelfolkson has quit IRC
402019-11-09T12:26:59  *** jonatack has quit IRC
412019-11-09T12:44:48  *** jonatack has joined ##taproot-bip-review
422019-11-09T12:50:23  *** jonatack has quit IRC
432019-11-09T13:01:50  *** Chris_Stewart_5 has joined ##taproot-bip-review
442019-11-09T13:02:43  *** jonatack has joined ##taproot-bip-review
452019-11-09T13:50:18  *** b10c has quit IRC
462019-11-09T14:07:38  *** Chris_Stewart_5 has quit IRC
472019-11-09T14:28:34  *** stacie has joined ##taproot-bip-review
482019-11-09T15:05:58  <moneyball> real_or_random and andytoshi likely know the latest status. My understanding is the theory is there but very hard to do in practice so they’re exploring alternative mechanisms that are more practical.
492019-11-09T15:08:31  <waxwing> gotcha. presumably the theory being based on shamir style stuff? (polynomials), but it absolutely doesn't surprise me if it's decidedly non trivial. but, we fallback to MAST things, i take it, for the cases where there is not a combinatorial blowup. albeit that has its privacy loss tradeoff.
502019-11-09T15:12:49  *** stacie has quit IRC
512019-11-09T15:26:23  *** mryandao has quit IRC
522019-11-09T15:27:38  *** mryandao has joined ##taproot-bip-review
532019-11-09T15:45:20  *** michaelfolkson has joined ##taproot-bip-review
542019-11-09T16:04:46  *** michaelfolkson has quit IRC
552019-11-09T16:22:14  *** michaelfolkson has joined ##taproot-bip-review
562019-11-09T16:34:22  *** HighOnBtc has joined ##taproot-bip-review
572019-11-09T16:37:27  <sipa> waxwing: my understanding is that there isn't much specific to musig in the context of threshold signatures
582019-11-09T16:38:12  <sipa> as in: if you have a secure threshold scheme it can probably be adapted to work with musig-derived kwys too
592019-11-09T16:39:05  <sipa> the question is more what security properties are proven for treshold schemes in general, and it seems the theory is laxking quite a bit... common schemes are only secure with k<k/2 or so
602019-11-09T16:49:48  <moneyball> k<n/2 right?
612019-11-09T17:03:50  *** hebasto has quit IRC
622019-11-09T17:04:08  *** hebasto has joined ##taproot-bip-review
632019-11-09T17:07:25  *** hebasto has quit IRC
642019-11-09T17:18:00  *** hebasto has joined ##taproot-bip-review
652019-11-09T17:22:07  *** michaelfolkson has quit IRC
662019-11-09T17:22:54  <kanzure> waxwing: andytoshi had a gist
672019-11-09T17:23:27  <kanzure> no.. not a gist. nevermind.
682019-11-09T17:39:50  *** michaelfolkson has joined ##taproot-bip-review
692019-11-09T17:42:06  *** michaelfolkson has quit IRC
702019-11-09T17:42:33  *** jonatack has quit IRC
712019-11-09T17:44:06  *** michaelfolkson has joined ##taproot-bip-review
722019-11-09T17:46:12  *** michaelfolkson has quit IRC
732019-11-09T17:46:59  *** hebasto has quit IRC
742019-11-09T17:48:15  *** hebasto has joined ##taproot-bip-review
752019-11-09T17:56:02  *** HighOnBtc has quit IRC
762019-11-09T18:05:59  *** r251d has joined ##taproot-bip-review
772019-11-09T18:23:42  *** andytoshi has joined ##taproot-bip-review
782019-11-09T18:31:17  *** yaslama has joined ##taproot-bip-review
792019-11-09T19:51:42  *** jonatack has joined ##taproot-bip-review
802019-11-09T21:04:37  *** HighOnBtc has joined ##taproot-bip-review
812019-11-09T21:18:01  *** b10c has joined ##taproot-bip-review
822019-11-09T21:42:54  *** mryandao_ has joined ##taproot-bip-review
832019-11-09T21:43:20  *** mryandao has quit IRC
842019-11-09T22:04:13  *** alon-e has joined ##taproot-bip-review
852019-11-09T23:17:14  *** HighOnBtc has quit IRC
862019-11-09T23:19:44  <nickler> waxwing: https://github.com/ElementsProject/secp256k1-zkp/pull/46/files#diff-286bf85b94befb0c9cf796503abf9f45 and https://www.youtube.com/watch?v=Wy5jpgmmqAg
872019-11-09T23:50:17  *** b10c has quit IRC
882019-11-09T23:51:12  <waxwing> nickler thanks