Content area
Full text
Abstract. The Next Bit Test brie y states that a sequence is random if and only if, given any i bits of the sequence, it is not possible to predict the next bit of the sequence with a probability of success significantly greater than 1=2. In 1996, Sadeghiyan and Mohajeri proposed a so-called \new universal test for bit strings", based on the theoretical next bit test. In this paper, we study different aspects of this test and show its weakness. Then, we improve it both theoretically and practically for better classification of the sequences. As a result, a Practical Next Bit (PNB) test is introduced in two Global and Local versions and a histogram, which gives an impression of the global evaluation of the underlying sequence. Testing samples of nonrandom sequences, using both the PNB test and the NIST Statistical Test Suite, indicates the superiority of the PNB test power over that of the NIST.
Keywords: Next bit test; Random sequences; Statistical test.
(ProQuest: ... denotes formulae omitted.)
INTRODUCTION
Random (or pseudorandom) sequences play an essential role in many fields. When there is a need to model a dynamic system or in the implementation of a simulation program, the use of random sequences is inevitable. However, in cryptographic applications, considering the sensitivity of the information, randomness is the major concern [1]. The output of an encryption algorithm is required to be random as a necessary condition of security. Cryptosystems do not reach their security level unless random keys are employed. Many cryptographic protocols, like digital signatures and challenge-response schemes, use random sequences as auxiliary quantities.
In regard to the above mentioned facts, distinguishing random from nonrandom sequences is critical in scientific areas and should be treated even more strictly in cryptology. Since the introduction of modern ciphers, various statistical tests have been developed, each of which assessing the presence or absence of a "Pattern" in the output of the ciphers. Such a pattern, if detected, would indicate that the sequence is nonrandom [2]. In searching for a criterion to test randomness, in 1982 Blum and Micali [3] were the first to show that the ability of predicting the next bit of a sequence is enough to judge the sequence to be nonrandom. Yao...