Paper 2026/2783
Bridging Correlation Measures and Unpredictability: Sharp Bounds and Insights for TRNG Validation
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
-
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}
}