# Minimizing Key Materials: The Even–Mansour Cipher Revisited and Its Application to Lightweight Authenticated Encryption

Authors: Ping Zhang; Qian Yuan
Journal: Security and Communication Networks
 (2020)

---

## Abstract

The Even–Mansour cipher has been widely used in block ciphers and lightweight symmetric-key ciphers because of its simple structure and strict provable security. Its research has been a hot topic in cryptography. This paper focuses on the problem to minimize the key material of the Even–Mansour cipher while its security bound remains essentially the same. We introduce four structures of the Even–Mansour cipher with a short key and derive their security by Patarin’s H-coefficients technique. These four structures are proven secure up toO˜2k/μ adversarial queries, where k is the bit length of the key material and μ is the maximal multiplicity. Then, we apply them to lightweight authenticated encryption modes and prove their security up to about minb/2,c,k−logμ-bit adversarial queries, where b is the size of the permutation and c is the capacity of the permutation. Finally, we leave it as an open problem to settle the security of the t-round iterated Even–Mansour cipher with short keys.


---

## Body

## 1. Introduction

In recent years, more and more attention has been paid to lightweight cryptography as smart home, Internet of things (IoT), smart transportation, and 5G/B5G networks are proposed. These new technologies brought convenience to our lives but have introduced a powerful security threat, such as the leakage of the private data in our smart phone. Lightweight cryptography is an effective countermeasure against the security threats in order to achieve the privacy and integrity protections of the sensitive data. Lightweight cryptography is mainly used in resource-constrained devices. The block cipher has become a very vital lightweight symmetric-key cryptography, due to its fast speed, easy implementation, and easy standardization on these devices. It is often used to implement sensitive data encryption, digital signature, message authentication, and key encapsulation schemes in the field of information security and network communication security.Thet-round iterated Even–Mansour cipher is simply described as a pure permutation-based block cipher:(1)y=PtPt−1⋯P1x⊕K1⊕K2⋯⊕Kt⊕Kt+1,where K1,K2,…,Kt,Kt+1 is a sequence of n-bit round keys which are usually derived from some master key and P1,P2,…,Pt is a sequence of t public random permutations. This iterated Even–Mansour cipher, also known as key-alternating ciphers, is of great significance in the design of block ciphers and is also favored in the design of lightweight cryptography. The security of the iterated Even–Mansour ciphers is based on the random permutation model (RPM). In RPM, all permutations are modeled as public random permutation oracles, in other words, anyone can query these permutations and obtain the corresponding responses. The related research includes [1–9].This paper focuses on the caset=1. Even and Mansour [10] did pioneering work in 1997 and proved that it is birthday-bound secure. That is where the name “Even–Mansour cipher” comes from. The Even–Mansour cipher has some very nice properties, such as simplest structure and strict provable security. Although the research of the Even–Mansour cipher went unnoticed for years, Gold will always shine. Fortunately, it has been a very hot topic in cryptography. In 2012, Dunkelman et al. [11] pointed out that the Even–Mansour cipher is minimal, i.e., any component (either one of the keys or the permutation) is removed; the Even–Mansour cipher becomes trivially breakable. In 2015, Cogliati et al. [12] introduced the tweakable Even–Mansour (TEM) cipher combined by the Even–Mansour cipher and a tweak, and proved its security. Meanwhile, Mouha and Luykx [13] revisited the Even–Mansour cipher and analyzed the multikey security. do Nascimento and Xexeo [14] applied the Even–Mansour cipher to the Internet of Things (IoT) environments and presented a flexible lightweight authenticated encryption mode in 2017. It follows that Cho et al. [15] presented a new family of white-box block ciphers based on the Even–Mansour cipher WEM which achieves balances between performance and security. Farshim et al. [16] analyzed the security of the Even–Mansour cipher under key-dependent messages. In 2018, we described a generalized tweakable Even–Mansour cipher and applied it to authentication and authenticated encryption modes [17].In the lightweight devices, the storage resources are limited. Therefore, a vital issue is the minimalism and agility of the key material in the design of lightweight ciphers. In this paper, we revisit the Even–Mansour cipher and consider as problem whether we can use the least key material to achieve the same security bound. The Even–Mansour cipher is proven security up to approximately2k/2 adversarial queries, where k is the bit-length of the key material. Can we decrease the key material and achieve the same security bound (this bound must be beyond-birthday-bound)?We answer positively to the question in this paper. We introduce four structures of the Even–Mansour cipher with a short key and present the provable security results. More concretely, we derive their security up toO˜2k/μ adversarial queries using Patarin’s H-coefficients technique, where k is the bit-length of the reducing key material and μ is the maximal multiplicity. The Even–Mansour cipher with a short key has many good advantages, such as calculating on-the-fly, avoiding the key schedule, and minimizing the key material. Therefore, it can be widely applied to resource-constrained lightweight devices. Then, we apply its four structures to lightweight authenticated encryption (AE) modes and prove their security up to about minb/2,c,k−logμ-bit adversarial queries, where b=r+c is the size of the permutation and c (resp. r) is the capacity (resp. rate) of the permutation. Finally, we leave it as an open problem to settle the security of the t-round iterated Even–Mansour cipher with short keys.The rest of this paper is organized as follows. In Section2, we introduce some preliminaries. In Section 3, we prove the security of the Even–Mansour cipher with a short key. Section 4 describes lightweight AE modes based on four structures of the Even–Mansour cipher with a short key. Section 5 ends up with this paper.


## 2. Preliminaries

Let0,1b be the set of binary strings of length b and N=2b. For two strings X and Y, let XY or XY be the concatenation of X and Y. Given a string X, we utilize X to denote the length in bits of X. Given a nonempty set X, let x←X denote an element x drawing from X uniformly at random and #X be the cardinality of X. Let Permb stand for the set of permutations on 0,1b. Let AO=1 be an event that an adversary A outputs 1 after interacting with the oracle O. Here, A never makes a query for which the response is obviously known. Let PrE be the probability that the event E occurs.


### 2.1. Multiplicity

Letxi,yii=1N be a set of N evaluations of a permutation P, where xi=x¯ix^i, yi=y¯iy^i. We introduce the total maximal multiplicity as μ=μfwd+μbwd inspired by [18], where(2)μfwd=maxa#i=1,…,N:x¯i=aorx^i=a,(3)μbwd=maxa#i=1,…,N:y¯i=aory^i=a.


### 2.2. H-Coefficients Technique

H-coefficients technique introduced by Patarin [19] is a very important analytical method in the symmetric-key cryptography. We briefly summarize this technique as follows. Consider an information-theoretic adversary A, whose goal is to distinguish a real world X and an ideal world Y and denote the distinguishing advantage of A as(4)AdvA=PrAX=1−PrAY=1.Without loss of generality, we can assume thatA is a deterministic adversary. The interaction with any of the two worlds X or Y is summarized in a transcript τ. Denote by DX the probability distribution of transcripts when interacting with X, and similarly, DY the distribution of transcripts when interacting with Y. A transcript τ is attainable if PrDY=τ>0, meaning that it can occur during interaction with Y. Let Γ be the set of attainable transcripts. We denote Γ1 as a set of good transcripts when interacting with X (Y). Let Γ2 be a set of bad transcripts such that the probability to obtain any τ∈Γ2 is small in the ideal world Γ=Γ1∪Γ2.Lemma 1 (H-coefficients lemma [19]).
Fix a deterministic adversaryA. Let Γ=Γ1∪Γ2 be a partition of the set of attainable transcripts. Assume that there exists ϵ1 such that for any τ∈Γ1, one has(5)PrDX=τPrDY=τ≥1−ϵ1,and that there exists ϵ2 such that(6)PrDY∈Γ2≤ϵ2.Then, the advantage of the adversaryA is(7)AdvA≤ϵ1+ϵ2.


## 2.1. Multiplicity

Letxi,yii=1N be a set of N evaluations of a permutation P, where xi=x¯ix^i, yi=y¯iy^i. We introduce the total maximal multiplicity as μ=μfwd+μbwd inspired by [18], where(2)μfwd=maxa#i=1,…,N:x¯i=aorx^i=a,(3)μbwd=maxa#i=1,…,N:y¯i=aory^i=a.


## 2.2. H-Coefficients Technique

H-coefficients technique introduced by Patarin [19] is a very important analytical method in the symmetric-key cryptography. We briefly summarize this technique as follows. Consider an information-theoretic adversary A, whose goal is to distinguish a real world X and an ideal world Y and denote the distinguishing advantage of A as(4)AdvA=PrAX=1−PrAY=1.Without loss of generality, we can assume thatA is a deterministic adversary. The interaction with any of the two worlds X or Y is summarized in a transcript τ. Denote by DX the probability distribution of transcripts when interacting with X, and similarly, DY the distribution of transcripts when interacting with Y. A transcript τ is attainable if PrDY=τ>0, meaning that it can occur during interaction with Y. Let Γ be the set of attainable transcripts. We denote Γ1 as a set of good transcripts when interacting with X (Y). Let Γ2 be a set of bad transcripts such that the probability to obtain any τ∈Γ2 is small in the ideal world Γ=Γ1∪Γ2.Lemma 1 (H-coefficients lemma [19]).
Fix a deterministic adversaryA. Let Γ=Γ1∪Γ2 be a partition of the set of attainable transcripts. Assume that there exists ϵ1 such that for any τ∈Γ1, one has(5)PrDX=τPrDY=τ≥1−ϵ1,and that there exists ϵ2 such that(6)PrDY∈Γ2≤ϵ2.Then, the advantage of the adversaryA is(7)AdvA≤ϵ1+ϵ2.


## 3. The Even–Mansour Cipher with a Short Key

Fix a public permutationP:0,1b⟶0,1b and integers r,c,andk, such that b=r+c and k≤minr,c. Let K=0,1k. The Even–Mansour cipher with a short key, called EM for short, is described in Figure 1. EM takes a uniform random key K∈0,1k and a plaintext x∈0,1b as inputs and outputs the ciphertext y=EMKPx∈0,1b. Let pad1K=0r−kK and pad2K=0c−kK. The four structures of EM are, respectively, shown as follows:(8)a:y=EMKPx=Px⊕pad1K0c⊕pad1K0c,b:y=EMKPx=Px⊕pad1K0c⊕0rpad2K,c:y=EMKPx=Px⊕0rpad2K⊕0rpad2K,d:y=EMKPx=Px⊕0rpad2K⊕pad1K0c.Figure 1
Four structures of EM.
(a)
(b)
(c)
(d)We consider the security of the Even–Mansour cipher with a short key and obtain the following theorem.Theorem 1.
ForEMKP with K∈0,1k and P←Permb, we have(9)AdvEMqe,qp≤μqp2k.The proof of Theorem1 utilizes the H-coefficients technique. We consider an adversary A which can interact with X=EMKP,P in the real world or Y=Q,P in the ideal world, where PandQ are uniform random and independent permutations and K is a (dummy) key. We assume that the adversary A makes at most qe construction queries and at most qp primitive queries. The transcripts can be expressed as this form τ=Qe,Qp,K, where Qe=xi,yii=1qe and Qp=uj,vjj=1qp. We start by defining bad transcripts.Definition 1.
We define an attainable transcriptτ=Qe,Qp,K∈Γ as bad if one of the two following conditions is fulfilled.Bad1 : ∃x,y∈Qe and u,v∈Qp, such that(10)a&b:x⊕u=pad1K0c,c&d:x⊕u=0rpad2K,Bad2 : ∃x,y∈Qe and u,v∈Qp, such that(11)a&d:y⊕v=pad1K0c,b&c:y⊕v=0rpad2K.
Otherwise we say thatτ is good. We denote Γgood, resp. Γbad the set of good, resp. bad transcripts, and Γ=Γgood⊔Γbad.
In the real worldX, a bad transcript implies that two invocations to P exist with the same input: one directly from querying the primitive oracle P and another one indirectly from querying the construction oracle EMKP, while all tuples in Qe,Qp uniquely determine an input-output pair of P for a good transcript. In the ideal world Y, the abovementioned result is clearly established for a bad transcript, while it is not for a good transcript.
We first upper bound the probability of bad transcripts in the ideal worldY by the following lemma.Lemma 2.
(12)
Pr
D
Y
∈
Γ
bad
≤
μ
q
p
2
k
.Proof.
In the ideal worldY, Qe,Qp is an attainable transcript with a dummy uniform random key K∈0,1k.
Here, we assume that an adversaryA makes at most qe construction queries and at most qp primitive queries. For each x,y∈Qe and each u,v∈Qp, we obtain at most μfwd (resp. μbwd) tuples x,y such that x¯=u¯ for structures (a) and (b) or x^=u^ for structures (c) and (d) (resp. y¯=v¯ for structures (a) and (d) or y^=v^ for structures (b) and (c)) from the property of multiplicity.
It follows thatPrBad1≤μfwdqp/2k and PrBad2≤μbwdqp/2k. Hence, the probability of bad transcripts in the ideal world Y is at most μqp/2k, where μ=μfwd+μbwd.
We then analyze good transcripts and lower bound the ratioPrDX=τ/PrDY=τ.Lemma 3.
For any good transcriptτ, one has(13)PrDX=τPrDY=τ≥1.Proof.
Consider a good transcriptτ∈Γgood. Let ΩX be a nonempty set of all possible oracles in the real world X and ΩY be a nonempty set of all possible oracles in the ideal world Y. Therefore, the cardinalities of sets ΩX and ΩY are, respectively, #ΩX=2b!⋅2k and #ΩY=2b!2⋅2k. Let compXτ⊆ΩX and compYτ⊆ΩY be the two sets of oracles compatible with transcript τ. The probabilities appearing in Lemma 1 can be evaluated as follows:(14)PrDX=τ=#compXτ#ΩX,(15)PrDY=τ=#compYτ#ΩY.
First, we calculate#compXτ. As τ∈Γgood consists of qe+qp query tuples and any query tuple in τ fixes exactly one input-output pair of the underlying permutation oracle, the number of possible oracles in the real world X equals 2b−qe−qp!.
Second, we calculate#compYτ. The number of possible oracles in the ideal world Y equals 2b−qp!2b−qe!, as P and Q are uniform random and independent permutations.
It follows that(16)PrDX=τ=#compXτ#ΩX=2b−qe−qp!2b!⋅2k=2b−qe−qp!2b!2b!2⋅2k≥2b−qp!2b−qe!2b!2⋅2k=PrDY=τ.
Therefore, we havePrDX=τ/PrDY=τ≥1.
Combining Lemmas1–3, we can obtain the result of Theorem 1.


## 4. Application to Lightweight Authenticated Encryption

With the rises of the smart home, IoT, and 5G/B5G networks, lightweight authenticated encryption (AE) modes are attracting more and more attentions [20–22]. A lightweight AE mode is a lightweight symmetric-key cipher which supports the services of privacy and authenticity of the sensitive data in the devices.The Even–Mansour cipher with a short key can be directly applied to a lightweight AE mode, which is shown in Figure2. It consists of an encryption algorithm E and a decryption algorithm D. The encryption algorithm E takes a plaintext M and a key K as inputs and returns a ciphertext C and an authentication tag T, i.e., CT=EMKPM0c=EK,M. The decryption algorithm D takes a key K, a ciphertext C, and an authentication tag T as inputs and returns a plaintext M or a reject symbol ⊥, i.e., M/⊥=DK,C,T. If the last c-bit of the EM decryption is 0, then the decryption algorithm D returns M. Otherwise, the decryption algorithm D returns ⊥.Figure 2
Lightweight authenticated encryption modes.
(a)
(b)
(c)
(d)LetΠ=E,D stand for our lightweight AE modes. We introduce the AE-security model as follows.Definition 2.
(AE security). Let P be a public random permutation. LetΠ=E,D be a P-based AE scheme. Let A be an adversary which interacts with X=E,D,P± in the real world or Y=$,⊥,P± in the ideal world. Let q,p>0. Then, the AE-security of Π=E,D is defined as follows:(17)AdvΠaeA=PrAE,D,P±=1−PrA$,⊥,P±=1,AdvΠaeq,p=maxAAdvΠaeA,where q is the number of queries to the encryption oracle E or the decryption oracle D, p is the number of queries to the random permutation P or its inverse P−1, $ is a random function which always returns a fresh and random response for each query, and ⊥ is a symbol which stands for the failure of the decryption oracles.Theorem 2.
LetP←Permb and b=r+c. Then,(18)AdvΠaeq,p≤μp2k+q22b+q2c.Proof Sketch. LetA be an adversary with access to the encryption oracle E, the decryption oracle D, and the random permutation P or its inverse P−1. Π can be represented as an EM scheme. We replace the EM modular structure to the random permutation Q. According to Theorem 1, we have(19)AdvΠaeA=PrAE,D,P±=1−PrA$,⊥,P±=1≤PrAE,D,P±=1−PrAQ,Q−1,P±=1+PrAQ,Q−1,P±=1−PrA$,⊥,P±=1=μp2k+PrAQ,Q−1,P±=1−PrA$,⊥,P±=1.It follows that(20)PrAQ,Q−1,P±=1−PrA$,⊥,P±=1≤PrAQ,Q−1,P±=1−PrAQ,⊥,P±=1+PrAQ,⊥,P±=1−PrA$,⊥,P±=1≤q2c+q22b,where q2/2b obtained by the PRP-PRF Switch Lemma [23] and q/2c is from the fact that the successful probability of the adversary is 1/2c for each forgery attempt.Combining equations (19) and (20), it is easy to draw the result of Theorem 2.According to Theorem2, we can find that these lightweight AE modes ensure about minb/2,c,k−logμ-bit AE-security.


## 5. Conclusions

The key material is crucial for the secure implementation of cryptographic schemes. Most of devices widely used in smart home, smart transportation, and Internet of Things (IoT) environments are resource constrained. Therefore, in the design of lightweight ciphers, a vital issue is the minimalism and agility of the key material.In this paper, we revisit the Even–Mansour cipher and discuss this problem whether we can use the least key material to achieve the same (even beyond conventional) security bound in the Even–Mansour cipher. We introduce four structures of the Even–Mansour cipher with a short key and derive security up toO˜2k/μ adversarial queries, where k is the bits of the key material and μ is the maximal multiplicity, using Patarin’s H-coefficients technique. Then, we apply them to lightweight authenticated encryption modes and prove their security up to about minb/2,c,k−logμ-bit adversarial queries, where b=r+c is the size of the permutation and c is the capacity of the permutation. Finally, we leave it as an open problem to settle the security of the t-round iterated Even–Mansour cipher with short keys. The Even–Mansour cipher with a short key is proven k−logμ-bit security. It is natural to consider whether our result can be generalized to the t-round iterated Even–Mansour cipher. But the situation of the t-round iterated Even–Mansour cipher with short keys is more complicated. Therefore, it is regarded as an open problem to attract scholars to discuss and analyze it in detail. The Even–Mansour cipher with a short key has many good advantages, such as calculating on-the-fly, avoiding the key schedule, and minimizing the area of the hardware implementation and the key material. Therefore, it can be widely applied to the data security of smart home, Internet of Things, and some lightweight devices.



---

*Source: 4180139-2020-03-10.xml*