<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

Publicado en línea: 25 mar 2016

Páginas: 371 - 378

Recibido: 15 ago 2015

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

Palabras clave
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

Publicado en línea: 25 mar 2016

Páginas: 371 - 378

Recibido: 15 ago 2015

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

Palabras clavepolynomially 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.

Palabras clave
polynomially bounded function, negligible functions