Chang-An Zhao
2016-10-11 08:59:29 UTC
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-***@moderncrypto.org
To: ***@moderncrypto.org
Sent: Tuesday, 11 October, 2016 3:00:01 AM
Subject: Curves Digest, Vol 243, Issue 1
Send Curves mailing list submissions to
***@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-***@moderncrypto.org
You can reach the person managing the list at
curves-***@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 <***@miracl.com>
To: "***@moderncrypto.org" <***@moderncrypto.org>
Subject: Re: [curves] Curves Digest, Vol 235, Issue 1
Message-ID:
<CAEseHRo+***@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
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161010/f2bc109d/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Curves mailing list
***@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
------------------------------
End of Curves Digest, Vol 243, Issue 1
**************************************
Best regards
-----------------------------------------
Chang-An Zhao
-----------------------------------------
Department of Mathematics,
Sun Yat-sen University,
P.R. China.
-----------------------------------------
----- Original Message -----
From: curves-***@moderncrypto.org
To: ***@moderncrypto.org
Sent: Tuesday, 11 October, 2016 3:00:01 AM
Subject: Curves Digest, Vol 243, Issue 1
Send Curves mailing list submissions to
***@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-***@moderncrypto.org
You can reach the person managing the list at
curves-***@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 <***@miracl.com>
To: "***@moderncrypto.org" <***@moderncrypto.org>
Subject: Re: [curves] Curves Digest, Vol 235, Issue 1
Message-ID:
<CAEseHRo+***@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 Fri, Oct 7, 2016 at 7:18 PM, Chang-An Zhao
information for me?
Hi Chang,
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
https://moderncrypto.org/mailman/listinfo/curves
-------------- next part --------------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 moreinformation for me?
Hi Chang,
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
https://moderncrypto.org/mailman/listinfo/curves
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161010/f2bc109d/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Curves mailing list
***@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
------------------------------
End of Curves Digest, Vol 243, Issue 1
**************************************