Bit Security Estimation Using Various Information-Theoretic Measures

Abstract

In this paper, we propose various quantitative information-theoretic bit security reduction measures that correlate the statistical difference between two probability distributions with the security level gap for two cryptographic schemes. We derive tighter relations between information-theoretic measures for quantifying the precision and guarantee the security level of the cryptographic scheme implemented over a precision-restricted environment. Further, the generalized versions of previous security reductions are devised by relaxing the constraints on the upper bounds of the information-theoretic measures. This makes it possible to estimate bit security more reliable and improves the security level. We also estimate the effects on the security level when the $\kappa $ -bit secure original scheme is implemented on a $p$ -bit precision system. In previous studies, $p$ was fixed as $\frac {\kappa }2$ ; however, the proposed schemes are generalized such that the security level $\kappa $ and precision $p$ can vary independently. This results in a significant difference. Moreover, previous results cannot provide the exact lower bound of the security level for $p\ne {\frac {\kappa }{2}}$ . However, the proposed results can provide the exact lower bound of the estimation value of the security level as long as the precision $p$ satisfies certain conditions. We provide diverse types of security reduction formulas for the six types of information-theoretic measures. The proposed schemes can provide information-theoretic guidelines regarding the difference between the security levels of two identical cryptographic schemes when extracting randomness from two different probability distributions. In particular, the proposed schemes can be used to quantitatively estimate the effect of the statistical difference between the ideal and real distributions on the security level.

Keywords

• Bit security
• Hellinger distance
• information-theoretic measures
• Kullback-Leibler divergence
• λ-efficient measure
• max-log distance