Study On The One-wayness Of Cryptographic Functions

Cryptography aims to study on the security of communication in the presence of adversaries.Secure cryptographic algorithm can make two parties in communication simple to encrypt the message,while the adversaries are hard to decrypt the message.This property is one-wayness.One-way functions,especially those are also permutations,have many important cryptographic applications.However,the existence of one-way functions is not proved.Widely-accepted one-way permutations are not artificially constructed.Thus,finding one-way functions is an unsolved fundamental problem in cryptography.Orthomorphic permutations have a similar structure with DaviesMeyer construction,which is a method to construct one-way functions.Orthomorphic permutations have good properties on differential analysis.Its algebraic degree can be used to characterize the resistance to higher order difference analysis.Compared with previous works,we propose a new method for the construction of orthomorphic permutations with the highest degree.This construction has the best resistance to higher order difference analysis.We generalize the construction and give the number of orthomorphic permutations constructed by this method.We also study on the one-wayness of these constructed orthomorphic permutations with the highest degree.We find they are still not a candidate of artificially constructed one-way permutations.In order to further study on the one-wayness of cryptographic functions,we also study on the one-wayness of cryptographic functions under nonuniform computational models.Security under non-uniform computational models is more in line with the security requirements of cryptographic functions.We propose an algorithm which enumerates all the gate circuit implementations and meanwhile returns the gate complexity of any Boolean functions.After implementing the algorithm on Spark,a distributed computing framework,due to the complexity of the algorithm and computing power constraints,we still cannot solve the problem on the existence of hard functions.PRESENT is an ultra-lightweight block cipher,mainly used in micro computing devices.Therefore,simplicity of its hardware implementation is of great importance.In the design documentation of PRESENT,the gate circuit complexity of the S-box is 28.Based on the results of the previous work,we propose a better gate circuit implementation of the S-box in PRESENT.This implementation involves 21 gates.For the hardware implementation of the entire PRESENT,our improvement can save the hardware space for roughly 7.14 percent.