<abstract xmlns="http://www.w3.org/1999/xhtml"><p>In this article we formalize negligible functions that play an essential role in cryptology [10], [2]. Generally, a cryptosystem is secure if the probability of succeeding any attacks against the cryptosystem is negligible. First, we formalize the algebra of polynomially bounded sequences [20]. Next, we formalize negligible functions and prove the set of negligible functions is a subset of the algebra of polynomially bounded sequences. Moreover, we then introduce equivalence relation between polynomially bounded sequences, using negligible functions.</p></abstract>

In this article we formalize negligible functions that play an essential role in cryptology [10], [2]. Generally, a cryptosystem is secure if the probability of succeeding any attacks against the cryptosystem is negligible. First, we formalize the algebra of polynomially bounded sequences [20]. Next, we formalize negligible functions and prove the set of negligible functions is a subset of the algebra of polynomially bounded sequences. Moreover, we then introduce equivalence relation between polynomially bounded sequences, using negligible functions.

Algebra of Polynomially Bounded Sequences and Negligible Functions

Formalized Mathematics

This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 License.

{"article-title":"Algebra of Polynomially Bounded Sequences and Negligible Functions"}

In this article we formalize negligible functions that play an essential role in cryptology [10], [2]. Generally, a cryptosystem is secure if the probability...

Algebra of Polynomially Bounded Sequences and Negligible Functions

Online veröffentlicht: 25. März 2016

Seitenbereich: 371 - 378

Eingereicht: 15. Aug. 2015

DOI: https://doi.org/10.1515/forma-2015-0029

Schlüsselwörter
polynomially bounded function, negligible functions

© 2015 Hiroyuki Okazaki, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 License.

Algebra of Polynomially Bounded Sequences and Negligible Functions

Online veröffentlicht: 25. März 2016

Seitenbereich: 371 - 378

Eingereicht: 15. Aug. 2015

DOI: https://doi.org/10.1515/forma-2015-0029

Schlüsselwörterpolynomially bounded function, negligible functions

© 2015 Hiroyuki Okazaki, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 License.

Schlüsselwörter
polynomially bounded function, negligible functions