使用压缩函数的非平衡Feistel结构的伪随机性和超伪随机性

1、使用压缩函数的非平衡Feistel结构的伪随机性和超伪随机性 本工作得到国家“八六三”高技术研究发展计划项目基金（2007AA01Z470）、国家自然科学基金（60873259）和国家“九七三”重点基础研究发展规划项目基金（2004CB318004）资助。张立廷 吴文玲（中国科学院软件研究所信息安全国家重点实验室 北京 100190）（中国科学院研究生院信息安全国家重点实验室 北京 100049）摘 要 分组密码的结构是影响其安全性能的重要因素之一。本文从可证明安全的角度研究使用压缩函数的非平衡Feistel结构（UFN-C）的安全性，证明了轮UFN-C是伪随机的，轮UFN-C是超伪随机的；进

2、一步地，本文探讨了UFN-C的有效构造，降低了Naor和Reingold在文 Moni Naor and Omer Reingold. On the construction of pseudorandom permutations: Luby-Rackoff revisited. Journal of Cryptology, 1999, 12(1):2966,.中类似结构对伪随机函数个数的要求。最后，针对一类具体的UFN-C SMS4 Office of State Commercial Cipher Administration. Block Cipher for WLAN Product

3、s-SMS4. (in Chinese)(国家商用密码管理办公室. 无线局域网产品使用的SMS4密码算法. ，本文分析其广义形式SMS4-like结构的伪随机性和超伪随机性，为设计与使用该类结构的分组密码提供了可证明安全的理论依据。关键词 伪随机性；超伪随机性；压缩函数；非平衡Feistel结构；SMS41 引言一个分组密码方案可以看作是消息空间上的一个置换族；选取一个密钥，即确定了一个具体的可以有效计算的置换。除了计算效率上的要求以外，一个理想的分组密码方案还要求它所代表的置换族尽可能地随机。为了刻画分组密码的随机特性，Luby和Rackoff Michael Luby and Charle

4、s Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Jorunal on Computing, 1988, 17(2):373386.提出了“伪随机置换”和“超伪随机置换”的概念；并在假定轮函数为伪随机函数的基础上，利用平衡的Feistel结构 Horst Feistel. Cryptography and Computer Privacy. Scientific American, 1973, 228(5):1523.给出了一个伪随机置换和一个超伪随机置换的实例。对于平

5、衡的Feistel结构，人们已经做了很多的研究工作：自Luby和Rackoff的工作开始，首先Maurer用概率的方法简化了Luby和Rackoff的证明，并且提出了“局部随机”的概念 Ueli M. Maurer. A simplified and generalized treatment of Luby-Rackoff pseudorandom permutation generators. In: Advances in Cryptology - EUROCRYPT 92, LNCS 658, Berlin, Springer-Verlag, 1992, 239255. ；后来Naor

6、在保证其伪随机性和超伪随机性的前提下，弱化了Luby-Rackoff结构中对第一轮和第四轮轮函数的要求，并进一步提出了一种框架结构1；还有很多人分析如何使用较少的伪随机函数结合平衡的Feistel结构构造伪随机置换，如 Yuliang Zheng, Tsutomu Matsumoto, and Hideki Imai. Impossibility and Optimally Results on Constructing Pseudorandom Permutations (Extended Abstract). In: Advances in Cryptology - EUROCRYPT 8

7、9, LNCS 434, Berlin, Springer-Verlag, 1989, 412422. Babak Sadeghiyan and Jsef Pieprzyk. On Necessary and Sufficient Conditions for the Construction of Super Pseudorandom Permutations. In: Advances in Cryptology - ASIACRYPT 91, LNCS 739, Berlin, Springer-Verlag, 1991, 194209. Babak Sadeghiyan and Jse

8、f Pieprzyk. A Construction for Super Pseudorandom Permutations from A Single Pseudorandom Function. In: Advances in Cryptology - EUROCRYPT 92, LNCS 658, Berlin, Springer-Verlag, 1992, 267284. Jsef Pieprzyk. How to construct pseudorandom permutations from single pseudorandom functions. In: Advances i

9、n Cryptology - EUROCRYPT 90, LNCS 473, Berlin, Springer-Verlag, 1990, 140150 Jacques Patarin. How to Construct Pseudorandom and Super Pseudorandom Permutations from One Single Pseudorandom Function. In: Advances in Cryptology - EUROCRYPT 92, LNCS 658, Berlin, Springer-Verlag, 1992, 256266.等；而Maurer等

10、在降低对轮函数的要求的前提下，分析了多轮平衡Feistel结构的安全性 Ueli M. Maurer, Yvonne Anne Oswald, Krzysztof Pietrzak, and Johan Sjodin. Luby-Rackoff Ciphers from Weak Round Functions? In: Advances in Cryptology - EUROCRYPT 06, LNCS 4004, Berlin, Springer-Verlag, 2006, 391408.；与此相关的其他工作还有 Sarvar Patel, Zulfikar Ramzan, and Ga

11、napathyS. Sundaram. Towards Making Luby-Rackoff Ciphers Optimal and Practical. In: Fast Software Encryption - FSE99, LNCS 1636, Berlin, Springer-Verlag, 1999, 171185. Jacques Patarin. Luby-Rackoff: 7 Rounds Are Enough for Security. In: Advances in Cryptology - CRYPTO03, LNCS 2729, Berlin, Springer-V

12、erlag, 2003, 513529. Jacques Patarin. Security of Random Feistel Schemes with 5 or More Rounds. In: Advances of Cryptology - CRYPTO04, LNCS 3152, Berlin, Springer-Verlag, 2004, 106122. Jacques Patarin. About Feistel Schemes with Six (or More) Rounds. In: Fast Software Encryption - FSE98, LNCS 1372,

13、Berlin, Springer-Verlag, 1998, 103121. Jacques Patarin. Improved security bounds for pseudorandom permutations. In: Proceedings of the 4th ACM Conference on Computer and Communications Security, Zurich, Switzerland, 1997, 142150.等。后来，人们希望设计分组长度更大的分组密码方案，以便一次能够处理更多的信息，但是发现平衡的Feistel结构有其无法避免的缺陷：轮函数输入与

14、输出的长度随着分组长度而增加，给算法设计带来诸多困难。于是有人开始逐步演化平衡的Fesitel结构，提出了各种类型的非平衡Feistel结构（UFN），设计了一些密码算法，并对其做了深入的分析，如 Bruce Schneier and John Kelsey. Unbalanced Feistel Networks and Block Cipher Design. In: Fast Software Encryption - FSE 96, LNCS 1039, Berlin, Springer-Verlag, 1996, 121144. Lawrie Brown and Jsef Piepr

15、zyk. Introducing the new LOKI97 Block Cipher. First AES Candidate Conference, Ventura, USA, 1998, 2022. Matt Blaze and Bruce Schneier. The Macguffin block cipher algorithm. In: Fast Software Encryption - FSE94, LNCS 1008, Berlin, Springer-Verlag, 1994, 97110. Ross Anderson and Eli Biham. Two Practic

16、al and Provably Secure Block Ciphers: BEAR and LION. In: Fast Software Encryption - FSE96, LNCS 1039, Berlin, Springer-Verlag, 1996, 113120. Vincent Rijmen and Bart Preneel. Cryptanalysis of McGuffin. In: Fast Software Encryption - FSE94, LNCS 1008, Berlin, Springer-Verlag, 1994, 353358. Stefan Luck

17、s. Faster Luby-Rackoff Ciphers. In: Fast Software Encryption - FSE 96, LNCS 1039, Berlin, Springer-Verlag, 1996, 189203. CharanjitS. Jutla. Generalized Birthday Arracks on Unbalanced Feistel Networks. In: Advances in Cryptology - CRYPTO 98, LNCS 1462, Berlin, Springer-Verlag, 1998, 186199. David A.

18、Wagner. The Security of Macguffin. Senior thesis, Princeton University, 1995. Jacques Patarin, Valrie Nachef, and Come Berbain. Generic Attacks on Unbalanced Feistel Schemes with Contracting Functions. In: Advances in Cryptology - ASIACRYPT06, LNCS 4284, Berlin, Springer-Verlag, 2006, 396411.等。使用压缩函

19、数的非平衡Feistel结构（UFN-C）就是在平衡Fesitel结构的基础上发展而来的。它与平衡Fesitel结构类似，也是一个多轮迭代结构，并且在每一轮中使用一个轮函数。它们的不同点在于：平衡Fesitel结构中使用的轮函数是对称的，即其输入长度与输出长度一致；而使用压缩函数的非平衡Feistel结构中的轮函数不是对称的，它们的输出长度小于输入长度。图1是一轮UFN-C的结构，其中：，表示两个长比特串相异或。轮UFN-C即在每一轮重复使用这种结构，上一轮的输出是下一轮的输入；只是每一轮使用的压缩函数可能不同。从总体来看，UFN-C仍然是一个输入与输出等长度的置换。人们使用UFN-C结构不但

20、设计了许多分组密码算法，如MacGuffin19，BEAR，LION20等，还设计了HASH函数如MDx Ronald Rivest. The MD5 Message Digest Algorithm, RFC 1321. IETF, 1992.，SHA-x PUB FIPS 180-1. Secure Hash Standard, 1995.系列。但是，相比较于平衡的Feistel结构，目前人们对UFN-C结构的研究还比较少。Naor和Reingold在他们提出的框架下，对一个更一般化的UFN-C做了可证明安全方面的分析，得到了比平衡的Feistel结构更好的界1；Patarin在25中提出

21、了几种对UFN-C的一般攻击。我们从可证明安全的角度分析UFN-C，在1的基础上，减少了要达到伪随机和超伪随机要求UFN-C所必需的伪随机函数的个数；并且研究了一类特殊UFN-C结构SMS4-like的伪随机性和超伪随机性，为设计、分析与使用SMS4-like结构的分组密码算法提供了参考依据。本文安排如下：第2部分介绍一些必需的预备知识，包括基本的符号说明、定义，可证明安全理论中的伪随机性、超伪随机性、敌手、区分优势等概念及其相互的联系；第3部分介绍我们分析UFN-C的主要结论；然后在第4部分中介绍关于SMS4-like的伪随机性和超伪随机性的的结论及一些攻击；在随后的第5部分中，我们总结本文

22、的主要成果，并提出未解决的问题以及有待以后继续研究的方向。2 预备知识2.1 符号说明与定义表示从到所有置换的集合；表示一个在第（）轮中使用压缩轮函数的比特轮非平衡Fesitel结构（，为明文分组数，为每个分组的长度，（）可以看作是由决定的中的一个随机置换族。表示从上均匀随机选取的一个置换。表示从到所有函数的集合，表示从集合中相互独立且均匀随机地选取；表示第轮使用轮函数的平衡Feistel结构。定义 1 Shafi Goldwasser and Mihir Bellare. Lecture notes on cryptography. Summer Course Cryptography an

23、d Computer Security at MIT, 1996-1999, 1999.：是一个可忽略函数，如果对于任意常数，都存在一个整数满足：，。定义 2 Phillip Rogaway. Bucket Hashing and its Application to Fast Message Authentication. In: Advances in Cryptology - CRYPTO 95, LNCS 963, Berlin, Springer-Verlag, 1995, 2942.：是一个密钥长度为的函数族，。如果满足：，那么称为-XOR泛哈希函数族。2.2 伪随机性和超伪随机性

24、假定是具有某种密码结构的一类置换（比如说，敌手是一个攻击者，它面对一个问答机。以相等的概率从或中随机地选取置换，然后接受敌手的查询。我们假定敌手的计算能力不受限制，但是它向问答机查询的次数受限制。敌手的目标是：在查询问答机一定次数后，给出一个判定问答机选取的置换是属于还是。如果问答机只允许敌手进行正向查询（第次查询中，任取，向查询，返回），那么称敌手是一个选择明文攻击者（cpachosen plaintext attacker）；如果问答机不但允许敌手进行正向查询，还允许其进行反向查询（第次查询中，可以任取，向查询，返回；也可以任取，向解密问答机查询，返回，但是要求，），那么称敌手是一个选择密

25、文攻击者（ccachosen ciphertext attacker）。这里限制，的原因是：本文所考察的密码结构及其理想模型都是确定性算法，所以敌手重复查询只会得到重复答案，对其区分优势没有任何帮助。如果限制敌手在第一次查询问答机之前就已经准备好所有要查询的问题，那么称敌手是非自适应的；如果允许敌手分析前面的查询结果，再给出下一次要查询的问题，那么称敌手是自适应的。我们把非自适应选择明文攻击简写为，自适应选择明文攻击简写为；同样地，把非自适应选择密文攻击简写为，自适应选择密文攻击简写为。为了定义敌手在查询问答机（或和）后，得到的区分和的优势，我们考虑下面两个实验： 其中表示从的密钥空间里均匀随

26、机地选取一个密钥（在中，密钥即决定了）；表示对回答的结果进行分析，并输出一个比特；和的含义与前者类似。定义敌手区分置换和的优势为：对所有查询次数最多为的敌手，定义区分置换和的优势为：即区分置换和的优势是在所有查询次数最多为的敌手中，区分置换和的优势的最大值。如果对于所有的（或）敌手而言，它们区分和的优势是一个可忽略函数，那么称是伪随机的；如果对于所有的（或）敌手而言，它们区分和的优势是一个可忽略函数，那么称是超伪随机的。定义 3：表示相互独立的伪随机函数，表示相互独立的随机函数，其中与的定义域与值域相同。引理 1：设是一个在第轮中使用轮函数的迭代结构的分组密码方案，；如果，（），（，）那么关于

27、引理 1的证明可参阅1。3 UFN-C结构的可证明安全性3.1 轮的UFN-C都不是伪随机的定理 1：，那么存在一个敌手，使得区分和的优势满足：。证明：根据UFN-C处理明文分组的特点，注意到：，我们构造一个敌手：1）任意选取一个明文；2）根据构造第二个明文，其中；3）向分别查询和，得到密文和；4）验证是否成立，若成立输出1，否则输出0。分析：如果从中随机选取了一个置换，那么在第4步中，所以；如果从中随机选取了一个置换，那么在第4步中，所以。所以，其中。由此可见，不是伪随机的。3.2 轮UFN-C是伪随机的，轮UFN-C是超伪随机的定理 2：，且，（），那么对所有不限计算能力的敌手，它们区分和

28、的优势满足：；对所有不限计算能力的敌手，它们区分和的优势满足：。在此基础上，我们可以使用-XOR泛哈希函数族弱化的第一轮，的首尾两轮，同样构造伪随机置换和超伪随机置换。定理 3：从一个-XOR泛哈希函数族（）中分别独立选取两个函数和，若，且，（），那么对所有不限计算能力的敌手，它们区分和的优势满足：；对所有不限计算能力的敌手，它们区分和的优势满足：。更进一步地，我们可以减少这类结构中使用伪随机函数的个数，有下面的定理：定理 4：从一个-XOR泛哈希函数族（）中分别独立选取两个函数和，从中选取伪随机函数（），轮，轮，那么对所有不限计算能力的敌手，它们区分和的优势满足：；对所有不限计算能力的敌手，

29、它们区分和的优势满足：。下面通过三个引理证明定理 4中超伪随机的情况，对于伪随机的情况，其证明方法与之类似而且更加简单，此处不在赘述。表示向加密问答机查询时，回答，此次查询记作，；表示向解密问答机查询时，回答，此次查询记作，；根据攻击的要求，第次向加密问答机查询时，应该满足：，；第次向解密问答机查询时，应该满足：，。敌手向问答机或查询或，并且对所有次查询结果进行分析。因为我们对的计算能力不作任何限制，而仅仅限制它向问答机或查询的次数，所以可以把当作一个确定性算法如果是一个概率算法，我们可以将其修改成一个确定性算法让遍历所有可能的情况，并做出获益最大的选择。这就意味着：，即第次向问答机查询的问题

30、，完全由前面次查询的问题和结果所确定；再约定。若是一个可能的查询序列，则必须满足：，。，表示从上相互独立地均匀随机选取的两个函数，轮；表示敌手向问答机和查询得到的序列，表示敌手向问答机和查询得到的序列，表示敌手向问答机和查询得到的序列；表示满足的任意一个可能的且满足查询要求的查询序列（显然可以表述为，其中，。表示所有的集合；事件，即事件表示中的所有元素中，各不相等且各不相等的元素。引理 2：。 证明：注 意：式3.1中，在事件发生的条件下，与的表现完全一致，所以；式3.2中，而不是，这是因为敌手不能重复查询，所以，或者，或者。若是一个向问答机和查询得到的序列，令集合，即集合表示所有满足下面要求

31、的的集合：中至少存在两次查询，这两次查询的加密过程中，；集合，即集合表示所有满足下面要求的的集合：中至少存在一次查询，这次查询加密过程中的和前面某个相等（；集合，即集合表示所有满足下面要求的的集合：中至少存在两次查询，这两次查询的解密过程中，；集合。引理 3：。 证明：首先我们分析向问答机和查询得到的序列：注意，是从-XOR泛哈希函数族（）中分别独立选取的两个函数，并且是一个满足查询要求的查询序列（即可以表述为，其中，），注意到，所以可类似得出；而是从上均匀随机选取的一个函数，显然然后考虑所以，所以，注 意：式3.3中，当时，中的个轮函数的整体表现和的表现完全一致，所以。 综上，我们可以证明：

32、最后，根据引理 1我们完成定理 4中关于超伪随机性的证明如下：证明：注 意：式3.4中，的系数不是是因为定理4中只使用了一个伪随机函数。具体证明方法可参照1。定理4中，我们只使用一个伪随机函数，两个-XOR泛哈希函数就构造了一个伪随机置换和一个超伪随机置换。这个成果在理论上改进了1中类似结构对伪随机函数个数的要求，在实际中有助于设计密钥长度短而且实现效率高的安全分组密码算法。4 SMS4-like结构的可证明安全性4.1 SMS4-like结构使用压缩函数的非平衡Feistel结构UFN-C在实际应用中已经有所体现，比如说分组密码算法SMS42就是一个典型代表（图2）。SMS4的每轮明文分组数

33、，其中右边3个分组异或后作为该轮轮函数的输入。图2 一轮使用压缩函数的SMS4结构下面我们考虑SMS4结构的广义形式：SMS4-like结构。如图3所示：SMS4-like结构没有像SMS4结构那样限制明文分组数，但是仍然保留了SMS4结构中将右边个明文分组先异或再输入到轮函数的特点。图3 一轮使用压缩函数的SMS4-like结构4.2 SMS4-like结构的伪随机性和超伪随机性分析4.2.1 为奇数时，SMS4-like结构不是伪随机的定理 5：明文分组个数为奇数，定义表示在第（）轮中使用轮函数的轮SMS4-like结构，那么存在一个敌手，使得区分和的优势满足：证明：利用轮函数处理的明文分

34、组个数为偶数的特点，我们构造一个敌手：1）选取一个明文，其中，（）为任意常数；2）根据构造第二个明文，其中，；3）向加密问答机分别查询和，得到密文和；4) 验证是否成立，若成立输出1，否则输出0。分析：如果从中随机选取了一个置换，那么在第4步中，所以；如果从中随机选取了一个置换，那么在第4步中，所以。所以，其中。4.2.2 为偶数时，轮SMS4-like结构是伪随机的定理 6：明文分组个数为偶数，且，。定义表示在第（）轮中使用轮函数的轮SMS4-like结构，那么对所有不限计算能力的敌手，它们区分和的优势满足：。证明：根据SMS4-like结构处理消息的特点，为了叙述方便，首先对输入的明文做一

35、个置换：即，。所以有，特别注意：表示向加密问答机查询时，回答，此次查询记作，；根据攻击的要求，第次向查询时，应该满足：，。若是一个可能的查询序列，则必须满足：，。敌手，事件的定义如前所述。，表示敌手向查询得到的序列，表示敌手向查询得到的序列，表示敌手向查询得到的序列。令集合首先根据引理2，我们有。下面考虑注 意：式4.1中，当时，考虑到，是相互独立的随机函数，所以，的整体表现和的表现完全一致，所以。综上，我们可以证明：最后，我们可以完成定理6的证明如下：证明：所以，轮SMS4-like结构是伪随机的；特别地，在，是相互独立的伪随机函数的基础上，7轮SMS4结构是伪随机的。4.2.3 为偶数时，

36、轮SMS4-like结构不是伪随机的定理 7：明文分组个数为偶数，定义表示在第（）轮中使用轮函数的轮SMS4-like结构，那么存在一个敌手，使得区分和的优势满足：证明：根据SMS4-like结构处理明文分组的特点， 特别注意：由此我们构造一个敌手：1）任意选取一个明文；（注意为偶数，的转置矩阵，逆矩阵。）2）根据构造第二个明文，其中；3）向分别查询和，得到密文和；4）验证是否。分析：如果从中随机选取了一个置换，那么在第4步中，所以；如果从中随机选取了一个置换，那么在第4步中，所以。所以，其中。4.2.4 为偶数时，轮SMS4-like结构是超伪随机的定理 8：明文分组个数为偶数，定义，其中，

37、。定义表示在第（）轮中使用轮函数的轮SMS4-like结构，那么对所有不限计算能力的cca-2敌手，它们区分（，）和（，）的优势满足：关于定理8的证明，可以用定理4中对超伪随机性的证明方法完成，此处不再赘述。特别地，在，是相互独立的伪随机函数的基础上，10轮SMS4结构是超伪随机的。注 意：文3中“3轮平衡Feistel结构是伪随机，4轮平衡Feistel结构是超伪随机”的结论正是当时，定理2和定理6、8的特例；所以定理2和定理6、8是3中主要结论的推广。5 结论和后续工作5.1 结论本文利用可证明安全技术分析了使用压缩函数的非平衡Feistel结构UFN-C的伪随机性和超伪随机性，并证明轮是

38、伪随机的，轮是超伪随机的，这个结果降低了Naor和Reingold对伪随机函数个数的要求1；然后，我们分析了SMS4-like结构的伪随机性和超伪随机性，为设计、分析与使用该类分组密码提供了可证明安全的理论依据。5.2 后续工作1）在， ，是相互独立的伪随机函数的基础上，是否是一个超伪随机置换？若是，试用可证明安全技术给予证明；若否，请给出一个攻击，以较大的概率将其与随机置换相区分。对此，我们猜测不是超伪随机的。我们的依据是攻击是双向的，这一特点在证明超伪随机性的过程中体现出来为了抵抗攻击，密码结构往往是前后“对称”的，比如说轮中的与（个保证了其随机性）。而在除去了个随机函数之后，就无法前后“

39、对称”了。但是又如何对此给出一个攻击呢？2），鉴于对SMS4-like结构的研究有更多的现实价值，我们可以进一步弱化密码结构对底层函数的要求，得到更深入的结果，为设计与使用该类结构的分组密码提供深入的可证明安全技术的理论保障。Pseudorandomness and Super Pseudorandomness on the Unbalanced Feistel Networks with Contracting FunctionsZHANG Li-Ting, WU Wen-LingState Key Laboratory of Information Security, Institute

40、of Software, Chinese Academy of Sciences, Beijing 100190State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, Beijing 100049Abstract The structure of a block cipher is one of the most important factors in its security. A good structure is able to protect t

41、he block cipher, while a bad one may induce some secret information leak out. Based on the former study of Balanced Feistel Networks, we study Unbalanced Feistel Networks with Contracting Functions (UFN-C) by provable security techniques. As a result, we prove that UFN-C with rounds is pseudorandom,

42、 and UFN-C with rounds is super pseudorandom. Furthermore, we simplify the necessary conditions step by step, and finally get that -round is pseudorandom and -round is super pseudorandom, which reduces the number of pseudorandom functions needed in Naor and Reingolds similar structure1. And then, co

43、nsidering that a special UFN-C called SMS42 has already been used in practice, we analyze its generalized form called SMS4-like structure. It is showed that as long as the number of blocks in each round is odd, SMS4-like is not pseudorandom, no matter how many rounds it runs; however, if is even, -r

44、ound SMS4-like is pseudorandom and -round is super pseudorandom. Thus, using provable security techniques we give some instructions in theory to design and employ block ciphers of this form.Key Words Pseudorandomness; Super Pseudorandomness; Contracting Functions; Unbalanced Feistel Network; SMS4.Ba

45、ckground 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 or

46、der to catch such a character, Luby and Rackoff3 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

47、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