Paper 2020/1251

Bit Security Estimation Using Various Information-Theoretic Measures

Dong-Hoon Lee, Young-Sik Kim, and Jong-Seon No

Abstract

In this paper, various quantitative information-theoretic security reductions which correlate statistical difference between two probability distributions with security level's gap for two cryptographic schemes are proposed. Security is the most important prerequisite for cryptographic primitives. In general, there are two kinds of security; one is computational security, and the other is information-theoretic security. We focus on the latter one in this paper, especially the view point of bit security which is a convenient notion to indicate the quantitative security level. We propose tighter and more generalized version of information-theoretic security reductions than those of the previous works [1,2]. More specifically, we obtain about 2.5-bit tighter security reduction than that in the previous work [2], and we devise a further generalized version of security reduction in the previous work [1] by relaxing the constraint on the upper bound of the information-theoretic measure, that is, $\lambda$-efficient. Through this work, we propose the methodology to estimate the affects on security level when $\kappa$-bit secure original scheme is implemented on $p$-bit precision system. (Here, $p$ can be set to any value as long as certain condition is satisfied.) In the previous work [1], $p$ was fixed as $\kappa\over2$, but the proposed scheme is generalized to make it possible for security level $\kappa$ and precision $p$ to variate independently. This makes a very big difference. The previous result cannot provide the exact lower bound value of security level for the case $p\ne{\kappa\over2}$, but, it can only provide inaccurate relative information for security level. In contrast to this, the proposed result can provide the exact lower bound of estimation value of security level as long as precision $p$ satisfies the certain condition. Moreover, we provide diverse types of security reduction formulas for the five kinds of information-theoretic measures. We are expecting that the proposed schemes could provide an information-theoretic guideline for how much the two identical cryptographic schemes with different probability distribution may show the difference in their security level when extracting their randomness from two different probability distributions. Especially, the proposed schemes can be used to obtain the quantitative estimation of how much the statistical difference between the ideal distribution and the real distribution affects the security level [8,10,11].

Note: In this paper, our contributions are given as follows. First, we derive tighter security reduction bounds than those of Micciancio and Walter. Second, we propose a further generalized version of Micciancio and Walter's security reduction result by relaxing the constraint on the upper bound of the measure, that is, $\lambda$-efficient. Through this work, we manage to propose the methodology to elaborately estimate the affects on security level when $\kappa$-bit secure original scheme is implemented on $p$-bit precision system. ($p$ can be set to any value as long as certain condition is satisfied.) Third, we provide various types of security reduction formulas for the five kinds of information-theoretic measures; statistical distance, Rényi divergence, Kullback-Leibler divergence, max-log distance, and relative error. These measures are often used in cryptography for security reduction analysis.