XPX: Generalized Tweakable Even-Mansour with Improved Security Guarantees

摘要

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