Investigate using new algorithm for scalar multiplication

paulmillr commented at 11:43 pm on April 4, 2022: contributor

This is an algorithm for EC multiplication that emulates the Montgomery Ladder double-and-add, but in a constant time way. An early version of this algorithm was published in 2017, and the version implemented here was published in 2020. The result is constant time multiply that is 85% faster than wNAF, <10% slower than endomorphic Montgommery Ladder and ~20% faster than w/o endomorphism.

https://eprint.iacr.org/2017/669.pdf https://web.archive.org/web/20201104025731/https://www.aimsciences.org/article/exportPdf?id=5c293be6-723e-4b97-ae1d-ff359e261cdb

Originally submitted as a pull request to my JS secp256k1 impl. I think it deserves some investigation.

Quirk: the algorithm researchers are from North Korea 😐

real-or-random commented at 1:03 pm on April 14, 2022: contributor

So this is about multiplication of a secret scalar with any public point, without precomputation (what we call ecmult_const here, used in ECDH here). The second link is the journal/accepted version of the first paper, if I understand correctly.

It’s very interesting, and apparently Mike Hamburg presented a simple variant of the ideas in a rump talk at CHES17, which is also described in the journal version of the paper. What makes this interesting: the approach here seems to be inspired by the Montgomery ladder but it works on every short Weierstrass curve. The slides even mention that it’s possible to turn it into an x-only ladder, which so far I assumed is only possible on Montgomery curves. (Related: #262 but this uses a different method to speed up x-only ECDH).

cc @brandonblack

Quirk: the algorithm researchers are from North Korea :neutral_face:

We should not judge people based on their origin or nationality but even if you disagree, we should not judge algorithms based on the origin or nationality of their inventors.

brandonblack commented at 1:45 pm on April 14, 2022: none

As somewhat discussed in my PR against noble-secp256k1, these algorithms are constant time on the number of bits in the scalar. It’s above my pay grade to know what modifications would correctly make them constant time on a fixed number of bits. To pass the sniff test, I ran the initialization function, the per-bit transform for each leading zero, and then the initialization again to begin computing the real output value.

I experimented with a couple of the algorithms they presented (8-, and 9-register), and found that in the context of JavaScript native bigints the 8-register version performed best. Which is fastest depends on the relationship between the cost of modmul, modadd, and modsub, as the 9-register version has 2 fewer multiplications, but 2 extra subtractions and 9 extra additions per iteration.

paulmillr commented at 2:09 pm on April 14, 2022: contributor

@real-or-random

we should not judge algorithms based on the origin or nationality of their inventors.

North Korea has a history of targeting security researchers all over the world with very elaborate schemes, so i’m thinking primarily in this context here. I don’t care who’ve made it, I do care about getting some subtle security issues in. Especially since the folks seem to be sitting inside NK, not outside. Also decided to mention this fact because i’ve never seen security papers from there.

mratsim cross-referenced this on Aug 6, 2022 from issue Scalar-mul: Constant-Time double-and-add by mratsim

Investigate using new algorithm for scalar multiplication #1099