Comments on eprint 2019/485

First online: September 15, 2020,
Last updated: October 5, 2020.

Remarks on the version of September 13, 2020 of eprint 2019/485 (Barbulescu, El Mrabet and Ghammam)

Differences in the model of cost

As explained in the 2020 version of eprint 2019/485, the model of cost is slightly different from eprint 2019/885. The preprint 2019/485 makes use of the general formula (equation 1 Section 3.2)

csieve × (1/𝒜) × (number of (a, b) pairs) + clinear algebra × ((number of prime ideals on both sides)/(𝒜×cfilter))2

There are two sets of differences:

  1. Differences in the choices of csieve, cfilter and clinear algebra;
  2. Differences in the choices of approximations (in the implementation).

In eprint 2017/334 and 2019/485 the values are csieve = 1, cfilter = log2B and clinear algebra = 128;

In eprint 2019/431 and 2019/885 the values are csieve = ln ln B, cfilter = 20 and clinear algebra = 200⌈(log2r)/64⌉.

The preprint 2019/485 follows the estimates from Barbulescu–Duquesne first designed in eprint 2017/334. The implementation choices are the following.

  • The number of pairs (a,b) is upper bounded by (2A + 1)2deg h/(2w) where w is the number of units up to sign in Kh, and lower bounded by
    (number of prime ideals on both sides) × ρ((log2Nf)/(log2B)) − 1ρ((log2Ng)/(log2B)) − 1
  • An approximation of the number of distinct prime ideals of norm up to B is the number of prime integers up to B, which is B/ln B where B is the smoothness bound
  • The (a, b) pairs are randomly sampled with randint(-A,A+1) in Python
  • The norms Nf, Ng are averaged before computing the Dickman-rho function on the average norms: ρ(log2(averaged Nf)/log2B)ρ(log2(averaged Ng)/log2B)
  • It is considered that α(f, h) = 0.0 and α(g, h) = 0.0
  • The smoothness probability of the norms is approximated with the first order term ρ(log2Nf/log2B)ρ(log2Ng/log2B)
  • 25600 random pairs are sampled to compute the average norms (3000 in eprint 2019/485)

Later in 2019 the implementation choices were refined with the following tricks.

  • The number of (a, b) pairs is estimated to be (2A + 1)2deg h/(2wζKh(2)) where 1/ζKh(2) allows to account for the duplicates due to non-coprime ideals
  • The number of distinct prime ideals of norm up to B is approximated with the formula LogIntegral(B) that is more accurate than B/ln B for large values of B
  • The (a, b) pairs are randomly sampled with randint(-A,A) or randrange(-A,A+1) in Python
  • The average is made on the Dickman-rho values instead of the norms
  • The exact value of α(f, h) and α(g, h) is computed, and polynomials are chosen to optimise α
  • Two terms are involved in the smoothness estimate as in Murphy’s thesis: uf = (ln Nf + α(f, h))/ln B and Prf = ρ(uf) + (1 − γ)ρ(uf − 1)/ln Nf and the same on g side
  • 105 to 106 random samples are used to compute the averages.

Tables of seeds

The Tables 10 to 17 at the end of the paper are mostly taken from the version of 2019 despite typos, wrong seeds and wrong security levels reported in eprint 2019/1371 and communicated to the authors on August 20, 2019. The following data is generated with this SageMath script. Because the tables below are generated from a script, the seeds are given in hexadecimal and 2-NAF form, and sparse form if it is short. Sometimes the 2-NAF form does not match exactly the sparse form given in eprint 2019/485 because it is not a 2-NAF form but another signed binary sparse representation. The seeds in the SageMath script are copied from the preprint.

The estimated security in Fpk is from eprint 2019/1371 Tables 4 and 10 in the version of December 6, 2019 (Table 10 was later removed in the version of February 2020 to fit in the 30 pages of the published version).

Some seeds for KSS do not provide integer values of p and r. Some seeds for k=27 and D=-3 are wrong. There are two families with D=-3 for k=27, construction 6.6 from Freeman, Scott, Teske (DOI 10.1007/s00145-009-9048-z, eprint 2006/372) and a BLS-like construction, with trace t(x) = x+1. It seems that the polynomials p(x) and r(x) from these two families were mixed when generating seeds, though the polynomials are correct in the paper.

Table 10 construction 6.2 k=1 mod 2

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.2 9 0x400637 222+210+29+25+24+22+2+1 222+211-29+26-23-1 483 265 4339 116
6.2 11 0x40ff 214+28-1 363 281 3989 122
6.2 13 0x10451b 220+214+210+28+24+23+2+1 220+214+210+28+25-22-1 599 481 7784 162

Table 10 construction 6.3 k=2 mod 4

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.3 10 0x18000000119 240+239+28+24+23+1 241-239+28+25-23+1 567 325 5662 Error p is not prime Error r is not prime
6.3 14 0x37723d 222-219-215-212+29+26-22+1 391 262 5464 131
6.3 18 0x4035ab 222+213+212+210+28+27+25+23+2+1 222+214-211-29-26-24-22-1 483 265 8678
6.3 22 0xc013 215+214+24+2+1 216-214+24+22-1 404 312 8871
6.3 26 0x1101 212+28+1 212+28+1 361 291 9377
6.3 30 0x13c0d 216+213+212+211+210+23+22+1 216+214-210+24-22+1 553 261 16571
6.3 34 0x43f1 214+210-24+1 534 451 18132
6.3 38 0x20a09 217+211+29+23+1 217+211+29+23+1 714 614 27101
6.3 42 0xd91 211+210+28+27+24+1 212-29-27+24+1 540 283 22641
6.3 46 0x2603 213+210+29+2+1 213+211-29+22-1 661 583 30380
6.3 50 0x4b91 214+211+29+28+27+24+1 214+212-210-27+24+1 767 570 38348
6.3 54 0xb2b 211+29+28+25+23+2+1 212-210-28+26-24-22-1 664 414 35852

Table 10 construction 6.4 k=4 mod 8

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.4 12 0x10000000000000b0b 264+211+29+28+23+2+1 264+212-210-28+24-22-1 511 257 6121 138
6.4 20 0x100010011 232+216+24+1 232+216+24+1 383 257 7641
6.4 28 0x40031b 222+29+28+24+23+2+1 222+210-28+25-22-1 351 265 9801
6.4 36 0x414405 222+216+214+210+22+1 222+216+214+210+22+1 439 265 15789
6.4 44 0x5181 214+212+28+27+1 214+212+29-27+1 343 287 15065
6.4 52 0x31c1 213+212+28+27+26+1 214-212+29-26+1 380 328 19752

Table 10 construction 6.7 even k

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.7 12 0x100024001 232+217+214+1 232+217+214+1 446 257 5341 134
6.7 24 0x100000305 232+29+28+22+1 232+210-28+22+1 382 257 9145
6.7 30 0xfa3 211+210+29+28+27+25+2+1 212-27+25+22-1 692 383 20733
6.7 36 0x12729 216+213+210+29+28+25+23+1 216+213+211-28+25+23+1 548 389 19728
6.7 48 0x1004569 224+214+210+28+26+25+23+1 224+214+211-29-27-25+23+1 526 385 25202

Table 10 construction 6.7 odd k

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.7 9 0xa2f 211+29+25+23+22+2+1 211+29+26-24-1 520 273 4672 140
6.7 15 0x5695 214+212+210+29+27+24+22+1 215-213-211-29+27+24+22+1 950 462 14247
6.7 21 0x1c93 212+211+210+27+24+2+1 213-210+27+24+22-1 1101 617 23120
6.7 27 0xb7d 212-210-27-22+1 1219 830 32896

Table 11 construction 6.6 k=0 mod 6

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.6 12 -0x1ffffffbfffe00000000 -(-277+250+233) 461 308 5525 134
6.6 24 -0xeffff000 -(-232+228+212) 318 256 7620 162
6.6 30 0x100006009 232+214+213+23+1 232+215-213+23+1 383 257 11473
6.6 42 -0x3bffc0 -(-222+218+26) 349 263 14655
6.6 48 0x16840 216+214+213+211+26 217-215-213+211+26 296 264 14174

Table 11 construction 6.6 k=2,4 mod 6

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.6 14 0x4226bf 222+217+213+211-28-26-1 352 265 4917 150
6.6 16 0x1c768 216+215+214+210+29+28+26+25+23 217-214+211-27-25+23 369 270 5900
6.6 20 0x20041 217+26+1 217+26+1 373 273 7449
6.6 22 0x20020 217+25 217+25 475 341 10438
6.6 26 0x60ac 214+213+27+25+23+22 215-213+28-26-24-22 408 351 10584
6.6 28 0x457c 214+210+28+26+25+24+23+22 214+211-29-27-22 479 339 13397
6.6 32 0x232 29+25+24+2 29+26-24+2 309 293 9888
6.6 34 0x42a 210+25+23+2 210+25+23+2 401 322 13625
6.6 38 0x4d5 210+27+26+24+22+1 210+28-26+24+22+1 410 370 15555
6.6 40 0x478 210+26+25+24+23 210+27-23 466 326 18631

Table 11 construction 6.6 k=3 mod 6

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.6 15 0x100011005 232+216+212+22+1 232+216+212+22+1 383 257 5737 138
6.6 21 0x41037e 222+216+210-27-2 351 265 7367 Error p is not prime
BLS3 27 0x7c09 214+213+212+211+210+23+1 215-210+23+1 298 268 8033
6.6 33 0x4283 214+29+27+2+1 214+29+27+22-1 336 282 11080
6.6 39 0x2c90 213+211+210+27+24 214-212-210+27+24 376 324 14656
6.6 45 0xcfb 212-210+28-22-1 373 281 16775

Table 11 construction 6.6 k=1,5 mod 6

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.6 11 0x46d0 214+210+29+27+26+24 214+211-28-26+24 338 283 3718 118
6.6 13 0x2c90 213+211+210+27+24 214-212-210+27+24 376 324 4886 152
6.6 29 0xb90 211+29+28+27+24 212-210-27+24 691 646 20019

Table 14 KSS

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
KSS 16 -0x3f87007ff -(-234+227-223+220-211+1) 330 257 5280 140
KSS 18 0x1000003ffe02 244+222-29+2 348 256 6257
KSS 32 0x180c20 220+219+211+210+25 221-219+212-210+25 350 283 11171 Error p(u) is not in Z Error r(u) is not in Z
KSS 36 0x1824213 224+223+217+214+29+24+2+1 225-223+217+214+29+24+22-1 330 268 11862 Error p(u) is not in Z Error r(u) is not in Z
KSS 40 0x42191 218+213+28+27+24+1 218+213+29-27+24+1 377 258 15077 Error p(u) is not in Z Error r(u) is not in Z
KSS 54 0x18888 216+215+211+27+23 217-215+211+27+23 349 314 18802 Error r is not prime

Table 14 other

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
LZZW 9 0x40000000007ffc00002 274+235-222+2 591 443 5314 128
BN 12 0x4001fffffffffffffffffffffbfff 2114+2101-214-1 462 462 5535 135
DCC 15 0x100090402 232+219+216+210+2 232+219+216+210+2 383 257 5737 138

Table 15 128 bits

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.3 14 0x37723d 222-219-215-212+29+26-22+1 391 262 5464 131
6.4 20 0x100010011 232+216+24+1 232+216+24+1 383 257 7641
6.4 28 0x40031b 222+29+28+24+23+2+1 222+210-28+25-22-1 351 265 9801
6.6 12 -0x1ffffffbfffe00000000 -(-277+250+233) 461 308 5525 134
6.6 15 0x100011005 232+216+212+22+1 232+216+212+22+1 383 257 5737 138
6.6 24 -0xeffff000 -(-232+228+212) 318 256 7620 162
BLS3 27 0x7c09 214+213+212+211+210+23+1 215-210+23+1 298 268 8033
6.7 12 0x100024001 232+217+214+1 232+217+214+1 446 257 5341 134
KSS 16 -0x3f87007ff -(-234+227-223+220-211+1) 330 257 5280 140
DCC 15 0x100090402 232+219+216+210+2 232+219+216+210+2 383 257 5737 138

Table 15 192 bits

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits) DL sec. in Fpk
6.3 14 0x10000000979 240+211+28+26+25+24+23+1 240+211+29-27-23+1 719 481 10053 172 Error p is not prime
6.4 20 0x2000000000011a41 261+216+212+211+29+26+1 261+216+213-211+29+26+1 731 489 14601
6.4 28 -0x80002003 -(231+213+2+1) -(-231-213-22+1) 495 373 13833 200
6.6 12 0xc0000000000000000000000002 000000000000000000000008c6 2207+2206+2105+211+27+26+22+2 2208-2206+2105+211+28-26+23-2 1244 831 14928
6.6 15 0x7000000000000018f01 274+273+272+216+215+211+210+29+28+1 275-272+217-215+212-28+1 897 599 13442
BLS3 27 0x6110e0 222+221+216+212+27+26+25 223-221+216+212+28-25 451 406 12162
6.6 24 -0x10007fffffffe40 -(-256-243+29-26) 559 449 13403 202
6.7 24 -0xfbffffffefff -(-248+242+212+1) 573 384 13746 205
KSS 16 0xa0000000000000201afd0 283+281+225+217-214-212-26+24 824 651 13173 Error p(u) is not in Z Error r(u) is not in Z
KSS 18 0x4000000000000000049e2 282+214+211+28+27+26+25+2 282+214+211+29-25+2 652 484 11729 Error p(u) is not in Z Error r(u) is not in Z
DCC 15 0x200000000000001d0108 277+220+219+218+216+28+23 277+221-218+216+28+23 923 617 13837

Table 15 256 bits exotic k

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits)
6.2 17 0x1000067bf 232+215-213+211-26-1 1215 1025 20639
6.3 18 0x8000000553f 243+214+212+210+28+26-1 945 517 16993
6.6 19 0x9bf0 215+213-210-24 610 551 11587
6.6 20 0x400000003df2 246+214-29-24+2 1011 737 20209
6.6 22 0x200008bd 229+211+27+25+24+23+22+1 229+211+28-26-22+1 811 581 17830
6.6 26 0x821104 223+217+212+28+22 223+217+212+28+22 644 553 16720
6.6 28 0x41f956 222+217-211+29-27-25-23-2 748 530 20942
6.7 9 0x305be9 222-220+215-213-210-25+23+1 991 519 8914

Table 15 256 bits

method k seed u u sparse u 2-NAF p (bits) r (bits) pk (bits)
6.4 20 0xe00000000000000073c9 280-277+215-212+210-26+23+1 956 639 19114
6.4 28 0x4000000000007d83 262+215-29-27+22-1 991 745 27721
6.6 15 0x40000000000000000000000000000040000c00 2150+230+211+210 2150+230+212-210 1799 1201 26977
6.6 24 0x60000000100004000000000000 2102+2101+268+250 2103-2101+268+250 1025 821 24583 Error p(u) is not in Z Error r is not prime
BLS3 27 -0xffffc14 -(-228+210-24-22) 559 503 15078
6.7 12 0x80000000000000000000000000720f 2119+214+213+212+29+23+22+2+1 2119+215-212+29+24-1 1664 953 19957
KSS 16 0x600000000000000000000000000000000016e1 2150+2149+212+210+29+27+26+25+1 2151-2149+213-211-28-25+1 1496 1189 23935 Error p(u) is not in Z Error r(u) is not in Z
LZZW 9 0x80000000000000000000000000000000000 000000000000000000000000000000005f090 2287+218+216+215+214+213+212+27+24 2287+219-217-212+27+24 2295 1721 20650
DCC 15 0x10000000000000000000000007f6b 2112+215-27-24-22-1 1343 897 20137