--- Log opened Thu Dec 03 00:00:34 2020
01:56 -!- jonatack [~jon@88.124.242.136] has quit [Ping timeout: 256 seconds]
01:57 -!- jonatack [~jon@134.19.179.187] has joined #secp256k1
03:43 -!- roconnor [~roconnor@host-45-58-200-239.dyn.295.ca] has quit [Remote host closed the connection]
05:04 -!- reallll is now known as belcher
05:55 -!- reallll [~belcher@unaffiliated/belcher] has joined #secp256k1
05:55 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 265 seconds]
06:10 -!- reallll [~belcher@unaffiliated/belcher] has quit [Ping timeout: 272 seconds]
06:11 -!- reallll [~belcher@unaffiliated/belcher] has joined #secp256k1
06:17 < andytoshi> sanket1729_: given a public point X, i know Y and z such that X = zY
07:33 -!- reallll is now known as belcher
08:06 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 260 seconds]
08:07 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1
09:53 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Quit: ZNC - http://znc.sourceforge.net]
09:58 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1
11:03 -!- jesseposner [~jp@2601:643:8980:bfd2:21a3:28f3:d78:7f10] has joined #secp256k1
12:11 < sanket1729_> andytoshi: that is always true
12:11 < sanket1729_> take z =1 and Y = X
12:12 < sanket1729_> you need some other constraint?
12:12 < andytoshi> yes, i have other constraints :)
12:12 < andytoshi> but i would like to know the cost of the EC mult
12:12 < sipa> well, affine addition is 3 gates
12:12 < sipa> iff you can guarantee you don't hit any of the edge conditions
12:13 < sipa> doubling is 4 gates
12:13 < andytoshi> oh great, i didn't know about doubling
12:13 < sipa> unified addition for weierstrass is going to be painful
12:13 < sipa> in a circuit
12:13 < andytoshi> i don't think i need that though
12:14 < sipa> probably not
12:14 < andytoshi> i think if i want to prove i have n*H for secret n < 2^64 and secret H
12:14 < sipa> a simple double-and-add ladder probabily works fine
12:14 < andytoshi> i can get 64 H, 2H, 4H etc which is 64*4 gates
12:14 < andytoshi> then selectively add which is 64*3 gates
12:14 < andytoshi> right
12:14 < sipa> don't forget you need constraints to force your scalar bits to be 0 or 1
12:14 < sanket1729_> andytoshi: Is the equivalent of the problem you are looking for A = a*G, B =b *G, C = c*g. a,b,c are secret. A,B,C are public. prove in zk c =a*b
12:14 < andytoshi> yes! so plus 64
12:14 < sipa> 1 gate per bit
12:15 < andytoshi> sanket1729_: no
12:15 < sipa> it's one gate less if you only need the x coordinate of the output
12:15 < andytoshi> i don't have a complete problem/protocol in mind :)
12:15 < andytoshi> sipa: so n_bits * 8 - 1
12:16 < sipa> eh let's see
12:16 < sipa> N bits for the boolean constraints
12:16 < andytoshi> i had thought addition was 2.67 gates
12:16 < andytoshi> if you know you have distincti points
12:16 < sanket1729_>  i think if i want to prove i have n*H for secret n < 2^64 and secret H. Is not exacty range proof?
12:17 < sipa> if you have precomputed multiples
12:17 < sipa> but you can't assume that
12:17 < andytoshi> ah ok damn
12:17 < sipa> as you'd need to prove to the circuit your precomputation was correct
12:17 < andytoshi> sanket1729_: right, it's not a rangeproof
12:17 < andytoshi> sipa: well sure, but i can do that with a bunch of doublings right
12:17 < sipa> (N-1)*4 to compute all 2^i*P, from P for i=0..N-1
12:17 < andytoshi> yeah
12:18 < sipa> then (N-1)*3 to do all additions
12:18 < sipa> and (N-1) at every stage to select between the original and the added version, based on the scalar bit
12:18 < andytoshi> not (N-1)*2.67?
12:18 < sipa> ah
12:18 < sipa> good question
12:19 < sipa> no, i don't think that works
12:19 < sipa> because computing or verifying the precomputed multiples is far more work than just doubling
12:19 < sipa> you need to compute various linear combinations
12:19 < andytoshi> it may be also that we could combine the double-and-add some how, i don't think we explored that
12:19 < andytoshi> ah! right they were not just powers of 2
12:20 < sipa> yeah, you precompute {-7,-5,-3,-1,1,3,5,7}*(8^i)*P
12:20 < sipa> (where negative/positive is free)
12:20 < sipa> i don't think this is a win if you need to verify the precomputation
12:20 < andytoshi> yeah agreed
12:21 < sipa> so i end up with 9 gates per bit approximately
12:21 < sipa> maybe there is a slightly better combined double-and-add circuit though
12:22 < sipa> also you need to deal with the scalar being possibly 0
12:22 < sipa> unless you can somehow guarantee to not end up at infinity
12:24 < andytoshi> ah yeah good point
12:25 < sanket1729_> can you share the complete problem. this is also trivially true. if you want C = n*H where n <2^64(secret), H(secret), this is again trivially true for n = 1 H = C.
12:25 < sanket1729_> I understand what you are trying to but I am wondering if there might be simpler solution if we know the whole problem.
12:26 < sanket1729_> Something feels wrong if a protocol relies on EC point being a secret when usually scalars are secrets
12:28 < andytoshi> well confidential assets works this way
12:28 < andytoshi> hint hint
12:33 < sipa> sanket1729_: the unintutive thing is that you're really not trying to prove anything about those 64 bits; you're trying to prove the 192 other ones are zero... and apparently this is only possible by proving something about the other ones
12:34 < andytoshi> right
12:37 < sanket1729_> I think I get the proving method. I am trying to understand the rationale design choice of having asset as a point when it was equivalent to have it as a scalar.
12:38 < sipa> sanket1729_: even without assets you need this
12:38 < sipa> ah, no
12:38 < sipa> there you can use fixed bases
12:42 < andytoshi> sanket1729_: it is not equivalent to use a scalar
12:42 < andytoshi> if assets were random scalars you could collide them with BLOR
12:42 < andytoshi> or collide linear combinations of them
12:42 < andytoshi> which is just as bad
12:43 < andytoshi> yeah without assets you could do this....but then you can just directly use a rangeproof :)
12:43 < sanket1729_> I need to work this out completely. But instead of C = x*G + v*H + a*H' where H' is and a is scalar asset tag. What is the issue with this formulation?
12:44 < sanket1729_> H' is fixed
12:44 < sipa> sanket1729_: that'd allow you to transmute assets, i think?
12:44 < sipa> i see this term BLOR appear everywhere but i have no idea what it means
12:45 < sanket1729_> H' is NUMS points. Given C there should only be one solution (x, v, a)
12:45 < andytoshi> BLOR is the super-fast wagner algorithm
12:46 < andytoshi> and sanket1729_ i mean there are clearly 2^512 solutions to that
12:46 < andytoshi> but there should be only one computationally accessible one, yes
12:46 < andytoshi> that is not sufficient for security
12:46 < andytoshi> becasue you can have assets which sum to other assetws
12:46 < andytoshi> and create non-balancing transactions which will pass validation
12:46 < sanket1729_> ah
13:04 < real_or_random> TIL we have a secp256k1_ec_pubkey_combine function
13:07 < real_or_random> I wonder if this is used in the wild
13:08 < andytoshi> oh right that's what that is called
13:08 < andytoshi> yes unfortunately it is used
13:09 < andytoshi> we tried to remove it some years ago and clightning complained
15:49 < sanket1729_> so I had a fundamental misunderstanding about confidential assets. The current implementation only proves that asset type is one of input asset types. I thought it could prove the current output asset could be any possible asset
15:50 < andytoshi> yeah, that would be nice
15:53 < sipa> it'd be sufficient to prove "P is HashToCurve(secret_asset_id) + secret_nonce*G"
15:53 < sipa> not cheap though :p
19:51 < andytoshi> i wonder what the exact property EC addition has that makes it immune to wagner's algo (or BLOR)
19:52 < andytoshi> in my head it's "you can't tell how many 0s you've gotten" or "you can't measure progress" but i assume there's something specific and algebraic
19:52 < andytoshi> and whether it is possible to get this property without EC. or even get this property in a quantum-secure way
19:53 < andytoshi> for reference: "BLOR" is "On the (in)security of ROS" https://eprint.iacr.org/2020/945
19:54 < andytoshi> and i just realized there are actually two L authors
19:54 < sipa> andytoshi: given that DL-hardness implies resistance to wagner's (and generized birthday problem in general), i guess your question is pretty much "what makes EC curves DL hard"
19:54 < sipa> and you can probably win a fancy prize if you answer that :)
19:56 < andytoshi> haha, hmm, but could you have resistance to wagner's algo without DL-hardness? i guess not.
19:56 < sipa> i think you can, yes
19:56 < sipa> the argument only works in one direction
19:56 < andytoshi> if you can efficiently map from points to integers, which let's say is what "breaking DL" means, then you can use wagner's attack
19:57 < andytoshi> by mapping to integers, using normal wagner, then mapping the results back to your curve
19:57 < sipa> hmm
19:57 < sipa> but could it be that there is no mapping to integers, but still no measurable progress?
19:58 < andytoshi> i think your second "no" shouldn't be there
19:58 < andytoshi> and i'm not sure. i don't know how to think about that question
19:59 < sipa> oh right
19:59 < sipa> yes my point makes no sense
20:00 < andytoshi> I think .. if you are using any cyclic group of known order, then with a quantum computer you could map your elements to integers and then use wagner's algorithm on them
20:01 < andytoshi> if you have unknown order i think you may be ok. though this surprises me because surely you can figure out your group order with some sort of cycle-finding which i'd expect QC to be good at
20:01 < andytoshi> but iirc people talk about class groups as being quantum-hard somehow
20:02 < andytoshi> and also about them having unknown order, and this being cryptographically important
20:02 < sipa> class groups are PQC?
20:02 < sipa> really?
20:03 < sipa> they have unknown order yes
20:06 < andytoshi> hmm no. duckduckgo says they definitely are not qc secure
20:06 < andytoshi> in that i searched "are ideal class groups secure" and got several papers describing algorithms for computing them with quantum computers
20:06 < andytoshi> and one called "quantum equivalence of the DLP and CDHP for group actions" which sounds pretty damning
20:07 < andytoshi> oh no, CDHP is just CDH
20:07 < andytoshi> not anything class-group related
20:08 < andytoshi> though "CDH for group actions" is something weirder than what we normally think of CDH, and i can't figure out what it :P
21:15 < sanket1729_> It does seem that class groups are not QC
21:16 < sipa> i think that's kind of implied bu the word "group"
21:17 < sipa> i guess isogeny based stuff is an exception tocthat, but that's also not working with group elements directly
23:44 < real_or_random> andytoshi: the second L (Loss) was added later https://twitter.com/real_or_random/status/1322089801244413952
23:49 < sipa> +1 on using LLL
23:50 < real_or_random> andytoshi sipa: not sure if this answers your question but https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf shows that the relation between generalized birthday and DL goes both ways
23:51 < sipa> real_or_random: cool, thanks
--- Log closed Fri Dec 04 00:00:36 2020