The Disparity between Work and Entropy in Cryptology

John Pliam

Paper 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.

Metadata

Available format(s): PS
Publication info: Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords: Entropy Information Theory Brute-Force Attack Work Factor Guessing Entropy.
Contact author(s): pliam @ ima umn edu
History: 1999-02-01: revised; 1998-11-09: received
Short URL: https://ia.cr/1998/024
License: CC BY

BibTeX

@misc{cryptoeprint:1998/024,
      author = {John Pliam},
      title = {The Disparity between Work and Entropy in Cryptology},
      howpublished = {Cryptology {ePrint} Archive, Paper 1998/024},
      year = {1998},
      url = {https://eprint.iacr.org/1998/024}
}