Zastosowanie funkcji L w kryptologii

• Autorzy: Kaczorowski J.

Warianty tytułu

EN

Applications of L-functions in cryptology

• Języki publikacji: PL

Abstrakty

PL

Bezpieczeństwo asymetrycznych systemów kryptologicznych opiera się na założeniu, że istnieją funkcje jednokierunkowe. Fakt ten nie został do tej pory ściśle udowodniony. Nie mniej jednak pewne trudne obliczeniowo problemy teorii liczb, takie jak na przykład problem faktoryzacji, czy też problem obliczania logarytmu dyskretnego w skończonych grupach abelowych, mogą być podstawą konstrukcji funkcji uważanych za jednokierunkowe. Idea wykorzystania w tym kontekście funkcji typu L (elementów klasy Selberga) pojawiła się po raz pierwszy w pracy M. Anshela i D. Goldfelda z 1997 roku. Ich przydatność ilustrujemy na przykładzie protokołu uwierzytelnienia przy użyciu współczynników Dirichleta funkcji L oraz eliptycznego generatora pseudolosowego. Na zakończenie przedstawiamy propozycję innego typu, a mianowicie opis protokołu rzutu monetą przez telefon opartego na wykorzystaniu nietrywialnych zer funkcji L.

EN

Security of asymmetric cryptological systems is based on the unproved hypothesis that one-way functions do exist. Some difficult computational problems in number theory, such as factorization or a discrete logarithm problem in finite Abelian groups may serve as a basis for constructing presumably one-way functions. The idea of using L-functions (elements of the Selberg class) in this context goes back to M. Anshel and D. Goldfeld (1997). Following them we describe an authentication protocol and an elliptic pseudo-random generator. The former uses Dirichlet L-functions, and the latter Hasse-Weil L-functions of elliptic curves over Q. We conclude by proposing a protocol of coin toss by phone based on the use of non-trivial zeros of L-functions.

Słowa kluczowe

PL

funkcje L; klasa Selberga; funkcja jednokierunkowa

EN

L-functions; Selberg class; one-way function

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Studia Bezpieczeństwa Narodowego
• Rocznik: 2014
• Tom: R. 4, Nr 6
• Strony: 258--273
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Kaczorowski J.

• Wydział Matematyki i Informatyki UAM, Poznań
• Instytut Matematyczny PAN, Warszawa

Bibliografia

• [1] M. Anshel, D. Goldfeld, Zeta functions, one-way functions, and pseudorandom number generators, Duke Math. J. 88(1997), 371–390.
• [2] C. Breuil, B. Conrad, F. Diamond, R. Taylor, On the modularity of elliptic curves over Q: wild 3-adic exercises, J. Amer. Math. Soc. 14 (2001), no. 4, 843–939.
• [3] D. Bump, Authomorphic forms and representations, Cambridge University Press, Cambridge 1997.
• [4] H. Davenport, Multiplicative number theory, 2nd ed. Springer, Berlin-Heidelberg 1980.
• [5] P. Deligne, Formes modulaires et representations l-adiques, Séminaire Bourbaki vol. 1968/69 Exposées 347-363, Lecture Notes in Mathematics 179, Berlin, New York: Springer-Verlag, 1971.
• [6] P. D. T. A. Elliott, The Riemann zeta function and coin tossing, J. Reine Angew. Math. 254 (1972), 100–109.
• [7] A. Fujii, On the zeros of Dirichlet L-functions, III, IV Trans. Amer. Math. Soc. 219 (1976), 347–349; J. Reine Angew. Math. 286(287) (1976), 139–143.
• [8] J. von zur Gathen, M. Karpinski, I. Shparlinski, Counting courves and their projections, in Proceedings of the 25th Annual Symposium on Theory of Computing, Association for Computing Machinery, New York, 1993, 805–812.
• [9] E. Hlawka, Über die Gleichverteilung gewisser Folgen, welche mit den Nullstellen der Zetafunktion zusammenhängen, Ӧsterreich. Akad. Wiss. Math.-Naturwiss. Kl. S.-B. II 184 (1975), no. 8-10, 459–471
• [10] D. Husemoller, Elliptic Curves, Grad. Texts in Math. 111, Springer-Verlag, New York 1987.
• [11] A. Ivíc, The Riemann Zeta-function, Wiley, New York, 1985.
• [12] H. Iwaniec, Topics in Classical Automorphic forms, Graduate Studies in Mathematics, 17, American Mathematical Society, Providence, Rhode Island, 1997.
• [13] J. Kaczorowski, The k-functions in multiplicative number theory, II, III, Acta Arith. 56(1990), 213–224; ibidem 57(1990), 199–210.
• [14] J. Kaczorowski, Axiomatic theory of L-functions: the Selberg class, in Analytic Number Theory, C.I.M.E. Summer School, Cetraro (Italy) 2002, ed. by A. Perelli, C. Viola, 133–209, Springer L.N. 1891, 2006.
• [15] J. C. Lagarias, A. M. Odlyzko, Effective versions of the Chebotarev density theorem. Algebraic number fields: L-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975), pp. 409–464. Academic Press, London, 1977.
• [16] J. Martinet, Character theory and Artin L-functions, in A. Fröhlich (ed.) Algebraic Number Theory, Academic Press London-New York-San Francisco 1977.
• [17] T. Miyake, Modular forms, Springer-Verlag 1989.
• [18] W. Narkiewicz, Elementary and analytic theory of algebraic numbers, PWN, Springer-Verlag, 1990.
• [19] K. Prachar, Primzahlverteilung, Springer-Verlag, 1978.
• [20] H. Rademacher, Collected papers of Hans Rademacher. Vol. II, Mathematicians of Our Time, 4. MIT Press, Cambridge, Mass.-London, 1974. xxi+638 pp.
• [21] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), no. 170, 483–494.
• [22] A. Selberg, Old and new conjecture and results about a class of Dirichlet series, Proceedings of the Amalfi Conference on Analytic Number Theory (Maiori, 1989) (ed. by E. Bombieri et. al.), 367-385, Università di Salerno, Salerno 1992; Collected papers vol II, 47-63, Springer, Berlin 1991.
• [23] J.-P. Serre, Propriétés galoisiennes des points d’ordre fini des courbes elliptiques, Invent. Math. 15 (1972), no. 4, 259–331.
• [24] E.C. Titchmarsh, The theory of the Riemann zeta function, 2nd ed., Clarendon Press, Oxford, 1988.
• [25] R. Taylor, A. Wiles, Ring-theoretic properties of certain Hecke algebras, Ann. of Math. (2) 141 (1995), no. 3, 553–572.
• [26] A. Wiles, Modular elliptic curves and Fermat’s last theorem, Ann. of Math. (2) 141 (1995), no. 3, 443–551.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).