Evolutionary Construction of de Bruijn Sequences

Meltem Sonmez Turan

Paper 2011/711

Evolutionary Construction of de Bruijn Sequences

Meltem Sonmez Turan

Abstract

A binary de Bruijn sequence of order $n$ is a cyclic sequence of period $2^{n}$ , in which each $n$ -bit pattern appears exactly once. These sequences are commonly used in random number generation and symmetric key cryptography particularly in stream cipher design, mainly due to their good statistical properties. Constructing de Bruijn sequences is of interest and well studied in the literature. In this study, we propose a new randomized construction method based on genetic algorithms. The method models de Bruijn sequences as a special type of traveling salesman tours (TSP) and tries to find optimal solutions. We present some experimental results for $n \leq 14$ .

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Previous version of this paper was published in AISec’11, October 21, 2011, Chicago, Illinois, USA
Keywords: De Bruijn sequences Genetic algorithms Traveling salesman problem
Contact author(s): meltemsturan @ gmail com
History: 2011-12-31: received
Short URL: https://ia.cr/2011/711
License: CC BY

BibTeX

@misc{cryptoeprint:2011/711,
      author = {Meltem Sonmez Turan},
      title = {Evolutionary Construction of de Bruijn Sequences},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/711},
      year = {2011},
      url = {https://eprint.iacr.org/2011/711}
}