(Virtually) free randomization techniques for elliptic curve cryptography

Randomization techniques play an important role in the protection of cryptosystems against implementation attacks. This paper studies the case of elliptic curve cryptography and propose three novel randomization methods, for the elliptic curve point multiplication, which do not impact the overall performance. Our first method, dedicated to elliptic curves over prime fields, combines the advantages of two previously known solutions: randomized projective coordinates and randomized isomorphisms. It is a generic point randomization and can be related to a certain multiplier randomization technique. Our second method introduces new elliptic curve models that are valid for all (non-supersingular) elliptic curves over binary fields. This allows to use randomized elliptic curve isomorphisms, which in turn allows to randomly compute on elliptic curves with affine coordinates. Our third method adapts a double ladder attributed to Shamir. We insist that all our randomization methods share the common feature to be free: the cost of our randomized implementations is virtually the same as the cost of the corresponding non-randomized implementations.