Paper 2014/891

Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity

Jean-Sebastien Coron, Johann Groszschaedl, Praveen Kumar Vadnala, and Mehdi Tibouchi


A general method to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean operations with arithmetic operations, one must then perform conversions between Boolean masking and arithmetic masking. At CHES 2001, Goubin described a very elegant algorithm for converting from Boolean masking to arithmetic masking, with only a constant number of operations. Goubin also described an algorithm for converting from arithmetic to Boolean masking, but with O(k) operations where k is the addition bit size. In this paper we describe an improved algorithm with time complexity O(log k) only. Our new algorithm is based on the Kogge-Stone carry look-ahead adder, which computes the carry signal in O(log k) instead of O(k) for the classical ripple carry adder. We also describe an algorithm for performing arithmetic addition modulo 2^k directly on Boolean shares, with the same complexity O(log k) instead of O(k). We prove the security of our new algorithms against first-order attacks.

Available format(s)
Publication info
A minor revision of an IACR publication in FSE 2015
Side-channel attackfirst-order countermeasurearithmetic to Boolean conversion.
Contact author(s)
jscoron @ gmail com
2015-02-11: revised
2014-10-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jean-Sebastien Coron and Johann Groszschaedl and Praveen Kumar Vadnala and Mehdi Tibouchi},
      title = {Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2014/891},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.