Candidate
Kalikinkar Mandal
Title
Cryptographic D-morphic Analysis and Fast Implementations of Composited De Bruijn Sequences
Supervisor
Gong, Guang
Abstract
Recently, Mandal and Gong refined and analyzed the composition method by Lempel and Mykkeltveit et al. for generating de Bruijn sequences where a composited feedback function is the sum of a feedback function with k-th order composition and a sum of (k+1) product-of-sum terms. A de Bruijn sequence produced by the composition method is called a composited de Bruijn sequence. In this talk we first present the linear complexity of a composited de Bruijn sequence. We then conduct a profound analysis of the composited construction by introducing the notion of higher order D-morphism of binary sequences where both linearly and nonlinearly generated composited de Bruijn sequences are taken into consideration. In the analysis, we discover the existence of many k-th order D-morphic order n de Bruijn preimages ((n,k)-DMDPs in brief) of length (2^n+k) and k-th order D-morphic order n m-sequence preimages ((n,k)-DMMPs in brief) of length (2n+k) in a nonlinearly and linearly generated composited de Bruijn sequence, respectively. The main objective of our analysis is the reconstruction of a composited de Bruijn sequence from an (n,k)-DMDP/(n,k)-DMMP. We formally show that an (n,k)-DMDP/(n,k)-DMMP is a vulnerable segment of a composited de Bruijn sequence as it allows one to first recover the feedback function and then reconstruct the composited de Bruijn sequence. We determine the exact number of (n,k)-DMDPs/(n,k)-DMMPs in a composited de Bruijn sequence and calculate the success probability of obtaining an (n,k)-DMDP/(n,k)-DMMP from a composited de Bruijn sequence. Based on our analysis, we propose some selection criteria of parameters for producing strong de Bruijn sequences by the composition method. Furthermore, we present a new iterative technique with its parallel extension for computing the product-of-sum terms of the feedback function where a product-of-sum term is calculated in an iteration. In addition, we present three de Bruijn sequences of period 2^{64} together with their software implementations and performances.