Algebra of Polynomially Bounded Sequences and Negligible Functions

• Autorzy: Hiroyuki Okazaki
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

polynomially bounded function; negligible functions

Kategorie tematyczne

• 03B35: Mechanization of proofs and logical operations
• 94A60: Cryptography
• 68Q25: Analysis of algorithms and problem complexity

• Wydawca: De Gruyter Open
• Czasopismo: Formalized Mathematics
• Rocznik: 2015
• Tom: 23
• Numer: 4
• Strony: 371-378

Daty

wydano

2015-12-01

otrzymano

2015-08-15

online

2016-03-25

Twórcy

autor

Hiroyuki Okazaki

• Shinshu University, Nagano, Japan

Bibliografia

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

Identyfikatory

DOI

10.1515/forma-2015-0029

bwmeta1.id-class.MML

ASYMPT 3