Cryptology ePrint Archive: Report 2014/891
Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity
Jean-Sebastien Coron and Johann Groszschaedl and Praveen Kumar Vadnala and Mehdi Tibouchi
Abstract: 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.
Category / Keywords: Side-channel attack, first-order countermeasure, arithmetic to Boolean conversion.
Original Publication (with minor differences): IACR-FSE-2015
Date: received 29 Oct 2014, last revised 11 Feb 2015
Contact author: jscoron at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20150211:164211 (All versions of this report)
Short URL: ia.cr/2014/891
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]