International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Fallen Sanctuary: A Higher-Order and Leakage-Resilient Rekeying Scheme

Authors:
Rei Ueno , Tohoku University, 2–1–1 Katahira, Aoba-ku, Sendai-shi, Miyagi, 980-8577, Japan
Naofumi Homma , Tohoku University, 2–1–1 Katahira, Aoba-ku, Sendai-shi, Miyagi, 980-8577, Japan
Akiko Inoue , NEC Secure System Platform Laboratories, 1753 Shimonumabe, Nakahara, Kawasaki, Kanagawa 211–8666, Japan
Kazuhiko Minematsu , NEC Secure System Platform Laboratories, 1753 Shimonumabe, Nakahara, Kawasaki, Kanagawa 211–8666, Japan
Download:
DOI: 10.46586/tches.v2024.i1.264-308
URL: https://tches.iacr.org/index.php/TCHES/article/view/11253
Search ePrint
Search Google
Abstract: This paper presents a provably secure, higher-order, and leakage-resilient (LR) rekeying scheme named LR Rekeying with Random oracle Repetition (LR4), along with a quantitative security evaluation methodology. Many existing LR primitives are based on a concept of leveled implementation, which still essentially require a leak-free sanctuary (i.e., differential power analysis (DPA)-resistant component(s)) for some parts. In addition, although several LR pseudorandom functions (PRFs) based on only bounded DPA-resistant components have been developed, their validity and effectiveness for rekeying usage still need to be determined. In contrast, LR4 is formally proven under a leakage model that captures the practical goal of side-channel attack (SCA) protection (e.g., masking with a practical order) and assumes no unbounded DPA-resistant sanctuary. This proof suggests that LR4 resists exponential invocations (up to the birthday bound of key size) without using any unbounded leak-free component, which is the first of its kind. Moreover, we present a quantitative SCA success rate evaluation methodology for LR4 that combines the bounded leakage models for LR cryptography and a state-of-the-art information-theoretical SCA evaluation method. We validate its soundness and effectiveness as a DPA countermeasure through a numerical evaluation; that is, the number of secure calls of a symmetric primitive increases exponentially by increasing a security parameter under practical conditions.
BibTeX
@article{tches-2023-33669,
  title={Fallen Sanctuary: A Higher-Order and Leakage-Resilient Rekeying Scheme},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={024 No. 1},
  pages={264-308},
  url={https://tches.iacr.org/index.php/TCHES/article/view/11253},
  doi={10.46586/tches.v2024.i1.264-308},
  author={Rei Ueno and Naofumi Homma and Akiko Inoue and Kazuhiko Minematsu},
  year=2023
}