Рассматриваются детерминированные методы построения графов Рамануджана в контексте их применения в качестве графов обобщённых клеточных автоматов, предназначенных для использования в криптографии. Изучены два семейства графов Любоцкого - Филипса - Сарнака (Xp'q и Yp'q), семейство графов Пайзера и семейство графов Моргенштерна. Сделан вывод, что для применения в указанном качестве подходят графы Пайзера и графы Yp'q. Приведены значения параметров графов из этих семейств, полученные численно.
Скачать электронную версию публикации
Загружен, раз: 314
- Title Детерминированные методы построения графов Рамануджана, предназначенных для применения в криптографических алгоритмах, основанных на обобщённых клеточных автоматах
- Headline Детерминированные методы построения графов Рамануджана, предназначенных для применения в криптографических алгоритмах, основанных на обобщённых клеточных автоматах
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 42
- Date:
- DOI 10.17223/20710410/42/6
Ключевые слова
расширяющий граф, граф Рамануджана, expander graph, Ramanujan graphАвторы
Ссылки
Ключарёв П. Г. Блочные шифры, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н. Э. Баумана. Электрон. журн. 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.
Детерминированные методы построения графов Рамануджана, предназначенных для применения в криптографических алгоритмах, основанных на обобщённых клеточных автоматах | Прикладная дискретная математика. 2018. № 42. DOI: 10.17223/20710410/42/6
Скачать полнотекстовую версию
Загружен, раз: 537