Interleaved Sequences of Geometric Sequences Binarized with Legendre Symbol of Two Types

Kazuyoshi TSUCHIYA; Yasuyuki NOGAMI; Satoshi UEHARA

doi:10.1587/transfun.E100.A.2720

Interleaved Sequences of Geometric Sequences Binarized with Legendre Symbol of Two Types

Kazuyoshi TSUCHIYA, Yasuyuki NOGAMI, Satoshi UEHARA

Full Text Views

0

Share
Cite this

Summary :

A pseudorandom number generator is widely used in cryptography. A cryptographic pseudorandom number generator is required to generate pseudorandom numbers which have good statistical properties as well as unpredictability. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a binary sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol. They showed the geometric sequences have good properties for the period, periodic autocorrelation and linear complexity. However, the geometric sequences do not have the balance property. In this paper, we introduce geometric sequences of two types and show some properties of interleaved sequences of the geometric sequences of two types. These interleaved sequences have the balance property and double the period of the geometric sequences by the interleaved structure. Moreover, we show correlation properties and linear complexity of the interleaved sequences. A key of our observation is that the second type geometric sequence is the complement of the left shift of the first type geometric sequence by half-period positions.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.12 pp.2720-2727

Publication Date: 2017/12/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E100.A.2720

Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)

Category: Sequences

Authors

Kazuyoshi TSUCHIYA
  the Koden Electronics Co., Ltd.
Yasuyuki NOGAMI
  Okayama University
Satoshi UEHARA
  the University of Kitakyushu

Keyword

pseudorandom number generator, geometric sequence, balance property, interleaved sequence

Cite this

Copy

Kazuyoshi TSUCHIYA, Yasuyuki NOGAMI, Satoshi UEHARA, "Interleaved Sequences of Geometric Sequences Binarized with Legendre Symbol of Two Types" in IEICE TRANSACTIONS on Fundamentals, vol. E100-A, no. 12, pp. 2720-2727, December 2017, doi: 10.1587/transfun.E100.A.2720.
Abstract: A pseudorandom number generator is widely used in cryptography. A cryptographic pseudorandom number generator is required to generate pseudorandom numbers which have good statistical properties as well as unpredictability. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a binary sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol. They showed the geometric sequences have good properties for the period, periodic autocorrelation and linear complexity. However, the geometric sequences do not have the balance property. In this paper, we introduce geometric sequences of two types and show some properties of interleaved sequences of the geometric sequences of two types. These interleaved sequences have the balance property and double the period of the geometric sequences by the interleaved structure. Moreover, we show correlation properties and linear complexity of the interleaved sequences. A key of our observation is that the second type geometric sequence is the complement of the left shift of the first type geometric sequence by half-period positions.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.2720/_p

Copy

@ARTICLE{e100-a_12_2720,
author={Kazuyoshi TSUCHIYA, Yasuyuki NOGAMI, Satoshi UEHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Interleaved Sequences of Geometric Sequences Binarized with Legendre Symbol of Two Types},
year={2017},
volume={E100-A},
number={12},
pages={2720-2727},
abstract={A pseudorandom number generator is widely used in cryptography. A cryptographic pseudorandom number generator is required to generate pseudorandom numbers which have good statistical properties as well as unpredictability. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a binary sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol. They showed the geometric sequences have good properties for the period, periodic autocorrelation and linear complexity. However, the geometric sequences do not have the balance property. In this paper, we introduce geometric sequences of two types and show some properties of interleaved sequences of the geometric sequences of two types. These interleaved sequences have the balance property and double the period of the geometric sequences by the interleaved structure. Moreover, we show correlation properties and linear complexity of the interleaved sequences. A key of our observation is that the second type geometric sequence is the complement of the left shift of the first type geometric sequence by half-period positions.},
keywords={},
doi={10.1587/transfun.E100.A.2720},
ISSN={1745-1337},
month={December},}

Copy

TY - JOUR
TI - Interleaved Sequences of Geometric Sequences Binarized with Legendre Symbol of Two Types
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2720
EP - 2727
AU - Kazuyoshi TSUCHIYA
AU - Yasuyuki NOGAMI
AU - Satoshi UEHARA
PY - 2017
DO - 10.1587/transfun.E100.A.2720
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2017
AB - A pseudorandom number generator is widely used in cryptography. A cryptographic pseudorandom number generator is required to generate pseudorandom numbers which have good statistical properties as well as unpredictability. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a binary sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol. They showed the geometric sequences have good properties for the period, periodic autocorrelation and linear complexity. However, the geometric sequences do not have the balance property. In this paper, we introduce geometric sequences of two types and show some properties of interleaved sequences of the geometric sequences of two types. These interleaved sequences have the balance property and double the period of the geometric sequences by the interleaved structure. Moreover, we show correlation properties and linear complexity of the interleaved sequences. A key of our observation is that the second type geometric sequence is the complement of the left shift of the first type geometric sequence by half-period positions.
ER -