[curves] Curves for pairings

[Watson Ladd]

On Thu, Sep 29, 2016 at 2:38 AM, Michael Scott <mike.scott at miracl.com> wrote:
> Hello Brendan,
>
>
> Yes that's roughly my experience. However I would expect the ratio for the
> pairing to rise from 2.5 to 1 to maybe 4 to 1 for highly optimised assembly
> language implementations (based on some back-of-the-envelope calculations).
> I would expect the pairing (and in particular the final exponentiation) to
> suffer more than scalar mults in G1 and G2, as there although the field size
> must increase, the group size ideally should not. So the impact is likely to
> be rather protocol dependent. In a good pairing-based protocol most of the
> action should take place in G1, with ideally just one pairing calculation.
>
>
> Here is another take on a possible response to the new estimates..
>
> There is an asteroid called "Quantum Computing" heading straight for "Planet
> Crypto". We know more or less exactly what damage it will do. And from what
> I have been hearing it is expected to hit around the year 2030.

This assumes a relatively large amount of progress in engineering. It
is unclear if this actually possible.

> Now if you look at papers estimating key sizes that we would need, often
> they were based on extrapolations of current technologies beyond 2050. Well
> that's all pretty pointless now. So why beat ourselves up between now and
> the asteroid strike? As of now 80 bits of (AES equivalent) security has
> still not been broken, and may still be fine in 2030!

There are several ways to interpret "still not been broken". One is to
look at the largest public computation which has taken place aimed a
crypto challenge. The other is to look at the cost of ongoing
computations. Globally Bitcoin hashing carries out 300*10^15 SHA-256
calculations per second, and thus could compute 7 SHA-1 collisions per
year. This has the same computation cost as breaking an elliptic curve
with 160-bit field
length. Every 3 years another 2 bits are added to the performance per
price. 18 years from now 92 bits will not

There are good reasons to believe that the performance of the number
field sieve variants used in these new attacks can increase. These
include the continuing rate of new results, the absence of sound
theoretical lower bounds, and the persistence of worse performance in
medium fields. Furthermore, these attacks are batchable. In some cases
a single key can be broken to enable forgery, such as in SNARKS.

>
> Now a 336-bit BLS curve is an ideal fit for 112-bits of security. I suggest
> that this would be more than enough to carry us forward to the
> end-of-the-world-as-we-know-it.
>
> The current response of the community rather reminds me of the French
> response at the end of WW1, which ignored the coming impact of the Tank and
> instead built a bigger and better trench system - the Maginot line.

<military history correction>

The Maginot line was not attacked with tanks but bypassed and
besieged, and surrendered after there was no point in fighting. It had
adequate artillery and anti-tank weapons. What did them in was the
assault via the Ardennes, crossing rough terrain with combined arms.
German tanks were inferior in armored warfare, with insufficient
firepower, poor maintainability, and lack of sloped armor. What the
Panzercorps had were innovative commanders and an army capable of
using them to full advantage.

</military history correction>
>
>
> Mike
>
>
> On Thu, Sep 29, 2016 at 6:21 AM, Brendan McMillion
> <brendanmcmillion at gmail.com> wrote:
>>
>> Hey Mike,
>>
>> This morning, I forked Golang's implementation of bn256 and fit it with a
>> 448-bit BN [1] curve based on the parameter
>>
>> u = 1910986621940954212840033034977453
>>
>> which, according to ellipticnews, should be closer to the 128-bit security
>> level. Interestingly, it's also very close to 2.5 times slower than the same
>> implementation for a 256-bit curve for all major operations. For scalar mult
>> in G1, 2 milliseconds to 5ms. For scalar mult in G2, 5ms to 13ms. For a
>> pairing, 15ms to 35ms. All of these numbers can be lowered by an order of
>> magnitude by porting them to C and the scalar multiplications can still be
>> sped up by implementing GLV decomposition.
>>
>> Is this also roughly the situation for the BLS curves you're experimenting
>> with?
>>
>> [1] https://github.com/Bren2010/bn448
>>
>>
>>
>> On Sep 28, 2016 4:09 PM, "Jeff Burdges" <burdges at gnunet.org> wrote:
>>>
>>> On Tue, 2016-09-27 at 05:28 +0000, Zooko Wilcox-OHearn wrote:
>>> > I was totally wrong about this. Our performance bottleneck is in a
>>> > path (zk-SNARK proving) that doesn't require pairing operations, so
>>> > using a curve which was 2.5 times slower at pairing operations would
>>> > not worsen our performance issues. However, if it was also 2.5 slower
>>> > for curve operations, then it would.
>>>
>>> It's still slower for scalar multiplication due to being a larger curve,
>>> no?
>>>
>>> In any case, you said there are no risks to the anonymity here, so an
>>> alternative to changing curves might be to prevent attacks from being
>>> profitable by capping the maximum value in a transaction or account,
>>> right?  In the short term, this should not require dong anything.
>>>
>>> Jeff
>>>
>>>
>>> _______________________________________________
>>> Curves mailing list
>>> Curves at moderncrypto.org
>>> https://moderncrypto.org/mailman/listinfo/curves
>>>
>>
>> _______________________________________________
>> Curves mailing list
>> Curves at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/curves
>>
>
>
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.