Key alternating ciphers based on involutions

Abstract

In this work, we study the security of Even---Mansour type ciphers whose encryption and decryption are based on a common primitive, namely an involution. Such ciphers possibly allow efficient hardware implementation as the same circuit is shared for encryption and decryption, and thus expected to be more suitable for lightweight environment in which low power consumption and implementation costs are desirable. With this motivation, we consider a single-round Even---Mansour cipher using an involution as its underlying primitive. The decryption of such a cipher is the same as encryption only with the order of the round keys reversed. It is known that such a cipher permits a birthday-bound attack using only construction queries, but whether it provides provable security in the range below the birthday bound has remained. We prove that the Even---Mansour cipher based on a random involution is as secure as the permutation-based one when the number of construction queries is limited by the birthday bound. In order to achieve security beyond the birthday bound, we propose a two-round Even---Mansour-like construction, dubbed $$\mathsf {EMSI}$$EMSI, based on a single involution I using a fixed permutation $$\sigma $$ź in the middle layer. Specifically, $$\mathsf {EMSI}$$EMSI encrypts a plaintext u by computing $$\begin{aligned} v=I\left( \sigma \left( I(u\oplus k_0)\right) \oplus k_1\right) \oplus k_2 \end{aligned}$$v=IźI(uźk0)źk1źk2with the key schedule $$\gamma =(\gamma _0,\gamma _1,\gamma _2)$$ź=(ź0,ź1,ź2) generating three round keys $$k_0=\gamma _0(k)$$k0=ź0(k), $$k_1=\gamma _1(k)$$k1=ź1(k) and $$k_2=\gamma _2(k)$$k2=ź2(k) from an n-bit master key k. We prove that if the key schedule $$\gamma =(\gamma _0,\gamma _1,\gamma _2)$$ź=(ź0,ź1,ź2) satisfies a certain condition, and $$\sigma $$ź is a linear orthomorphism, then this construction is secure up to $$2^{\frac{2n}{3}}$$22n3 construction and permutation queries. $$\mathsf {EMSI}$$EMSI is the first construction that uses a single involution--a primitive weaker than a truly random permutation--and that provides security beyond the birthday bound at the same time. Encryption and decryption of $$\mathsf {EMSI}$$EMSI are the same except for the key schedule and the middle layer. Since encryption and decryption are both based on a common primitive, $$\mathsf {EMSI}$$EMSI is expected to be particularly suitable for modes of operation that use both encryption and decryption of the underlying block cipher such as OCB3.