Paper 1997/004
A note on negligible functions
Mihir Bellare
Abstract
In theoretical cryptography, one formalizes the notion of an adversary's success probability being ``too small to matter'' by asking that it be a negligible function of the security parameter. We argue that the issue that really arises is what it might mean for a collection of functions to be ``negligible.'' We consider (and define) two such notions, and prove them equivalent. Roughly, this enables us to say that any cryptographic primitive has a specific associated ``security level.'' In particular we say this for any one-way function. We also reconcile different definitions of negligible error arguments and computational proofs of knowledge that have appeared in the literature. Although the motivation is cryptographic, the main result is purely about negligible functions.
Metadata
- Available format(s)
-
PDF
PS
- Publication info
- Published elsewhere. Appears in Journal of Cryptology, Vol. 15, 2002, pp. 271-284. Earlier version was Technical Report CS97-529, Department of Computer Science and Engineering, UCSD, March 1997.
- Keywords
- theoryone-way functionscomputationally sound proofsproofs of knowledge
- Contact author(s)
- mihir @ cs ucsd edu
- History
- 2002-10-07: revised
- 1997-03-12: received
- Short URL
- https://ia.cr/1997/004
- License
-
CC BY
BibTeX
@misc{cryptoeprint:1997/004,
author = {Mihir Bellare},
title = {A note on negligible functions},
howpublished = {Cryptology ePrint Archive, Paper 1997/004},
year = {1997},
note = {\url{https://eprint.iacr.org/1997/004}},
url = {https://eprint.iacr.org/1997/004}
}
