Efficient and provably secure methods for switching from arithmetic to boolean masking

A large number of secret key cryptographic algorithms combine Boolean and arithmetic instructions. To protect such algorithms against first order side channel analysis, it is necessary to perform conversions between Boolean masking and arithmetic masking. Louis Goubin proposed in [5] an efficient method to convert from Boolean to arithmetic masking. However the conversion method he also proposed in [5] to switch from arithmetic to Boolean is less efficient and could be a bottleneck in some implementations. Two faster methods were proposed in [2] and [9], both using precomputed tables. We show in this paper that the algorithm in [2] is bugged, and propose an efficient correction. Then, we propose an alternative to the algorithm in [9] with a valuable timing/ memory tradeoff. This new method offers better security in practice and is well adapted for 8-bit architectures in terms of time performance (3.3 times faster than Goubin's algorithm for one single conversion).