Lightweight Authenticated Encryption Mode Suitable for Threshold Implementation

This paper proposes tweakable block cipher (TBC) based modes minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {PFB\_Plus}$documentPFB_Plus and minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {PFB}\omega$documentPFBω that are efficient in threshold implementations (TI). Let t be an algebraic degree of a target function, e.g. minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$t=1$documentt=1 (resp. minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$t>1$documentt>1) for linear (resp. non-linear) function. The d-th order TI encodes the internal state into minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$d t + 1$documentdt+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. PFB and 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 minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$t=2$documentt=2 and the first-order TI (minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$d=1$documentd=1). Our first design minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {PFB\_Plus}$documentPFB_Plus aims to break the barrier of the 3s-bit state in TI. The block size of an underlying TBC is s/2 bits and the output of TBC is linearly expanded to s bits. This expanded state requires only 2 shares in the first-order TI, which makes the total state size 2.5s bits. We also provide rigorous security proof of minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {PFB\_Plus}$documentPFB_Plus. Our second design minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {PFB}\omega$documentPFBω further increases a parameter minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\omega$documentω: a ratio of the security level s to the block size of an underlying TBC. We prove security of minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {PFB}\omega$documentPFBω for any minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\omega$documentω under some assumptions for an underlying TBC and for parameters used to update a state. Next, we show a concrete instantiation of minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {PFB\_Plus}$documentPFB_Plus 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 SKINNY and provide basic security evaluation. Finally, we give hardware benchmarks of minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {PFB\_Plus}$documentPFB_Plus in the first-order TI to show that TI of minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {PFB\_Plus}$documentPFB_Plus is smaller than that of PFB by more than one thousand gates and is the smallest within the schemes having 128-bit security.