Curves Digest, Vol 243, Issue 1
(too old to reply)
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

To subscribe or unsubscribe via the World Wide Web, visit
or, via email, send a message with subject or body 'help' to

You can reach the person managing the list at

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
Content-Type: text/plain; charset="utf-8"

This standard C program might help...

L Function calculation - complexity of Integer factorisation/discrete
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
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)

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;

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,
The security situation isn't entirely clear yet, though that post
mentions some estimates.
Curves mailing list
-------------- 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


End of Curves Digest, Vol 243, Issue 1