Evolutionary heuristics for finding cryptographically strong s-boxes

Recent advances are reported in the use of heuristic optimisation for the design of cryptographic mappings. The genetic algorithm (GA) is adapted for the design of regular substitution boxes (s-boxes) with relatively high nonlinearity and low autocorrelation. We discuss the selection of suitable GA parameters, and in particular we introduce an effective technique for breeding s-boxes. This assimilation operation, produces a new s-box which is a simple and natural compromise between the properties of two dissimilar parent s-boxes. Our results demonstrate that assimilation provides rapid convergence to good solutions. We present an analysis comparing the relative effectiveness of including a local optimisation procedure at various stages of the CA. Our results show that these algorithms find cryptographically strong s-boxes faster than exhaustive search.