>> (p.1)
    Author Topic: Pollard's kangaroo ECDLP solver  (Read 62384 times)

    • Jean_Luc (OP)
    Sr. Member
    ****
    Offline Offline

    Activity: 462
    Merit: 737


    View Profile
    May 01, 2020, 05:22:44 AM
    Merited by ABCbits (61), hugeblack (25), vapourminer (21), NotATether (20), joniboini (13), Welsh (12), RetiredCoder (10), gmaxwell (5), math09183 (5), suchmoon (4), Husna QA (4), Heisenberg_Hunter (3), MrFreeDragon (3), Cyrus (2), nc50lc (2), A-Bolt (1), o_e_l_e_o (1), gizmoh (1), DaCryptoRaccoon (1), albert0bsd (1), citb0in (1), nullius (1)
     #1
    Hello,

    I would like to present an interval ECDLP solver based on the Pollard's kangaroo method.
    This program is fully open source and available on GitHub: https://github.com/JeanLucPons/Kangaroo
    It has GPU support (CUDA Only) and works on both Linux and Windows.
    This program is currently under development.

    Thanks to test it and to share ideas of improvements here Wink

  • Jean_Luc (OP)
    Sr. Member
    ****
    Offline Offline

    Activity: 462
    Merit: 737


    View Profile
    May 01, 2020, 05:44:43 AM
     #2
    Quote from: arulbero on April 30, 2020, 07:50:08 PM
    It is enough to modify slightly the way we generate the next jump:

    + jP[tamePosi.x % n]*G if y > p/2,  - jP[tamePosi.x % n]*G is y <p/2

    (then I will indicate 'y' if y > p/2, '-y' if y < p/2)


    in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision

    The tame and the wild will go on with 2 specular paths:

    Q -> Q + k*G -> Q + k*G -r*G ->  ... -> DP
    (x,y)    (x1,-y1)          (x2,y2)              (x0, y0)

    -Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
    (x,-y)   (x1,y1)         (x2, -y2)              (x0, -y0)

    until they reach 2 symetric DP, for both of which we know the private key.


    Quote from: Jean_Luc on April 30, 2020, 04:35:06 PM
    May be a brownian motion can be interesting (having positive and negative jump).

    I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.


    I'm not sure to fully understand your idea.
    You want to add a condition on the y parity to determine the jump ?
    You let the starting positions as they are or you translate them ?

  • arulbero
    Legendary
    *
    Offline Offline

    Activity: 2023
    Merit: 2267


    View Profile
    May 01, 2020, 05:47:01 AM
    Last edit: May 01, 2020, 06:09:06 AM by arulbero
     #3
    Quote from: Jean_Luc on May 01, 2020, 05:44:43 AM
    Quote from: arulbero on April 30, 2020, 07:50:08 PM
    It is enough to modify slightly the way we generate the next jump:

    + jP[tamePosi.x % n]*G if y > p/2,  - jP[tamePosi.x % n]*G is y <p/2

    (then I will indicate 'y' if y > p/2, '-y' if y < p/2)


    in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision

    The tame and the wild will go on with 2 specular paths:

    Q -> Q + k*G -> Q + k*G -r*G ->  ... -> DP
    (x,y)    (x1,-y1)          (x2,y2)              (x0, y0)

    -Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
    (x,-y)  (x1,y1)         (x2, -y2)              (x0, -y0)

    until they reach 2 symetric DP, for both of which we know the private key.


    Quote from: Jean_Luc on April 30, 2020, 04:35:06 PM
    May be a brownian motion can be interesting (having positive and negative jump).

    I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.


    I'm not sure to fully understand your idea.
    You want to add a condition on the y parity to determine the jump ?
    You let the starting positions as they are or you translate them ?



    The start interval must be: [-(b-a)/2, +(b-a)/2]

    and yes, I want to add a condition on the y parity to determine the jump's direction.

    In this way a wild and a tame collide if they reach:

    1) the same point
    2) two symetric points

    In the interval [-(b-a)/2, +(b-a)/2], the x-coordinates of [1, +(b-a)/2] are equal to the x-coordinates of [-(b-a)/2, -1]; we should get more collisions, because we work in a space of 2^(n-1) points instead of 2^n.

    We introduce a equivalence class [P], where P ~ Q if Q = -P and the jump function goes from [P] to [P1], i.e. it is defined between 2 equivalence classes instead of between 2 points.


    A problem could be that many paths could enter in a loop before they reach a DP, because each kangaroo jumps back and forth and then a single kangaroo can collide with itself.

  • Jean_Luc (OP)
    Sr. Member
    ****
    Offline Offline

    Activity: 462
    Merit: 737


    View Profile
    May 01, 2020, 06:06:40 AM
     #4
    OK i will try this.
    But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.

  • arulbero
    Legendary
    *
    Offline Offline

    Activity: 2023
    Merit: 2267


    View Profile
    May 01, 2020, 06:26:01 AM
    Last edit: May 01, 2020, 06:44:07 AM by arulbero
     #5
    Quote from: Jean_Luc on May 01, 2020, 06:06:40 AM
    OK i will try this.
    But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.


    Now:

    tamei = rand(0..(k2-k1)) # Scalar operation
    wildi = rand(0..(k2-k1)) - (k2-k1)/2 # Scalar operation
    wildPosi = P + wildi.G # Group operation


    My proposal (assuming that private key of P is for sure in [-(k2-k1)/2, (k2-k1)/2])

    tamei = rand(0,..(k2-k1)/2) # Scalar operation (you can avoid negative numbers for tame)
    wildi = rand(-(k2-k1)/4,...(k2-k1)/4) # Scalar operation
    wildPosi = P + wildi.G # Group operation

  • Tamarindei
    Newbie
    *
    Offline Offline

    Activity: 17
    Merit: 25


    View Profile
    May 01, 2020, 06:29:30 AM
    Merited by joniboini (10), suchmoon (4), Welsh (4), arulbero (3), ABCbits (1), o_e_l_e_o (1), Heisenberg_Hunter (1)
     #6
    Quote from: Jean_Luc on May 01, 2020, 06:06:40 AM
    OK i will try this.
    But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.


    I think there's a paper about this already:
    https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf

    You probably need to detect frutiless cycles with this method (stuck kangaroos in a loop without distinguished points).

  • arulbero
    Legendary
    *
    Offline Offline

    Activity: 2023
    Merit: 2267


    View Profile
    May 01, 2020, 06:34:15 AM
    Last edit: May 01, 2020, 06:50:56 AM by arulbero
     #7
    Quote from: Tamarindei on May 01, 2020, 06:29:30 AM
    Quote from: Jean_Luc on May 01, 2020, 06:06:40 AM
    OK i will try this.
    But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.


    I think there's a paper about this already:
    https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf

    You probably need to detect frutiless cycles with this method (stuck kangaroos in a loop without distinguished points).


    Many thanks!!!  I didn't know it !

    EDIT:

    from the article:

    Quote
    Average number of group operations performed by our algorithm: 1.46 * sqrt(2^n)

    The cost of searching the list of previous group elements is not included in our experimental results, but our count of group operations does include the “wasted” steps from being in a cycle.

  • Jean_Luc (OP)
    Sr. Member
    ****
    Offline Offline

    Activity: 462
    Merit: 737


    View Profile
    May 01, 2020, 07:14:20 AM
     #8
    Thanks for the readings Smiley
    I will try to see if this can be implemented on ECDLP.

  • COBRAS
    Member
    **
    Offline Offline

    Activity: 1131
    Merit: 25


    View Profile
    May 01, 2020, 08:11:43 AM
     #9
    Hello everybodey. Big thanks for your work. My GPU is ready for tests !!!!
    [

  • Jean_Luc (OP)
    Sr. Member
    ****
    Offline Offline

    Activity: 462
    Merit: 737


    View Profile
    May 01, 2020, 02:19:34 PM
     #10
    I coded the stuff as it is described in the paper using this:

    Code:
    T={{a,−a}:a∈[−N/2,N/2]},
    W={{n+a,−(n+a)}:a∈[−N/4,N/4]

    And a of translation of -N/2.G of the public key to solve in order to have as specified:

    Quote
    Each experiment involved choosing uniformly at random−N/2≤n≤N/2  and  solving the  DLP  for Q=  [n]P.

    It found as expected from time to time the symmetric point.
    It is slower than the classic version (~2^21.2 on 40bit search) and far from 1.46sqrt(n) Sad

    But, they are not very clear on the jumps and especially the average distance of the jumps.
    As the wild are on a shorter range, may be steps have to be different than tame's one (not yet tested).
    I also didn't coded a stop and retry after a certain number of jump (sqrt(n) ?), i let the algorithm continue outside the range, so it may loose the symmetry...

    To be continued...
     

  • Tamarindei
    Newbie
    *
    Offline Offline

    Activity: 17
    Merit: 25


    View Profile
    May 01, 2020, 02:56:18 PM
    Last edit: May 01, 2020, 03:23:36 PM by Tamarindei
     #11
    Quote from: Jean_Luc on May 01, 2020, 02:19:34 PM
    I coded the stuff as it is described in the paper using this:

    Code:
    T={{a,−a}:a∈[−N/2,N/2]},
    W={{n+a,−(n+a)}:a∈[−N/4,N/4]

    And a of translation of -N/2.G of the public key to solve in order to have as specified:

    Quote
    Each experiment involved choosing uniformly at random−N/2≤n≤N/2  and  solving the  DLP  for Q=  [n]P.

    It found as expected from time to time the symmetric point.
    It is slower than the classic version (~2^21.2 on 40bit search) and far from 1.46sqrt(n) Sad

    But, they are not very clear on the jumps and especially the average distance of the jumps.
    As the wild are on a shorter range, may be steps have to be different than tame's one (not yet tested).
    I also didn't coded a stop and retry after a certain number of jump (sqrt(n) ?), i let the algorithm continue outside the range, so it may loose the symmetry...

    To be continued...
     



    Did you also re-randomize the point after distinguished point was found (they are using gaudry schost method in the paper)?

    Edit:

    Another way to optimize memory access and speed:
    Don't save jumped distances. When a collision between wild and tame was found you know T and W starting offsets and replay the walk for this pair only but this time with jump distances saved (replay of single pair on CPU should be sufficient).
    I got this idea from another paper which I can't remember right now.

    This is straightforward with Pollard Kangaroo but you have to account for the re-randomization when using Gaudry Schost method (remember new offsets).

  • arulbero
    Legendary
    *
    Offline Offline

    Activity: 2023
    Merit: 2267


    View Profile
    May 01, 2020, 03:19:41 PM
     #12
    Quote from: Jean_Luc on May 01, 2020, 02:19:34 PM
    But, they are not very clear on the jumps and especially the average distance of the jumps.
    As the wild are on a shorter range, may be steps have to be different than tame's one (not yet tested).
    I also didn't coded a stop and retry after a certain number of jump (sqrt(n) ?), i let the algorithm continue outside the range, so it may loose the symmetry...

    You cannot loose the symmetry.

    Are you sure that the algorithm goes outside the range so often? I don't think so, with this kind of jump (back and forth), I would use longer jumps, because you in sqrt(n) steps shouldn't go outside of the interval (on average) like the classic version.

    I suppose the main problem is the loops (a single kangaroo with itself)

  • Jean_Luc (OP)
    Sr. Member
    ****
    Offline Offline

    Activity: 462
    Merit: 737


    View Profile
    May 01, 2020, 03:45:30 PM
    Merited by Welsh (4)
     #13
    Yes From time to time it fails and go out the range. The number of dead kangaroo (collision in same herd) increase.
    The idea of replaying walk is good, I do like this in my BTCCollider.

    Here is an output on 30 trials.
    The final private key is not reconstructed here, you need to add (mod n) start range + N/2

    Code:
    Kangaroo v1.3
    Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000
    Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF
    Keys :1000
    Number of CPU thread: 2
    Range width: 2^40
    Jump Avg distance: 2^20.00
    Number of kangaroos: 2^11.00
    Suggested DP: 8
    Expected operations: 2^21.15
    Expected RAM: 6.5MB
    DP size: 5 [0xF800000000000000]
    SolveKeyCPU Thread 0: 1024 kangaroos
    SolveKeyCPU Thread 1: 1024 kangaroos

    Key# 0 S3Pub:  0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CFE36A1
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3E9F06D632
    [  0] 2^21.709 Dead:4 Avg:2^21.709 (2^21.148)

    Key# 1 S3Pub:  0x03CB4F9578029F67C76438379DBA854BB9AE6F8EFB219614404A3B4F9FE8D50DC6
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3EA329D8F1
    [  1] 2^21.520 Dead:4 Avg:2^21.618 (2^21.148)

    Key# 2 S0Pub:  0x021CCEE21580FFDCFB8DD18A21B9931E1A585E6A381F3BFAC8B84FC57152FD706F
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E0D7752C567
    [  2] 2^19.253 Dead:0 Avg:2^21.166 (2^21.148)

    Key# 3 S3Pub:  0x027CAEB7E334C27E5881F37317FC16E220D425E11DC3ABB6E1D4FEC8651F9672F7
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8012448821
    [  3] 2^20.289 Dead:1 Avg:2^20.992 (2^21.148)

    Key# 4 S3Pub:  0x0266556C83D982677B2BD1BFA996828A1F4F7004E92BBE5AA4B393B46999C3B3B5
           Priv: 0x4EF20EBCFE
    [  4] 2^20.205 Dead:0 Avg:2^20.865 (2^21.148)

    Key# 5 S0Pub:  0x03A20F2F01ED2C30EEFDDA39369ECA064B42784C1828B64EA07B350A9B1E989264
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E4F6D1E4921
    [  5] 2^21.066 Dead:1 Avg:2^20.901 (2^21.148)

    Key# 6 S0Pub:  0x02AC1FC88FB9AFF706E26C61D0B35491BD0F6F515A4307D46E183991C87DF530C3
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E2ED6F15717
    [  6] 2^20.659 Dead:1 Avg:2^20.869 (2^21.148)

    Key# 7 S3Pub:  0x03753BFF59D2EA1A5DC79BE76279EF6E4B2714043A8DBB747F0147AF566C8D537A
           Priv: 0x636F05D644
    [  7] 2^22.343 Dead:8 Avg:2^21.158 (2^21.148)

    Key# 8 S0Pub:  0x03A57000087A7CF565318CDD11F379C329A0DA2A28F3D251EAF6D8B29A7DAC799D
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E410D2DB133
    [  8] 2^19.576 Dead:0 Avg:2^21.047 (2^21.148)

    Key# 9 S3Pub:  0x035C394D4E9654206CA0A894FB95D76840BB728673403A41101C02E13A8C2DA78A
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8B56E16E5A
    [  9] 2^20.700 Dead:1 Avg:2^21.016 (2^21.148)

    Key#10 S3Pub:  0x02E7C093503548B3E41C4912913FD0601FDCE26BBEE94740812931737B663C90CB
           Priv: 0x6F1F0B5EF4
    [ 10] 2^21.156 Dead:0 Avg:2^21.029 (2^21.148)

    Key#11 S0Pub:  0x03FDFC12CCD11AA5113A12DE3DA7F75A74F57B9D2C9E163A6502C69997373CFA5B
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3EC4A94243
    [ 11] 2^19.762 Dead:1 Avg:2^20.957 (2^21.148)

    Key#12 S3Pub:  0x029942527E4DE7EA2DD931C284A71FCD2C6F86988C3BCC343CF25639599D183958
           Priv: 0x61625FF76D
    [ 12] 2^22.054 Dead:4 Avg:2^21.078 (2^21.148)

    Key#13 S3Pub:  0x03EDE29C2AA47726E75B9FF565A97907671BD2255DE2AE9C639F5E57B2ED64B509
           Priv: 0x70A6A72B9C
    [ 13] 2^22.660 Dead:8 Avg:2^21.270 (2^21.148)

    Key#14 S0Pub:  0x0361354FA9C10998E21B18BF911CF85C9CC9CC7314ECFFE2F2FE62DBBAC7528462
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E234F90C389
    [ 14] 2^19.719 Dead:1 Avg:2^21.206 (2^21.148)

    Key#15 S3Pub:  0x03EE26BFC9AC228D6313797F11C0ED0D57BC2AA2909AA4CB938825EC571685A104
           Priv: 0xD513ABE3E
    [ 15] 2^21.614 Dead:2 Avg:2^21.235 (2^21.148)

    Key#16 S3Pub:  0x023D8A5B0DFDDAF4974CBCA698C11A7CFF77C3432E0A528CDB00B39DFA94F35CE1
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E1875ED6231
    [ 16] 2^21.401 Dead:1 Avg:2^21.245 (2^21.148)

    Key#17 S3Pub:  0x032BD888A2DD0ED92A1E938F4546565CFD35172D502B36CA51CD3094C68B5A8F99
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8629B915FA
    [ 17] 2^20.966 Dead:1 Avg:2^21.231 (2^21.148)

    Key#18 S3Pub:  0x02BC1AA451042525998B3EB746F90F33B04CC87D525F0C576AD133FB60BD390635
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E84E933A860
    [ 18] 2^22.359 Dead:6 Avg:2^21.318 (2^21.148)

    Key#19 S0Pub:  0x02C379FD7FF86C5F5EDA2EA7EC2A17E629A6C5E550CFD1480F942224C96ADB29B4
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E16BAA606C7
    [ 19] 2^19.383 Dead:0 Avg:2^21.264 (2^21.148)

    Key#20 S0Pub:  0x03BB6EE07839B4652D2E5E542E1D566756908C92A325212BF77C47F986CA49E50C
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E1894FE660B
    [ 20] 2^20.533 Dead:0 Avg:2^21.236 (2^21.148)

    Key#21 S3Pub:  0x0365D82BF4021C9BDA3F3518368D92E2D5B5B31A74F656DA795F945CF3452B388E
           Priv: 0x18C8633EB7
    [ 21] 2^20.180 Dead:1 Avg:2^21.202 (2^21.148)

    Key#22 S3Pub:  0x02F68338FAB7DFB6B826B0B516671EA9744BF87A9105EEF57CB04B8262C246197C
           Priv: 0x54698374C2
    [ 22] 2^21.979 Dead:5 Avg:2^21.246 (2^21.148)

    Key#23 S3Pub:  0x026B0539B338B11BC3BF89CAB51182D8AA9EFA27C40CAAC90CA30B1184548D7380
           Priv: 0x1EC240D56C
    [ 23] 2^20.536 Dead:0 Avg:2^21.222 (2^21.148)

    Key#24 S3Pub:  0x0296F8ECE1DD51B1B15E6A9D0A2545C8AAC9C4CFA72BBBE1DCD6C03D1D51E21C42
           Priv: 0x11274B7F03
    [ 24] 2^20.651 Dead:0 Avg:2^21.203 (2^21.148)

    Key#25 S3Pub:  0x03D013A7A59A42D1EB6333EFBE1DA208586DD3940BCFB381ADEA98F76C4D26B2B5
           Priv: 0x414A6EFD99
    [ 25] 2^20.480 Dead:0 Avg:2^21.181 (2^21.148)

    Key#26 S0Pub:  0x02D5FEDD123EF2BDCC3FE37C4D79DD1E5B2EC95AD9B2C7452907391A1CCC5EF9C0
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E137A8D7A6F
    [ 26] 2^21.945 Dead:7 Avg:2^21.218 (2^21.148)

    Key#27 S0Pub:  0x02B227090548A1497FCDCAFB0DB7900851872CF7E0AD2A0B7EC832DAA7BA30637C
           Priv: 0xE2511D7A
    [ 27] 2^21.535 Dead:1 Avg:2^21.231 (2^21.148)

    Key#28 S1Pub:  0x024A4FCE4455879E9CB6806DB6367D7287A28A2C59CF29B156EDF016EDB377BDB4
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E1E87F79995
    [ 28] 2^21.683 Dead:2 Avg:2^21.249 (2^21.148)

    Key#29 S2Pub:  0x02F81D6B0179834773E92F8FCB23014727E8B78BDD30C605F50BBCC205EEB1C386
           Priv: 0x7F0B60C903
    [ 29] 2^21.590 Dead:3 Avg:2^21.262 (2^21.148)

    Key#30 S2Pub:  0x034848FA03EC2FA52ACAE70BE58720A5621CF90565BBC925D624BFB31CDC1ACB66
           Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8016BDBA3D
    [ 30] 2^19.910 Dead:1 Avg:2^21.233 (2^21.148)

  • arulbero
    Legendary
    *
    Offline Offline

    Activity: 2023
    Merit: 2267


    View Profile
    May 01, 2020, 03:53:14 PM
     #14
    Quote from: Jean_Luc on May 01, 2020, 03:45:30 PM
    Yes From time to time it fails and go out the range. The number of dead kangaroo (collision in same herd) increase.
    The idea of replaying walk is good, I do like this in my BTCCollider.

    Your jumps are: +-G, +-2*G, ...., +-2^19*G ?

  • Jean_Luc (OP)
    Sr. Member
    ****
    Offline Offline

    Activity: 462
    Merit: 737


    View Profile
    May 01, 2020, 04:04:14 PM
     #15
    Not in this release, I use a random set of jump [32 jumps] with an average of 2^20.

  • arulbero
    Legendary
    *
    Offline Offline

    Activity: 2023
    Merit: 2267


    View Profile
    May 01, 2020, 04:08:11 PM
     #16
    Quote from: Jean_Luc on May 01, 2020, 04:04:14 PM
    Not in this release, I use a random set of jump [32 jumps] with an average of 2^20.

    But with both signs (+-) or not?

    Could you try with an average of 2^21 - 2^22 instead?

  • MrFreeDragon
    Sr. Member
    ****
    Offline Offline

    Activity: 443
    Merit: 350


    View Profile
    May 01, 2020, 06:18:15 PM
     #17
    Quote from: Tamarindei on May 01, 2020, 06:29:30 AM
    -snip-
    I think there's a paper about this already:
    https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf

    You probably need to detect frutiless cycles with this method (stuck kangaroos in a loop without distinguished points).

    Thank for this reading.
    In abstract it was noted that the method "to solve the DLP in an interval of size N with heuristic average case expected running time of close to 1.36√N group operations for groups with fast inversion".

    We do not have fast inversions. They also showed in practice that the total number of operations was not 1.36sqrt(N), but 1.46-1.49sqrt(N).

    1.49 is 25% less than 2. Th question is, if we perform 2sqrt(N) operations with the speed 1000MKey/sec, what will be the speed for 1.49sqrt(N) operations? If it is only 5-10% less, probably nice. But if it decreases down twice to 500MKey/sec?

  • arulbero
    Legendary
    *
    Offline Offline

    Activity: 2023
    Merit: 2267


    View Profile
    May 01, 2020, 06:24:58 PM
     #18
    Quote from: MrFreeDragon on May 01, 2020, 06:18:15 PM
    Quote from: Tamarindei on May 01, 2020, 06:29:30 AM
    -snip-
    I think there's a paper about this already:
    https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf

    You probably need to detect frutiless cycles with this method (stuck kangaroos in a loop without distinguished points).

    Thank for this reading.
    In abstract it was noted that the method "to solve the DLP in an interval of size N with heuristic average case expected running time of close to 1.36√N group operations for groups with fast inversion".

    We do not have fast inversions. They also showed in practice that the total number of operations was not 1.36sqrt(N), but 1.46-1.49sqrt(N).

    We do have fast inversions. Inversion in additive group means: -P, and -P is pratically for free.

    Quote
    we  show  how  to  speed  up  the  Gaudry-Schost  method in  groups  with  fast  inversion  (such  as  elliptic  curve ... )
    Here fast inversion means that computing u^−1 for any u in the group is much faster  than  a  general  group  operation.

  • MrFreeDragon
    Sr. Member
    ****
    Offline Offline

    Activity: 443
    Merit: 350


    View Profile
    May 01, 2020, 07:04:29 PM
     #19
    Quote from: arulbero on May 01, 2020, 06:24:58 PM
    -snip-
    We do have fast inversions. Inversion in additive group means: -P, and -P is pratically for free.
    -snip-

    For the whole group with range [0, order] yes it is free to make -P from P. But for the subgroup within a pecified range you need to make scalar operations.

  • arulbero
    Legendary
    *
    Offline Offline

    Activity: 2023
    Merit: 2267


    View Profile
    May 01, 2020, 08:06:41 PM
     #20
    Quote from: MrFreeDragon on May 01, 2020, 07:04:29 PM
    Quote from: arulbero on May 01, 2020, 06:24:58 PM
    -snip-
    We do have fast inversions. Inversion in additive group means: -P, and -P is pratically for free.
    -snip-

    For the whole group with range [0, order] yes it is free to make -P from P. But for the subgroup within a pecified range you need to make scalar operations.

    If you shift the range [a,b] -> [-(b-a)/2, (b-a)/2], each point P in this interval has the property that -P is in interval too. No other operations are needed.
    Pages: [1] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 ... 146 »
      Print  
Page 1
Viewing Page: 1

IRLBTC™ © 2025 IRLBTC.com