[curves] Scalar blinding on elliptic curves with special structure
Michael Hamburg
mike at shiftleft.org
Wed Aug 12 13:45:41 PDT 2015
Neat. The recoding would be a little annoying, but not awful. For ECDH it might be enough to just do both steps with the same random blinded base-48 encoding.
You can make it work with the Montgomery ladder too. You’d use some unmixed ladder steps:
(P, Q, P+Q)
-> 2Q+P = (P+Q + Q) where (P+Q - Q) = P
-> 3Q+P = (2Q+P + Q) where (2Q+P - Q) = (P+Q)
and 3Q+2P = (2Q+P + Q+P) where (2Q+P) - (Q+P) = Q
3Q = 2Q+Q where 2Q-Q=Q.
3(Q+P) = 2(Q+P) + (Q+P) where 2(Q+P) - (Q+P) = Q+P
These last steps might not work with all ladders though… I don’t remember whether eg Jacobian co-z ladder works for steps like these.
— Mike
> On Aug 10, 2015, at 9:52 PM, Trevor Perrin <trevp at trevp.net> wrote:
>
> A new paper by Fluhrer is relevant to the discussion about scalar
> blinding with special-prime vs random-prime curves:
>
> http://eprint.iacr.org/2015/801
>
>
> My earlier impression [1] was that scalar-blinding on 25519 might use
> a 128-bit blinding factor, whereas a similar-but-random-prime curve
> would use a 64-bit blinding factor, resulting in a slowdown for 25519
> of around (256+128)/(256+64) = 1.2.
>
> Fluhrer's paper argues for using the same size blinding factor, but
> recoding the digits of the scalar used for windowing into a form where
> the group's order "would, at first glance, appear random". He gives
> an example of base-48 digits instead of base-32, and estimates a
> slowdown for 25519 of around 1.1.
>
> I don't think this helps implementations that use Montgomery ladder
> (instead of windowing). Beyond that, I don't have a good sense how
> well this would work, how awkward the encoding would be, or how it
> would interact with other scalar encoding methods.
>
> Anyone have a more informed opinion?
>
> Trevor
>
> [1] https://moderncrypto.org/mail-archive/curves/2015/000563.html
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
More information about the Curves
mailing list