Constant-time higher-order Boolean-to-arithmetic masking

Converting a Boolean mask to an arithmetic mask, and vice versa, is often required in implementing side-channel-resistant instances of cryptographic algorithms that mix Boolean and arithmetic operations. In this paper, we describe a method for converting a Boolean mask to an arithmetic mask that runs in constant time for a fixed order and has quadratic complexity as the security order increases, a significant improvement in previous work that has exponential complexity. We propose explicit algorithms for a second-order secure Boolean-to-arithmetic mask conversion that uses 31 instructions and for a third-order secure mask conversion that uses 74 instructions. We show that our second-order secure algorithm is at least an order of magnitude faster and our third-order secure algorithm is more than twice as fast as other algorithms in the literature.