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
EntropyInformation TheoryBrute-Force AttackWork FactorGuessing 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/1998/024}},
      url = {https://eprint.iacr.org/1998/024}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.