On The Constructions Of Super-Pseudorandom Permutations And Security Proof

The theory of pseudorandomness is one of the important theory foundations of modern cryptography, and permutation theory plays an important role in studying and designing of block cipher. In essence, stream cipher is such a pseudorandom generator that its chaos sequence of output and random sequence are computational indistinguishability; and the aim in designing block cipher materially is to design a pseudorandom permutation which is computationally indistinguishable from random permutations.Using the theories of probability, algebra, cryptography, Information theory and "Hybrid technique" and "Reduction theory" as tools, and basing on the notion of computational indistinguishability, properties and constructions of DES-model permutations are studied in this dissertation and some useful conclusions are given. First a review of history of researching DES-model permutations is given. Then some pseudorandom properties of DES-model permutations are discussed. At last we put more efforts on the construction of 4-round DES-model super-pseudorandom permutations and proof of its security. The result obtained in this thesis offers some new ideas and methods for studying of permutation theory in cipher system. The main contributions of this dissertation are as follows:1) The pseudorandom properties of DES-model permutation are studied. The relationships between pseudorandomness and unpredictability -, one-way function; Pseudorandom generator and pseudorandom function are also studied.2) A new construction of super pseudorandom permutation that is of four-round DES-model is given which is efficient in terms of computations and key material used.3) A new construction of super pseudorandom permutations based on the rotation Permutations and DES-permutations is presented, which reduces somewhat the complexity of construction and simplify its proof of security based on the Random Oracle Model by showing that two DES-model permutations is sufficient to be super-pseudorandom permutation together with initial and final rotation permutations. The revised construction reduces the success probability of the adversary and the upper bound of advantage and also requirements of the first and the end functions. And the upper bound of advantage decreased by m2/2~2n.4) The construction is generalized, and security can be easily proved in the general framework.