Algebra of Polynomially Bounded Sequences and Negligible Functions

Hiroyuki Okazaki

Formalized Mathematics (2015)

  • Volume: 23, Issue: 4, page 371-378
  • ISSN: 1426-2630

Abstract

top
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.

How to cite

top

Hiroyuki Okazaki. "Algebra of Polynomially Bounded Sequences and Negligible Functions." Formalized Mathematics 23.4 (2015): 371-378. <http://eudml.org/doc/276933>.

@article{HiroyukiOkazaki2015,
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.},
author = {Hiroyuki Okazaki},
journal = {Formalized Mathematics},
keywords = {polynomially bounded function; negligible functions},
language = {eng},
number = {4},
pages = {371-378},
title = {Algebra of Polynomially Bounded Sequences and Negligible Functions},
url = {http://eudml.org/doc/276933},
volume = {23},
year = {2015},
}

TY - JOUR
AU - Hiroyuki Okazaki
TI - Algebra of Polynomially Bounded Sequences and Negligible Functions
JO - Formalized Mathematics
PY - 2015
VL - 23
IS - 4
SP - 371
EP - 378
AB - 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.
LA - eng
KW - polynomially bounded function; negligible functions
UR - http://eudml.org/doc/276933
ER -

References

top
  1. [1] Grzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41–46, 1990. Zbl06213858
  2. [2] Mihir Bellare. A note on negligible functions, 2002. 
  3. [3] Józef Białas. Group and field definitions. Formalized Mathematics, 1(3):433–439, 1990. 
  4. [4] Czesław Byliński. The complex numbers. Formalized Mathematics, 1(3):507–513, 1990. 
  5. [5] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1): 55–65, 1990. 
  6. [6] Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153–164, 1990. 
  7. [7] Czesław Byliński. Partial functions. Formalized Mathematics, 1(2):357–367, 1990. 
  8. [8] Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47–53, 1990. 
  9. [9] Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165–167, 1990. 
  10. [10] Oded Goldreich. Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press, 2001. 
  11. [11] Krzysztof Hryniewiecki. Basic properties of real numbers. Formalized Mathematics, 1(1): 35–40, 1990. 
  12. [12] Andrzej Kondracki. Basic properties of rational numbers. Formalized Mathematics, 1(5): 841–845, 1990. 
  13. [13] Artur Korniłowicz. On the real valued functions. Formalized Mathematics, 13(1):181–187, 2005. 
  14. [14] Jarosław Kotowicz. Real sequences and basic operations on them. Formalized Mathematics, 1(2):269–272, 1990. 
  15. [15] Jarosław Kotowicz. Convergent sequences and the limit of sequences. Formalized Mathematics, 1(2):273–275, 1990. 
  16. [16] Richard Krueger, Piotr Rudnicki, and Paul Shelley. Asymptotic notation. Part I: Theory. Formalized Mathematics, 9(1):135–142, 2001. 
  17. [17] Richard Krueger, Piotr Rudnicki, and Paul Shelley. Asymptotic notation. Part II: Examples and problems. Formalized Mathematics, 9(1):143–154, 2001. 
  18. [18] Eugeniusz Kusak, Wojciech Leończuk, and Michał Muzalewski. Abelian groups, fields and vector spaces. Formalized Mathematics, 1(2):335–342, 1990. 
  19. [19] Adam Naumowicz. Conjugate sequences, bounded complex sequences and convergent complex sequences. Formalized Mathematics, 6(2):265–268, 1997. 
  20. [20] Hiroyuki Okazaki and Yuichi Futa. Polynomially bounded sequences and polynomial sequences. Formalized Mathematics, 23(3):205–213, 2015. doi:10.1515/forma-2015-0017.[Crossref] Zbl1321.68276
  21. [21] Henryk Oryszczyszyn and Krzysztof Prażmowski. Real functions spaces. Formalized Mathematics, 1(3):555–561, 1990. 
  22. [22] Konrad Raczkowski and Andrzej Nędzusiak. Real exponents and logarithms. Formalized Mathematics, 2(2):213–216, 1991. 
  23. [23] Konrad Raczkowski and Andrzej Nędzusiak. Series. Formalized Mathematics, 2(4):449–452, 1991. 
  24. [24] Andrzej Trybulec. Binary operations applied to functions. Formalized Mathematics, 1 (2):329–334, 1990. 
  25. [25] Michał J. Trybulec. Integers. Formalized Mathematics, 1(3):501–505, 1990. 
  26. [26] Wojciech A. Trybulec. Groups. Formalized Mathematics, 1(5):821–827, 1990. 
  27. [27] Wojciech A. Trybulec. Vectors in real linear space. Formalized Mathematics, 1(2):291–296, 1990. 
  28. [28] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67–71, 1990. 
  29. [29] Tetsuya Tsunetou, Grzegorz Bancerek, and Yatsuka Nakamura. Zero-based finite sequences. Formalized Mathematics, 9(4):825–829, 2001. 
  30. [30] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1 (1):73–83, 1990. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.