Abstract In this paper, we study the security of the Key-Alternating Feistel (KAF) ciphers, a class of key alternating ciphers with the Feistel structure, where each round of the cipher is instantiated with n -bit public round permutation $$P_i$$ P i , namely the i -th round of the cipher maps $$\begin{aligned} (X_L, X_R) \mapsto (X_R, P_i(X_R \oplus K_i) \oplus K_i \oplus X_L). \end{aligned}$$ ( X L , X R ) ↦ ( X R , P i ( X R ⊕ K i ) ⊕ K i ⊕ X L ) . We have shown that our 5 round construction with independent round permutations and independent round keys achieves 2 n /3-bit security in the random permutation model, i.e., the setting where the adversary is allowed to make forward and inverse queries to the round permutations in a black box way.