It is known that a super-pseudorandom permutation on 2n bits can be obtained from a random function f on n bits and two bisymmetric and AXU hash functions h
1 and h
2 on n bits. It has a Feistel type structure which is usually denoted by ø (h
1, f, f,h
2). Bi-symmetric and AXU hash functions h
1, h
2 are muchw eaker primitives than a random function f and they can be computed much faster than random functions. This paper shows that we can further weaken the condition on
h
1.
Keywords Block/Stream Ciphers - Provable Security - Cryptographic - Primitives