Cryptology ePrint Archive: Report 2020/1103

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

Weijia Wang; Chun Guo; François-Xavier Standaert; Yu Yu; 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.

Category / Keywords: implementation / Side-channel attacks, Masking, Cost amortization

Original Publication (with minor differences): IACR-ASIACRYPT-2020

Date: received 12 Sep 2020

Contact author: wjwang at sdu edu cn,chun guo@sdu edu cn,francois-xavier standaert@uclouvain be,yuyu@yuyu hk,gaetan cassiers@uclouvain be

Available format(s): PDF | BibTeX Citation

Version: 20200915:112307 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]