Existence Of Costas Arrays, Counting Problems And Its Applications In Cryptography

A cryptography system without information expansion may be viewed as the product of permutations. Costas arrays, special permutation matrices, derive from radar signal design. There is one-to-one mapping between Costas arrays and permutations. After dimension being descended, Costas arrays produce Costas sequences which are special permutations. In modern cryptography, a public-key system is based on a certain hard mathematical problem. Existence problem and counting problem of Costas arrays remain unsolved yet, and become hard mathematical problems. Concentrating on existence problem and counting problem of Costas arrays and its cryptographic application, three achievements have been obtained in this thesis.1. A lacked necessary condition of extended Golomb construction was given, and stochastic algorithms were applied to existence detection of Costas arrays. Firstly, extended Golomb construction was studied. The extension was lack of a necessary condition and the condition was given. Algebraic methods could construct infinitely many orders of Costas arrays, but did not work on part of orders. Thus the existence of Costas arrays for some orders was not known. Computer enumeration could detect the existence of Costas arrays, which took exponential time. To avoid high complexity, existence detection was thought as an optimization problem, and an optimization model was developed. On model solution, SAACAS, GACAS and GPSOCAS were presented respectively based on simulated annealing algorithm, genetic algorithm and general particle swarm optimization which were stochastic algorithms. The experiment result preliminarily showed that three algorithms were effective for detection of Costas arrays whose orders were lower than 18.2. The relation between number of Costas arrays and number of symmetric ones was disclosed, and the existented sequential search algorithm of Costas arrays was improved and parallelized. Counting problem of symmetric Costas arrays was studied and relation formula was obtained. The formula disclosed the relation between number of symmetric Costas arrays for a certain order and number of Costas arrays for the same order. Existented enumeration algorithms were based on backtracking, and determined further search or backtracking by computing difference of the permutation. Focusing on computing, storing necessary difference and checkouting repetition, the thesis improved the algorithm and proved correlative theorems. The improved algorithm was parallelized, and the parallel algorithm had linear speedup and scalability.3. A digital signature scheme based on Costas arrays was constructed, and Costas arrays were applied to Shamir knapsack signature scheme, Niederreiter public-key system and S-boxes. Constructing Costas arrays took exponential time, but checkouting whether a permutation matrix was a Costas array or not took polynomial time. So Costas arrays were difficult to construct but easy to checkout. Based on this property, a digital signature scheme was designed. Based on low density, Costas arrays were applied to Shamir knapsack signature scheme and Niederreiter public-key system, and their security was enhanced. S-boxes were the only nonlinear components in many block ciphers. So, their cryptographic properties had determined the security of the whole cipher algorithms. An n-order bijection S-box could be regard as a permutation of all integers between 0 and 2n-1. The thesis presented that Costas arrays could be initial S-boxes for evolution to get S-boxes with better cryptographic properties, and provided abundant nonlinear resources for the further design of symmetric cryptographic algorithms.