CryptoDB
A note on negligible functions
| Authors: |
- Mihir Bellare
|
| Download: |
- URL: http://eprint.iacr.org/1997/004
- Search ePrint
- Search Google
|
| 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. |
BibTeX
@misc{eprint-1997-11286,
title={A note on negligible functions},
booktitle={IACR Eprint archive},
keywords={theory, one-way functions, computationally sound proofs, proofs of knowledge},
url={http://eprint.iacr.org/1997/004},
note={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. mihir@cs.ucsd.edu 11967 Received 12 Mar 1997, last revised 7 Oct 2002},
author={Mihir Bellare},
year=1997
}
