Almost p-ary perfect sequences and their applications to cryptography

In this thesis we study almost $p$-ary sequences and their autocorrelation coefficients. We first study the number $\ell$ 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 $\ell$. It is shown that $\ell$ 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 $(\gamma_1, \gamma_2)$ and period $n+2$ with two consecutive zero-symbols and a cyclic $\left(n+2,p,n,\frac{n-\gamma_2 - 2}{p}+\gamma_2,0,\frac{n-\gamma_1 -1}{p}+\gamma_1,\frac{n-\gamma_2 - 2}{p},\frac{n-\gamma_1 -1}{p}\right)$ PDPDS for arbitrary integers $\gamma_1$ and $\gamma_2$. We show that the almost $p$-ary sequences of type $(\gamma_1,\gamma_2)$ and period $n+2$ with two consecutive zero-symbols are symmetric sequences except for zero entries. Then we prove a necessary condition on $\gamma_2$ for the existence of such sequences. In particular, we show that they don't exist for $\gamma_2 \leq -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 $(\gamma_1,\gamma_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 $(\gamma_1,\gamma_2)$ in CDMA communication. We simulate the bit-error-rate (BER) performance of CDMA with these sequences.