Almost P-Ary Perfect Sequences And Their Applications To Cryptography

Abstract

In this thesis we study almost p-ary sequences and their autocorrelation coefficients. We first study the number L of distinct out-of-phase autocorrelation coefficients for an almost p-ary sequence of period n + s with s consecutive zero-symbols. We prove an upper bound and a lower bound on L. It is shown that L can not be less than min{s, p, n}. In particular, it is shown that a nearly perfect sequence with at least two consecutive zero symbols does not exist. Next we define a new difference set, partial direct product difference set (PDPDS), and we prove the connection between an almost p-ary nearly perfect sequence of type (γ1, γ2) and period n + 2 with two consecutive zero-symbols and a cyclic (n + 2, p, n, (n−γ2−2)/p + γ2, 0, (n−γ1−1)p + γ1,(n−γ2−2)/p,(n−γ1−1)/p) PDPDS for arbitrary integers γ1 and γ2. We show that the almost p-ary sequences of type (γ1, γ2) and period n + 2 with two consecutive zero-symbols are symmetric sequences except for zero entries. Then we prove a necessary condition on γ2 for the existence of such sequences. In particular, we show that they don’t exist for γ2 ≤ −3. Perfect sequences are very important for achieving non-linearity in a cryptosystem, and they are important in Code Division Multiple Access (CDMA) to ensure a proper communication. In this thesis, we show a method for obtaining cryptographic functions from almost p-ary nearly perfect sequences (NPS) of type (γ1, γ2). In fact, most of the cases we obtain functions with the highest non-linearity, i.e. generalized bent functions. We use almost p-ary NPS of type (γ1, γ2) in CDMA communication. We simulate the bit-error-rate (BER) performance of CDMA with these sequences.