Jean_Luc (OP)
|
The existence of the endomorphism is a roughly 20% speedup in a plain multi-exp due to halving the number of doublings. What it does is gives many algorithms which could be batched across multiple point the efficiency they'd have at twice the number of pubkeys. It's a pretty big speedup and AFAIK at an equivalent level of optimization it makes secp256k1 the fastest to verify of any widely deployed curve. So the motivation there is pretty clear, I think.
Could you give more info on this because I don't see how to have efficient decomposition k.P= (k1+k2.lambda).P using such lambda. Thanks
|
|
|
|
gmaxwell
Moderator
Legendary
Offline
Activity: 4242
Merit: 8654
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 02, 2020, 08:44:10 PM Last edit: July 02, 2020, 09:21:44 PM by gmaxwell |
|
Could you give more info on this because I don't see how to have efficient decomposition k.P= (k1+k2.lambda).P using such lambda.
Sure! You rewrite k*P as k1*P + k2*lambda*P -- lambda*P is trivial to compute, since its {beta * P.x, P.y} and k1 and k2 are 128-bit numbers instead of 256. Then this sum of products can be computed efficiently using Strauss' algorithm (also called Shamir Trick) or similar. Here is an implementation that splits k into k1 and k2 for secp256k1: https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar_impl.h#L268 with a couple scalar operations. The endomorphism optimization in libsecp256k1 is (currently) disabled by default (and can be enabled via a configure option) because it's potentially covered by a patent that expires pretty soon. (I think history suggests that the patent is actually invalid, but the benefit isn't great enough to worry about it). The implementation in libsecp256k1 is a little more complicated than described above due to some common and some novel optimizations in its version of Strauss' algorithm. It uses WNAF so it pre-computes a small table of P times odd numbers using an efficient addition ladder. It then performs all the additions over an alternative isomorphic curve so that it's able to treat the precomputed P multiplies as affine points without needing an inverse to reproject them. As a result the application of beta is done on demand late in the algorithm rather than needing to compute two tables.
|
|
|
|
Jean_Luc (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 03, 2020, 07:52:19 AM |
|
@gmaxwell Many thanks ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) I discovered this book "Guide to Elliptic Curve Cryptography" which is great ![Wink](https://bitcointalk.org/Smileys/default/wink.gif)
|
|
|
|
Jean_Luc (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 03, 2020, 11:44:30 AM Last edit: July 03, 2020, 12:15:18 PM by Jean_Luc Merited by vapourminer (1) |
|
I implemented the algorithm 3.74 of the above book and I found different results: At iteration #70/#71, I well found the same constants a1 and a2 that are mentioned in the comment of the code. but b1 and b2 are different and strangely b2=a1 in the comment ![Huh](https://bitcointalk.org/Smileys/default/huh.gif) I would expect b1 = -1839468DB3DC795B42AD17D3CA5C15137 and b2 = 4A5AC2BF7B5F37F9F1DB10D7A2A9C981. I didn't check yet g1 and g1 constants. * "Guide to Elliptic Curve Cryptography" (Hankerson, Menezes, Vanstone) gives an algorithm * (algorithm 3.74) to find k1 and k2 given k, such that k1 + k2 * lambda == k mod n, and k1 * and k2 have a small size. * It relies on constants a1, b1, a2, b2. These constants for the value of lambda above are: * * - a1 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15} * - b1 = -{0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3} * - a2 = {0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,0xd8} * - b2 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
s0=1 t0=0 r0=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
s1=0 t1=1 r1=5363AD4CC05C30E0A5261C028812645A122E22EA20816678DF02967C1B23BD72
s2=1 t2=E r2=5D4F819BEEB6D5E108DABF867C8D2F0842474284DC46CD122CA9B187ECB08EB ...
s70=FCE9B1DD4EB7DD2718A2906787061B2 t70=4A5AC2BF7B5F37F9F1DB10D7A2A9C981 r70=114CA50F7A8E2F3F657C1108D9D44CFD8 (>sqrt(n))
s71=4A5AC2BF7B5F37F9F1DB10D7A2A9C981 t71=1839468DB3DC795B42AD17D3CA5C15137 r71=3086D221A7D46BCDE86C90E49284EB15 (<sqrt(n))
|
|
|
|
j2002ba2
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 03, 2020, 01:53:22 PM |
|
@Jean_Luc Your code for EEA seems incorrect. Here are the correct values: s70=FCE9B1DD4EB7DD2718A2906787061B2 t70=-3086D221A7D46BCDE86C90E49284EB15 r70=114CA50F7A8E2F3F657C1108D9D44CFD8 (>=sqrt(n))
s71=-4A5AC2BF7B5F37F9F1DB10D7A2A9C981 t71=E4437ED6010E88286F547FA90ABFE4C3 r71=3086D221A7D46BCDE86C90E49284EB15 (<sqrt(n))
s72=1839468DB3DC795B42AD17D3CA5C15137 t72=-4A5D84C4FAD1D149815130F31C84462E4 r72=2228364F61BCD8F0CDA23C16C0AC386F
(a1, b1) = (r71, -t71) = (3086D221A7D46BCDE86C90E49284EB15, -E4437ED6010E88286F547FA90ABFE4C3) (a2, b2) = (r70, -t70) = (114CA50F7A8E2F3F657C1108D9D44CFD8, 3086D221A7D46BCDE86C90E49284EB15) r70^2 + t70^2 = 13477B4472B4233ECA232A74B45B8E7F37640C02AF64BF4EEAEE3ABED3D0695F9 r72^2 + t72^2 = 159EC1A05B158DF471EAE76C8FA0CDA199E5599D41EC1E5915FBD403A750EC1B31
|
|
|
|
Jean_Luc (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 03, 2020, 02:29:09 PM |
|
Thanks ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) I found the issue.
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 902
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 03, 2020, 07:05:55 PM |
|
Thanks ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) I found the issue. Jean_Luc, hi. Then you include endomorfism to yout project - vanitysearch and kangaroo ? Br
|
[
|
|
|
Jean_Luc (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 04, 2020, 07:11:58 AM |
|
Jean_Luc, hi. Then you include endomorfism to yout project - vanitysearch and kangaroo ?
VanitySearch already use endomorphism and for kangaroo, I will see if it is possible to do something but I'm note sure it is possible to define equivalence classes for endomorphism as for symmetry. Now we need a rule to define a unique representative for each equivalence class {P,−P}. A simple rule in this case is: treat they-coordinate of P as an integer 0≤yP< qand let the unique representative be (xP,min{yP,q−yP}). The pseudorandomwalk is then defined using the unique equivalence class representative.
https://www.iacr.org/archive/pkc2010/60560372/60560372.pdfBut symmetry is not interesting on large range due to small cycle apparition in random walks. The overhead needed to limit cycle is more than the gain of using equivalence class, especially on GPU where the cache usage can drastically decrease performance.
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 04, 2020, 07:41:11 AM |
|
But symmetry is not interesting on large range due to small cycle apparition in random walks. The overhead needed to limit cycle is more than the gain of using equivalence class, especially on GPU where the cache usage can drastically decrease performance.
I did some tests with symmetry (python for cpu), with num_jumps = 32 you can get 1.6 / 1.7.sqrt(N) steps (instead of 2.08.sqrt(N)) if the DP is 12 or lower. With longer paths you have to increase the number of the jumps, and that decreases the performance.
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 902
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 04, 2020, 10:58:13 AM Last edit: July 06, 2020, 01:28:41 AM by gmaxwell |
|
Jean_Luc, hi. Then you include endomorfism to yout project - vanitysearch and kangaroo ?
VanitySearch already use endomorphism and for kangaroo, I will see if it is possible to do something but I'm note sure it is possible to define equivalence classes for endomorphism as for symmetry. Maybe 128 byte keys is more good I think. 256 byte is harde to fined !!! Implement please endomorphism in Kangaroo Bro ?
|
[
|
|
|
gmaxwell
Moderator
Legendary
Offline
Activity: 4242
Merit: 8654
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 06, 2020, 01:30:05 AM |
|
I'm note sure it is possible to define equivalence classes for endomorphism as for symmetry.
All six points related through negation and endomorphism share the same value for x^3. (see your forum messages from me, from a few months back)
|
|
|
|
Jean_Luc (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 06, 2020, 05:44:23 AM Last edit: July 06, 2020, 06:09:30 AM by Jean_Luc |
|
All six points related through negation and endomorphism share the same value for x^3. (see your forum messages from me, from a few months back
Yes I know, but I don't see how to use this property in the random walk. For the symmetry you can select the next point according to the sign of the y value and then select always the positive point which divide by 2 the search space. It is easy to calculate the corresponding distance at each step of the random walk but it generates useless cycles. If I cube the x value of a DP and look for collision on x^3 then the gain is negligible due to the fact that the selection is not done at each step of the random walk. Any idea would be welcome ![Wink](https://bitcointalk.org/Smileys/default/wink.gif)
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 06, 2020, 06:09:17 AM Last edit: July 06, 2020, 06:41:49 AM by arulbero Merited by gmaxwell (2), ABCbits (2) |
|
All six points related through negation and endomorphism share the same value for x^3. (see your forum messages from me, from a few months back
Yes I know, but I don't see how to use this property in the random walk. For the symmetry you can select the next point according to the sign of the y value and then select always the positive point which divide by 2 the search space. It is easy to calculate the corresponding distance at each step of the random walk but it generates useless cycles. If I cube the x value of a DP and look for collision on x^3 then the gain is negligible due to the fact that the selection is not done at each step of the random walk. Any idea would be welcome ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) Each step (each jump) must depend on the last bits of x^3 mod p. But you have no advantage in the search in [-(a+b)/2,(a+b)/2] interval, you have a speedup only in the union of 3 intervals: [-(a+b)/2,(a+b)/2] U [-lambda*(a+b)/2,lambda*(a+b)/2] U [-lambda^2*(a+b)/2,lambda^2*(a+b)/2]
|
|
|
|
Jean_Luc (OP)
|
Yes and the overlap between these ranges will be very small unless you search on very large range. I'm wondering if something can be do using x^(P-1)/3 (mod p) with give 1,beta or beta^2 with uniform distribution. Of course computing a modexp is expensive but just for try... 0^((P-1)/3): 0 1^((P-1)/3): 1 2^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 3^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40 4^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40 5^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40 6^((P-1)/3): 1 7^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 8^((P-1)/3): 1 9^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 10^((P-1)/3): 1 11^((P-1)/3): 1 12^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 13^((P-1)/3): 1 14^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40 15^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 16^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 17^((P-1)/3): 1 18^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40 19^((P-1)/3): 1 20^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
|
|
|
|
gmaxwell
Moderator
Legendary
Offline
Activity: 4242
Merit: 8654
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 06, 2020, 07:31:08 AM |
|
Each step (each jump) must depend on the last bits of x^3 mod p. But you have no advantage in the search in [-(a+b)/2,(a+b)/2] interval, you have a speedup only in the union of 3 intervals: [-(a+b)/2,(a+b)/2] U [-lambda*(a+b)/2,lambda*(a+b)/2] U [-lambda^2*(a+b)/2,lambda^2*(a+b)/2]
Right. I don't know a way to use the endomorphism to get a speedup over a single compact interval-- and I somewhat doubt that it's possible. If it were, then I think in the application of endomorphism to the multiexp it would be possible to recursively apply the endomorphism to decompose to smaller and smaller scalars, but it isn't. The speedup over the set of three intervals is still potentially interesting: e.g. imagine you have an elgammal encryption where the decryption leaves with with a point you need to take the discrete log. And you can arrange that the DL is in some small enough range that this isn't unrealistic, and could potentially support the sparse ranges. This shows up in things like electronic voting or in confidential transactions. (In CT I avoided the need to solve a DL in the receiver by sneaking an encryption of it into a sidechannel in the range proofs).... or just for DL challenge bragging rights.
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 902
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 06, 2020, 09:00:21 AM |
|
Yes and the overlap between these ranges will be very small unless you search on very large range. I'm wondering if something can be do using x^(P-1)/3 (mod p) with give 1,beta or beta^2 with uniform distribution. Of course computing a modexp is expensive but just for try... 0^((P-1)/3): 0 1^((P-1)/3): 1 2^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 3^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40 4^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40 5^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40 6^((P-1)/3): 1 7^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 8^((P-1)/3): 1 9^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 10^((P-1)/3): 1 11^((P-1)/3): 1 12^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 13^((P-1)/3): 1 14^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40 15^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 16^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE 17^((P-1)/3): 1 18^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40 19^((P-1)/3): 1 20^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
Good Day everybody. 128 bytes is big range i think, if endomorphism can solve so ranges it will be supper. But if no method for solve 128-256 bytes, I think all solutions will hard work with something another then puzzle addresses.
|
[
|
|
|
Jean_Luc (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 06, 2020, 09:47:53 AM |
|
A 128bit range compared to a 256bit range is very very small. 340282366920938463463374607431768211456 times smaller ![Wink](https://bitcointalk.org/Smileys/default/wink.gif)
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 902
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 06, 2020, 10:32:55 AM |
|
A 128bit range compared to a 256bit range is very very small. 340282366920938463463374607431768211456 times smaller ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) Yes, but with endomorphism needed only 128 bytes for solve 256 and only 64 for solve 128 !!! p.s. and as i know endomorphism +0.7 fester !!!
|
[
|
|
|
|