IEICE TRANSACTIONS on Fundamentals
A New Randomness Test Based on Linear Complexity Profile
Summary :
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
