
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Linear Complexity of Geometric Sequences Defined by Cyclotomic Classes and Balanced Binary Sequences Constructed by the Geometric Sequences
Kazuyoshi TSUCHIYA Chiaki OGAWA Yasuyuki NOGAMI Satoshi UEHARA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E101A
No.12
pp.23822391 Publication Date: 2018/12/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E101.A.2382
Type of Manuscript: Special Section PAPER (Special Section on Signal Design and Its Applications in Communications) Category: Cryptography and Information Security Keyword: pseudorandom number generator, geometric sequence, linear complexity, balance property, interleaved sequence,
Full Text: PDF(1.4MB)>>
Summary:
Pseudorandom number generators are required to generate pseudorandom numbers which have good statistical properties as well as unpredictability in cryptography. An msequence is a linear feedback shift register sequence with maximal period over a finite field. Msequences have good statistical properties, however we must nonlinearize msequences for cryptographic purposes. A geometric sequence is a sequence given by applying a nonlinear feedforward function to an msequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol, and showed the period, periodic autocorrelation and linear complexity of the sequence. Furthermore, Nogami et al. proposed a generalization of the sequence, and showed the period and periodic autocorrelation. In this paper, we first investigate linear complexity of the geometric sequences. In the case that the ChanGames formula which describes linear complexity of geometric sequences does not hold, we show the new formula by considering the sequence of complement numbers, Hasse derivative and cyclotomic classes. Under some conditions, we can ensure that the geometric sequences have a large linear complexity from the results on linear complexity of Sidel'nikov sequences. The geometric sequences have a long period and large linear complexity under some conditions, however they do not have the balance property. In order to construct sequences that have the balance property, we propose interleaved sequences of the geometric sequence and its complement. Furthermore, we show the periodic autocorrelation and linear complexity of the proposed sequences. The proposed sequences have the balance property, and have a large linear complexity if the geometric sequences have a large one.

