Paper 2020/1103

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

Weijia Wang, Chun Guo, François-Xavier Standaert, Yu Yu, and Gaëtan Cassiers

Abstract

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 $\ell$ parallel field multiplications for appropriate integer $\ell >1$, and design a kit named {\it packed multiplication} for implementing such a batch. For $$, when $$ parallel multiplications over $$ with $$-th order probing security are implemented, packed multiplication consumes $$ bilinear multiplications and $$ random field variables, outperforming the state-of-the-art results with $$ multiplications and $$ randomness. To prove $$-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 $$, our implementation of AES Subbytes in ARM Cortex M architecture achieves a gain of up to $$ in total speeds and saves up to $$ random bits than the state-of-the-art bitsliced implementation reported at ASIACRYPT~2018.