International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Analysis and Improvement of Entropy Estimators in NIST SP 800-90B for Non-IID Entropy Sources

Authors:
Shuangyi Zhu , Data Assurance and Communications Security Research Center, Chinese Academy of Sciences; State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences; School of Cyber Security, University of Chinese Acade
Yuan Ma , Data Assurance and Communications Security Research Center, Chinese Academy of Sciences; State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing
Tianyu Chen , Data Assurance and Communications Security Research Center, Chinese Academy of Sciences; State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing
Jingqiang Lin , Jingqiang Lin Data Assurance and Communications Security Research Center, Chinese Academy of Sciences; State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences; School of Cyber Security, University of
Jiwu Jing , Jiwu Jing Data Assurance and Communications Security Research Center, Chinese Academy of Sciences; State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences; School of Cyber Security, University of Chi
Download:
DOI: 10.13154/tosc.v2017.i3.151-168
URL: https://tosc.iacr.org/index.php/ToSC/article/view/769
Search ePrint
Search Google
Abstract: Random number generators (RNGs) are essential for cryptographic applications. In most practical applications, the randomness of RNGs is provided by entropy sources. If the randomness is less than the expected, the security of cryptographic applications could be undermined. Accurate entropy estimation is a critical method for the evaluation of RNG security, and significant overestimation and underestimation are both inadvisable. The NIST Special Publication 800-90B is one of the most common certifications for entropy estimation. It makes no assumption of the entropy source and provides min-entropy estimation results by a set of entropy estimators. It estimates the entropy sources in two tracks: the IID (independent and identically distributed) track and non-IID track. In practice, non-IID entropy sources are more common, as physical phenomenon, sampling process or external perturbation could cause the dependency of the outputs. In this paper, we prove that the Collision Estimate and the Compression Estimate in non-IID track could provide significant underestimates in theory. In order to accurately estimate the min-entropy of non-IID sources, we provide a formula of minentropybased on conditional probability, and propose a new estimator to approximate the result of this formula. Finally, we perform experiments to compare our estimator with the NIST estimators using simulated non-IID data. Results show that our estimator gives close estimates to the real min-entropy.
BibTeX
@article{tosc-2017-28476,
  title={Analysis and Improvement of Entropy Estimators in NIST SP 800-90B for Non-IID Entropy Sources},
  journal={IACR Trans. Symmetric Cryptol.},
  publisher={Ruhr-Universität Bochum},
  volume={2017, Issue 3},
  pages={151-168},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/769},
  doi={10.13154/tosc.v2017.i3.151-168},
  author={Shuangyi Zhu and Yuan Ma and Tianyu Chen and Jingqiang Lin and Jiwu Jing},
  year=2017
}