[curves] Curves Digest, Vol 235, Issue 1

Michael Scott mike.scott at miracl.com
Mon Oct 10 10:33:35 PDT 2016

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 <trevp at trevp.net> wrote:

> On Fri, Oct 7, 2016 at 7:18 PM, Chang-An Zhao
> <zhaochan3 at 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 at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161010/f2bc109d/attachment.html>