[curves] Curves for pairings

[Michael Scott]

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.

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!

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.


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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20160929/42cd8d50/attachment.html>