[curves] Curves Digest, Vol 243, Issue 1

[Chang-An Zhao]

Hi,　Mike, thanks a lot for your explicit explanation for my puzzle. 

Best regards

-----------------------------------------
Chang-An Zhao
-----------------------------------------
Department of Mathematics, 
Sun Yat-sen University,
P.R. China.
-----------------------------------------



----- Original Message -----
From: curves-request at moderncrypto.org
To: curves at moderncrypto.org
Sent: Tuesday, 11 October, 2016 3:00:01 AM
Subject: Curves Digest, Vol 243, Issue 1

Send Curves mailing list submissions to
	curves at moderncrypto.org

To subscribe or unsubscribe via the World Wide Web, visit
	https://moderncrypto.org/mailman/listinfo/curves
or, via email, send a message with subject or body 'help' to
	curves-request at moderncrypto.org

You can reach the person managing the list at
	curves-owner at moderncrypto.org

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Curves digest..."


Today's Topics:

   1. Re: Curves Digest, Vol 235, Issue 1 (Michael Scott)


----------------------------------------------------------------------

Message: 1
Date: Mon, 10 Oct 2016 18:33:35 +0100
From: Michael Scott <mike.scott at miracl.com>
To: "curves at moderncrypto.org" <curves at moderncrypto.org>
Subject: Re: [curves] Curves Digest, Vol 235, Issue 1
Message-ID:
	<CAEseHRo+6S0wxpPGLnaVXzVnEvVAMYfNmE4QrCCCPJLZreEX5Q at mail.gmail.com>
Content-Type: text/plain; charset="utf-8"

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

------------------------------

Subject: Digest Footer

_______________________________________________
Curves mailing list
Curves at moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves


------------------------------

End of Curves Digest, Vol 243, Issue 1
**************************************