Paper 2020/1251

Bit Security Estimation Using Various Information-Theoretic Measures

Dong-Hoon Lee and 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 between 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 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 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, λ-efficient. Through this work, we propose the methodology to estimate the affects on security level when κ-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 κ/2, but our result is generalized to make it possible to security level κ and precision p variate independently. Moreover, we provide diverse types of security reduction formulas for the five kinds of information-theoretic measures. We are expecting that our results could provide an information-theoretic guideline for how much the two identical cryptographic schemes (i.e., the only difference is probability distribution) may show the difference in their security level when extracting their randomness from two different probability distributions. Especially, our results 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.

Note: In this paper, our contributions are 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, λ-efficient. Through this work, we manage to propose the methodology to estimate the affects on security level when κ-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, Re'nyi divergence, Kullback-Leibler divergence, max-log distance, and relative error. These measures are often used in cryptography for security reduction analysis.