Discussion:
Curves Digest, Vol 243, Issue 1
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

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
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,
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 --------------
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
**************************************