Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity
English
Coron, Jean-Sébastien[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Groszschädl, Johann[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Tibouchi, Mehdi[NTT Secure Platform Laboratories > Okamoto Research Laboratory]
Vadnala, Praveen Kumar[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Mar-2015
Fast Software Encryption, 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers
Leander, Gregor
Springer Verlag
Lecture Notes in Computer Science, volume 9054
130-149
Yes
International
978-3-662-48115-8
22nd International Workshop on Fast Software Encryption (FSE 2015)
[en] A general technique 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 algorithm against first-order attacks. Our algorithm performs well in practice, as for k=64 we obtain a 23% improvement compared to Goubin’s algorithm.