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

P. G. Klyucharev

Prikladnaâ diskretnaâ matematika, no. 4 (2018), pp. 76-93.

Résumé

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 — $X^{p, q}$ and $Y^{p, 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 $Y^{p, 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 $X^{p, 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.

Détail

Keywords: expander graph, Ramanujan graph.

Bibliographie

[1] Klyucharev P. G., “Block ciphers based on generalized cellular automata”, Science and Education of the Bauman MSTU, 2012, no. 2, 361–374 (in Russian)

[2] Klyucharev P. G., “Cryptographic hash functions based on generalized cellular automata”, Science and Education of the Bauman MSTU, 2013, no. 1, 161–172 (in Russian)

[3] Toffoli T., Margolus N., Cellular Automata Machines, MIT Press, 1987, 276 pp.

[4] Kauffman S. A., “Metabolic stability and epigenesis in randomly constructed genetic net”, J. Theor. Biol., 1969, no. 22, 437–467 | DOI | MR

[5] Suhinin B. M., “Construction of pseudorandom binary sequence generators based on cellular automata”, Science and Education of the Bauman MSTU, 2010, no. 9 | Zbl

[6] Davidoff G., Sarnak P., Valette A., Elementary Number Theory, Group Theory and Ramanujan Graphs, London Mathematical Society Student Texts, 55, Cambridge University Press, Cambridge, 2003, 144 pp. | MR | Zbl

[7] Hoory S., Linial N., Wigderson A., “Expander graphs and their applications”, Bull. Amer. Math. Soc., 43:4 (2006), 439–562 | DOI | MR

[8] Lubotzky A., Phillips R., Sarnak P., “Ramanujan graphs”, Combinatorica, 8:3 (1988), 261–277 | DOI | MR | Zbl

[9] Krebs M., Shaheen A., Expander Families and Cayley Graphs: A Beginner's Guide, Oxford University Press, Oxford, 2011, 258 pp. | MR | Zbl

[10] Sarnak P., Some Applications of Modular Forms, Cambridge Tracts in Mathematics, 99, Cambridge University Press, Cambridge, 1990, 111 pp. | MR | Zbl

[11] Chung F., Spectral Graph Theory, Amer. Math. Soc., 1997, 207 pp. | MR | Zbl

[12] Sarnak P., What is ... an expander?, Notices Amer. Math. Soc., 51, 762–770 | MR

[13] Lubotzky A., Discrete Groups, Expanding Graphs and Invariant Measures, Springer Science Business Media, 2010, 196 pp. | MR

[14] Lubotzky A., Phillips R., Sarnak P., “Explicit expanders and the Ramanujan conjectures”, Proc. 18th Ann. ACM Symp. on Theory of Computing, ACM, 1986, 240–246

[15] Grove L., Classical Groups and Geometric Algebra, Fields Institute Communications, 39, Amer. Math. Soc., 2002, 169 pp. | MR

[16] Humphreys J., A Course in Group Theory, Oxford Graduate Texts in Mathematics, Oxford University Press, Oxford, 1996, 279 pp. | MR | Zbl

[17] James G., Liebeck M., Representations and Characters of Groups, Cambridge Mathematical Textbooks, Cambridge University Press, Cambridge, 2001, 458 pp. | MR | Zbl

[18] Lanski C., Concepts in Abstract Algebra, Amer. Math. Soc., 2005, 545 pp. | MR

[19] Kargapolov M. I., Merzlyakov Yu. I., Foundations of Group Theory, Nauka, Fizmatlit Publ., M., 1996, 287 pp. (in Russian) | MR

[20] Morgenstern M., “Existence and explicit constructions of $q+1$ regular Ramanujan graphs for every prime power $q$”, J. Combinatorial Theory. Ser. B, 62:1 (1994), 44–62 | DOI | MR | Zbl

[21] Petit C., On Graph-Based Cryptographic Hash Functions, PhD Thesis, Catholic University of Louvain, 2009, 286 pp. http://www0.cs.ucl.ac.uk/staff/c.petit/files/thesis.pdf

[22] Nikkel T., Ramanujan Graphs, Master's Thesis, University of Manitoba, 2007, 112 pp. http://mspace.lib.umanitoba.ca/bitstream/handle/1993/9146/thesis.pdf

[23] Pizer A. K., “Ramanujan graphs and Hecke operators”, Bull. Amer. Math. Soc., 23:1 (1990), 127–137 | DOI | MR | Zbl

[24] Charles D. X., Lauter K. E., Goren E. Z., “Cryptographic hash functions from expander graphs”, J. Cryptology, 22:1 (2009), 93–113 | DOI | MR | Zbl

[25] Silverman J., Advanced Topics in the Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, Springer, N.Y., 2013, 528 pp. | MR

[26] Blake I., Seroussi G., Smart N., Elliptic Curves in Cryptography, Lecture Note Series, Cambridge University Press, Cambridge, 1999, 204 pp. | MR | Zbl

[27] Silverman J., The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, Springer, N.Y., 2009, 402 pp. | DOI | MR | Zbl

[28] Washington L., Elliptic Curves: Number Theory and Cryptography, Discrete Mathematics and its Applications, 2nd Ed., CRC Press, Boca Raton, 2008, 536 pp. | DOI | MR | Zbl

[29] Vélu J., “Isogénies entre courbes elliptiques”, C. R. Acad. Sci. Paris Sér. AB, 273 (1971), A238–A241 | MR

[30] Shumow D., Isogenies of Elliptic Curves: A Computational Approach, Master's Thesis, University of Washington, 2009, 78 pp., arXiv: abs/0910.5370

[31] Bosma W., Cannon J., Playoust C., “The Magma algebra system. I. The user language”, J. Symbolic Comput., 24:3–4 (1997), 235–265 | DOI | MR | Zbl

[32] W. Bosma, J. Cannon, C. Fieker, A. Steel (eds.), Handbook of Magma Functions, Edition 2.20, , 2014, 5583 pp. https://www.math.uzh.ch/sepp/magma-2.19.8-cr/Handbook.pdf

[33] Klyucharev P. G., “Construction of pseudorandom functions based on generalized cellular automata”, Science and Education of the Bauman MSTU, 2012, no. 10, 263–274 (in Russian)