3 ms·
For those interested in "Warp Speed", I've written a tutorial about how to exploit group laws to implement fast scalar multiplication: https://loup-vaillant.fr/
by loup-vaillant 5y ago
For those interested in "Warp Speed", I've written a tutorial about how to exploit group laws to implement fast scalar multiplication: https://loup-vaillant.fr/tutorials/fast-scalarmult https://loup-vaillant.fr/tutorials/fast-scalarmult
As a bonus, there are remarks about secure implementations as well.
- mratsim 5y agoAnd then there is super warp speed using group endomorphisms to increase scalar multiplication by 2x over windowed methods.
- loup-vaillant 5y agoDoes that apply to any group? I know of a method that applies to the double scalar multiplication, but it speeds up Ed255119 only by 25%, at the cost of doubling stack usage. Also, if a group has a structure that allows such speedups, I would fear that the same structure could also enable attacks… Ideally, you want your group to have as little structure as possible, that's what makes attacks infeasible.
- mratsim 5y agoSpeeding 2x isn't enough to enable attacks when they already take exponential time. It applies most commonly to curves with an equation of the form y^3 = x² + b which mathematically imply that (x, y) and (x, cuberoot(y)) are both points on a curve and so you can split a n bits scalar into two n/2 bits scalar and do double scalar multiplication.