The Disparity between Work and Entropy in Cryptology.
John O. Pliam · 1998
A brief theory of work is developed. In it, the work-factor and guesswork of a random variable are linked to intuitive notions of time complexity in a brute-force attack. Bounds are given for a specific work-factor called the minimum majority. Tight bounds are given for the guesswork in terms of variation distance. Differences between work-factor, guesswork and the entropy of a random variable are pointed out, calling into question a common misconception about entropy indicating work. The purpose of this document is to discuss measures of work and uncertainty relevant to cryptology. In [Pli99], these ideas are used to develop the necessary machinery for quantifying the fundamental limits facing a cryptanalytic adversary in a cipher attack. This machinery plays a role analogous to that of the basic inequalities of information theory [CT91] (e.g. Jensen's inequality, the information inequality, etc.). 1 Definitions of Work It is important to note at the outset that entropy, the classic...