Graph Theoretic Approach to Randomness Test Based on the Overlapping Blocks

Date

2023-06-01

Author

Uğuz, Muhiddin

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

173
views

40
downloads

Cite This

Cryptographic parameters such as secret keys, should be chosen randomly and at the same time it should not be so difficult to reproduce them when necessary. Because of this, pseudorandom bit (or number) generators take the role of true random generators. Outputs of pseudorandom generators, although they are produced through some deterministic process, should be random looking, that is not distinguishable from true random sequences. In other words they should not follow any pattern. In this paper we propose a new approach using graph theory, to determine the expected value of the index at which a fixed pattern start to appear in a random sequence for the first time. Using the method proposed, a recursion for the number of paths of length n starting from a pattern and never coming back to that pattern can be computed. By means of these recursions, we obtain the probabilities for the indexes at which a fixed pattern appears in the sequence for the first time. Using these expected values and comparing them with the observed values a randomness test can be defined. In this work patters are traced through the sequence in an overlapping manner.

Subject Keywords

Cryptography, Statistical Randomness Testing, NIST Test Suite, Recursion

URI

https://dergipark.org.tr/tr/pub/ijiss/issue/78497/1288854
https://hdl.handle.net/11511/105072

Collections

Department of Mathematics, Article