Costas arrays exist , counting problems in cryptography 

Author  LiuTao 
Tutor  YinXinChun 
School  Yangzhou University 
Course  Applied Computer Technology 
Keywords  COSTAS ARRAYS EXISTENCE PROBLEM COUNTING PROBLEM SIMULATED ANNEALING ALGORITHM GENETIC ALGORITHM GENERAL PARTICLE SWARM OPTIMIZATION DIGITAL SIGNATURE SCHEME NIEDERREITER PUBLICKEY SYSTEM SBOXES 
CLC  TN918.1 
Type  Master's thesis 
Year  2007 
Downloads  53 
Quotes  0 
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 onetoone mapping between Costas arrays and permutations. After dimension being descended, Costas arrays produce Costas sequences which are special permutations. In modern cryptography, a publickey 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 publickey system and Sboxes. 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 publickey system, and their security was enhanced. Sboxes were the only nonlinear components in many block ciphers. So, their cryptographic properties had determined the security of the whole cipher algorithms. An norder bijection Sbox could be regard as a permutation of all integers between 0 and 2n1. The thesis presented that Costas arrays could be initial Sboxes for evolution to get Sboxes with better cryptographic properties, and provided abundant nonlinear resources for the further design of symmetric cryptographic algorithms.