Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity

TLDR

The paper proposes simple methods to transform cryptographic algorithms into side‑channel‑attack‑resistant versions. The authors present several protected exponentiation schemes—including square‑and‑multiply, right‑to‑left, and sliding‑window variants—and demonstrate the approach on elliptic‑curve point multiplication. These techniques achieve side‑channel protection without increasing execution time, are generic for virtually any algorithm, and maintain the same overall complexity as unprotected versions.

Abstract

We introduce simple methods to convert a cryptographic algorithm into an algorithm protected against simple side-channel attacks. Contrary to previously known solutions, the proposed techniques are not at the expense of the execution time. Moreover, they are generic and apply to virtually any algorithm. In particular, we present several novel exponentiation algorithms, namely, a protected square-and-multiply algorithm, its right-to-left counterpart, and several protected sliding-window algorithms. We also illustrate our methodology applied to point multiplication on elliptic curves. All these algorithms share the common feature that the complexity is globally unchanged compared to the corresponding unprotected implementations.