Preview

Математика и математическое моделирование

Расширенный поиск

Построение случайных графов, предназначенных для применения в криптографических алгоритмах, основанных на обобщенных клеточных автоматах

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


Для цитирования:


Ключарёв П.Г. Построение случайных графов, предназначенных для применения в криптографических алгоритмах, основанных на обобщенных клеточных автоматах. Математика и математическое моделирование. 2017;(3):77-90. https://doi.org/10.24108/mathm.0317.0000076

For citation:


Klyucharev P.G. Random Graph Construction for Cryptographic Applications. Mathematics and Mathematical Modeling. 2017;(3):77-90. (In Russ.) https://doi.org/10.24108/mathm.0317.0000076

Просмотров: 237


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)