
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.

A New Randomness Test Based on Linear Complexity Profile
Kenji HAMANO Fumio SATO Hirosuke YAMAMOTO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E92A
No.1
pp.166172 Publication Date: 2009/01/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E92.A.166
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Mathematics Keyword: randomness test, linear complexity profile, NIST SP80022,
Full Text: PDF(247.6KB) >>Buy this Article
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 Msequences 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.

