Abstract
This paper presents a rigorous information-theoretic framework for evaluating Chaotic-Map Truly Random Number Generators (TRNGs). By modeling the bit-generation process as a Hidden Markov Process (HMP), the authors demonstrate that traditional metrics like output bias are insufficient. They establish the "entropy-rate" as the fundamental limit for extracting randomness and provide theoretical bounds for post-processing units.
Introduction: The Challenge of Real-World TRNGs
Truly Random Number Generators (TRNGs) are essential for modern cryptography and secure data transmission. Chaotic maps are favored for TRNG construction due to their high sensitivity to initial conditions, speed, and ease of implementation in analog circuitry. However, physical implementations often suffer from non-idealities like process variations and environmental noise.
Traditional evaluation methods often rely on simple Markov models or basic statistical tests, such as checking for equal bit distribution. The authors argue these are inadequate because they ignore the "hidden" nature of the internal state. While we observe the bitstream, the exact internal state of the chaotic map remains hidden, potentially creating correlations between bits that simple tests fail to detect.
Methodology: Modeling as a Hidden Markov Process
The core contribution of this research is treating the TRNG as a Hidden Markov Process (HMP). The system is defined by a chaotic map function $M(x)$ and a bit-generation function $B(x)$. While the sequence of internal states follows a Markov process, the observed bit sequence is an HMP.
To calculate the entropy-rate, which lacks a closed-form solution for HMPs, the authors use conditional entropy $H(Z_n | Z^{n-1})$ as an approximation. As illustrated in Figure 6(c), this value converges exponentially fast, allowing for efficient estimation even with short sequences (e.g., $n=10$). This method is significantly faster than empirical tests like the NIST suite, predicting performance in seconds rather than minutes.
Theoretical Bounds and Key Insights
The paper establishes two critical theorems regarding post-processing:
- Theorem 1: A post-processing unit's output rate $R$ cannot exceed the source's entropy-rate $H$ if it is to be asymptotically truly random. This establishes a theoretical "speed limit" for randomness extraction.
- Theorem 2: Conversely, an ideal post-processing function exists for any rate $R \le H$, though its practical implementation may be complex.
A key insight is that uniformity does not guarantee randomness. A map can produce 0s and 1s with equal probability (zero bias) but still have a low entropy-rate due to strong temporal correlations. Furthermore, the rate at which entropy converges is directly linked to the map's Lyapunov exponent.
Key Results and Robustness
In testing an example map, the authors found a significant gap between bias (0.36) and entropy-rate (~0.57). This gap represents "hidden" randomness that could be recovered with optimal post-processing. They also demonstrated that common algorithms like Von-Neumann post-processing are highly inefficient, achieving a rate of only $R \approx 0.11$ compared to the $0.57$ theoretical limit.
For hardware robustness, a "zigzag map" was evaluated via 1,000 Monte Carlo simulations to mimic manufacturing variations. It maintained a high mean entropy of 0.97 bits per symbol, with 99% of samples passing the rigorous NIST 800-22 tests, proving it to be a resilient design for physical hardware.
Conclusion
This HMP-based framework provides a faster and more theoretically sound method for evaluating TRNGs than empirical testing alone. While it establishes the theoretical limits for randomness extraction, the design of practical, low-complexity post-processors that can reach these limits remains an important open problem for future research.
Summary updated