Cryptology ePrint Archive: Report 1998/024

The Disparity between Work and Entropy in Cryptology

John Pliam

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

Short URL: ia.cr/1998/024

Discussion forum: Show discussion | Start new discussion