Paper 2025/1236
Exploring Marginal Guesswork with the Theorem of Berry-Esséen
, Ruhr University BochumAbstract
In 2000, Pliam showed that there does not exist an upper or lower bound in terms of Shannon entropy alone for the number of guesses required in order to guess some randomly sampled element $s$ with certainty $0<q<1$, denoted as marginal guesswork. In comparison, it was shown by Arikan in 1996 that, if the distribution is defined over finite support, the expected guesswork, that is the expected amount of trials it takes to guess some random element $s$ with certainty, is bound in terms of R\'enyi entropy $\operatorname{H}_{1/2}$. In this paper, we utilize the Theorem of Berry-Ess\'een to amend Pliams result. We show that there exists some asymptotic expression for the marginal guesswork in terms of Shannon entropy, variance in information and the probit function, provided $q$ is fixed.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- GuessworkTheorem of Berry-EsseenShannon EntropyRényi EntropyProbit FunctionVariance in Information
- Contact author(s)
- timo glaser @ rub de
- History
- 2025-07-09: approved
- 2025-07-03: received
- See all versions
- Short URL
- https://ia.cr/2025/1236
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1236,
author = {Timo Glaser},
title = {Exploring Marginal Guesswork with the Theorem of Berry-Esséen},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1236},
year = {2025},
url = {https://eprint.iacr.org/2025/1236}
}
