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 $\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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
Keywords
Side-channel attacksMaskingCost amortization
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
2020-09-15: received
Short URL
https://ia.cr/2020/1103
License
Creative Commons Attribution
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.