Using secp256k1 endomorphism

[Jean_Luc]

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

[1696065346]

1696065346

[1696065346]

1696065346

[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]

@gmaxwell
Many thanks
I discovered this book "Guide to Elliptic Curve Cryptography" which is great

[Jean_Luc]

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
I would expect b1 = -1839468DB3DC795B42AD17D3CA5C15137 and b2 = 4A5AC2BF7B5F37F9F1DB10D7A2A9C981.
I didn't check yet g1 and g1 constants.

Code:

* "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}

Code:

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]

@Jean_Luc Your code for EEA seems incorrect. Here are the correct values:

Code:

s70=FCE9B1DD4EB7DD2718A2906787061B2
t70=-3086D221A7D46BCDE86C90E49284EB15
r70=114CA50F7A8E2F3F657C1108D9D44CFD8   (>=sqrt(n))

s71=-4A5AC2BF7B5F37F9F1DB10D7A2A9C981
t71=E4437ED6010E88286F547FA90ABFE4C3
r71=3086D221A7D46BCDE86C90E49284EB15  (<sqrt(n))

s72=1839468DB3DC795B42AD17D3CA5C15137
t72=-4A5D84C4FAD1D149815130F31C84462E4
r72=2228364F61BCD8F0CDA23C16C0AC386F

Code:

(a1, b1) = (r71, -t71) = (3086D221A7D46BCDE86C90E49284EB15, -E4437ED6010E88286F547FA90ABFE4C3)
(a2, b2) = (r70, -t70) = (114CA50F7A8E2F3F657C1108D9D44CFD8, 3086D221A7D46BCDE86C90E49284EB15)
r70^2 + t70^2 = 13477B4472B4233ECA232A74B45B8E7F37640C02AF64BF4EEAEE3ABED3D0695F9
r72^2 + t72^2 = 159EC1A05B158DF471EAE76C8FA0CDA199E5599D41EC1E5915FBD403A750EC1B31

[Jean_Luc]

Thanks I found the issue.

[COBRAS]

Thanks I found the issue.

Jean_Luc, hi. Then you include endomorfism to yout project - vanitysearch and kangaroo ?

Br

[Jean_Luc]

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.pdf

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.

[arulbero]

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]

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]

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]

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

[arulbero]

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

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]

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...

Code:

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]

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]

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...

Code:

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]

A 128bit range compared to a 256bit range is very very small. 340282366920938463463374607431768211456 times smaller

[COBRAS]

A 128bit range compared to a 256bit range is very very small. 340282366920938463463374607431768211456 times smaller

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 !!!