XPX: Generalized Tweakable Even-Mansour with Improved Security Guarantees

We present \(\mathrm {XPX}\), a tweakable blockcipher based on a single permutation \(P\). On input of a tweak \((t_{11},t_{12},t_{21},t_{22})\in \mathcal {T}\) and a message m, it outputs ciphertext \(c=P(m\oplus \varDelta _1)\oplus \varDelta _2\), where \(\varDelta _1=t_{11}k\oplus t_{12}P(k)\) and \(\varDelta _2=t_{21}k\oplus t_{22}P(k)\). Here, the tweak space \(\mathcal {T}\) is required to satisfy a certain set of trivial conditions (such as \((0,0,0,0)\not \in \mathcal {T}\)). We prove that \(\mathrm {XPX}\) with any such tweak space is a strong tweakable pseudorandom permutation. Next, we consider the security of \(\mathrm {XPX}\) under related-key attacks, where the adversary can freely select a key-deriving function upon every evaluation. We prove that \(\mathrm {XPX}\) achieves various levels of related-key security, depending on the set of key-deriving functions and the properties of \(\mathcal {T}\). For instance, if \(t_{12}, t_{22}\ne 0\) and \((t_{21}, t_{22})\ne (0,1)\) for all tweaks, \(\mathrm {XPX}\) is XOR-related-key secure. \(\mathrm {XPX}\) generalizes Even-Mansour (\(\mathrm {EM}\)), but also Rogaway’s \(\mathrm {XEX}\) based on \(\mathrm {EM}\), and various other tweakable blockciphers. As such, \(\mathrm {XPX}\) finds a wide range of applications. We show how our results on \(\mathrm {XPX}\) directly imply related-key security of the authenticated encryption schemes Prøst-\(\mathrm {COPA}\) and \(\mathrm {Minalpher}\), and how a straightforward adjustment to the MAC function \(\mathrm {Chaskey}\) and to keyed Sponges makes them provably related-key secure.