### 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 $\ell+d\leq2^m$, when $\ell$ parallel multiplications over $\mathbb{F}_{2^{m}}$ with $d$-th order probing security are implemented, packed multiplication consumes $d^2+2\ell d + \ell$ bilinear multiplications and $2d^2 + d(d+1)/2$ random field variables, outperforming the state-of-the-art results with $O(\ell d^2)$ multiplications and $\ell \left \lfloor d^2/4\right \rfloor + \ell 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.

Available format(s)
Category
Implementation
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
Keywords
Contact author(s)
wjwang @ sdu edu cn
chun guo @ sdu edu cn
francois-xavier standaert @ uclouvain be
yuyu @ yuyu hk
gaetan cassiers @ uclouvain be
History
Short URL
https://ia.cr/2020/1103

CC BY

BibTeX

@misc{cryptoeprint:2020/1103,
author = {Weijia Wang and Chun Guo and François-Xavier Standaert and Yu Yu and Gaëtan Cassiers},
title = {Packed Multiplication: How to Amortize the Cost of Side-channel Masking ?},
howpublished = {Cryptology ePrint Archive, Paper 2020/1103},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1103}},
url = {https://eprint.iacr.org/2020/1103}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.