This standard C program might help... /* L Function calculation - complexity of Integer factorisation/discrete logarithm gcc -O2 complexity.c -o complexity.exe */
#include <stdio.h> #include <math.h> #define FIDDLE_FACTOR 12 // To answer your next question - I have no idea! /* Enter number of bits in modulus (or extension field) and assumed complexity - usually 64, 48 or 32 (over 9) depending on the actual calculation */ /* Its assumed to be (64/9) for factorisation, but maybe as low as (32/9) for extension field discrete log */ /* Returns approximate amount of work required for optimal Index Calculus method */ /* Ideally for pairing friendly curve NB*2*k*rho bits should require work 2^NB */ /* The number of bits in the curve modulus is NB*2*rho */ /* 2^NB is work required to break using Pollard-rho, and k is embedding degree */ /* So for example a BN curve is ideal at the NB level if inputting NB*2*12*1 bits were to produce an output of 2^NB, for the assumed complexity (64, 48 or 32) If (64/9) is appropriate, then 256-bit BN curves are ideal for the 128-bit level But it would appear that if (32/9) applies, 256-bit BN curves provide only 99-bits of security. */ void L(int bts,int cpx) { double w=bts*log(2.0); double c= exp(pow(((double)cpx/9.0)*w,1.0/3.0)*pow(log(w),2.0/3.0)); printf("bits= %d Complexity (%d/9) work=2^%d\n",bts,cpx,1+(int)log2(c)-FIDDLE_FACTOR); return; } int main() { L(80*2*12*1,32); // 160-bit BN curve ideal for 80-bit security L(3072,64); // factoring a 3072 bit number L(128*2*12*1,32); // 256-bit BN curve L(128*2*12*1,16); // hope this never happens... L(224*2*12*1,32); // restoring faith with 448-bit BN curve - but group size too big! L(128*2*8*2,48); // 512-bit Cocks-Pinch curve, embedding degree 8 L(112*2*12*3/2,32); // BLS k=12 curve ideal at 112-bit security L(128*2*16*5/4,32); // KSS k=16 curve ideal at 128-bit security L(128*2*18*4/3,32); // KSS k=18 L(192*2*24*5/4,32); // BLS k=24 L(192*2*32*9/8,32); // KSS k=32 curve ideal at 192-bit level L(256*2*36*7/6,32); // KSS k=36 L(256*2*48*9/8,32); // BLS k=48 curve ideal at 256-bit level return 0; } Mike On Sat, Oct 8, 2016 at 3:34 AM, Trevor Perrin <tr...@trevp.net> wrote: > On Fri, Oct 7, 2016 at 7:18 PM, Chang-An Zhao > <zhaoch...@mail.sysu.edu.cn> wrote: > > Do you have an exact citation for this claim of "BN128 still has at > least 96 bits of security"? or any other experts can provide more > information for me? > > Hi Chang, > > See the discussion in my original post: > > https://moderncrypto.org/mail-archive/curves/2016/000740.html > > The security situation isn't entirely clear yet, though that post > mentions some estimates. > > Trevor > _______________________________________________ > Curves mailing list > Curves@moderncrypto.org > https://moderncrypto.org/mailman/listinfo/curves >
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves