Paper 2026/2783

Bridging Correlation Measures and Unpredictability: Sharp Bounds and Insights for TRNG Validation

Maciej Skorski, University of Warsaw, University of Luxembourg
Onur Günlü, TU Dortmund University
Abstract

Do small correlations certify high unpredictability? We answer this for the high-order correlation measures (Mauduit and Sárközy) and finite-memory sources. We develop minimax sharp bounds on next-bit prediction from high-order correlations and show that the min-entropy-rate deficit is linear in the largest correlation, with optimal first-order constants. We also bridge population and sample correlations through ergodic limits and finite-sample guarantees. As an application, we show that the validation method for true random number generators recently proposed at WAIFI 2026 over-rejects: shrinking (sub-constant) thresholds strongly reject sources of nearly full entropy.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
correlation measuresunpredictabilityparitypseudorandomnessMarkov sourcesrandom number generators
Contact author(s)
maciej skorski @ gmail com
onur guenlue @ tu-dortmund de
History
2026-11-09: approved
2026-11-05: received
See all versions
Short URL
https://ia.cr/2026/2783
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2783,
      author = {Maciej Skorski and Onur Günlü},
      title = {Bridging Correlation Measures and Unpredictability: Sharp Bounds and Insights for {TRNG} Validation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2783},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2783}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.