Packed Multiplication: How to Amortize the Cost of Side-Channel Masking?

Higher-order masking countermeasures provide strong provable security against side-channel attacks at the cost of incurring significant overheads, which largely hinders its applicability. Previous works towards remedying cost mostly concentrated on “local” calculations, i.e., optimizing the cost of computation units such as a single AND gate or a field multiplication. This paper explores a complementary “global” approach, i.e., considering multiple operations in the masked domain as a batch and reducing randomness and computational cost via amortization. In particular, we focus on the amortization of ℓ parallel field multiplications for appropriate integer ℓ> 1, and design a kit named packed multiplication for implementing such a batch. For ℓ+ d≤ 2^m, when ℓ parallel multiplications over F2m with d-th order probing security are implemented, packed multiplication consumes d²+ 2 ℓd+ ℓ bilinear multiplications and 2 d²+ d(d+ 1 ) / 2 random field variables, outperforming the state-of-the-art results with O(ℓd²) multiplications and ℓ⌊d²/ 4 ⌋ + ℓd randomness. To prove d-probing security for packed multiplications, we introduce some weaker security notions for multiple-inputs-multiple-outputs gadgets and use them as intermediate steps, which may be of independent interest. As parallel field multiplications exist almost everywhere in symmetric cryptography, lifting optimizations from “local” to “global” substantially enlarges the space of improvements. To demonstrate, we showcase the method on the AES Subbytes step, GCM and TET (a popular disk encryption). Notably, when d= 8, our implementation of AES Subbytes in ARM Cortex M architecture achieves a gain of up to 33 % in total speeds and saves up to 68 % random bits than the state-of-the-art bitsliced implementation reported at ASIACRYPT 2018.