The search functionality is under construction.

The search functionality is under construction.

Linear complexity can be used to detect predictable nonrandom sequences, and hence it is included in the NIST randomness test suite. But, as shown in this paper, the NIST test suite cannot detect nonrandom sequences that are generated, for instance, by concatenating two different M-sequences with low linear complexity. This defect comes from the fact that the NIST linear complexity test uses deviation from the ideal value only in the last part of the whole linear complexity profile. In this paper, a new faithful linear complexity test is proposed, which uses deviations in all parts of the linear complexity profile and hence can detect even the above nonrandom sequences. An efficient formula is derived to compute the exact area distribution needed for the proposed test. Furthermore, a simple procedure is given to compute the proposed test statistic from linear complexity profile, which requires only *O*(*M*) time complexity for a sequence of length *M*.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.1 pp.166-172

- Publication Date
- 2009/01/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E92.A.166

- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)

- Category
- Mathematics

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Kenji HAMANO, Fumio SATO, Hirosuke YAMAMOTO, "A New Randomness Test Based on Linear Complexity Profile" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 1, pp. 166-172, January 2009, doi: 10.1587/transfun.E92.A.166.

Abstract: Linear complexity can be used to detect predictable nonrandom sequences, and hence it is included in the NIST randomness test suite. But, as shown in this paper, the NIST test suite cannot detect nonrandom sequences that are generated, for instance, by concatenating two different M-sequences with low linear complexity. This defect comes from the fact that the NIST linear complexity test uses deviation from the ideal value only in the last part of the whole linear complexity profile. In this paper, a new faithful linear complexity test is proposed, which uses deviations in all parts of the linear complexity profile and hence can detect even the above nonrandom sequences. An efficient formula is derived to compute the exact area distribution needed for the proposed test. Furthermore, a simple procedure is given to compute the proposed test statistic from linear complexity profile, which requires only *O*(*M*) time complexity for a sequence of length *M*.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.166/_p

Copy

@ARTICLE{e92-a_1_166,

author={Kenji HAMANO, Fumio SATO, Hirosuke YAMAMOTO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={A New Randomness Test Based on Linear Complexity Profile},

year={2009},

volume={E92-A},

number={1},

pages={166-172},

abstract={Linear complexity can be used to detect predictable nonrandom sequences, and hence it is included in the NIST randomness test suite. But, as shown in this paper, the NIST test suite cannot detect nonrandom sequences that are generated, for instance, by concatenating two different M-sequences with low linear complexity. This defect comes from the fact that the NIST linear complexity test uses deviation from the ideal value only in the last part of the whole linear complexity profile. In this paper, a new faithful linear complexity test is proposed, which uses deviations in all parts of the linear complexity profile and hence can detect even the above nonrandom sequences. An efficient formula is derived to compute the exact area distribution needed for the proposed test. Furthermore, a simple procedure is given to compute the proposed test statistic from linear complexity profile, which requires only *O*(*M*) time complexity for a sequence of length *M*.},

keywords={},

doi={10.1587/transfun.E92.A.166},

ISSN={1745-1337},

month={January},}

Copy

TY - JOUR

TI - A New Randomness Test Based on Linear Complexity Profile

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 166

EP - 172

AU - Kenji HAMANO

AU - Fumio SATO

AU - Hirosuke YAMAMOTO

PY - 2009

DO - 10.1587/transfun.E92.A.166

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E92-A

IS - 1

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - January 2009

AB - Linear complexity can be used to detect predictable nonrandom sequences, and hence it is included in the NIST randomness test suite. But, as shown in this paper, the NIST test suite cannot detect nonrandom sequences that are generated, for instance, by concatenating two different M-sequences with low linear complexity. This defect comes from the fact that the NIST linear complexity test uses deviation from the ideal value only in the last part of the whole linear complexity profile. In this paper, a new faithful linear complexity test is proposed, which uses deviations in all parts of the linear complexity profile and hence can detect even the above nonrandom sequences. An efficient formula is derived to compute the exact area distribution needed for the proposed test. Furthermore, a simple procedure is given to compute the proposed test statistic from linear complexity profile, which requires only *O*(*M*) time complexity for a sequence of length *M*.

ER -