Paper 2023/1658

On the Security of Triplex- and Multiplex-type Constructions with Smaller Tweaks

Abstract

In TCHES’22, Shen et al. proposed Triplex, a single-pass leakage-resistant authenticated encryption scheme based on Tweakable Block Ciphers (TBCs) with 2n-bit tweaks. Triplex enjoys beyond-birthday-bound ciphertext integrity in the CIML2 setting and birthday-bound confidentiality in the CCAmL1 notion. Despite its strengths, Triplex’s operational efficiency was hindered by its sequential nature, coupled with a rate limit of 2/3. In an endeavor to surmount these efficiency challenges, Peters et al. proposed Multiplex, a variant of Triplex with increased parallelism and a flexible rate of d/(d+1) that retains similar security guarantees. However, the innovation came at the price of requiring TBCs with dn-bit tweaks, which are unusual and potentially costly for d > 3. In this paper, we investigate the limits of generalized Triplex- and Multiplex-type constructions for single-pass leakage-resilient authenticated encryption. Our contributions are threefold. First, we show that such constructions cannot provide CIML2 integrity for any tweak lengths below dn/2 bits. Second, we provide a birthday-bound attack for constructions with TBCs of tweak lengths between dn/2 and (d − 1)n + n/2 bits. Finally, on the constructive side, we propose a family of single-pass leakage-resilient authenticated ciphers, dubbed Tweplex, that uses tweaks of dn/2 bits and provides a rate of d/(d + 1) while providing n/2-bit CIML2 integrity and CCAmL1 confidentiality.

Note: This is the full version of the paper titled "On the Security of Triplex- and Multiplex-type Constructions with Smaller Tweaks" that has been accepted at INDOCRYPT 2023.