Improved Longest Repeated Substring Estimator

Abstract

The min-entropy is a widely used metric to quantify the randomness of generated random numbers, which measures the difficulty of guessing the most likely output. It is difficult to accurately estimate the min-entropy of a non-independent and identically distributed (non-IID) source. Hence, NIST Special Publication (SP) 800- 90B adopts ten different min-entropy estimators and then conservatively selects the minimum value among ten min-entropy estimates. Among these estimators, the longest repeated substring (LRS) estimator estimates the collision entropy instead of the min-entropy by counting the number of repeated substrings. Since the collision entropy is an upper bound on the min-entropy, the LRS estimator inherently provides overestimated outputs. In this paper, we propose two techniques to estimate the min-entropy of a non-IID source accurately. The first technique resolves the overestimation problem by translating the collision entropy into the min-entropy. Next, we generalize the LRS estimator by adopting the general Renyi entropy instead of the collision entropy (i.e., Renyi entropy of order two). We show that adopting a higher order can reduce the variance of min-entropy estimates. By integrating these techniques, we propose a generalized LRS estimator that effectively resolves the overestimation problem and provides stable min-entropy estimates. Theoretical analysis and empirical results support that the proposed generalized LRS estimator improves the estimation accuracy significantly, which makes it an appealing alternative to the LRS estimator.

본 논문은 정보이론 및 암호, 통신 분야에서 활용되는 최소 엔트로피를 추정하기 위한 알고리즘을 제시한다. 정보의 보호가 필요한 암호 분야에서는 난수(Random number)를 통해 보안을 설계한다. 이러한 난수는 규칙적이면 보안이 취약하므로 높은 무작위성을 가지고 있어야 한다. 이러한 무작위성을 측정하기 위해 정보이론의 최소 엔트로피를 사용한다. 국제 표준 기구(NIST)에서는 최소 엔트로피 추정을 위해 10 가지의 추정 방안을 제시하였고, 추정하고자 하는 데이터에 대해 이 10 가지 추정방법을 통해 도출된 최소 엔트로피 중 가장 작은 엔트로피를 최종적인 최소 엔트로피로 채택하도록 하였다. 이 중 Longest Repeated Substring(이하 LRS) 추정 방법은 최소 엔트로피가 아닌 충돌 엔트로피를 추정하는 문제를 가졌다. 엔트로피의 종류는 Renyi 엔트로피의 차수로 표현할 수 있는데, 최소 엔트로피는 Renyi 엔트로피의 차수가 무한이고, 충돌 엔트로피는 Renyi 엔트로피의 차수가 2 이다. 주어진 데이터의 분포가 Uniform distribution 일 때는 Renyi 엔트로피가 항상 동일한 값을 가지게 되지만, 이를 제외한 모든 분포에서는 Renyi 엔트로피의 차수가 커질수록 엔트로피의 값은 감소한다. 따라서 이 충돌 엔트로피는 항상 최소 엔트로피 보다 크거나 같게 되어 LRS 추정기는 항상 과추정 문제를 발생시키기에 가장 작은 값을 채택해야 하는 최소 엔트로피 추정방법에서, 항상 큰 값을 지니게 되어 채택되지 못하는 문제를 가진다. 이를 해결하기 위해 본 논문에서는 충돌 엔트로피를 최소 엔트로피로 변환하는 알고리즘을 추가하였고, 이를 일반화시켜 LRS 추정기가 Renyi 엔트로피의 차수가 2 인 충돌 엔트로피를 추정하지 않고 일반적인 차수 ɑ(3,4,5,6)를 가지는 Renyi 엔트로피를 추정하도록 하고, 이 Renyi 엔트로피를 최소 엔트로피로 변환하는 알고리즘을 제시하였다. 이렇게 제시한 알고리즘을 통해 기존 LRS 의 과추정 문제를 해결하고, 일반화의 과정을 통해 추정값의 분산을 줄이는 성과를 낼 수 있었다. 본 논문에서 제시한 일반화된 LRS 추정 방법을 통해 암호와 같은 보안이 필요한 분야에서 더욱 안정적이고 정확한 난수의 추정이 가능해 많은 활용이 될 것으로 기대된다.