Transition Probability Test for an RO-Based Generator and the Relevance between the Randomness and the Number of ROs

Abstract

A ring oscillator is a well-known circuit used for generating random numbers, and interested readers can find many research results concerning the evaluation of the randomness with a packaged test suit. However, the authors think there is room for evaluating the unpredictability of a sequence from another viewpoint. In this paper, the authors focus on Wold’s RO-based generator and propose a statistical test to numerically evaluate the randomness of the RO-based generator. The test adopts the state transition probabilities in a Markov process and is designed to check the uniformity of the probabilities based on hypothesis testing. As a result, it is found that the RO-based generator yields a biased output from the viewpoint of the transition probability if the number of ROs is small. More precisely, the transitions 01→01 and 11→11 happen frequently when the number l of ROs is less than or equal to 10. In this sense, l>10 is recommended for use in any application, though a packaged test suit is passed. Thus, the authors believe that the proposed test contributes to evaluating the unpredictability of a sequence when used together with available statistical test suits, such as NIST SP800-22.

Keywords

• true random number generator
• ring oscillator
• Markov process
• hypothesis testing