How to Enhance the Security on the Least Significant Bit

Scalar multiplication, which computes dP for a given point P and a scalar d, is the dominant computation part of Elliptic Curve Cryptosystems (ECC). Recently, Side Channel Attacks (SCA) on scalar multiplication have become real threats. This is why secure and efficient scalar multiplication is important for ECC, and many countermeasures have been proposed so far. The Montgomery Ladder and the Regular right-to-left algorithm are the simplest and the most elegant algorithms. However, they are vulnerable to an SCA on the Least Significant Bit (LSB). In this paper, we investigate how to enhance the LSB security without spoiling the original features of simplicity. Our elegant techniques make the previous schemes secure against the SCA on LSB, while maintaining original performances.11th International Conference, CANS 2012, Darmstadt, Germany, December 12-14, 2012. Proceeding