International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Lightweight Authenticated Encryption Mode Suitable for Threshold Implementation

Authors:
Yusuke Naito , Mitsubishi Electric Corporation
Yu Sasaki , NTT Secure Platform Laboratories
Takeshi Sugawara , The University of Electro-Communications
Download:
DOI: 10.1007/978-3-030-45724-2_24 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: This paper proposes tweakable block cipher (TBC) based modes \textsf{PFB}\_\textsf{Plus} and \textsf{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 $d t + 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 \textsf{PFB}\_\textsf{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 \textsf{PFB}\_\textsf{Plus}. Our second design \textsf{PFB}$\omega$ further increases a parameter $\omega$: a ratio of the security level $s$ to the block size of an underlying TBC. We prove security of \textsf{PFB}$\omega$ for any $\omega$ under some assumptions for an underlying TBC and for parameters used to update a state. Next, we show a concrete instantiation of \textsf{PFB}\_\textsf{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 \textsf{SKINNY} and provide basic security evaluation. Finally, we give hardware benchmarks of \textsf{PFB}\_\textsf{Plus} in the first-order TI to show that TI of \textsf{PFB}\_\textsf{Plus} is smaller than that of \textsf{PFB} by more than one thousand gates and is the smallest within the schemes having 128-bit security.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30210,
  title={Lightweight Authenticated Encryption Mode Suitable for Threshold Implementation},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={Authenticated encryption;threshold implementation;beyond-birthday-bound security;tweakable block cipher;lightweight.},
  volume={12105},
  doi={10.1007/978-3-030-45724-2_24},
  author={Yusuke Naito and Yu Sasaki and Takeshi Sugawara},
  year=2020
}