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.