HomeIssuesDeterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automata

Deterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automata | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 42. DOI: 10.17223/20710410/42/6

Earlier, the author proposed a number of methods for constructing symmetric cryptographic algorithms based on generalized cellular automata. In order to make such automata to be cryptographically strong, their graphs must satisfy a number of requirements. In particular, they must be regular not bipartite graphs with a small diameter, a small degree (but not less than 4) and the amount of graphs in the family with the number of vertices from dozens to several thousand must be large enough (it would be desirable to have at least several dozens of graphs with a number of vertices more or less uniformly distributed in the given range). Some of Ramanujan graphs satisfy these requirements. There are two ways to construct relatively small Ramanujan graph: the random way and the deterministic way. In this paper, the deterministic methods for Ramanujan graphs construction in the context of their application in generalized cellular automata being a base of cryptographic algorithms are considered. Each method can be identified with the family of graphs generated by it. Among them are two families of graphs constructed by Lubotzky, Philips and Sarnak - Xp'q and Yp'q, the family of graphs constructed by Pizer, and the family of graphs constructed by Morgenstern. Values of parameters of graphs from these families are numerically computed. After research, we came to conclusion that Pizer graphs (based on isogenies of elliptic curves over finite fields) and the Yp,q Lubotzky - Philips - Sarnak graphs (based on projective transformations of a projective line over a finite field) are suitable for the purposes under consideration, because, according to literature review, they meet all the necessary requirements, in particular, they are not bipartite, and among them there are sufficiently large amount of relatively small graphs with small degrees (all Ramanujan graphs are regular and have a small diameter). At the same time, the Xp,q Lubotzky - Philips - Sarnak graphs and Morgenstern graphs are not suitable for considered purposes, because among them there are too few not bipartite graphs with a small degree and with a number of vertices in the desired range.
Download file
Counter downloads: 318
  • Title Deterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automata
  • Headline Deterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automata
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 42
  • Date:
  • DOI 10.17223/20710410/42/6
Keywords
расширяющий граф, граф Рамануджана, expander graph, Ramanujan graph
Authors
References
Ключарёв П. Г. Блочные шифры, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н. Э. Баумана. Электрон. журн. 2012. №12. C. 361-374.
Ключарёв П. Г. Криптографические хэш-функции, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н. Э. Баумана. Электрон. журн. 2013. №1. C. 161-172.
Тоффоли Т., Марголус Н. Машины клеточных автоматов: пер. с англ. М.: Мир, 1991. 280 с.
Kauffman S. A. Metabolic stability and epigenesis in randomly constructed genetic net // J. Theor. Biol. 1969. No. 22. P. 437-467.
Сухинин Б. М. Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов // Наука и образование. МГТУ им. Н. Э. Баумана. Электрон. журн. 2010. №9. http://engineering-science.ru/doc/159714.html
Davidoff G., Sarnak P., and Valette A. Elementary Number Theory, Group Theory and Ramanujan Graphs. Cambridge: Cambridge University Press, 2003. V. 55. 144 p.
Hoory S., Linial N., and Wigderson A. Expander graphs and their applications // Bull. Amer. Math. Soc. 2006. V. 43. No. 4. P. 439-562.
Lubotzky A., Phillips R., and Sarnak P. Ramanujan graphs // Combinatorica. 1988. V. 8. No. 3. P. 261-277.
Krebs M. and Shaheen A. Expander Families and Cayley Graphs: A Beginner's Guide. Oxford: Oxford University Press, 2011. 258 p.
Sarnak P. Some Applications of Modular Forms. Cambridge: Cambridge University Press, 1990. V. 99. 111 p.
Chung F. Spectral Graph Theory. Amer. Math. Soc., 1997. 207 p.
Sarnak P. What is.. an expander? // Notices Amer. Math. Soc. 2004. V. 51. P. 762-770.
Lubotzky A. Discrete Groups, Expanding Graphs and Invariant Measures. Springer Science & Business Media, 2010. 196 p.
Lubotzky A., Phillips R., and Sarnak P. Explicit expanders and the Ramanujan conjectures // Proc. 18th Ann. ACM Symp. on Theory of Computing. ACM, 1986. P. 240-246.
Grove L. Classical Groups and Geometric Algebra. Fields Institute Communications. Amer. Math. Soc., 2002. 169 p.
Humphreys J. A Course in Group Theory. Oxford Graduate Texts in Mathematics. Oxford: Oxford University Press, 1996. 279 p.
James G. and Liebeck M. Representations and Characters of Groups. Cambridge Mathematical Textbooks. Cambridge: Cambridge University Press, 2001. 458 p.
Lanski C. Concepts in Abstract Algebra. Amer. Math. Soc., 2005. 545 p.
Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. М.: Наука, Физматлит, 1996. 287 с.
Morgenstern M. Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q //J. Combinatorial Theory. Ser. B. 1994. V. 62. No. 1. P. 44-62.
Petit C. On Graph-Based Cryptographic Hash Functions. PhD Thesis. Catholic University of Louvain, 2009. 286p. wwwO.cs.ucl.ac.uk/staff/c.petit/files/thesis.pdf
Nikkel T. Ramanujan Graphs. Master's Thesis. University of Manitoba, 2007. 112 p. http: //mspace.lib.umanitoba.ca/bitstream/handle/1993/9146/thesis.pdf
Pizer A. K. Ramanujan graphs and Hecke operators // Bull. Amer. Math. Soc. 1990. V. 23. No. 1. P. 127-137.
Charles D. X., Lauter K. E., and Goren E. Z. Cryptographic hash functions from expander graphs // J. Cryptology. 2009. V. 22. No. 1. P. 93-113.
Silverman J. Advanced Topics in the Arithmetic of Elliptic Curves. Graduate Texts in Mathematics. N.Y.: Springer, 2013. 528p.
Blake I., Seroussi G., and Smart N. Elliptic Curves in Cryptography. Lecture Note Series. Cambridge: Cambridge University Press, 1999. 204 p.
Silverman J. The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics. N.Y.: Springer, 2009. 402 p.
Washington L. Elliptic Curves: Number Theory and Cryptography. 2nd Ed. Discrete Mathematics and its Applications. Boca Raton: CRC Press, 2008. 536 p.
Velu J. Isogenies entre courbes elliptiques // CR Acad. Sci. Paris Ser. AB. 1971. V. 273. P. A238-A241.
Shumow D. Isogenies of Elliptic Curves: A Computational Approach. Master's Thesis. University of Washington, 2009. 78p. https://arxiv.org/abs/0910.5370
Bosma W., Cannon J., and Playoust C. The Magma algebra system. I. The user language // J. Symbolic Comput. 1997. V.24. No. 3-4. P. 235-265.
Handbook of Magma Functions. Edition 2.20 / eds. W. Bosma, J. Cannon, C. Fieker, and A. Steel. 2014. 5583p. https://www.math.uzh.ch/sepp/magma-2.19.8-cr/Handbook.pdf
Ключарёв П. Г. Построение псевдослучайных функций на основе обобщенных клеточных автоматов // Наука и образование. МГТУ им. Н. Э. Баумана. Электрон. журн. 2012. №10. С. 263-274.
Deterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automata | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 42. DOI: 10.17223/20710410/42/6
Deterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automata | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 42. DOI: 10.17223/20710410/42/6
Download full-text version
Counter downloads: 538