Cryptology ePrint Archive: Report 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 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].

Category / Keywords: foundations / bit security information-theoretic measures security reduction Re'nyi divergence statistical distance max-log distance λ-efficient measure.

Date: received 8 Oct 2020, last revised 23 Jan 2021

Contact author: scott814 at ccl snu ac kr

Available format(s): PDF | BibTeX Citation

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\'{e}nyi divergence, Kullback-Leibler divergence, max-log distance, and relative error. These measures are often used in cryptography for security reduction analysis.

Version: 20210124:062734 (All versions of this report)

Short URL: ia.cr/2020/1251


[ Cryptology ePrint archive ]