Paper 2026/122

The Motte-and-Bailey Framework for Leakage-Resilient Accordion Modes: Featuring Qaitbay and Alicante

Mustafa Khairallah, Nanyang Technological University

Abstract

Accordion modes have experienced a surge in popularity, partially motivated by the recent NIST Accordion modes project. None of the popular candidates is leakage-resilient by default. In this work, we study the design of a leakage-resilient Accordion mode. Firstly, we present a generic analysis of the Encode-then-Encipher paradigm in the leakage-resilient setting, assuming the enciphering is a leakage resilient STPRP. However, we show that the resulting security, while strong, suffers from some limitations. Next, we introduce Motte-and-Bailey, a general framework building leakage resilient accordion modes, in the spirit of the PIV construction. Motte-and-Bailey, or MaB, for short, is a leveled construction, requiring light assumptions on most of its components to guarantee good STPRPl2, CIML2 and CCAmL2 security. In particular, we require two fully protected calls to a TBC, a collision-resistant hash function (with unbounded or light leakage), and an ideal leakage-resilient PRG, secure against single-trace attacks. Additionally, we present particular instantiations, Qaitbay and Alicante. In Qaitbay the PRG and the hash function are replaced by Sponge functions, while an independent TBC is used for the leak-free calls. Alicante makes use of ideal ciphers, and uses the MDPH hash function and the 2PRG construction, while the leak-free calls are implemented using independent calls to the ideal cipher. Also, we propose to instantiate the TBC in Qaitbay with the permutation based XPX. Moreover, Qaitbay and Alicante come in two flavors, the first one is a normal instantiation of MaB, while the second one, at the cost of one additional protected call to a TBC, provides CCAMl2, a quite elusive security property. We note that our construction provide some of the strongest combinations of security notions that are believed to be possible: Qaitbay-1 and Alicante-1 provide STPRPl2 +CIML2 +CCAMl2, while Qaitbay-2 and Alicante-2 provide the same combination in addition to CCAmL2.

BibTeX

@misc{cryptoeprint:2026/122,
author = {Mario Marhuenda Beltrán and Mustafa Khairallah},
title = {The Motte-and-Bailey Framework for Leakage-Resilient Accordion Modes: Featuring Qaitbay and Alicante},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/122},
year = {2026},
url = {https://eprint.iacr.org/2026/122}
}