International Association
for Cryptologic Research

Since Kuwakado and Morii's work (ISIT 2010 \& ISITA 2012), it is known that the classically secure 3-round Luby-Rackoff PRP and Even-Mansour cipher become insecure against an adversary equipped with \emph{quantum} query access. However, while this query model (the so-called Q2 model) has led to many more attacks, it seems that restricting the adversary to classical query access prevents such breaks (the so-called Q1 model). Indeed, at EUROCRYPT 2022, Alagic et al. proved the Q1-security of the Even-Mansour cipher. Notably, such a proof needs to take into account the dichotomy between construction queries, which are classical, and primitive queries, which are quantum (since the random oracle / permutation models a public function that the adversary can compute). In this paper, we focus on Feistel ciphers. More precisely, we consider Key-Alternating Feistels built from random functions or permutations. We borrow the tools used by Alagic et al. and adapt them to this setting, showing that in the Q1 setting: $\bullet$~the 3-round Key-Alternating Feistel, even when the round functions are the same random oracle, is a pseudo-random permutation; $\bullet$~similarly the 4-round KAF is a strong pseudo-random permutation.

During recent years, research on authenticated encryption has been thriving through two highly active and practically motivated research directions: provable leakage resilience and key- or context-commitment security. However, the intersection of both fields had been overlooked until very recently. In ToSC 1/2024, Struck and Weishäupl studied generic compositions of encryption schemes and message authentication codes for building committing leakage-resilient schemes. They showed that, in general, Encrypt-then-MAC (EtM) and MAC-then-Encrypt (MtE) are not committing while Encrypt-and-MAC (EaM) is, under plausible and weak assumptions on the components. However, real-world schemes are rarely strict blackbox constructions. Instead, while various leakage-resilient schemes follow blueprints inspired by generic compositions, they often tweak them for security or efficiency.In this paper, we study two blueprints, the first one based on EtM for one of the strongest possible levels of leakage resilience. The second one is a single-pass framework based on leveled implementations. We show that, with a careful selection of the underlying primitives such as with identical encryption and authentication keys and a collision-resistant PRF as the MAC, these blueprints are committing. Our results do not contradict the results by Struck and Weishäupl since we pose more, but practically-motivated, requirements on the components. We demonstrate the practical relevance of our results by showing that our results on those blueprints allow us to easily derive proofs that several state-of-the-art leakage-resilient schemes are indeed committing, including TEDT and its descendants TEDT2 and Romulus-T, as well as the single-pass scheme Triplex.