Paper 2020/542

Lightweight Authenticated Encryption Mode Suitable for Threshold Implementation

Yusuke Naito, Yu Sasaki, and Takeshi Sugawara

Abstract

This paper proposes tweakable block cipher (TBC) based modes $\mathsf{PFB}\mathsf{\_}\mathsf{Plus}$ and $\mathsf{PFB}\omega$ that are efficient in threshold implementations (TI). Let $t$ be an algebraic degree of a target function, e.g.~$t=1$ (resp.~$t>1$) for linear (resp.~non-linear) function. The $d$-th order TI encodes the internal state into $dt+1$ shares. Hence, the area size increases proportionally to the number of shares. This implies that TBC based modes can be smaller than block cipher (BC) based modes in TI because TBC requires $s$-bit block to ensure $s$-bit security, e.g. \textsf{PFB} and \textsf{Romulus}, while BC requires $2s$-bit block. However, even with those TBC based modes, the minimum we can reach is 3 shares of $s$-bit state with $t=2$ and the first-order TI ($d=1$). Our first design $$ aims to break the barrier of the $$-bit state in TI. The block size of an underlying TBC is $$ bits and the output of TBC is linearly expanded to $$ bits. This expanded state requires only 2 shares in the first-order TI, which makes the total state size $$ bits. We also provide rigorous security proof of $$. Our second design $$ further increases a parameter $$: a ratio of the security level $$ to the block size of an underlying TBC. We prove security of $$ for any $$ under some assumptions for an underlying TBC and for parameters used to update a state. Next, we show a concrete instantiation of $$ for 128-bit security. It requires a TBC with 64-bit block, 128-bit key and 128-bit tweak, while no existing TBC can support it. We design a new TBC by extending \textsf{SKINNY} and provide basic security evaluation. Finally, we give hardware benchmarks of $$ in the first-order TI to show that TI of $$ is smaller than that of \textsf{PFB} by more than one thousand gates and is the smallest within the schemes having 128-bit security.