| Chinese Journal of Computers Full Text | |
| Title | Pseudorandomness and Super Pseudorandomness on the Unbalanced Feistel Networks with Contracting Functions |
| Authors | ZHANG Li-Ting WU Wen-Ling |
| Address | (State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing 100190) (State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, Beijing 100049) |
| Year | 2009 |
| Issue | No.7(1320―1330) |
| Abstract & Background | Abstract The structure of a block cipher is one of the most important factors in its security. Based on the former analysis of Balanced Feistel Networks, the authors study Unbalanced Feistel Networks with Contracting Functions (UFN-C) by provable security techniques. As showed, UFN-C with k+1 rounds is pseudorandom, and UFN-C with k+2 rounds is super pseudorandom. Furthermore, the authors simplify the necessary conditions step by step, and finally get that k+1-round U(h1,f,…,f) is pseudorandom and k+2-round U(h1,f,…,f,h2) is super pseudorandom, where h1 and h2 are independently ε-XOR universal hash functions and f is a pseudorandom function. This result reduces the number of pseudorandom functions needed in Naor and Reingold’s similar structure. Then, noticing that a special UFN-C called SMS4 has already been used in practice, the authors analyze its generalized form, “SMS4-like” structure. It is showed that as long as the number of blocks k in each round is odd, “SMS4-like” would not be pseudorandom, no matter how many rounds it has; however, if k is even, 2k-1-round SMS4-like is pseudorandom and 3k-2-round is super pseudorandom. Thus, by provable security techniques the authors give some theoretical suggestions to design and employ block ciphers of this form. Keywords pseudorandomness; super pseudorandomness; contracting functions; unbalanced Feistel network; SMS4 Background A block cipher can be considered as a family of permutations on its message space; if you select a key, you specify a permutation which can be calculated efficiently. Besides the requirements on the efficiency of calculation, an ideal block cipher should also be as random as possible. In order to catch such a character, Luby and Rackoff have proposed the notions of “pseudorandom permutation” and “super pseudorandom permutation”. Furthermore, they gave an example to show how to establish a pseudorandom permutation and a super pseudorandom permutation by Balanced Feistel Networks and some pseudorandom functions. From then on, many papers have been proposed to construct pseudorandom permutations and super pseudorandom permutations from pseudorandom functions by Balanced Feistel Networks. However, comparing with the considerable research on Balanced Feistel Networks, little attention has been paid to study the Unbalanced Feistel Networks. Naor and Reingold obtain a better security bound on Unbalanced Feistel Networks when they generalize their results on Balanced Feistel Networks. Based on the former analysis of Balanced Feistel Networks, the authors of this paper study Unbalanced Feistel Networks with Contracting Functions (UFN-C) by provable security techniques. As they show, UFN-C with k+1 rounds is pseudorandom, and UFN-C with k+2 rounds is super pseudorandom. Furthermore, they simplify the necessary conditions step by step, and finally get that k+1-round U(h1,f,…,f) is pseudorandom and k+2-round U(h1,f,…,f,h2) is super pseudorandom, where h1 and h2 are independently ε-XOR universal hash functions and f is a pseudorandom function. This result reduces the number of pseudorandom functions needed in Naor and Reingold’s similar structure. Then, noticing that a special UFN-C called SMS4 has already been used in practice, they analyze its generalized form, “SMS4-like” structure. It is showed that as long as the number of blocks k in each round is odd, “SMS4-like” would not be pseudorandom, no matter how many rounds it has; however, if k is even, 2k-1-round SMS4-like is pseudorandom and 3k-2-round is super pseudorandom. Thus, by provable security techniques they give some theoretical suggestions to design and employ block ciphers of this form. |