Cryptology ePrint Archive: Report 1998/024
The Disparity between Work and Entropy in Cryptology
Abstract: 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.
Category / Keywords: Entropy, Information Theory, Brute-Force Attack, Work Factor, Guessing Entropy.
Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Date: received November 9th, 1998. Revised, February 1st, 1999.
Contact author: pliam at ima umn edu
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]