Guesswork, Large Deviations, and Shannon Entropy
Guesswork, Large Deviations, and Shannon Entropy
复制标题
DOI：
10.1109/tit.2012.2219036
复制
发表时间：
2013-02-01
影响因子：
2.5
通讯作者：
Duffy, Ken R.
中科院分区：
文献类型：
--
作者：
Christiansen, Mark M.;Duffy, Ken R.
猜密码有多难？Massey证明了选择密码的分布的香农熵的一个简单函数是期望猜测次数的下界，但一般来说这个下界并不严密。在随后的一系列论文中，在限制性更少的随机假设下，确定了随密码长度增长，猜测的比例矩与特定的Renyi熵之间的渐近关系。在这里，我们表明，当适当缩放时，随着密码长度的增长，猜测的对数满足大偏差原理（LDP），提供了密码长时猜测分布的直接估计。控制自民党的比率函数具有一种特定的、限制性的形式，它将底层结构封装在猜测的性质中。回到Massey最初的观察，LDP的一个推论表明，猜测工作的对数的期望是密码选择过程的特定香农熵。
How hard is it to guess a password? Massey showed that a simple function of the Shannon entropy of the distribution from which the password is selected is a lower bound on the expected number of guesses, but one which is not tight in general. In a series of subsequent papers under ever less restrictive stochastic assumptions, an asymptotic relationship as password length grows between scaled moments of the guesswork and specific Renyi entropy was identified. Here, we show that, when appropriately scaled, as the password length grows, the logarithm of the guesswork satisfies a large deviation principle (LDP), providing direct estimates of the guesswork distribution when passwords are long. The rate function governing the LDP possesses a specific, restrictive form that encapsulates underlying structure in the nature of guesswork. Returning to Massey's original observation, a corollary to the LDP shows that expectation of the logarithm of the guesswork is the specific Shannon entropy of the password selection process.