Paper 2023/1213
Fallen Sanctuary: A Higher-Order and Leakage-Resilient Rekeying Scheme
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.
Note: Errata: In the definition of AR_{d,m}, the center union to m^{i} was incorrect, but m^{i-1} is correct (as well, \sigma_{d,m} should be \sum_{i=1}^d m^{i-1}). The numerical evaluation has been conducted with the correct definition.
Metadata
- Available format(s)
- Category
- Secret-key cryptography
- Publication info
- A minor revision of an IACR publication in TCHES 2024
- DOI
- 10.46586/tches.v2024.i1.264-308
- Keywords
- Fresh rekeyingLeakage resilienceSide-channel attack
- Contact author(s)
-
rei ueno a8 @ tohoku ac jp
naofumi homma c8 @ tohoku ac jp
a_inoue @ nec com
k-minematsu @ nec com - History
- 2023-12-05: revised
- 2023-08-10: received
- See all versions
- Short URL
- https://ia.cr/2023/1213
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1213, author = {Rei Ueno and Naofumi Homma and Akiko Inoue and Kazuhiko Minematsu}, title = {Fallen Sanctuary: A Higher-Order and Leakage-Resilient Rekeying Scheme}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1213}, year = {2023}, doi = {10.46586/tches.v2024.i1.264-308}, url = {https://eprint.iacr.org/2023/1213} }