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

  • 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 Academy of Sciences, Beijing
  • 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 Chinese Academy of Sciences, Beijing
  • 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 Chinese Academy of Sciences, Beijing
Keywords: Entropy estimation, NIST SP 800-90B, Min-entropy, Random number generator

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.
Published
2017-09-19
How to Cite
Zhu, S., Ma, Y., Chen, T., Lin, J., & Jing, J. (2017). Analysis and Improvement of Entropy Estimators in NIST SP 800-90B for Non-IID Entropy Sources. IACR Transactions on Symmetric Cryptology, 2017(3), 151-168. https://doi.org/10.13154/tosc.v2017.i3.151-168
Section
Articles