Математика и математическое моделирование. 2017; : 77-90
Построение случайных графов, предназначенных для применения в криптографических алгоритмах, основанных на обобщенных клеточных автоматах
https://doi.org/10.24108/mathm.0317.0000076Аннотация
Ранее автором в целом ряде работ были предложены методы построения симметричных криптографических алгоритмов, основанных на обобщенных клеточных автоматах. Дабы такие автоматы обладали хорошими криптографическими свойствами, их графы должны удовлетворять ряду условий. Производить построение таких графов возможно как детерминированными, так и рандомизированными методами. Рандомизированному методу их построения посвящена настоящая работа.
В работе приведены краткие сведения об обобщенных клеточных автоматах и требования, предъявляемые к графам таких автоматов, в том числе, следующие: граф должен иметь свойства, близкие к свойствам случайно выбранного графа; диаметр графа должен быть как можно меньше; граф должен быть регулярным; граф не должен быть двудольным; граф должен иметь как можно меньшее число петель и кратных ребер; граф должен иметь как можно меньшую степень (чтобы снизить коммуникационную сложность клеточного автомата); степень графа должна быть не меньше четырех; в семействе графов должно существовать достаточно большое количество графов с количеством вершин от нескольких десятков до нескольких тысяч.
Этим требованиям удовлетворяют расширяющие графы, в особенности, так называемые графы Рамануджана. Известно два способа построения небольших графов Рамануджана: построение случайного регулярного графа с последующей проверкой спектральных характеристик и построение графа при помощи некоторого известного детерминированного алгоритма. В данной работе рассмотрен первый способ. Приведен алгоритм генерации таких графов.
Для практических целей важно знать какие характеристики имеют случайные регулярные графы. С целью установления этого был проведен вычислительный эксперимент. Для каждого N из множества {256,512,1024,2048,4096} и каждого d из множества {3,4,5,6,7,8,9,10,11,12,13,14,15,16} было сгенерировано большое число случайных d-регулярных графов на N вершинах. Всего было сгенерировано 448 тыс. графов. Приведены графики плотностей распределения параметров λ и диаметров этих графов. Из графиков видно, что среди случайно сгенерированных регулярных графов, графы Рамануджана появляются с большой вероятностью, а диаметр полученных графов весьма мал. В целом, такие графы хорошо подходят для рассматриваемых целей.
Работа выполнена при финансовой поддержке РФФИ в рамках научного проекта №16-07-00542 а.
Список литературы
1. Ключарёв П.Г. Блочные шифры, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 12. С. 361-374. DOI: 10.7463/0113.0517543
2. Ключарёв П.Г. Криптографические хэш-функции, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2013. № 1. С. 161-172. DOI: 10.7463/0113.0534640
3. Davidoff G., Sarnak P., Valette A. Elementary number theory, group theory and Ramanujan graphs. N.Y.: Camb. Univ. Press, 2003. 144 p.
4. Hoory S., Linial N., Wigderson A. Expander graphs and their applications // Bulletin of the American Mathematical Society. 2006. Vol. 43. No. 4. Pp. 439–561. DOI: 10.1090/S0273-0979-06-01126-8
5. Lubotzky A., Phillips R., Sarnak P. Ramanujan graphs // Combinatorica. 1988. Vol. 8. No. 3. Pp. 261–277. DOI: 10.1007/BF02126799
6. Krebs M., Shaheen A. Expander families and Cayley graphs: A beginner’s guide. N.Y.: Oxf. Univ. Press, 2011. 258 p.
7. Sarnak P. Some applications of modular forms. Camb.; N.Y.: Camb. Univ. Press, 1990. 111 p.
8. Chung F.R.K. Spectral graph theory. Providence: Amer. Mathematical Soc., 1997. 207 p.
9. Sarnak P. What is... an expander? // Notices of the Amer. Mathematical Soc. 2004. Vol. 51. No. 7. Pp. 762–763.
10. Alon N., Roichman Y. Random Cayley graphs and expanders // Random Structures & Algorithms. 1994. Vol. 5. No. 2. Pp. 271–284. DOI: 10.1002/rsa.3240050203
11. Durrett R. Random graph dynamics. Camb.; N.Y.: Camb. Univ. Press, 2007. 212 p.
12. Hofstad R. van der. Random graphs and complex networks. Camb.: Camb. Univ. Press, 2017.
13. Janson S., Luczak T., Rucinski A. Random graphs: electronic resource. N.Y.: Wiley, 2011. DOI: 10.1002/9781118032718
14. Kolchin V.F. Random graphs. Camb.; N.Y.: Camb. Univ. Press, 1999. 252 p.
15. Krivelevich M., Penrose M., Fountoulakis N., Hefetz D. Random graphs, geometry and asymptotic structure. Camb.: Camb. Univ. Press, 2016.
16. Marchette D.J. Random graphs for statistical pattern recognition. Hoboken: Wiley-Interscience, 2004. 237 p. DOI: 10.1002/047172209X
17. Spencer J.H. The strange logic of random graphs. B.; N.Y.: Springer, 2001. 168 p. DOI: 10.1007/978-3-662-04538-1
18. Райгородский А.М. Модели случайных графов. 2-е изд. М.: МЦНМО, 2016. 139 с.
19. Friedman J. On the second eigenvalue and random walks in randomd-regular graphs // Combinatorica. 1991.Vol. 11. No. 4. Pp. 331–362.
20. Steger A., Wormald N. Generating random regular graphs quickly // Combinatorics, Probability and Computing. 1999. Vol. 8. No. 4. Pp. 377–396.
21. Kim J.H., Vu V.H. Generating random regular graphs // 35th Annual ACM symp. on theory of computing: STOC (San Diego, CA, June 9-11, 2003): Proc. N.Y.: ACM, 2003. Pp. 213–222. DOI: 10.1145/780542.780576
Mathematics and Mathematical Modeling. 2017; : 77-90
Random Graph Construction for Cryptographic Applications
https://doi.org/10.24108/mathm.0317.0000076Abstract
The author in a number of his previous papers proposed methods to construct symmetric cryptographic algorithms based on the generalized cellular automata. To possess good cryptographic properties, graphs of such automata must meet a number of requirements. To construct such graphs both the deterministic methods and the randomized ones can be used. The paper deals with the randomized method of their construction.
Briefly describing the generalized cellular automata it gives the requirements for graphs of such automata, including the following: the graph must have properties close to those of a randomly chosen graph; the graph diameter should be as small as possible; the graph must be regular; the graph should not be bipartite; the graph should have as minimum number of loops and multiple edges as possible; the graph degree should be (to reduce the communication complexity of the cellular automata) four, at least.
In the family of graphs there must be a sufficiently large number of graphs with the number of vertices from several tens to several thousand.
The expanding graphs, in particular, the so-called Ramanujan graphs meet these requirements. To build small Ramanujan graphs two methods are known, namely constructing a random regular graph with subsequent verification of spectral characteristics and constructing a graph by using a certain known deterministic algorithm. The paper considers the first method and gives an algorithm for generating such graphs.
For practical purposes, it is important to know what characteristics random regular graphs have. In order to find this, a computer experiment was carried out. For each N of the set {256,512,1024,2048,4096} and each d of the set {3,4,5,6,7,8,9,10,11,12,13,14,15,16} was generated a large number of random d-regular graphs on N vertices. A total of 448 thousand graphs were generated. The paper presents graphs of the density distribution of λ parameters and diameters of these graphs. It can be seen from the graphs that among the randomly generated regular graphs, the Ramanujan graphs appear with a high probability, and the diameter of the graphs obtained is quite small. In general, such graphs are well suitable for the purposes considered.
The research activity was supported by the Grant of the Russian Foundation for Basic Research within the framework of the scientific project No. 16-07-00542 a.
References
1. Klyucharev P.G. Blochnye shifry, osnovannye na obobshchennykh kletochnykh avtomatakh // Nauka i obrazovanie. MGTU im. N.E. Baumana. Elektron. zhurn. 2012. № 12. S. 361-374. DOI: 10.7463/0113.0517543
2. Klyucharev P.G. Kriptograficheskie khesh-funktsii, osnovannye na obobshchennykh kletochnykh avtomatakh // Nauka i obrazovanie. MGTU im. N.E. Baumana. Elektron. zhurn. 2013. № 1. S. 161-172. DOI: 10.7463/0113.0534640
3. Davidoff G., Sarnak P., Valette A. Elementary number theory, group theory and Ramanujan graphs. N.Y.: Camb. Univ. Press, 2003. 144 p.
4. Hoory S., Linial N., Wigderson A. Expander graphs and their applications // Bulletin of the American Mathematical Society. 2006. Vol. 43. No. 4. Pp. 439–561. DOI: 10.1090/S0273-0979-06-01126-8
5. Lubotzky A., Phillips R., Sarnak P. Ramanujan graphs // Combinatorica. 1988. Vol. 8. No. 3. Pp. 261–277. DOI: 10.1007/BF02126799
6. Krebs M., Shaheen A. Expander families and Cayley graphs: A beginner’s guide. N.Y.: Oxf. Univ. Press, 2011. 258 p.
7. Sarnak P. Some applications of modular forms. Camb.; N.Y.: Camb. Univ. Press, 1990. 111 p.
8. Chung F.R.K. Spectral graph theory. Providence: Amer. Mathematical Soc., 1997. 207 p.
9. Sarnak P. What is... an expander? // Notices of the Amer. Mathematical Soc. 2004. Vol. 51. No. 7. Pp. 762–763.
10. Alon N., Roichman Y. Random Cayley graphs and expanders // Random Structures & Algorithms. 1994. Vol. 5. No. 2. Pp. 271–284. DOI: 10.1002/rsa.3240050203
11. Durrett R. Random graph dynamics. Camb.; N.Y.: Camb. Univ. Press, 2007. 212 p.
12. Hofstad R. van der. Random graphs and complex networks. Camb.: Camb. Univ. Press, 2017.
13. Janson S., Luczak T., Rucinski A. Random graphs: electronic resource. N.Y.: Wiley, 2011. DOI: 10.1002/9781118032718
14. Kolchin V.F. Random graphs. Camb.; N.Y.: Camb. Univ. Press, 1999. 252 p.
15. Krivelevich M., Penrose M., Fountoulakis N., Hefetz D. Random graphs, geometry and asymptotic structure. Camb.: Camb. Univ. Press, 2016.
16. Marchette D.J. Random graphs for statistical pattern recognition. Hoboken: Wiley-Interscience, 2004. 237 p. DOI: 10.1002/047172209X
17. Spencer J.H. The strange logic of random graphs. B.; N.Y.: Springer, 2001. 168 p. DOI: 10.1007/978-3-662-04538-1
18. Raigorodskii A.M. Modeli sluchainykh grafov. 2-e izd. M.: MTsNMO, 2016. 139 s.
19. Friedman J. On the second eigenvalue and random walks in randomd-regular graphs // Combinatorica. 1991.Vol. 11. No. 4. Pp. 331–362.
20. Steger A., Wormald N. Generating random regular graphs quickly // Combinatorics, Probability and Computing. 1999. Vol. 8. No. 4. Pp. 377–396.
21. Kim J.H., Vu V.H. Generating random regular graphs // 35th Annual ACM symp. on theory of computing: STOC (San Diego, CA, June 9-11, 2003): Proc. N.Y.: ACM, 2003. Pp. 213–222. DOI: 10.1145/780542.780576
