NDLI: Guesswork, Large Deviations, and Shannon Entropy

Content Provider	IEEE Xplore Digital Library
Author	Christiansen, M.M. Duffy, K.R.
Copyright Year	1963
Abstract	How hard is it to guess a password? Massey showed that a simple function of the Shannon entropy of the distribution from which the password is selected is a lower bound on the expected number of guesses, but one which is not tight in general. In a series of subsequent papers under ever less restrictive stochastic assumptions, an asymptotic relationship as password length grows between scaled moments of the guesswork and specific Rényi entropy was identified. Here, we show that, when appropriately scaled, as the password length grows, the logarithm of the guesswork satisfies a large deviation principle (LDP), providing direct estimates of the guesswork distribution when passwords are long. The rate function governing the LDP possesses a specific, restrictive form that encapsulates underlying structure in the nature of guesswork. Returning to Massey's original observation, a corollary to the LDP shows that expectation of the logarithm of the guesswork is the specific Shannon entropy of the password selection process.
Sponsorship	IEEE Information Theory Society
Starting Page	796
Ending Page	802
Page Count	7
File Size	1695177
File Format	PDF
ISSN	00189448
Volume Number	59
Issue Number	2
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Entropy Approximation methods Equations Upper bound Markov processes Complexity theory Atmospheric measurements Shannon entropy Guesswork large deviations Rényi entropy
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

High-Resolution Scalar Quantization With Rényi Entropy Constraint

Rescaling Entropy and Divergence Rates

The Shannon Cipher System With a Guessing Wiretapper: General Sources

One-Parameter Fisher–Rényi Complexity: Notion and Hydrogenic Applications

Guesswork, large deviations and Shannon entropy

Minimax Estimation of Functionals of Discrete Distributions

Large Deviations for Re-Sequencing Buffer Size

A Unified Approach to Cramér–Rao Inequalities

Encoding Tasks and Rényi Entropy

Guesswork, Large Deviations, and Shannon Entropy

Similar Documents

High-Resolution Scalar Quantization With Rényi Entropy Constraint

Rescaling Entropy and Divergence Rates

The Shannon Cipher System With a Guessing Wiretapper: General Sources

One-Parameter Fisher–Rényi Complexity: Notion and Hydrogenic Applications

Guesswork, large deviations and Shannon entropy

Minimax Estimation of Functionals of Discrete Distributions

Large Deviations for Re-Sequencing Buffer Size

A Unified Approach to Cramér–Rao Inequalities

Encoding Tasks and Rényi Entropy

Guesswork, Large Deviations, and Shannon Entropy