<div dir="ltr">This standard C program might help...<div><br></div><div><div>/*</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L Function calculation - complexity of Integer factorisation/discrete logarithm</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>gcc -O2 complexity.c -o complexity.exe</div><div> */</div><div><br></div><div>#include <stdio.h></div><div>#include <math.h></div><div><br></div><div>#define FIDDLE_FACTOR 12 // To answer your next question - I have no idea!</div><div><br></div><div>/* Enter number of bits in modulus (or extension field) and assumed complexity - usually 64, 48 or 32 (over 9) depending on the actual calculation */</div><div>/* Its assumed to be (64/9) for factorisation, but maybe as low as (32/9) for extension field discrete log */</div><div>/* Returns approximate amount of work required for optimal Index Calculus method */</div><div><br></div><div>/* Ideally for pairing friendly curve NB*2*k*rho bits should require work 2^NB */</div><div>/* The number of bits in the curve modulus is NB*2*rho */</div><div>/* 2^NB is work required to break using Pollard-rho, and k is embedding degree */</div><div>/* So for example a BN curve is ideal at the NB level if inputting NB*2*12*1 bits</div><div> were to produce an output of 2^NB, for the assumed complexity (64, 48 or 32)</div><div> If (64/9) is appropriate, then 256-bit BN curves are ideal for the 128-bit level</div><div> But it would appear that if (32/9) applies, 256-bit BN curves provide only 99-bits of security.</div><div>*/</div><div><br></div><div>void L(int bts,int cpx)</div><div>{</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>double w=bts*log(2.0);</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>double c= exp(pow(((double)cpx/9.0)*w,1.0/3.0)*pow(log(w),2.0/3.0));</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>printf("bits= %d Complexity (%d/9) work=2^%d\n",bts,cpx,1+(int)log2(c)-FIDDLE_FACTOR);</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>return;</div><div>}</div><div><br></div><div>int main()</div><div>{</div><div> L(80*2*12*1,32);<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>// 160-bit BN curve ideal for 80-bit security</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(3072,64);<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>// factoring a 3072 bit number</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(128*2*12*1,32); // 256-bit BN curve</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(128*2*12*1,16); // hope this never happens...</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(224*2*12*1,32); // restoring faith with 448-bit BN curve - but group size too big!</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(128*2*8*2,48); // 512-bit Cocks-Pinch curve, embedding degree 8</div><div><br></div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(112*2*12*3/2,32); // BLS k=12 curve ideal at 112-bit security</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(128*2*16*5/4,32); // KSS k=16 curve ideal at 128-bit security</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(128*2*18*4/3,32); // KSS k=18</div><div><br></div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(192*2*24*5/4,32); // BLS k=24</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(192*2*32*9/8,32); // KSS k=32 curve ideal at 192-bit level</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(256*2*36*7/6,32); // KSS k=36</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>L(256*2*48*9/8,32); // BLS k=48 curve ideal at 256-bit level</div><div><br></div><div> return 0;</div><div>}</div><div><br></div></div><div><br></div><div>Mike</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Oct 8, 2016 at 3:34 AM, Trevor Perrin <span dir="ltr"><<a href="mailto:trevp@trevp.net" target="_blank">trevp@trevp.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Fri, Oct 7, 2016 at 7:18 PM, Chang-An Zhao<br>
<<a href="mailto:zhaochan3@mail.sysu.edu.cn">zhaochan3@mail.sysu.edu.cn</a>> wrote:<br>
> 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?<br>
<br>
</span>Hi Chang,<br>
<br>
See the discussion in my original post:<br>
<br>
<a href="https://moderncrypto.org/mail-archive/curves/2016/000740.html" rel="noreferrer" target="_blank">https://moderncrypto.org/mail-<wbr>archive/curves/2016/000740.<wbr>html</a><br>
<br>
The security situation isn't entirely clear yet, though that post<br>
mentions some estimates.<br>
<div class="HOEnZb"><div class="h5"><br>
Trevor<br>
______________________________<wbr>_________________<br>
Curves mailing list<br>
<a href="mailto:Curves@moderncrypto.org">Curves@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/curves" rel="noreferrer" target="_blank">https://moderncrypto.org/<wbr>mailman/listinfo/curves</a><br>
</div></div></blockquote></div><br></div>