<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

Data publikacji: 25 mar 2016

Zakres stron: 371 - 378

Otrzymano: 15 sie 2015

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

Słowa kluczowe
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

Data publikacji: 25 mar 2016

Zakres stron: 371 - 378

Otrzymano: 15 sie 2015

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

Słowa kluczowepolynomially 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.

Słowa kluczowe
polynomially bounded function, negligible functions