# New Approach towards Generalizing Feistel Networks and Its Provable Security

Authors: Jiajie Liu; Bing Sun; Chao Li
Journal: Security and Communication Networks
 (2021)

---

## Abstract

This paper proposes a new approach to generalizing Feistel networks, which unifies the classical (balanced) Feistel network and the Lai–Massey structure. We call the new structure extended Feistel (E-Feistel) network. To justify its soundness, we investigate its indistinguishability using Patarin’s H-coefficient technique. As a result, it is proved that the 4-round key-alternating E-Feistel (KAEF) cipher with adequately derived keys and identical round functions is secure up to2n/2 queries, i.e., birthday-bound security. In addition, when adjacent round keys are independent and independent round functions are used, the 6-round KAEF is secure up to beyond-birthday-bound 22n/3 queries. Our results indicate that the E-Feistel structure is secure and reliable and can be adopted in designing practical block ciphers.


---

## Body

## 1. Introduction

In recent years, as a result of more attention paid on privacy protection and information security, research on the design and cryptanalysis of block ciphers has become a research hotpot. The design of block ciphers strictly highlights efficiency and security, which deeply rely on iterative structures they choose. According to whether encryption is consistent with decryption, iterative structures can be divided into two categories. The structures that have consistent encryption and decryption are beneficial in hardware implementation because decryption does not take up extra storage. This kind of structures contains the Feistel structure, the SM4 structure, the Mars structure, and the Lai–Massey structure as specific instances. Another kind of structures mainly consists of the substitution-permutation networks (SPN).The Feistel structure was proposed by Feistel and Tuchman of IBM when designing Lucifer in the late 1960s [1]. The Feistel structure became popular after the widespread use of the data encryption standard (DES) [2]. The input of the Feistel structure is divided into two blocks whose length is equal. The round function is applied to one half, using a subkey, and then, the output is XORed with the other half. Then, two halves are exchanged with each other. As a result, the diffusion of the Feistel structure is relatively slow. The Feistel structure has consistent encryption with decryption, which is efficiently beneficial in hardware implementation. Several well-known block ciphers adopt the Feistel structure, for example, SIMON [3] and SIMECK [4]. In addition, there are many extensions of the Feistel structure, such as the SM4 structure [5], the Mars structure [6], and the generalized Feistel structure [7, 8].The Lai–Massey scheme was proposed by Lai and Massey in the International Data Encryption Algorithm (IDEA) [9]. Similar to the Feistel structure, the Lai–Massey scheme takes two equal-sized plaintexts as its input. Unlike the Feistel structure, the round function is applied to the sum of the two pieces, and the result is then added to both half blocks. Furthermore, an orthomorphism is always introduced to one of the halves, to compensate the existence of a differential covering any rounds with probability 1. Generally, the Lai–Massey structure also has consistent encryption and decryption. There are several instances, such as MESH [10] and FOX [11], that utilize this structure.Different from the Feistel structure and the Lai–Massey scheme, one round function of the SPN structure is composed of an invertible nonlinear function S layer controlled by a subkey and an invertible linear transformation P layer. Compared to the Feistel structure, the diffusion of the SPN structure might be faster. However, the decryption of an SPN structure is usually different from that of the encryption; thus, more resources might be required for the implementation. In recent years, there have been many ciphers using the SPN structure such as AES [12] and PHOTON [13]. Additionally, the SPN structure is often adopted as round functions in the design of Feistel ciphers such as SM4 [5] and Camellia [14].Traditionally, the security of block ciphers is defined as the indistinguishability from random permutations when the keys are random and secret. This is known as pseudorandomness. However, in some block cipher-based schemes such as hash functions, the underlying block ciphers may not have secret keys. The security arguments for these schemes thereby cannot be based on the pseudorandomness of the underlying ciphers. To remedy this, theory community usually assumes their underlying ciphers as ideal ciphers, i.e., sets of independent random permutations indexed by the keys, and then argues the security of the whole schemes. By this, we expect practical block ciphers to be as secure as ideal ciphers, and a proof for such security is the final goal of the theory community. However, given the state of the art, the only choice is to replace some of the underlying components of the block ciphers by idealized oracles and then argue the closeness of the obtained idealized block ciphers and the ideal ciphers. The security proved in this way cannot be used as a guarantee for the actual security of practical block ciphers, but it is still helpful to deepen the understanding of that and promote theoretical research to the ultimate goal.Luby and Rackoff [15] proposed Luby–Rackoff (LR) scheme in 1985. They also proved that the balanced Feistel structure covering 3 rounds is a pseudorandom permutation and that covering 4 rounds is a super-pseudorandom permutation. Later, the LR scheme has attracted a lot of attention and become the most popular model for Feistel ciphers in which the round functions are set as random functions. Following [15], a long series of work established better security (maybe using a larger number of rounds) [16–18]. Significantly, Gentry and Ramzan [19] proved that the Feistel cipher covering 4 rounds without keys is secure against 2n/2 queries. On the basis, Guo and Wang [20] showed that 4-round key-alternating Feistel (KAF) using the same round function is secure against 2n/2 queries, i.e., birthday-bound security. Guo also proved that the 6-round key-alternating Feistel (KAF) using the independent round functions and appropriate keys is secure up to 22n/3 queries, i.e., beyond-birthday-bound security.Iterative structures in block ciphers mainly adopt the three structures: the Feistel structure, the SPN structure, and the Lai–Massey scheme. The solidification of iterative structure may bring security risks; once backdoors of some iterative structures are founded, a series of block ciphers that adopt the structure would be effectively attacked and will not be secure any more. This promotes the diversity research of iterative structures. In this paper, we extend the original Feistel structure and propose an extended Feistel (E-Feistel) structure. This paper mainly focuses on studying the security of the E-Feistel structure from the perspective of theoretical security of the structure using H-coefficient technique. The main contributions are as follows:(1)
We propose a new iterative structure, the E-Feistel structure, which also has consistent encryption with decryption(2)
For birthday-bound security, we prove that the 4-round KAEF with the same round function is secure up to2n/2 queries(3)
For beyond-birthday-bound security, we prove that the 6-round KAEF with independent round functions is secure up to22n/3 queriesThis paper is organized as follows. We introduce the notations in Section2. Section 3 presents the extended Feistel structure. Then, Sections 4 and 5, respectively, present our results on 4-round KAESF and 6-round KAEF and their security proofs. Section 6 concludes this paper.


## 2. Notations

LetF2 denote the binary field and F2n denote the n−dimensional vector space over F2. Throughout this paper, x1,x2,…,xn always corresponds to a column vector. Let c=c1,c2,…,cn∈F2n,d=d1,d2,…,dn∈F2n. Then, the point product of two vectors c and d is calculated as(1)c⋅d=c1d1⊕c2d2⊕⋯⊕cndn,denoted as cTd.


### 2.1. The H-Coefficient Technique

We use Patarin’s H-coefficient technique [21, 22] to prove the birthday-bound security of 4-round KAEF and the beyond-birthday-bound security of 6-round KAEF. Therefore, we sum up the interaction between distinguisher D and its oracles in the queries of transcripts. Suppose D enquiring the ith oracle (KAEFkiF or Pi) for q times; a record QEi=L1R1,S1T1,…,LqiRqi,SqiTqi can be obtained, where LjRj,SjTj represents the queries and answers of KAEF. Similarly, the queries made to fi are recorded as Qfi=xi,1,yi,1,…,xi,p,yi,p, denoting the answer yi,j obtained by querying fi with xi,j. Let QE=QE1,…,QEm and QF=Qf1,…,Qft. The transcript of the distinguisher D is denoted as τ=QE,QF.Given a setQfi of function queries and a function fi, we say that fi extends Qfi, denoted fi⊢Qfi if fix=y, for all x,y∈Qfi. Similarly, given a transcript of permutation queries QEi and a permutation Pi, we say Pi extends QEi, denoted Pi⊢QEi, if PiLR=ST, for all LR,ST∈QEi. The latter definition also extends to the t-round KAEF built on F and a key ki; in that case, we write KAEFkiF⊢QEi. Finally, for QF=Qf1,…,Qft and F=f1,…,ft, if f1⊢Qf1∧⋯∧ft⊢Qft, then F⊢QF.With regard to all achievable transcriptsτ which represent an achievable record for queries of a series of oracles F,P1,…,Pm or F,KAEFk1F,…,KAEFkmF, the probability that D interacts with the real world and the ideal world is denoted as Prreτ and Pridτ, respectively. Prreτ and Pridτ are defined formally as follows:(2)Prreτ=Prk1,…,km←$Km,F←$ℱnt:KAEFk1F⊢QE1∧⋯∧KAEFkmF⊢QEm∧F⊢QF,Pridτ=PrP1,…,Pm←$P2nm,F←$ℱnt:P1⊢QE1∧⋯∧Pm⊢QEm∧F⊢QF.We can estimate the distinguishing advantage by calculatingPrreτ and Pridτ. The lemma is stated as follows:Lemma 1 (see [23]).
Assume that there exists a functionεqf,qe>0 such that, for every achievable transcript τ with qe and qf queries of two types, the following equation holds:(3)Pridτ−Prreτ≤Pridτ⋅εqf,qe.
Then, the following equation holds:(4)AdvKAEFqf,qe≤εqf,qe.Lemma 2 (see [23]).
Fix a transcript withPridτ>0. Assume that (i) Prk∈Kbad≤δ and (ii) there is a function g:K⟶0,∞ such that, for all k∈Kgood, the following equation holds Prreτ,k/Pridτ,k≥1−gk. Then, we have(5)Pridτ−Prreτ≤Pridτ⋅δ+Ek∈Kgk.


## 2.1. The H-Coefficient Technique

We use Patarin’s H-coefficient technique [21, 22] to prove the birthday-bound security of 4-round KAEF and the beyond-birthday-bound security of 6-round KAEF. Therefore, we sum up the interaction between distinguisher D and its oracles in the queries of transcripts. Suppose D enquiring the ith oracle (KAEFkiF or Pi) for q times; a record QEi=L1R1,S1T1,…,LqiRqi,SqiTqi can be obtained, where LjRj,SjTj represents the queries and answers of KAEF. Similarly, the queries made to fi are recorded as Qfi=xi,1,yi,1,…,xi,p,yi,p, denoting the answer yi,j obtained by querying fi with xi,j. Let QE=QE1,…,QEm and QF=Qf1,…,Qft. The transcript of the distinguisher D is denoted as τ=QE,QF.Given a setQfi of function queries and a function fi, we say that fi extends Qfi, denoted fi⊢Qfi if fix=y, for all x,y∈Qfi. Similarly, given a transcript of permutation queries QEi and a permutation Pi, we say Pi extends QEi, denoted Pi⊢QEi, if PiLR=ST, for all LR,ST∈QEi. The latter definition also extends to the t-round KAEF built on F and a key ki; in that case, we write KAEFkiF⊢QEi. Finally, for QF=Qf1,…,Qft and F=f1,…,ft, if f1⊢Qf1∧⋯∧ft⊢Qft, then F⊢QF.With regard to all achievable transcriptsτ which represent an achievable record for queries of a series of oracles F,P1,…,Pm or F,KAEFk1F,…,KAEFkmF, the probability that D interacts with the real world and the ideal world is denoted as Prreτ and Pridτ, respectively. Prreτ and Pridτ are defined formally as follows:(2)Prreτ=Prk1,…,km←$Km,F←$ℱnt:KAEFk1F⊢QE1∧⋯∧KAEFkmF⊢QEm∧F⊢QF,Pridτ=PrP1,…,Pm←$P2nm,F←$ℱnt:P1⊢QE1∧⋯∧Pm⊢QEm∧F⊢QF.We can estimate the distinguishing advantage by calculatingPrreτ and Pridτ. The lemma is stated as follows:Lemma 1 (see [23]).
Assume that there exists a functionεqf,qe>0 such that, for every achievable transcript τ with qe and qf queries of two types, the following equation holds:(3)Pridτ−Prreτ≤Pridτ⋅εqf,qe.
Then, the following equation holds:(4)AdvKAEFqf,qe≤εqf,qe.Lemma 2 (see [23]).
Fix a transcript withPridτ>0. Assume that (i) Prk∈Kbad≤δ and (ii) there is a function g:K⟶0,∞ such that, for all k∈Kgood, the following equation holds Prreτ,k/Pridτ,k≥1−gk. Then, we have(5)Pridτ−Prreτ≤Pridτ⋅δ+Ek∈Kgk.


## 3. The Extended Feistel Structure

The extended Feistel structure (E-Feistel structure) denoted asℱA,B is defined in the following.The round function and the branch have the same length, denoted asn. Let A=A1,A2 and B=B1,B2, where Ai,Bj∈F2n×n and A1B1⊕A2B2=0. Let f be a map over F2n. The input and output of ℱA,B,f are denoted as x=x1,x2∈F2n×2 and y=y1,y2∈F2n×2, respectively. Then, the map ℱA,B,f:F2n×2⟶F2n×2 is defined as(6)y1,y2=x2,x1⊕B2fg,B1fg,where g=A1x1⊕A2x2, as illustrated in Figure 1.Figure 1
The extended feistel structure.Denote byℳn all the maps from F2n to F2n. Then, the structure ℱA,B is defined as ℱA,B=ℱA,B,f|f∈ℳn. ℱA,B has similar procedures of decryption and encryption.LetA∗=A1T,A2T and B∗=B1T,B2T. We further associate AandB and branch swapping with the following two matrices:(7)A=A1A2A2A1,ℬ=B1TB2TB2TB1T.


## 4. Four Rounds for Birthday-Bound Security

As seen in Figure2, we assume that the 4-round idealized KAEF cipher uses the same random round function f and 4 independent random round keys k=k1,k2,k3,k4.Figure 2
The 4-round KAEF with the same round function.Firstly, we give the definition of round-key vectors in the 4-round key-alternating extended Feistel using the same round function (KAEFSF). The constraint on round keys does not need the round key to satisfy the condition of complete independence and randomness.Definition 1 (suitable round-key vector for 4 rounds).
A round-key vectork=k1,k2,k3,k4 is suitable if it satisfies the following conditions:(i)
k1 and k4 are uniform in 0,1n (but they need not to be independent)(ii)
k1⊕k4 is also uniformly distributed in 0,1nProposition 1.
ForℱA,B, assume rankA=rankℬ=2n, and A1B2⊕A2B1 is a nonsingular matrix.Proof.
SincerankA=rankℬ=2n, A and ℬ are both nonsingular matrices. So,(8)A·ℬT=0A1B2⊕A2B1A2B1⊕A1B20is a nonsingular matrix. As a result, A1B2⊕A2B1 is a nonsingular matrix. For convenience, A1B2⊕A2B1 is denoted as O.Theorem 1.
AssumingrankA=rankℬ=2n, for the 4-round idealized KAEFSF, the following equation holds:(9)AdvKAEFSFqf,qe≤9qe2+4qeqfN.Proof.
According to Lemma2, we can translate the proof of equation (9) into the proof of the following equation:(10)Pridτ−Prreτ≤Pridτ⋅9qe2+4qeqfN.
For a fixed transcriptτ=QE,QF with QE=qe and QF=qf, key vectors can be distinguished whether good or bad concerning τ. Then, the probability Prreτ,k for good key k can be estimated. For convenience’s sake, for any x∈0,1n, x∈Domℱ (x∉Domℱ otherwise) denotes whether there exists a corresponding record x,y in QF or not.
Bad keys are now defined as follows.Definition 2 (bad round-key vector for 4 rounds).
In regard ofτ=QE,QF, a suitable round-key vector k is bad, as long as either of the two following conditions is satisfied:(B-1): there existsLR,ST∈QE that satisfies either A1L⊕A2R⊕k1∈Domℱ or A1T⊕A2S⊕k4∈Domℱ(B-2): there exist two (not necessarily different)LR,ST and L′R′,S′T′ in QE that satisfies A1L⊕A2R⊕k1=A1T′⊕A2S′⊕k4
The other transcripts are defined as good round-key vectors, denoted byKgood.
For each of theqe records LR,ST, since both k1 and k4 are uniformly distributed in 0,1n and since Domℱ=QF=qf, the probability that it satisfies (B-1) does not exceed 2qf/N. On the contrary, for each of the qe2 pairs of records LR,ST and L′R′,S′T′, since k1⊕k4 is uniform, the probability that the pair satisfies (B-2) does not exceed 1/N. Therefore,(11)Prk←$K:k∈Kbad≤2qeqf+qe2N.


### 4.1. Lowering Bounding the Probability for Good Keys

We now lower bound the probabilityPrreτ,k for an arbitrary good round-key vector k. For this, we follow a clean “predicate” approach from [24]. We define a “bad” predicate BadF on F. When conditions of BadF are not fulfilled, the event KAEFSFkF⊢QE occurs if and only if 2qe new and distinct equations on the random round function F are satisfied. For convenience’s sake, we first define(12)Extℱ=defx∈0,1n:LR,ST∈QEforA1L⊕A2R=k1⊕xand someS,T,orLR,ST∈QEforA1T⊕A2S=k4⊕xand someL,R.Clearly,Extℱ≤2qe. Then, for any n− to −n bit function f⊢QF, the predicate BadF holds if one of the following conditions is fulfilled:(C-1):∃LR,ST∈QE such that k2⊕A1R⊕A2L⊕OFA1L⊕A2R⊕k1∈Domℱ∪Extℱ or k3⊕A1S⊕A2T⊕OFA1T⊕A2S⊕k4∈Domℱ∪Extℱ(C-2): there exist two (not necessarily different)LR,ST and L′R′,S′T′ in QE such that k2⊕A1R⊕A2L⊕OFA1L⊕A2R⊕k1=k3⊕A1S′⊕A2T′⊕OFA1T′⊕A2S′⊕k4(C-3): there exist two differentLR,ST∈QE and L′R′,S′T′∈QE such that A1R⊕A2L⊕OFA1L⊕A2R⊕k1=A1R′⊕A2L′⊕OFA1L′⊕A2R′⊕k1 or A1S⊕A2T⊕OFA1T⊕A2S⊕k4=A1S′⊕A2T′⊕OFA1T′⊕A2S′⊕k4To computePrF←$ℱn:BadF|F⊢QF, we consider the conditions in turn. First, as k is good, for any LR,ST∈QE, we have k1⊕A1L⊕A2R∉Domℱ and k4⊕A1T⊕A2S∉Domℱ. Thus, based on f⊢QF, the values Fk1⊕A1L⊕A2R and Fk4⊕A1T⊕A2S remain uniformly distributed, and thus,(13)−Prk2⊕A1R⊕A2L⊕OFA1L⊕A2R⊕k1∈Domℱ∪Extℱ≤qf+2qeN,−Prk3⊕A1S⊕A2T⊕OFA1T⊕A2S⊕k4∈Domℱ∪Extℱ≤qf+2qeN.So,PrC−1≤2qeqf+2qe/N. Second, for any two tuples LR,ST and L′R′,S′T′ from QE, the two function values FA1L⊕A2R⊕k1 and FA1T′⊕A2S′⊕k4 are independent by ¬B−2. Then, as argued, we have(14)−Prk2⊕A1R⊕A2L⊕OFA1L⊕A2R⊕k1=k3⊕A1S′⊕A2T′⊕OFA1T′⊕A2S′⊕k4=1N,and thus, PrC−2≤qe2/N.Third, for any tuplesLR,ST and L′R′,S′T′, if A1L⊕A2R=A1L′⊕A2R′, then A1R⊕A2L⊕OFA1L⊕A2R⊕k1=A1R′⊕A2L′⊕OFA1L′⊕A2R′⊕k1 is not possible. Otherwise, since FA1L⊕A2R⊕k1 is uniform (as argued before), the probability to have A1R⊕A2L⊕OFA1L⊕A2R⊕k1=A1R′⊕A2L′⊕OFA1L′⊕A2R′⊕k1 is 1/N. It is similar for the other condition A1S⊕A2T⊕OFA1T⊕A2S⊕k4=A1S′⊕A2T′⊕OFA1T′⊕A2S′⊕k4; thus, PrC−3≤qe2/N and(15)PrF←$ℱn:BadF|F⊢QF≤2qeqf+2qeN+qe2N+2qe2N≤7qe2+2qeqfN.Using an arbitrary order, writeQE=L1R1,S1T1,…,LqeRqe,SqeTqe, and for a given F, let(16)x21=k2⊕A1R1⊕A2L1⊕OFA1L1⊕A2R1⊕k1⋮x2qe=k2⊕A1Rqe⊕A2Lqe⊕OFA1Lqe⊕A2Rqe⊕k1x31=k3⊕A1S1⊕A2T1⊕OFA1T1⊕A2S1⊕k4⋮x3qe=k3⊕A1Sqe⊕A2Tqe⊕OFA1Tqe⊕A2Sqe⊕k4.For eachLiRi,SiTi∈QE, we assume that the outputs of F in the 2 and 3 rounds are denoted as Xi and Yi, respectively:(17)PrFAEFSFkFLiRi=SiTi=PrFx2i=Xi∧Fx3i=Yi.Additionally, conditioned onF⊢QF and ¬BadF, (a) the induced values x21,…,x2qe,x31,…,x3qe are 2qe distinct ones (otherwise if x2i=x2j or x3i=x3j, for some i≠j, then (C-3) is fulfilled; if x2i=x3j, then (C-2) is fulfilled) and (b) the 2qe images Fx21,…,Fx2qe,Fx31,…,Fx3qe remain fully undetermined and thus uniform, otherwise (C-1) is fulfilled. Therefore, for each i∈1,…,qe, we have(18)PrFx2i=Xi∧Fx3i=Yi=1N2,and for any k∈Kgood,(19)Prreτ,kPridτ,k=1/K⋅Nqf⋅PrKAEFSFkF⊢QF|F⊢QF1/⋅KNqf⋅∏i=0qe−11/N2−i≥PrKAEFSFkF⊢QF|F⊢QF∧¬BadF⋅1−PrBadF|F⊢QF∏i=0qe−11/N2−i≥1−7qe2+2qeqf/N1/N2qe∏i=0qe−11/N2−i≥1−7qe2+2qeqfN1−qe2N2≥1−7qe2+2qeqfN−qe2N2.Gathering this and equation (11) and Lemma 2 yields the claim of equation (10).


## 4.1. Lowering Bounding the Probability for Good Keys

We now lower bound the probabilityPrreτ,k for an arbitrary good round-key vector k. For this, we follow a clean “predicate” approach from [24]. We define a “bad” predicate BadF on F. When conditions of BadF are not fulfilled, the event KAEFSFkF⊢QE occurs if and only if 2qe new and distinct equations on the random round function F are satisfied. For convenience’s sake, we first define(12)Extℱ=defx∈0,1n:LR,ST∈QEforA1L⊕A2R=k1⊕xand someS,T,orLR,ST∈QEforA1T⊕A2S=k4⊕xand someL,R.Clearly,Extℱ≤2qe. Then, for any n− to −n bit function f⊢QF, the predicate BadF holds if one of the following conditions is fulfilled:(C-1):∃LR,ST∈QE such that k2⊕A1R⊕A2L⊕OFA1L⊕A2R⊕k1∈Domℱ∪Extℱ or k3⊕A1S⊕A2T⊕OFA1T⊕A2S⊕k4∈Domℱ∪Extℱ(C-2): there exist two (not necessarily different)LR,ST and L′R′,S′T′ in QE such that k2⊕A1R⊕A2L⊕OFA1L⊕A2R⊕k1=k3⊕A1S′⊕A2T′⊕OFA1T′⊕A2S′⊕k4(C-3): there exist two differentLR,ST∈QE and L′R′,S′T′∈QE such that A1R⊕A2L⊕OFA1L⊕A2R⊕k1=A1R′⊕A2L′⊕OFA1L′⊕A2R′⊕k1 or A1S⊕A2T⊕OFA1T⊕A2S⊕k4=A1S′⊕A2T′⊕OFA1T′⊕A2S′⊕k4To computePrF←$ℱn:BadF|F⊢QF, we consider the conditions in turn. First, as k is good, for any LR,ST∈QE, we have k1⊕A1L⊕A2R∉Domℱ and k4⊕A1T⊕A2S∉Domℱ. Thus, based on f⊢QF, the values Fk1⊕A1L⊕A2R and Fk4⊕A1T⊕A2S remain uniformly distributed, and thus,(13)−Prk2⊕A1R⊕A2L⊕OFA1L⊕A2R⊕k1∈Domℱ∪Extℱ≤qf+2qeN,−Prk3⊕A1S⊕A2T⊕OFA1T⊕A2S⊕k4∈Domℱ∪Extℱ≤qf+2qeN.So,PrC−1≤2qeqf+2qe/N. Second, for any two tuples LR,ST and L′R′,S′T′ from QE, the two function values FA1L⊕A2R⊕k1 and FA1T′⊕A2S′⊕k4 are independent by ¬B−2. Then, as argued, we have(14)−Prk2⊕A1R⊕A2L⊕OFA1L⊕A2R⊕k1=k3⊕A1S′⊕A2T′⊕OFA1T′⊕A2S′⊕k4=1N,and thus, PrC−2≤qe2/N.Third, for any tuplesLR,ST and L′R′,S′T′, if A1L⊕A2R=A1L′⊕A2R′, then A1R⊕A2L⊕OFA1L⊕A2R⊕k1=A1R′⊕A2L′⊕OFA1L′⊕A2R′⊕k1 is not possible. Otherwise, since FA1L⊕A2R⊕k1 is uniform (as argued before), the probability to have A1R⊕A2L⊕OFA1L⊕A2R⊕k1=A1R′⊕A2L′⊕OFA1L′⊕A2R′⊕k1 is 1/N. It is similar for the other condition A1S⊕A2T⊕OFA1T⊕A2S⊕k4=A1S′⊕A2T′⊕OFA1T′⊕A2S′⊕k4; thus, PrC−3≤qe2/N and(15)PrF←$ℱn:BadF|F⊢QF≤2qeqf+2qeN+qe2N+2qe2N≤7qe2+2qeqfN.Using an arbitrary order, writeQE=L1R1,S1T1,…,LqeRqe,SqeTqe, and for a given F, let(16)x21=k2⊕A1R1⊕A2L1⊕OFA1L1⊕A2R1⊕k1⋮x2qe=k2⊕A1Rqe⊕A2Lqe⊕OFA1Lqe⊕A2Rqe⊕k1x31=k3⊕A1S1⊕A2T1⊕OFA1T1⊕A2S1⊕k4⋮x3qe=k3⊕A1Sqe⊕A2Tqe⊕OFA1Tqe⊕A2Sqe⊕k4.For eachLiRi,SiTi∈QE, we assume that the outputs of F in the 2 and 3 rounds are denoted as Xi and Yi, respectively:(17)PrFAEFSFkFLiRi=SiTi=PrFx2i=Xi∧Fx3i=Yi.Additionally, conditioned onF⊢QF and ¬BadF, (a) the induced values x21,…,x2qe,x31,…,x3qe are 2qe distinct ones (otherwise if x2i=x2j or x3i=x3j, for some i≠j, then (C-3) is fulfilled; if x2i=x3j, then (C-2) is fulfilled) and (b) the 2qe images Fx21,…,Fx2qe,Fx31,…,Fx3qe remain fully undetermined and thus uniform, otherwise (C-1) is fulfilled. Therefore, for each i∈1,…,qe, we have(18)PrFx2i=Xi∧Fx3i=Yi=1N2,and for any k∈Kgood,(19)Prreτ,kPridτ,k=1/K⋅Nqf⋅PrKAEFSFkF⊢QF|F⊢QF1/⋅KNqf⋅∏i=0qe−11/N2−i≥PrKAEFSFkF⊢QF|F⊢QF∧¬BadF⋅1−PrBadF|F⊢QF∏i=0qe−11/N2−i≥1−7qe2+2qeqf/N1/N2qe∏i=0qe−11/N2−i≥1−7qe2+2qeqfN1−qe2N2≥1−7qe2+2qeqfN−qe2N2.Gathering this and equation (11) and Lemma 2 yields the claim of equation (10).


## 5. Six Rounds for Beyond-Birthday-Bound Security

As seen in Figure3, we assume that the 6-round idealized KAEF cipher uses the 6 independent random round functions F=F1,F2,F3,F4,F5,F6 and 6 random round keys k=k1,k2,k3,k4,k5,k6.Figure 3
The 6-round KAEF with independent round functions.Similarly, we first define suitable round-key vectors.Definition 3 (suitable round-key vector for 6 rounds).
A round-key vectork=k1,k2,k3,k4,k5,k6 is suitable if it satisfies the following conditions:(i)
k1, k3, and k5 are uniformly distributed in 0,1n(ii)
k2, k4, and k6 are uniformly distributed in 2n−r possibilities(iii)
Fori,j∈1,2,2,3,4,5,5,6,1,6, ki and kj are independent
Different from the proof of birthday-bound security, the upper bound of probability of various collisions should be small enough. As a result, all of key vectors need to be uniform. It is the same for the independence of key vectors. Beyond-birthday-bound security of KAEF can be proved under the instantiation with suitable round-key vectors.Theorem 2.
For the 6-round idealized cipher KAEF with the suitable round-key vector, the following equation holds:(20)AdvKAEFqf,qe≤7qe3+13qeqf2+22qe2qfN2+2r8qeqf2+2qe2qfN2.It is worth noting that whenr<n/2, the security is beyond-birthday security. For example, when r=0, the bound is of “typical” beyond-birthday form Oq3/N2.Similarly, we can translate the proof into the proof of the result; for any transcriptτ, the following equation holds:(21)Pridτ−Prreτ≤Pridτ⋅7qe3+13qeqf2+22qe2qf+2r8qeqf2+2qe2qfN2.For a fixed a transcriptτ=QE,QF with QF=QF1,QF2,QF3,QF4,QF5,QF6, QE=qe, and QFi=qfi, for i=1,…,6, we follow similar procedures in Section 4 to complete the proof.


### 5.1. Bad Round-Key Vectors and Probability

For convenience,xi∈Domℱi (and xi∉Domℱi otherwise) denotes, for any xi∈0,1n, whether there exists a corresponding record xi,yi in QFi or not. Additionally, Imgℱixi denotes the corresponding yi. The bad round-key vector is defined as follows.Definition 4 (bad round-key vector for 6 rounds).
With respect toτ=QE,QF, a suitable key vector k is bad if it satisfies one of the following conditions:(B-1): there existLR,ST∈QE, x1,y1∈QF1, and x6,y6∈QF6 such that k1=A1L⊕A2R⊕x1 and k6=A1T⊕A2S⊕x6(B-2): there existLR,ST∈QE, x1,y1∈QF1, and x2,y2∈QF2 such that k1=A1L⊕A2R⊕x1 and k2=A1R⊕A2L⊕Oy1⊕x2(B-3): there existLR,ST∈QE, x5,y5∈QF5, and x6,y6∈QF6 such that k6=A1T⊕A2S⊕x6 and k5=A1S⊕A2T⊕Oy6⊕x5
These bad key vectors are denoted asKbad. The other key vectors are defined as good key vectors, denoted by Kgood.
Because there are at mostqeqf2 choices for LR,ST∈QE, x1,y1∈QF1, and x6,y6∈QF6 and since k1, resp. k6, is uniform in 2n, resp. 2n−r possibilities, and furthermore, since k1 and k6 are independent, the following equation holds PrB−1≤qeqf2/22n−r≤2rqeqf2/N2.
Similarly, we havePrB−2≤2rqeqf2/N2. By symmetry, PrB−3≤2rqeqf2/N2. As a result,(22)Prk←$K:k∈Kbad≤3⋅2r⋅qeqf2N2.


### 5.2. Analysis for Good Keys

For a fixed good round-key vectork, we would get a lower bound for the probability PrF←$ℱn6:KAEFkF⊢QE|F⊢QF. Inspired by Cogliati et al. [25, 26], it takes two steps. Firstly, through defining certain “bad” functions on F1,F6, we would lower bound the probability under the condition. Secondly, under the assumption of “good” functions F1,F6, the outer two rounds are removed; we only need to analyze the induced 4-round transcript to yield the final bounds.For a fixed pair ofF1,F6 such that F1⊢QF1 and F6⊢QF6 and for each LR,ST∈QE, we set X←A1R⊕A2L⊕OF1A1L⊕A2R⊕k1 and U←A1S⊕A2T⊕OF6A1T⊕A2S⊕k6. Then, qe tuples LRX,UST are obtained. The induced tuples are denoted by QE∗F1,F6. For convenience, εQx is used to denote all tuples LRX,UST whose third coordinate equals X. Similarly, we define εQU:(23)−εQX=LRX,UST:LRX,UST∈QE∗F1,F6,−εQU=LRX,UST:LRX,UST∈QE∗F1,F6.Additionally, we define several key-independent quantities characterizingτ:(24)α1k=defLR,ST,x1,y1∈QE×QF1:k1=A1L⊕A2R⊕x1,α2k=defLR,ST,x6,y6∈QE×QF6:k6=A1T⊕A2S⊕x6,α2,3k=defLR,ST,x2,y2,x3,y3∈QE×QF2×QF3:k3=A1L⊕A2R⊕Oy2⊕x3,α4,5k=defLR,ST,x4,y4,x5,y5∈QE×QF4×QF5:k4=A1T⊕A2S⊕Oy5⊕x4.The predicateBadF1,F6 holds if the induced set QE∗F1,F6 satisfies one of the following conditions:(C-1): there exist three recordsLRX,UST∈QE∗F1,F6, x2,y2∈QF2, and x5,y5∈QF5 such that k2=X⊕x2 and k5=U⊕x5(C-2): there exist three recordsLRX,UST∈QE∗F1,F6, x2,y2∈QF2, and x3,y3∈QF3 such that k2=X⊕x2 and k3=A1L⊕A2R⊕Oy2⊕x3(C-3): there exist three recordsLRX,UST∈QE∗F1,F6, x4,y4∈QF4, and x5,y5∈QF5 such that k5=A⊕x5 and k4=A1T⊕A2S⊕Oy5⊕x4(C-4): there exist two distinctLRX,UST and L′R′X′,U′S′T′ in QE∗F1,F6, and a pair x2,y2 in QF2 such that X=X′ and k2=X⊕x2, or symmetrically, two distinct LRX,UST and L′R′X′,A′S′T′ in QE∗F1,F6 and a pair x5,y5 in QF5 such that A=A′ and k5=A⊕x5(C-5): there exist two distinctLRX,UST and L′R′X′,U′S′T′ in QE∗F1,F6 and a pair x2,y2 in QF2 such that U=U′ and k2=X⊕x2, or symmetrically, two distinct LRX,UST and L′R′X′,U′S′T′ in QE∗F1,F6 and a pair x5,y5 in QF5 such that X=X′ and k5=U⊕x5F1,F6 is defined as good if BadF1,F6 does not hold.Lemma 3.
We have(25)PrF1,F6BadF1,F6|F1⊢QF1∧F6⊢QF6≤qeqf2N2+4qe2qfN2+α2,3k+α4,5kN+qfα1k+α2kN.Proof.
Due to page limits, see Appendix A.


#### 5.2.1. Analyzing the Inner Four Rounds

LetF∗=F2,F3,F4,F5. We denote(26)pτ,F1,F6=PrF∗←$ℱn:KAEFE∗⊢QE∗F1,F6|Fi⊢QFi,i=1,2,3,4,5,6.This captures the probability that the inner four rounds of KAEF “extend” the tuples inQE∗F1,F6. The probability Prreτ,k can be related to it.Lemma 4 (see [17]).
Assume that there exists a functionε:ℱn2×K⟶0,∞ such that, for any good F1,F6, the following equation holds:(27)pτ,F1,F6∏i=0qe−11/N2−i≥1−εF1,F6,k.Then, we have(28)Prreτ,kPridτ,k≥1−PrBadF1,F6|F1⊢QF1,F6⊢QF6−EF1,F6εF1,F6,k|F1⊢QF1,F6⊢QF6.Now, we prove the assumption of Lemma4.Lemma 5.
For any fixed good tupleF1,F6, there exists a function εF1,F6,k of the function pair and the round-key vector k such that inequality (20) mentioned in Lemma 4 holds. Moreover,(29)EF1,F6,kεF1,F6,k≤7qe3+10qeqf2+18qe2qf+3⋅2r⋅qeqf2+2⋅2r⋅qe2qfN2.Proof.
The general expression ofεF1,F6,k is a function of several variables defined before, which suffers from a bad readability. Therefore, we directly establish (and present) the bound on its expectation. However, due to space constraints, for the full proof, refer to Appendix B.
Below, we present a sketch and the core results. According to the type of the involved collisions, we divide the tuples inQE∗F1,F6 into four groups:(30)−G1=LRX,UST∈QE∗F1,F6:εQX=εQU=1,k2⊕X∉Domℱ2∧k5⊕U∉Domℱ5,−G2=LRX,UST∈QE∗F1,F6:k2⊕X∈Domℱ2,−G3=LRX,UST∈QE∗F1,F6:k5⊕U∈Domℱ5,−G4=LRX,UST∈QE∗F1,F6:εQX≥2,orεQU≥2.
Letβ1=G2, β2=G3, and β3=G4. Note that, by definition, these sets form a partition of QE∗F1,F6:−G1∩G2=G1∩G3=G1∩G4=∅ by definition−G2∩G3=∅, since otherwise QE∗F1,F6 would satisfy (C-1)−G2∩G4=∅, since, for any LRX,UST∈G3,εQX≥2 would imply QE∗F1,F6 fulfilling (C-4), while εQU≥2 would imply (C-5)−G3∩G4=∅, since, for any LRX,UST∈G3,εQX≥2 would imply (C-5), while εQU≥2 would imply (C-4)
We denoteEG1,EG2,EG3, and EG4 the event KAEFkF∗⊢G1,G2,G3 and G4. It can be seen that(31)pτ,F1,F6=PrEG1∧EG2∧EG3∧EG4|F⊢QF
We next analyze the four groups in turn. The first one, i.e.,PrEG1|F⊢QF, involves the most complicated analysis. Briefly, for each tuple LRX,UST in G1, it consists of three cases.
In the first case, neither of the two corresponding intermediate valuesY and Z derived from F2 and F5 collides with values that have been in the history. The probability that KAEFkF extends LRX,UST in this case is roughly at least(32)1−qf+qe+β1N1−qf+qe+β2N1N2.
In the second case, the corresponding intermediate valueY collides with some “existing” values, yet the further derived Z is “free.” The probability that KAEFkF extends LRX,UST in this case is roughly at least(33)qf+qeN−O2r⋅qf2N2+qf+qe2N21N2.
The third case is symmetrical to the second one:Z collides with “existing” values, yet Y is “free.” The probability is roughly at least(34)qf+qeN−Oqf+qe2N21N2.
Summing over the above, we obtain(35)PrEG1|F⊢QF≥∏l=1G11−β1N−β2N−O2r⋅qf2N2+qf+qe2N21N2.
The concrete bound is(36)EkPrEG1|F⊢QF≥1−2r⋅qeqf2N2−2qe2qf+qeqf+qeN2−qf+2qeβ1+β2N1N2|G1|.
To analyzeEG2,EG3, and EG4, we again apply the bad predicate approach. These groups involve collisions and have relatively small sizes: EG2,EG3,EG4=O2r⋅q2/N (will be proved later). Therefore, any collisions between tuples in these groups and values related to QF or EG1 can be included in the bad predicates; for each tuple, in these three groups, the probability would be Oq/N with q=maxqe,qf, yet it remains Oq/N⋅O2r⋅q2/N=O2r⋅q3/N in total. In all, the results are(37)PrEG2∧EG3|EG1∧F⊢QF≥1−β1+β2qf+qeN1N2G2+G3,PrEG4|EG1∧EG2∧EG3∧F⊢QF≥1−2β3qf+qeN1N2G4.Proof.
It is analyzes forG2,G3, and G4.
Lowering boundingPrEG2∧EG3|EG1∧F⊢QF. Consider EG2 first; we lower bound that probability that is equivalent to F4 and F5, satisfying 2G2 new and distinct equations. To this end, again, we define a predicate Bad1F3, which holds if there exists LRX,UST∈G2 that fulfills one of the following conditions:(i)
Thex4 value derived using F3 is in Domℱ4, i.e., k4⊕OF3x3∈Domℱ4, where x3=k3⊕A1L⊕A2R⊕OImgF2k2⊕X(ii)
TheZ value derived using F3 collides with Z′ value of another tuple in G2, i.e., there exists L′R′X′,U′S′T′∈G2 such that X⊕OF3x3=X′⊕OF3x3′, where x3′=k3⊕A1L′⊕A2R′⊕OImgF2k2⊕X′(iii)
TheZ value derived using F3 collides with Z′ value of another tuple in G2 or G3, i.e., there exists L∗R∗X∗,U∗S∗T∗∈G1∪G3 such that X⊕OF3x3=A1T∗⊕A2S∗⊕OF5k5⊕U∗
We note that, for eachLRX,UST∈G2, let x3=k3⊕A1L⊕A2R⊕OImgF2k2⊕X; then, the following equation holds x3∉Domℱ3(otherwise fulfilling (C-2)) and x3∈Extℱ3G1(according to the analysis of EG1). Thus, conditioned on EG1∧F3⊢QF3, the value F3x3 remains uniform. Therefore, for this LRX,UST,(i)
The probability that condition (i) is fulfilled at mostqf/N(ii)
For eachL′R′X′,U′S′T′∈G2, if the corresponding x3′ does not equal x3, then the probability of X⊕OF3x3=X′⊕OF3x3′ is at most 1/N; otherwise, since the two tuples are distinct, it has to be X≠X′, and thus, X⊕OF3x3≠X′⊕OF3x3′(iii)
For eachL∗R∗X∗,U∗S∗T∗∈G1∪G3, the probability of X⊕OF3x3=A1T∗⊕A2S∗⊕OF5k5⊕U∗ is at most 1/N
Summing over the above yields(38)PrBad1F3|EG1∧F⊢QF≤G2⋅qf+G1+G2+G3N≤β1⋅qf+qeN.
It is not hard to see that conditioned on¬Bad1F3, the G2 tuples in G2 indeed give rise to G2 distinct values Z1,…,ZG2 (otherwise condition (ii) is fulfilled), for which F4Z1⊕k4,…,F4ZG2⊕k4, all remain undetermined (otherwise condition (i) or (iii) is fulfilled)). Furthermore, at the “right side,” they also give rise to G2 distinct values U1,…,UG2 with F5U1⊕k5,…,F5UG2⊕k5, all remain undetermined:(i)
U1,…,UG2 are also distinct, otherwise fulfilling (C-5)(ii)
None ofU1⊕k5,…,UG2⊕k5 is in Domℱ5, otherwise fulfilling (C-1)(iii)
Conditioned onEG1, F5U1⊕k5,…,F5UG2⊕k5, all remain undetermined, otherwise some Ui is shared between tuples in G1 and G2
Thus, in this case, the eventEG2 is equivalent to F4 and F5 satisfying 2G2 new and distinct equations, and the probability does not exceed 1/N2G2.
We then considerEG3. The analysis is similar to EG2 by symmetry; we define a predicate Bad1F4 on F4, which holds if there exists LRX,UST∈G3 such that one of the following conditions is fulfilled:(i)
The induced valuex3 is in Domℱ3, i.e., k3⊕OF4x4∈Domℱ3, where x4=k4⊕A1T⊕A2S⊕OImgF5k5⊕U. The probability is at most qf/N in total.(ii)
The induced valueY collides with the Y′ value of another tuple in G3, i.e., there exists L′R′X′,U′S′T′∈G3 such that U⊕OF4x4=U′⊕OF4x4′, where x4′=k4⊕A1T′⊕A2S′⊕OImgF5k5⊕U′. The probability is at most G3/N.(iii)
The induced valueY collides with Y′ value of another tuple in G1 or G2, i.e., there exists L∗R∗X∗,U∗S∗T∗∈G1∪G2 such that U⊕OF4x4=A1L∗⊕A2R∗⊕OF2k2⊕X∗. The probability is at most G1+G2/N in total.
Similar toBad1F3,(39)PrBad2F4|EG1∧F⊢QF≤G3⋅qf+G1+G2+G3N≤β2⋅qf+qeN.
And, conditioned onBad1F4, tuples in G3 give rise to G3 distinct values Y1,…,YG3, while the assumption ¬Bad1F1,F6 ensures that they give rise to G3 distinct values X1,…,XG3. Thus, the event EG3 is equivalent to F2 and F3 satisfying 2G3 new and distinct equations. Therefore, conditioned on EG1∧F⊢QF, we have(40)PrEG2∧EG3|EG1∧F⊢QF≥1−PrBad1F2−PrBad1F3⋅PrEG2∧EG3|¬Bad1F2∧¬Bad1F3≥1−β1+β2⋅qf+qeN1N2G2+G3.
Lower boundingPrEG4|EG1∧EG2∧EG3∧F⊢QF: by definition, for any tuple LRX,UST∈G4, let x2=k2⊕X and x5=k5⊕U; then, we have both x2∉Domℱ2 and x5∉Domℱ5. Moreover, conditioned on EG1∧EG2∧EG3, the two values F2x2 and F5x5 remain “undetermined” and uniform (otherwise, if EG1,EG2, and EG3 imply F2x2 being fixed, then a tuple in G1,G2, or G3 would share the same X value with a tuple in G4, contradicting the definition of G1 or fulfilling (C-4) or (C-5), respectively).
For these tuples, we would lower bound the probability that they induce2G4 new and distinct equations on F3 and F4. To this end, we define a predicate ¬Bad3F2,F5 on F2 and F5, which holds if there exists a tuple LRX,UST∈G4 such that if we let x2=k2⊕X and x5=k5⊕U, then one of the following conditions is fulfilled:At the “left side,” concerningF2x2,(i)
The inducedx3 value falls in Domℱ3, i.e., k3⊕A1L⊕A2R⊕OF2x2∈Domℱ3. As discussed, F2x2 remains random; thus, the probability is clearly at most qf/N.(ii)
The inducedY value collides with some “previously determined” Y′, i.e., there exists another tuple L′R′X′,U′S′T′∈G1∪G2∪G3 such that A1L⊕A2R⊕OF2x2=A1L′⊕A2R′⊕OF2x2′. It necessarily is X≠X′; again, using the randomness of F2x2, we obtain the upper bound G1+G2+G3/N≤qe/N, for each LRX,UST∈G4.At the “right side,” concerningF5x5, similar to the above symmetry,(i)
k4⊕A1T⊕A2S⊕HF5x5∈Domℱ4: the probability is clearly at most qf/N.(ii)
There exists another tupleL′R′X′,U′S′T′∈G1∪G2∪G3 such that A1T⊕A2S⊕OF5x5=A1T′⊕A2S′⊕OF5x5′. The upper bound is G1+G2+G3/N≤qe/N, for each LRX,UST∈G4.
Thus, usingG4=β3, we obtain(41)PrBad3F2,F5|EG1∧EG2∧EG3∧F⊢QF≤2G4⋅qf+qeN≤2β3⋅qf+qeN.
Similar to the analysis forEG2 and EG3, conditioned on ¬Bad3F2,F5, the event EG4 is equivalent to F3 and F4 satisfying 2G4 new and distinct equations. Therefore,(42)PrEG4|EG1∧EG2∧EG3∧F⊢QF≥1−PrBad3F2,F5⋅1N2G4≥1−2β3qf+qeN⋅1N2G4.
Summing up would yield a lower bound of the form(43)pτ,F1,F6=PrEG1∧EG2∧EG3∧EG4|F⊢QF≥1−ε11−ε21−ε31N2G1+G2+G3+G4≥1−ε1+ε2+ε31N2qeSinceG1+G2+G3+G4=qe.
We note1/N2qe/∏i=0qe−11/N2−i≥1−qe/N2qe≥1−qe2/N2≥1−qe3/N2. Thus, using 1−A1−B≥1−A+B, we obtain(44)pτ,F1,F6∏i=0qe−11/N2−i≥1−εF1,F6,k,for which(45)EkεF1,F6,k≤2qf+3qeβ1+β2+2β3qf+qeN+2r⋅qeqf2N2+2qe2qf+qeqf+qe+qe3N2.
We now deriveEF1,F6EkεF1,F6,k|F1⊢QF1,F6⊢QF6. To this end, note that, by definition, β1,β2, and β3 are quantities that depend on F1,F6:(46)β1=LRX,UST∈QE∗F1,F6:k2⊕X=k2⊕A1R⊕A2L⊕OF1k1⊕A1L⊕A2R∈Domℱ2,β2=LRX,UST∈QE∗F1,F6:k5⊕U=k5⊕A1S⊕A2T⊕OF6k6⊕A1T⊕A2S∈Domℱ5,β3=LRX,UST∈QE∗F1,F6:∃L′R′X′,U′S′T′such thatX=X′,or:∃L′R′X′,U′S′T′∈QE∗F1,F6such thatU=U′.
We considerβ1 first. For each LRX,UST∈QE∗F1,F6, if k1⊕A1L⊕A2R∈Domℱ1, then k2⊕X∉Domℱ2 by ¬B−2. Thus, conditioned on F1⊢QF1, F1k1⊕R remains uniform, and Prk2⊕A1R⊕A2L⊕OF1k1⊕A1L⊕A2R∈Domℱ2≤qf/N. Therefore,(47)Ekβ1≤qeqfN.
Similarly, by symmetry, using the randomness supplied byF6, Ekβ2≤qeqf/N.
Then, we considerβ3. We fix a record LR,ST such that k1⊕A1L⊕A2R∉Domℱ1, and consider another L′R′,S′T′. If A1L⊕A2R=A1L′⊕A2R′, then it has to be 2n, and thus, X=X′. Otherwise, as k1⊕A1L⊕A2R∉Domℱ1, F1k1⊕A1L⊕A2R remains random conditioned on F1⊢QF1, and(48)PrX=X′=PrOF1k1⊕A1L⊕A2R⊕OF1k1⊕A1L′⊕A2R′=A1R⊕A2L⊕A1R′⊕A2L′=1N.
The number of distinct pairs of such tuples is at mostqe2. Thus, we know the expectation of the number of pairs:(49)EkLRX,UST:k1⊕A1L⊕A2R∉Domℱ1,∃L′R′X′,U′S′T′s.t.X=X′|≤qe2N.
As the number ofLR,ST such that k1⊕A1L⊕A2R∈Domℱ1 is α1k, we obtain(50)EkLRX,UST:∃L′R′X′,U′S′T′s.t.X=X′|≤qe2N+α1k.
Symmetrically,EkLRX,UST:∃L′R′X′,U′S′T′s.t.U=U′|≤qe2/N+α2k. Thus, Ekβ3≤2qe2/N+α1k+α2k. Finally, since k1 and resp. k6 are uniform in 2n and resp. 2n−r possibilities,(51)Ekα1k=∑LR,ST∈QE∑x1,y1∈QF1Prk1=A1L⊕A2R⊕x1≤qeqfN.and Ekα2k≤2r⋅qeqf/N. Gathering all the above yields(52)EF1,F6,kεF1,F6,k≤4qeqf2+6qe2qfN2+2qf+qe2rqeqf+qeqf+2qe2N2+2r⋅qeqf2N2+2qe2qf+qeqf+qe+qe3N2=7qe3+10qeqf2+18qe2qf+3⋅2r⋅qeqf2+2⋅2r⋅qe2qfN2,as claimed in (8).


### 5.3. Concluding the Pointwise Proximity Proof

Gathering Lemma2, Lemma 4, and equation (22), we obtain(53)PrreτPridτ≥1−3⋅2r⋅qeqf2N2+EkPrBadF1,F6|F1⊢QF1,F6⊢QF6+EkEF1,F6εF1,F6,k|F1⊢QF1,F6⊢QF6,where εF1,F6,k is the function specified in equation (44). Note that its expectation has been bounded in Lemma 5.ForEkPrBadF1,F6|F1⊢QF1,F6⊢QF6, since k3 and resp. k4 are both uniformly distributed in 2n and resp. 2n−r possibilities, we have(54)Ekα2,3k≤qeqf2N,Ekα4,5k≤2rqeqf2N.At the end of previous section, we have shownEkα1k≤qeqf/N and Ekα1k≤2rqeqf/N. Injecting them into the bound of Lemma 3 yields(55)EkPrBadF1,F6|F1⊢QF1,F6⊢QF6≤3qeqf2N2+2rqeqf2N2+4qe2qfN2.Gathering all the above eventually establishes equation (21).


## 5.1. Bad Round-Key Vectors and Probability

For convenience,xi∈Domℱi (and xi∉Domℱi otherwise) denotes, for any xi∈0,1n, whether there exists a corresponding record xi,yi in QFi or not. Additionally, Imgℱixi denotes the corresponding yi. The bad round-key vector is defined as follows.Definition 4 (bad round-key vector for 6 rounds).
With respect toτ=QE,QF, a suitable key vector k is bad if it satisfies one of the following conditions:(B-1): there existLR,ST∈QE, x1,y1∈QF1, and x6,y6∈QF6 such that k1=A1L⊕A2R⊕x1 and k6=A1T⊕A2S⊕x6(B-2): there existLR,ST∈QE, x1,y1∈QF1, and x2,y2∈QF2 such that k1=A1L⊕A2R⊕x1 and k2=A1R⊕A2L⊕Oy1⊕x2(B-3): there existLR,ST∈QE, x5,y5∈QF5, and x6,y6∈QF6 such that k6=A1T⊕A2S⊕x6 and k5=A1S⊕A2T⊕Oy6⊕x5
These bad key vectors are denoted asKbad. The other key vectors are defined as good key vectors, denoted by Kgood.
Because there are at mostqeqf2 choices for LR,ST∈QE, x1,y1∈QF1, and x6,y6∈QF6 and since k1, resp. k6, is uniform in 2n, resp. 2n−r possibilities, and furthermore, since k1 and k6 are independent, the following equation holds PrB−1≤qeqf2/22n−r≤2rqeqf2/N2.
Similarly, we havePrB−2≤2rqeqf2/N2. By symmetry, PrB−3≤2rqeqf2/N2. As a result,(22)Prk←$K:k∈Kbad≤3⋅2r⋅qeqf2N2.


## 5.2. Analysis for Good Keys

For a fixed good round-key vectork, we would get a lower bound for the probability PrF←$ℱn6:KAEFkF⊢QE|F⊢QF. Inspired by Cogliati et al. [25, 26], it takes two steps. Firstly, through defining certain “bad” functions on F1,F6, we would lower bound the probability under the condition. Secondly, under the assumption of “good” functions F1,F6, the outer two rounds are removed; we only need to analyze the induced 4-round transcript to yield the final bounds.For a fixed pair ofF1,F6 such that F1⊢QF1 and F6⊢QF6 and for each LR,ST∈QE, we set X←A1R⊕A2L⊕OF1A1L⊕A2R⊕k1 and U←A1S⊕A2T⊕OF6A1T⊕A2S⊕k6. Then, qe tuples LRX,UST are obtained. The induced tuples are denoted by QE∗F1,F6. For convenience, εQx is used to denote all tuples LRX,UST whose third coordinate equals X. Similarly, we define εQU:(23)−εQX=LRX,UST:LRX,UST∈QE∗F1,F6,−εQU=LRX,UST:LRX,UST∈QE∗F1,F6.Additionally, we define several key-independent quantities characterizingτ:(24)α1k=defLR,ST,x1,y1∈QE×QF1:k1=A1L⊕A2R⊕x1,α2k=defLR,ST,x6,y6∈QE×QF6:k6=A1T⊕A2S⊕x6,α2,3k=defLR,ST,x2,y2,x3,y3∈QE×QF2×QF3:k3=A1L⊕A2R⊕Oy2⊕x3,α4,5k=defLR,ST,x4,y4,x5,y5∈QE×QF4×QF5:k4=A1T⊕A2S⊕Oy5⊕x4.The predicateBadF1,F6 holds if the induced set QE∗F1,F6 satisfies one of the following conditions:(C-1): there exist three recordsLRX,UST∈QE∗F1,F6, x2,y2∈QF2, and x5,y5∈QF5 such that k2=X⊕x2 and k5=U⊕x5(C-2): there exist three recordsLRX,UST∈QE∗F1,F6, x2,y2∈QF2, and x3,y3∈QF3 such that k2=X⊕x2 and k3=A1L⊕A2R⊕Oy2⊕x3(C-3): there exist three recordsLRX,UST∈QE∗F1,F6, x4,y4∈QF4, and x5,y5∈QF5 such that k5=A⊕x5 and k4=A1T⊕A2S⊕Oy5⊕x4(C-4): there exist two distinctLRX,UST and L′R′X′,U′S′T′ in QE∗F1,F6, and a pair x2,y2 in QF2 such that X=X′ and k2=X⊕x2, or symmetrically, two distinct LRX,UST and L′R′X′,A′S′T′ in QE∗F1,F6 and a pair x5,y5 in QF5 such that A=A′ and k5=A⊕x5(C-5): there exist two distinctLRX,UST and L′R′X′,U′S′T′ in QE∗F1,F6 and a pair x2,y2 in QF2 such that U=U′ and k2=X⊕x2, or symmetrically, two distinct LRX,UST and L′R′X′,U′S′T′ in QE∗F1,F6 and a pair x5,y5 in QF5 such that X=X′ and k5=U⊕x5F1,F6 is defined as good if BadF1,F6 does not hold.Lemma 3.
We have(25)PrF1,F6BadF1,F6|F1⊢QF1∧F6⊢QF6≤qeqf2N2+4qe2qfN2+α2,3k+α4,5kN+qfα1k+α2kN.Proof.
Due to page limits, see Appendix A.


### 5.2.1. Analyzing the Inner Four Rounds

LetF∗=F2,F3,F4,F5. We denote(26)pτ,F1,F6=PrF∗←$ℱn:KAEFE∗⊢QE∗F1,F6|Fi⊢QFi,i=1,2,3,4,5,6.This captures the probability that the inner four rounds of KAEF “extend” the tuples inQE∗F1,F6. The probability Prreτ,k can be related to it.Lemma 4 (see [17]).
Assume that there exists a functionε:ℱn2×K⟶0,∞ such that, for any good F1,F6, the following equation holds:(27)pτ,F1,F6∏i=0qe−11/N2−i≥1−εF1,F6,k.Then, we have(28)Prreτ,kPridτ,k≥1−PrBadF1,F6|F1⊢QF1,F6⊢QF6−EF1,F6εF1,F6,k|F1⊢QF1,F6⊢QF6.Now, we prove the assumption of Lemma4.Lemma 5.
For any fixed good tupleF1,F6, there exists a function εF1,F6,k of the function pair and the round-key vector k such that inequality (20) mentioned in Lemma 4 holds. Moreover,(29)EF1,F6,kεF1,F6,k≤7qe3+10qeqf2+18qe2qf+3⋅2r⋅qeqf2+2⋅2r⋅qe2qfN2.Proof.
The general expression ofεF1,F6,k is a function of several variables defined before, which suffers from a bad readability. Therefore, we directly establish (and present) the bound on its expectation. However, due to space constraints, for the full proof, refer to Appendix B.
Below, we present a sketch and the core results. According to the type of the involved collisions, we divide the tuples inQE∗F1,F6 into four groups:(30)−G1=LRX,UST∈QE∗F1,F6:εQX=εQU=1,k2⊕X∉Domℱ2∧k5⊕U∉Domℱ5,−G2=LRX,UST∈QE∗F1,F6:k2⊕X∈Domℱ2,−G3=LRX,UST∈QE∗F1,F6:k5⊕U∈Domℱ5,−G4=LRX,UST∈QE∗F1,F6:εQX≥2,orεQU≥2.
Letβ1=G2, β2=G3, and β3=G4. Note that, by definition, these sets form a partition of QE∗F1,F6:−G1∩G2=G1∩G3=G1∩G4=∅ by definition−G2∩G3=∅, since otherwise QE∗F1,F6 would satisfy (C-1)−G2∩G4=∅, since, for any LRX,UST∈G3,εQX≥2 would imply QE∗F1,F6 fulfilling (C-4), while εQU≥2 would imply (C-5)−G3∩G4=∅, since, for any LRX,UST∈G3,εQX≥2 would imply (C-5), while εQU≥2 would imply (C-4)
We denoteEG1,EG2,EG3, and EG4 the event KAEFkF∗⊢G1,G2,G3 and G4. It can be seen that(31)pτ,F1,F6=PrEG1∧EG2∧EG3∧EG4|F⊢QF
We next analyze the four groups in turn. The first one, i.e.,PrEG1|F⊢QF, involves the most complicated analysis. Briefly, for each tuple LRX,UST in G1, it consists of three cases.
In the first case, neither of the two corresponding intermediate valuesY and Z derived from F2 and F5 collides with values that have been in the history. The probability that KAEFkF extends LRX,UST in this case is roughly at least(32)1−qf+qe+β1N1−qf+qe+β2N1N2.
In the second case, the corresponding intermediate valueY collides with some “existing” values, yet the further derived Z is “free.” The probability that KAEFkF extends LRX,UST in this case is roughly at least(33)qf+qeN−O2r⋅qf2N2+qf+qe2N21N2.
The third case is symmetrical to the second one:Z collides with “existing” values, yet Y is “free.” The probability is roughly at least(34)qf+qeN−Oqf+qe2N21N2.
Summing over the above, we obtain(35)PrEG1|F⊢QF≥∏l=1G11−β1N−β2N−O2r⋅qf2N2+qf+qe2N21N2.
The concrete bound is(36)EkPrEG1|F⊢QF≥1−2r⋅qeqf2N2−2qe2qf+qeqf+qeN2−qf+2qeβ1+β2N1N2|G1|.
To analyzeEG2,EG3, and EG4, we again apply the bad predicate approach. These groups involve collisions and have relatively small sizes: EG2,EG3,EG4=O2r⋅q2/N (will be proved later). Therefore, any collisions between tuples in these groups and values related to QF or EG1 can be included in the bad predicates; for each tuple, in these three groups, the probability would be Oq/N with q=maxqe,qf, yet it remains Oq/N⋅O2r⋅q2/N=O2r⋅q3/N in total. In all, the results are(37)PrEG2∧EG3|EG1∧F⊢QF≥1−β1+β2qf+qeN1N2G2+G3,PrEG4|EG1∧EG2∧EG3∧F⊢QF≥1−2β3qf+qeN1N2G4.Proof.
It is analyzes forG2,G3, and G4.
Lowering boundingPrEG2∧EG3|EG1∧F⊢QF. Consider EG2 first; we lower bound that probability that is equivalent to F4 and F5, satisfying 2G2 new and distinct equations. To this end, again, we define a predicate Bad1F3, which holds if there exists LRX,UST∈G2 that fulfills one of the following conditions:(i)
Thex4 value derived using F3 is in Domℱ4, i.e., k4⊕OF3x3∈Domℱ4, where x3=k3⊕A1L⊕A2R⊕OImgF2k2⊕X(ii)
TheZ value derived using F3 collides with Z′ value of another tuple in G2, i.e., there exists L′R′X′,U′S′T′∈G2 such that X⊕OF3x3=X′⊕OF3x3′, where x3′=k3⊕A1L′⊕A2R′⊕OImgF2k2⊕X′(iii)
TheZ value derived using F3 collides with Z′ value of another tuple in G2 or G3, i.e., there exists L∗R∗X∗,U∗S∗T∗∈G1∪G3 such that X⊕OF3x3=A1T∗⊕A2S∗⊕OF5k5⊕U∗
We note that, for eachLRX,UST∈G2, let x3=k3⊕A1L⊕A2R⊕OImgF2k2⊕X; then, the following equation holds x3∉Domℱ3(otherwise fulfilling (C-2)) and x3∈Extℱ3G1(according to the analysis of EG1). Thus, conditioned on EG1∧F3⊢QF3, the value F3x3 remains uniform. Therefore, for this LRX,UST,(i)
The probability that condition (i) is fulfilled at mostqf/N(ii)
For eachL′R′X′,U′S′T′∈G2, if the corresponding x3′ does not equal x3, then the probability of X⊕OF3x3=X′⊕OF3x3′ is at most 1/N; otherwise, since the two tuples are distinct, it has to be X≠X′, and thus, X⊕OF3x3≠X′⊕OF3x3′(iii)
For eachL∗R∗X∗,U∗S∗T∗∈G1∪G3, the probability of X⊕OF3x3=A1T∗⊕A2S∗⊕OF5k5⊕U∗ is at most 1/N
Summing over the above yields(38)PrBad1F3|EG1∧F⊢QF≤G2⋅qf+G1+G2+G3N≤β1⋅qf+qeN.
It is not hard to see that conditioned on¬Bad1F3, the G2 tuples in G2 indeed give rise to G2 distinct values Z1,…,ZG2 (otherwise condition (ii) is fulfilled), for which F4Z1⊕k4,…,F4ZG2⊕k4, all remain undetermined (otherwise condition (i) or (iii) is fulfilled)). Furthermore, at the “right side,” they also give rise to G2 distinct values U1,…,UG2 with F5U1⊕k5,…,F5UG2⊕k5, all remain undetermined:(i)
U1,…,UG2 are also distinct, otherwise fulfilling (C-5)(ii)
None ofU1⊕k5,…,UG2⊕k5 is in Domℱ5, otherwise fulfilling (C-1)(iii)
Conditioned onEG1, F5U1⊕k5,…,F5UG2⊕k5, all remain undetermined, otherwise some Ui is shared between tuples in G1 and G2
Thus, in this case, the eventEG2 is equivalent to F4 and F5 satisfying 2G2 new and distinct equations, and the probability does not exceed 1/N2G2.
We then considerEG3. The analysis is similar to EG2 by symmetry; we define a predicate Bad1F4 on F4, which holds if there exists LRX,UST∈G3 such that one of the following conditions is fulfilled:(i)
The induced valuex3 is in Domℱ3, i.e., k3⊕OF4x4∈Domℱ3, where x4=k4⊕A1T⊕A2S⊕OImgF5k5⊕U. The probability is at most qf/N in total.(ii)
The induced valueY collides with the Y′ value of another tuple in G3, i.e., there exists L′R′X′,U′S′T′∈G3 such that U⊕OF4x4=U′⊕OF4x4′, where x4′=k4⊕A1T′⊕A2S′⊕OImgF5k5⊕U′. The probability is at most G3/N.(iii)
The induced valueY collides with Y′ value of another tuple in G1 or G2, i.e., there exists L∗R∗X∗,U∗S∗T∗∈G1∪G2 such that U⊕OF4x4=A1L∗⊕A2R∗⊕OF2k2⊕X∗. The probability is at most G1+G2/N in total.
Similar toBad1F3,(39)PrBad2F4|EG1∧F⊢QF≤G3⋅qf+G1+G2+G3N≤β2⋅qf+qeN.
And, conditioned onBad1F4, tuples in G3 give rise to G3 distinct values Y1,…,YG3, while the assumption ¬Bad1F1,F6 ensures that they give rise to G3 distinct values X1,…,XG3. Thus, the event EG3 is equivalent to F2 and F3 satisfying 2G3 new and distinct equations. Therefore, conditioned on EG1∧F⊢QF, we have(40)PrEG2∧EG3|EG1∧F⊢QF≥1−PrBad1F2−PrBad1F3⋅PrEG2∧EG3|¬Bad1F2∧¬Bad1F3≥1−β1+β2⋅qf+qeN1N2G2+G3.
Lower boundingPrEG4|EG1∧EG2∧EG3∧F⊢QF: by definition, for any tuple LRX,UST∈G4, let x2=k2⊕X and x5=k5⊕U; then, we have both x2∉Domℱ2 and x5∉Domℱ5. Moreover, conditioned on EG1∧EG2∧EG3, the two values F2x2 and F5x5 remain “undetermined” and uniform (otherwise, if EG1,EG2, and EG3 imply F2x2 being fixed, then a tuple in G1,G2, or G3 would share the same X value with a tuple in G4, contradicting the definition of G1 or fulfilling (C-4) or (C-5), respectively).
For these tuples, we would lower bound the probability that they induce2G4 new and distinct equations on F3 and F4. To this end, we define a predicate ¬Bad3F2,F5 on F2 and F5, which holds if there exists a tuple LRX,UST∈G4 such that if we let x2=k2⊕X and x5=k5⊕U, then one of the following conditions is fulfilled:At the “left side,” concerningF2x2,(i)
The inducedx3 value falls in Domℱ3, i.e., k3⊕A1L⊕A2R⊕OF2x2∈Domℱ3. As discussed, F2x2 remains random; thus, the probability is clearly at most qf/N.(ii)
The inducedY value collides with some “previously determined” Y′, i.e., there exists another tuple L′R′X′,U′S′T′∈G1∪G2∪G3 such that A1L⊕A2R⊕OF2x2=A1L′⊕A2R′⊕OF2x2′. It necessarily is X≠X′; again, using the randomness of F2x2, we obtain the upper bound G1+G2+G3/N≤qe/N, for each LRX,UST∈G4.At the “right side,” concerningF5x5, similar to the above symmetry,(i)
k4⊕A1T⊕A2S⊕HF5x5∈Domℱ4: the probability is clearly at most qf/N.(ii)
There exists another tupleL′R′X′,U′S′T′∈G1∪G2∪G3 such that A1T⊕A2S⊕OF5x5=A1T′⊕A2S′⊕OF5x5′. The upper bound is G1+G2+G3/N≤qe/N, for each LRX,UST∈G4.
Thus, usingG4=β3, we obtain(41)PrBad3F2,F5|EG1∧EG2∧EG3∧F⊢QF≤2G4⋅qf+qeN≤2β3⋅qf+qeN.
Similar to the analysis forEG2 and EG3, conditioned on ¬Bad3F2,F5, the event EG4 is equivalent to F3 and F4 satisfying 2G4 new and distinct equations. Therefore,(42)PrEG4|EG1∧EG2∧EG3∧F⊢QF≥1−PrBad3F2,F5⋅1N2G4≥1−2β3qf+qeN⋅1N2G4.
Summing up would yield a lower bound of the form(43)pτ,F1,F6=PrEG1∧EG2∧EG3∧EG4|F⊢QF≥1−ε11−ε21−ε31N2G1+G2+G3+G4≥1−ε1+ε2+ε31N2qeSinceG1+G2+G3+G4=qe.
We note1/N2qe/∏i=0qe−11/N2−i≥1−qe/N2qe≥1−qe2/N2≥1−qe3/N2. Thus, using 1−A1−B≥1−A+B, we obtain(44)pτ,F1,F6∏i=0qe−11/N2−i≥1−εF1,F6,k,for which(45)EkεF1,F6,k≤2qf+3qeβ1+β2+2β3qf+qeN+2r⋅qeqf2N2+2qe2qf+qeqf+qe+qe3N2.
We now deriveEF1,F6EkεF1,F6,k|F1⊢QF1,F6⊢QF6. To this end, note that, by definition, β1,β2, and β3 are quantities that depend on F1,F6:(46)β1=LRX,UST∈QE∗F1,F6:k2⊕X=k2⊕A1R⊕A2L⊕OF1k1⊕A1L⊕A2R∈Domℱ2,β2=LRX,UST∈QE∗F1,F6:k5⊕U=k5⊕A1S⊕A2T⊕OF6k6⊕A1T⊕A2S∈Domℱ5,β3=LRX,UST∈QE∗F1,F6:∃L′R′X′,U′S′T′such thatX=X′,or:∃L′R′X′,U′S′T′∈QE∗F1,F6such thatU=U′.
We considerβ1 first. For each LRX,UST∈QE∗F1,F6, if k1⊕A1L⊕A2R∈Domℱ1, then k2⊕X∉Domℱ2 by ¬B−2. Thus, conditioned on F1⊢QF1, F1k1⊕R remains uniform, and Prk2⊕A1R⊕A2L⊕OF1k1⊕A1L⊕A2R∈Domℱ2≤qf/N. Therefore,(47)Ekβ1≤qeqfN.
Similarly, by symmetry, using the randomness supplied byF6, Ekβ2≤qeqf/N.
Then, we considerβ3. We fix a record LR,ST such that k1⊕A1L⊕A2R∉Domℱ1, and consider another L′R′,S′T′. If A1L⊕A2R=A1L′⊕A2R′, then it has to be 2n, and thus, X=X′. Otherwise, as k1⊕A1L⊕A2R∉Domℱ1, F1k1⊕A1L⊕A2R remains random conditioned on F1⊢QF1, and(48)PrX=X′=PrOF1k1⊕A1L⊕A2R⊕OF1k1⊕A1L′⊕A2R′=A1R⊕A2L⊕A1R′⊕A2L′=1N.
The number of distinct pairs of such tuples is at mostqe2. Thus, we know the expectation of the number of pairs:(49)EkLRX,UST:k1⊕A1L⊕A2R∉Domℱ1,∃L′R′X′,U′S′T′s.t.X=X′|≤qe2N.
As the number ofLR,ST such that k1⊕A1L⊕A2R∈Domℱ1 is α1k, we obtain(50)EkLRX,UST:∃L′R′X′,U′S′T′s.t.X=X′|≤qe2N+α1k.
Symmetrically,EkLRX,UST:∃L′R′X′,U′S′T′s.t.U=U′|≤qe2/N+α2k. Thus, Ekβ3≤2qe2/N+α1k+α2k. Finally, since k1 and resp. k6 are uniform in 2n and resp. 2n−r possibilities,(51)Ekα1k=∑LR,ST∈QE∑x1,y1∈QF1Prk1=A1L⊕A2R⊕x1≤qeqfN.and Ekα2k≤2r⋅qeqf/N. Gathering all the above yields(52)EF1,F6,kεF1,F6,k≤4qeqf2+6qe2qfN2+2qf+qe2rqeqf+qeqf+2qe2N2+2r⋅qeqf2N2+2qe2qf+qeqf+qe+qe3N2=7qe3+10qeqf2+18qe2qf+3⋅2r⋅qeqf2+2⋅2r⋅qe2qfN2,as claimed in (8).


## 5.2.1. Analyzing the Inner Four Rounds

LetF∗=F2,F3,F4,F5. We denote(26)pτ,F1,F6=PrF∗←$ℱn:KAEFE∗⊢QE∗F1,F6|Fi⊢QFi,i=1,2,3,4,5,6.This captures the probability that the inner four rounds of KAEF “extend” the tuples inQE∗F1,F6. The probability Prreτ,k can be related to it.Lemma 4 (see [17]).
Assume that there exists a functionε:ℱn2×K⟶0,∞ such that, for any good F1,F6, the following equation holds:(27)pτ,F1,F6∏i=0qe−11/N2−i≥1−εF1,F6,k.Then, we have(28)Prreτ,kPridτ,k≥1−PrBadF1,F6|F1⊢QF1,F6⊢QF6−EF1,F6εF1,F6,k|F1⊢QF1,F6⊢QF6.Now, we prove the assumption of Lemma4.Lemma 5.
For any fixed good tupleF1,F6, there exists a function εF1,F6,k of the function pair and the round-key vector k such that inequality (20) mentioned in Lemma 4 holds. Moreover,(29)EF1,F6,kεF1,F6,k≤7qe3+10qeqf2+18qe2qf+3⋅2r⋅qeqf2+2⋅2r⋅qe2qfN2.Proof.
The general expression ofεF1,F6,k is a function of several variables defined before, which suffers from a bad readability. Therefore, we directly establish (and present) the bound on its expectation. However, due to space constraints, for the full proof, refer to Appendix B.
Below, we present a sketch and the core results. According to the type of the involved collisions, we divide the tuples inQE∗F1,F6 into four groups:(30)−G1=LRX,UST∈QE∗F1,F6:εQX=εQU=1,k2⊕X∉Domℱ2∧k5⊕U∉Domℱ5,−G2=LRX,UST∈QE∗F1,F6:k2⊕X∈Domℱ2,−G3=LRX,UST∈QE∗F1,F6:k5⊕U∈Domℱ5,−G4=LRX,UST∈QE∗F1,F6:εQX≥2,orεQU≥2.
Letβ1=G2, β2=G3, and β3=G4. Note that, by definition, these sets form a partition of QE∗F1,F6:−G1∩G2=G1∩G3=G1∩G4=∅ by definition−G2∩G3=∅, since otherwise QE∗F1,F6 would satisfy (C-1)−G2∩G4=∅, since, for any LRX,UST∈G3,εQX≥2 would imply QE∗F1,F6 fulfilling (C-4), while εQU≥2 would imply (C-5)−G3∩G4=∅, since, for any LRX,UST∈G3,εQX≥2 would imply (C-5), while εQU≥2 would imply (C-4)
We denoteEG1,EG2,EG3, and EG4 the event KAEFkF∗⊢G1,G2,G3 and G4. It can be seen that(31)pτ,F1,F6=PrEG1∧EG2∧EG3∧EG4|F⊢QF
We next analyze the four groups in turn. The first one, i.e.,PrEG1|F⊢QF, involves the most complicated analysis. Briefly, for each tuple LRX,UST in G1, it consists of three cases.
In the first case, neither of the two corresponding intermediate valuesY and Z derived from F2 and F5 collides with values that have been in the history. The probability that KAEFkF extends LRX,UST in this case is roughly at least(32)1−qf+qe+β1N1−qf+qe+β2N1N2.
In the second case, the corresponding intermediate valueY collides with some “existing” values, yet the further derived Z is “free.” The probability that KAEFkF extends LRX,UST in this case is roughly at least(33)qf+qeN−O2r⋅qf2N2+qf+qe2N21N2.
The third case is symmetrical to the second one:Z collides with “existing” values, yet Y is “free.” The probability is roughly at least(34)qf+qeN−Oqf+qe2N21N2.
Summing over the above, we obtain(35)PrEG1|F⊢QF≥∏l=1G11−β1N−β2N−O2r⋅qf2N2+qf+qe2N21N2.
The concrete bound is(36)EkPrEG1|F⊢QF≥1−2r⋅qeqf2N2−2qe2qf+qeqf+qeN2−qf+2qeβ1+β2N1N2|G1|.
To analyzeEG2,EG3, and EG4, we again apply the bad predicate approach. These groups involve collisions and have relatively small sizes: EG2,EG3,EG4=O2r⋅q2/N (will be proved later). Therefore, any collisions between tuples in these groups and values related to QF or EG1 can be included in the bad predicates; for each tuple, in these three groups, the probability would be Oq/N with q=maxqe,qf, yet it remains Oq/N⋅O2r⋅q2/N=O2r⋅q3/N in total. In all, the results are(37)PrEG2∧EG3|EG1∧F⊢QF≥1−β1+β2qf+qeN1N2G2+G3,PrEG4|EG1∧EG2∧EG3∧F⊢QF≥1−2β3qf+qeN1N2G4.Proof.
It is analyzes forG2,G3, and G4.
Lowering boundingPrEG2∧EG3|EG1∧F⊢QF. Consider EG2 first; we lower bound that probability that is equivalent to F4 and F5, satisfying 2G2 new and distinct equations. To this end, again, we define a predicate Bad1F3, which holds if there exists LRX,UST∈G2 that fulfills one of the following conditions:(i)
Thex4 value derived using F3 is in Domℱ4, i.e., k4⊕OF3x3∈Domℱ4, where x3=k3⊕A1L⊕A2R⊕OImgF2k2⊕X(ii)
TheZ value derived using F3 collides with Z′ value of another tuple in G2, i.e., there exists L′R′X′,U′S′T′∈G2 such that X⊕OF3x3=X′⊕OF3x3′, where x3′=k3⊕A1L′⊕A2R′⊕OImgF2k2⊕X′(iii)
TheZ value derived using F3 collides with Z′ value of another tuple in G2 or G3, i.e., there exists L∗R∗X∗,U∗S∗T∗∈G1∪G3 such that X⊕OF3x3=A1T∗⊕A2S∗⊕OF5k5⊕U∗
We note that, for eachLRX,UST∈G2, let x3=k3⊕A1L⊕A2R⊕OImgF2k2⊕X; then, the following equation holds x3∉Domℱ3(otherwise fulfilling (C-2)) and x3∈Extℱ3G1(according to the analysis of EG1). Thus, conditioned on EG1∧F3⊢QF3, the value F3x3 remains uniform. Therefore, for this LRX,UST,(i)
The probability that condition (i) is fulfilled at mostqf/N(ii)
For eachL′R′X′,U′S′T′∈G2, if the corresponding x3′ does not equal x3, then the probability of X⊕OF3x3=X′⊕OF3x3′ is at most 1/N; otherwise, since the two tuples are distinct, it has to be X≠X′, and thus, X⊕OF3x3≠X′⊕OF3x3′(iii)
For eachL∗R∗X∗,U∗S∗T∗∈G1∪G3, the probability of X⊕OF3x3=A1T∗⊕A2S∗⊕OF5k5⊕U∗ is at most 1/N
Summing over the above yields(38)PrBad1F3|EG1∧F⊢QF≤G2⋅qf+G1+G2+G3N≤β1⋅qf+qeN.
It is not hard to see that conditioned on¬Bad1F3, the G2 tuples in G2 indeed give rise to G2 distinct values Z1,…,ZG2 (otherwise condition (ii) is fulfilled), for which F4Z1⊕k4,…,F4ZG2⊕k4, all remain undetermined (otherwise condition (i) or (iii) is fulfilled)). Furthermore, at the “right side,” they also give rise to G2 distinct values U1,…,UG2 with F5U1⊕k5,…,F5UG2⊕k5, all remain undetermined:(i)
U1,…,UG2 are also distinct, otherwise fulfilling (C-5)(ii)
None ofU1⊕k5,…,UG2⊕k5 is in Domℱ5, otherwise fulfilling (C-1)(iii)
Conditioned onEG1, F5U1⊕k5,…,F5UG2⊕k5, all remain undetermined, otherwise some Ui is shared between tuples in G1 and G2
Thus, in this case, the eventEG2 is equivalent to F4 and F5 satisfying 2G2 new and distinct equations, and the probability does not exceed 1/N2G2.
We then considerEG3. The analysis is similar to EG2 by symmetry; we define a predicate Bad1F4 on F4, which holds if there exists LRX,UST∈G3 such that one of the following conditions is fulfilled:(i)
The induced valuex3 is in Domℱ3, i.e., k3⊕OF4x4∈Domℱ3, where x4=k4⊕A1T⊕A2S⊕OImgF5k5⊕U. The probability is at most qf/N in total.(ii)
The induced valueY collides with the Y′ value of another tuple in G3, i.e., there exists L′R′X′,U′S′T′∈G3 such that U⊕OF4x4=U′⊕OF4x4′, where x4′=k4⊕A1T′⊕A2S′⊕OImgF5k5⊕U′. The probability is at most G3/N.(iii)
The induced valueY collides with Y′ value of another tuple in G1 or G2, i.e., there exists L∗R∗X∗,U∗S∗T∗∈G1∪G2 such that U⊕OF4x4=A1L∗⊕A2R∗⊕OF2k2⊕X∗. The probability is at most G1+G2/N in total.
Similar toBad1F3,(39)PrBad2F4|EG1∧F⊢QF≤G3⋅qf+G1+G2+G3N≤β2⋅qf+qeN.
And, conditioned onBad1F4, tuples in G3 give rise to G3 distinct values Y1,…,YG3, while the assumption ¬Bad1F1,F6 ensures that they give rise to G3 distinct values X1,…,XG3. Thus, the event EG3 is equivalent to F2 and F3 satisfying 2G3 new and distinct equations. Therefore, conditioned on EG1∧F⊢QF, we have(40)PrEG2∧EG3|EG1∧F⊢QF≥1−PrBad1F2−PrBad1F3⋅PrEG2∧EG3|¬Bad1F2∧¬Bad1F3≥1−β1+β2⋅qf+qeN1N2G2+G3.
Lower boundingPrEG4|EG1∧EG2∧EG3∧F⊢QF: by definition, for any tuple LRX,UST∈G4, let x2=k2⊕X and x5=k5⊕U; then, we have both x2∉Domℱ2 and x5∉Domℱ5. Moreover, conditioned on EG1∧EG2∧EG3, the two values F2x2 and F5x5 remain “undetermined” and uniform (otherwise, if EG1,EG2, and EG3 imply F2x2 being fixed, then a tuple in G1,G2, or G3 would share the same X value with a tuple in G4, contradicting the definition of G1 or fulfilling (C-4) or (C-5), respectively).
For these tuples, we would lower bound the probability that they induce2G4 new and distinct equations on F3 and F4. To this end, we define a predicate ¬Bad3F2,F5 on F2 and F5, which holds if there exists a tuple LRX,UST∈G4 such that if we let x2=k2⊕X and x5=k5⊕U, then one of the following conditions is fulfilled:At the “left side,” concerningF2x2,(i)
The inducedx3 value falls in Domℱ3, i.e., k3⊕A1L⊕A2R⊕OF2x2∈Domℱ3. As discussed, F2x2 remains random; thus, the probability is clearly at most qf/N.(ii)
The inducedY value collides with some “previously determined” Y′, i.e., there exists another tuple L′R′X′,U′S′T′∈G1∪G2∪G3 such that A1L⊕A2R⊕OF2x2=A1L′⊕A2R′⊕OF2x2′. It necessarily is X≠X′; again, using the randomness of F2x2, we obtain the upper bound G1+G2+G3/N≤qe/N, for each LRX,UST∈G4.At the “right side,” concerningF5x5, similar to the above symmetry,(i)
k4⊕A1T⊕A2S⊕HF5x5∈Domℱ4: the probability is clearly at most qf/N.(ii)
There exists another tupleL′R′X′,U′S′T′∈G1∪G2∪G3 such that A1T⊕A2S⊕OF5x5=A1T′⊕A2S′⊕OF5x5′. The upper bound is G1+G2+G3/N≤qe/N, for each LRX,UST∈G4.
Thus, usingG4=β3, we obtain(41)PrBad3F2,F5|EG1∧EG2∧EG3∧F⊢QF≤2G4⋅qf+qeN≤2β3⋅qf+qeN.
Similar to the analysis forEG2 and EG3, conditioned on ¬Bad3F2,F5, the event EG4 is equivalent to F3 and F4 satisfying 2G4 new and distinct equations. Therefore,(42)PrEG4|EG1∧EG2∧EG3∧F⊢QF≥1−PrBad3F2,F5⋅1N2G4≥1−2β3qf+qeN⋅1N2G4.
Summing up would yield a lower bound of the form(43)pτ,F1,F6=PrEG1∧EG2∧EG3∧EG4|F⊢QF≥1−ε11−ε21−ε31N2G1+G2+G3+G4≥1−ε1+ε2+ε31N2qeSinceG1+G2+G3+G4=qe.
We note1/N2qe/∏i=0qe−11/N2−i≥1−qe/N2qe≥1−qe2/N2≥1−qe3/N2. Thus, using 1−A1−B≥1−A+B, we obtain(44)pτ,F1,F6∏i=0qe−11/N2−i≥1−εF1,F6,k,for which(45)EkεF1,F6,k≤2qf+3qeβ1+β2+2β3qf+qeN+2r⋅qeqf2N2+2qe2qf+qeqf+qe+qe3N2.
We now deriveEF1,F6EkεF1,F6,k|F1⊢QF1,F6⊢QF6. To this end, note that, by definition, β1,β2, and β3 are quantities that depend on F1,F6:(46)β1=LRX,UST∈QE∗F1,F6:k2⊕X=k2⊕A1R⊕A2L⊕OF1k1⊕A1L⊕A2R∈Domℱ2,β2=LRX,UST∈QE∗F1,F6:k5⊕U=k5⊕A1S⊕A2T⊕OF6k6⊕A1T⊕A2S∈Domℱ5,β3=LRX,UST∈QE∗F1,F6:∃L′R′X′,U′S′T′such thatX=X′,or:∃L′R′X′,U′S′T′∈QE∗F1,F6such thatU=U′.
We considerβ1 first. For each LRX,UST∈QE∗F1,F6, if k1⊕A1L⊕A2R∈Domℱ1, then k2⊕X∉Domℱ2 by ¬B−2. Thus, conditioned on F1⊢QF1, F1k1⊕R remains uniform, and Prk2⊕A1R⊕A2L⊕OF1k1⊕A1L⊕A2R∈Domℱ2≤qf/N. Therefore,(47)Ekβ1≤qeqfN.
Similarly, by symmetry, using the randomness supplied byF6, Ekβ2≤qeqf/N.
Then, we considerβ3. We fix a record LR,ST such that k1⊕A1L⊕A2R∉Domℱ1, and consider another L′R′,S′T′. If A1L⊕A2R=A1L′⊕A2R′, then it has to be 2n, and thus, X=X′. Otherwise, as k1⊕A1L⊕A2R∉Domℱ1, F1k1⊕A1L⊕A2R remains random conditioned on F1⊢QF1, and(48)PrX=X′=PrOF1k1⊕A1L⊕A2R⊕OF1k1⊕A1L′⊕A2R′=A1R⊕A2L⊕A1R′⊕A2L′=1N.
The number of distinct pairs of such tuples is at mostqe2. Thus, we know the expectation of the number of pairs:(49)EkLRX,UST:k1⊕A1L⊕A2R∉Domℱ1,∃L′R′X′,U′S′T′s.t.X=X′|≤qe2N.
As the number ofLR,ST such that k1⊕A1L⊕A2R∈Domℱ1 is α1k, we obtain(50)EkLRX,UST:∃L′R′X′,U′S′T′s.t.X=X′|≤qe2N+α1k.
Symmetrically,EkLRX,UST:∃L′R′X′,U′S′T′s.t.U=U′|≤qe2/N+α2k. Thus, Ekβ3≤2qe2/N+α1k+α2k. Finally, since k1 and resp. k6 are uniform in 2n and resp. 2n−r possibilities,(51)Ekα1k=∑LR,ST∈QE∑x1,y1∈QF1Prk1=A1L⊕A2R⊕x1≤qeqfN.and Ekα2k≤2r⋅qeqf/N. Gathering all the above yields(52)EF1,F6,kεF1,F6,k≤4qeqf2+6qe2qfN2+2qf+qe2rqeqf+qeqf+2qe2N2+2r⋅qeqf2N2+2qe2qf+qeqf+qe+qe3N2=7qe3+10qeqf2+18qe2qf+3⋅2r⋅qeqf2+2⋅2r⋅qe2qfN2,as claimed in (8).


## 5.3. Concluding the Pointwise Proximity Proof

Gathering Lemma2, Lemma 4, and equation (22), we obtain(53)PrreτPridτ≥1−3⋅2r⋅qeqf2N2+EkPrBadF1,F6|F1⊢QF1,F6⊢QF6+EkEF1,F6εF1,F6,k|F1⊢QF1,F6⊢QF6,where εF1,F6,k is the function specified in equation (44). Note that its expectation has been bounded in Lemma 5.ForEkPrBadF1,F6|F1⊢QF1,F6⊢QF6, since k3 and resp. k4 are both uniformly distributed in 2n and resp. 2n−r possibilities, we have(54)Ekα2,3k≤qeqf2N,Ekα4,5k≤2rqeqf2N.At the end of previous section, we have shownEkα1k≤qeqf/N and Ekα1k≤2rqeqf/N. Injecting them into the bound of Lemma 3 yields(55)EkPrBadF1,F6|F1⊢QF1,F6⊢QF6≤3qeqf2N2+2rqeqf2N2+4qe2qfN2.Gathering all the above eventually establishes equation (21).


## 6. Conclusion

For diversity of iterative structures, we propose an extended Feistel structure. The new iterative structure also has similar encryption with decryption. This paper mainly investigates the security of the new structure from studying the distinguishability between the ideal cipher adopting this structure and a random permutation. Results show that, for birthday-bound security, the 4-round KAEF is secure against2n/2 queries and for beyond-birthday-bound security, the 6-round KAEF is secure against 22n/3 queries. As a result, the new iterative is a reliable structure and can provide more choices for cipher designing.



---

*Source: 2751797-2021-09-23.xml*