International Association
for Cryptologic Research

We propose the first updatable white-box secure cipher, EWEMrl, and its natural extension EWEMxl, both achieving longevity against non-adaptive read-only malware. The notion of longevity, introduced by Koike et al., addresses continuous code leakage and is stronger than incompressibility. While Yoroi claimed longevity, but was broken by Isobe and Todo. Given the prevalence of continuous leakage, developing such ciphers is crucial in white-box cryptography. Precisely, we have the following.

• We first introduce EWEMr (Extended WEM against non-adaptive read-only adversaries), a generalization of WEM (White-box Even-Mansour). WEM is the first (and possibly only) white-box cipher based on EM, replacing its key addition layer with a secret Sbox. EWEMr achieves a high space-hardness bound, with a new generic proof strategy, but does not provide longevity. Instead, it serves as the base for EWEMrl.

• We also present EWEMx, which uses EWEMr as subroutines and is secure in the stronger adaptive model. While EWEMx does not achieve longevity, it is the base design for EWEMxl.

• We next propose EWEMrl, which is the first cipher to achieve longevity against non-adaptive read-only adversaries. No existing ciphers, such as SPNbox and SPACE, are designed for longevity. We show that EWEMrl ensures (against non-adaptive read-only adversaries) (1) longevity, (2) high space-hardness in both known-space and chosen-space settings, and (3) security against hybrid code-lifting attacks.

• Finally, we introduce EWEMxl, a natural extension of EWEMrl with a structure similar to EWEMx. EWEMxl achieves (2) and (3) in the stronger adaptive model while maintaining (1) in the same non-adaptive and read-only setting.

In summary, EWEMrl and EWEMxl are the first ciphers providing longevity against non-adaptive read-only malware while ensuring security confidence in the black-box setting.