ГлавнаяАрхивДиофантова криптография на бесконечных группах

Диофантова криптография на бесконечных группах | Прикладная дискретная математика. 2012. № 2(16).

В работе даётся краткое представление криптографии, основанной на группах («group-based cryptography»),- современного направления, главными объектами в котором являются абстрактные бесконечные группы, а основной целью - построение на них криптографических примитивов, систем и протоколов. Исследования по этому направлению ведутся методами теории групп, теории сложности и теории вычислений. Обращается внимание на использование неразрешимых и трудноразрешимых алгоритмических проблем теории групп в качестве основы обозначенного построения. Обсуждаются аспекты сложности алгоритмических проблем и связанных с ними проблем поиска. Объясняется универсальность диофантова языка в криптографии. Отмечается его объединяющая роль. В качестве возможных платформ для криптографических систем и протоколов предлагается использовать свободные метабелевы группы. Приводятся основания для такого использования, в том числе алгоритмическая разрешимость в этих группах проблемы равенства и наличие нормальных форм записи элементов группы. Ещё одним основанием является алгоритмическая неразрешимость в таких группах проблемы существования решений у групповых уравнений и алгоритмическая неразрешимость проблемы эндоморфной сводимости, вытекающих из неразрешимости 10-й Проблемы Гильберта. Предполагается, что в последующей работе автора совместно с С.Ю. Ерофеевым материал данной работы будет использован для построения на свободных метабелевых группах возможно односторонних функций и протоколов аутентификации с нулевым разглашением.
  • Title Диофантова криптография на бесконечных группах
  • Headline Диофантова криптография на бесконечных группах
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(16)
  • Date:
  • DOI
Ключевые слова
endomorphism problem, free metabelian group, diophantine cryptography, diophantine language, generic complexity, search problem, algorithmic problem, group-based cryptography, проблема эндоморфной сводимости, свободная метабелева группа, диофантова криптография, диофантов язык, генерическая сложность, проблема поиска, алгоритмическая проблема, основанная на группах, криптография
Авторы
Ссылки
Jones J. Universal diophantine equation // J. Symbolic Logic. 1982. V. 47. No. 3. P. 549-571.
Алламбергенов Х. С., Романьков В. А. Произведения коммутаторов в группах // Докл. АН Уз. ССР. 1984. Т. 4. С. 14-15.
Холл М. Теория групп. М.: ИЛ, 1962. 467 с.
Stroud P. Ph. D. Thesis. Cambridge, 1966. 121 p.
Segal D. Words: notes on verbal width in groups // London Math. Soc. Lect. Notes. V. 361. Cambridge: Cambridge Univ. Press, 2009. 215 p.
Hall P. Nilpotent groups // Canad. Math. Cong. Summer Sem. Vankuver: University of Alberta, 1957. P. 12-30.
Baumslag G., Mikhailov R., and Orr K. E. A new look at finitely generated metabelian groups // arXiv math. Group Theory. 2012. No. 1203.5431. 17 p.
Groves J. R. J. and Miller III C. F. Recognizing free metabelian groups // Illinois J. Math. 1986. V.30. No. 2. P. 246-254.
Baumslag G., Cannonito F., and Robinson D. J. S. The algorithmic theory of finitely generated metabelian groups // Trans. Amer. Math. Soc. 1994. V. 344. P. 629-648.
Вентура Э., Романьков В. А. Проблема скрученной сопряженности для эндоморфизмов метабелевых групп // Алгебра и логика. 2009. Т. 48. №2. С. 157-173.
Носков Г. А. О сопряженности в метабелевых группах // Математические заметки. 1982. Т. 31. №4. С. 495-507.
Тимошенко Е. И. Алгоритмические проблемы для метабелевых групп // Алгебра и логика. 1973. Т. 12. №2. С. 232-240.
Романовский Н. С. О некоторых алгоритмических проблемах для разрешимых групп // Алгебра и логика. 1974. Т. 13. №1. С. 26-34.
Vassileva S. Polynomial time conjugacy in wreath products and free solvable groups // Groups. Complexity. Cryptology. 2011. V. 3. P. 105-120.
Myasnikov A., Roman'kov V., Ushakov A., and VershikA. The word and geodesic problems in free solvable groups // Trans. Amer. Math. Soc. 2010. V.362. P. 4655-4682.
Рыбалов А. Н. О генерической неразрешимости десятой проблемы Гильберта // Вестник Омского университета. 2011. №4. С. 19-22.
Тимошенко Е. И. Эндоморфизмы и универсальные теории разрешимых групп. Новосибирск: Изд-во НГТУ, 2011. 327 с.
Goldreich O. Foundations of cryptography. Cambridge: Cambridge Univ. Press., 2001. V1. 451 p.; 2004. V.2. 798 p.
Ерофеев С. Ю. Схемы построения двушагово односторонних функций // Вестник Омского университета. 2011. №4. С. 15-18.
Ерофеев С. Ю. Диофантовость дискретного логарифма // Вестник Омского университета. 2010. №4. С. 13-15.
Ерофеев С.Ю. Диофантовость дискретного логарифма // Прикладная дискретная математика. Приложение. 2011. №4. С. 31-32.
Kellerer H., Pferschy U., and Pisinger D. Knapsack Problems. Berlin, New York: Springer Verlag, 2004. 546 p.
Cook S. A. and Mitchell D. G. Finding hard instances of the satisfiability problem: A survey // Satisfiability problem: Theory and Applications. V. 35. Providence, RI: Amer. Math. Soc., 1997. P. 1-17.
Gilman R., Myasnikov A. G., Miasnikov A. D., and Ushakov A. Report on generic case complexity // Вестник Омского университета. Спец. вып.: Комбинаторные методы алгебры и сложность вычислений. 2007. С. 103-110.
Smale S. On the average number of steps of the simplex method of linear programming // Math. Programming. 1983. V. 27. P. 241-262.
Вершик А. М., Спорышев П. В. Ограничение среднего числа шагов в симплекс-методе и проблемы асимптотической интегральной геометрии // Докл. АН СССР. Т. 271. № 5. С.1044-1048.
Хачиян Л. А. Полиномиальный алгоритм в линейном программировании // Докл. АН СССР. 1979. Т. 244. №5. С. 1093-1096.
Borovik A., Myasnikov A., and Shpilrain V. Measuring sets in infinite groups // Contemp. Math. V. 298. Providence, RI: Amer. Math. Soc., 2002. P. 21-42.
Klee V. and Minty G. How good is the simplex algorithm? // Inequalities. Proc. Third. Symp., Univ. California. California: Academic Press, 1972. P. 159-175.
Celler F., Leedham-Green C. R., Murray S. H., et al. Generating random elements of a finite group // Comm. Algebra. 1995. V.23. No.3. P. 4931-4948.
Kapovich I., Myasnikov A., Shupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. V. 264. P. 665-694.
Kapovich I., Myasnikov A., Shupp P., and Shpilrain V. Average-case complexity and decision problems in group theory // Adv. Math. 2005. V. 190. P. 343-359.
Gurevich Y. Average case comleteness // J. Comput. Syst. Sci. 1991. V. 42. P. 346-398.
Levin L. Average case complete problems // SIAM J. Comput. 1986. V. 15. P. 285-286.
Computational complexity theory / eds. S. Rudich and A. Wigderson. Amer. Math. Soc. Institute for Advanced Study, IAS/Park City Math. Series. V. 10. Providence, RI: Amer. Math. Soc., 2004. 389 p.
Papadimitriou C. Computation complexity. Boston: Addison-Wesley, 1994. 523 p.
Fine B., Habeeb M., Kahrobaei D., and Rosenberger G. Survey and open problems in noncommutative cryptography // JP J. Algebra, Number Theory and Applications. 2011. V. 21. P. 1-40.
Magyarik M. R. and Wagner N. P. A public key cryptosystem based on the word problem // LNCS. 1985. V. 196. P. 19-36.
Petrides G. Cryptoanalisis of the public key cryptosystem based on the word problem on the Grigorchuk groups // LNCS. 2003. V. 2898. P. 234-244.
Gebhardt V. A new approach to the conjugacy problem in Garside groups // J. Algebra. 2005. V.292. P. 282-302.
Курош А. Г. Теория групп. М.: Физматгиз, 2008. 808 с.
Garside F. A. The braid group and other groups // Quart. J. Math. 1969. V. 20. No. 78. P. 235-254.
Gebhardt V. Conjugacy search in braid groups from a braid-based cryptography point of view // Applicable Algebra in Engineering Communication and Computing. 2006. V. 17. P. 219-238.
Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. М.: Лань, 2009. 288 с.
Михайлова К. А. Проблема вхождения для прямых произведений групп // Докл. АН СССР. 1958. Т. 119. С. 1103-1105.
HoltD.F., EickB., and O'Brien E. A. Handbook of computational group theory. London: Chapman & Hall/CRC, 2005. 414 p.
Detinko A., Eick B., and Flannery D. Computing with matrix groups // London Math. Soc. Lect. Notes Ser. 2011. V.387. P. 256-270.
Sims C. C. Computation with finitely presented groups. Cambridge: Cambridge Univ. Press, 1994. 604 p.
Miller III C. F. Decision problems for groups - survey and reflections // Algorithms and Classification in Combinatorial Group Theory. Berlin, Heidelberg, New York: Springer Verlag, 1992. P. 1-60.
Адян С. И., Дурнев В. Г. Алгоритмические проблемы для групп и полугрупп // Успехи матем. наук. 2000. Т. 55. С. 3-94.
Ремесленников В. Н., Романьков В. А. Теоретико-модельные и алгоритмические вопросы теории групп // Итоги науки и техн. Алгебра. Геометрия. Топология. Т. 21. М.: ВИНИТИ, 1983. С. 3-79.
Адян С. И. Неразрешимость некоторых алгоритмических проблем в теории групп // Труды Моск. матем. общества. 1957. Т. 6. С. 231-298.
Новиков П. С. Неразрешимость проблемы сопряженности в теории групп // Изв. АН СССР. Сер. матем. 1954. Т. 18. №6. С. 485-524.
Новиков П. С. Об алгоритмической неразрешимости проблемы тождества слов в теории групп // Труды Матем. ин-та АН СССР. 1955. Т. 44. С. 3-143.
Birget J.-C., Magliveras S., and Sramka M. On public-key cryptosystems based on combinatorial group theory // Tatra Mountains Math. Publ. 2006. V. 33. P. 137-148.
Kurt Y. A new key exchange primitive based on the triple decomposition problem // Preprint: http://eprint.iacr.org/2006/378
Shpilrain V. and Zapata G. Combinatorial group theory and public key cryptography // Applicable Algebra in Engineering Communication and Computing. 2006. V. 17. P. 291-302.
Shpilrain V. and Zapata G. Using decision problems in public key cryptography // Groups. Complexity. Cryptology. 2009. V. 1. P. 33-40.
Shpilrain V. and Zapata G. Using the subgroup membership problem in public key cryptography // Contemp. Math. V. 418. Providence, RI: Amer. Math. Soc., 2006. P. 169-179.
Матиясевич Ю. В. Десятая проблема Гильберта. М.: Наука, 1993. 223 с.
Матиясевич Ю. В. Диофантово представление перечислимых предикатов // Изв. АН СССР. Сер. матем. 1971. Т. 35. №1. С. 3-30.
Grigoriev D. and Shpilrain V. Zero-knowledge autentification schemes from actions on graphs, groups and rings // Ann. Pure Appl. Logic. 2010. V. 162. P. 194-200.
Матиясевич Ю. В. Диофантовость перечислимых множеств // Докл. АН СССР. 1970. Т. 191. №2. С. 279-282.
Романьков В. А. Об уравнениях в свободных метабелевых группах // Сиб. матем. ж. 1979. Т. 40. №3. С. 671-673.
Mahlburg K. An overview of braid group cryptography. 2004. www.math.wisc.edu/~boston/ mahlburg.pdf
Нейман Х. Многообразия групп. М.: Мир, 1974. 264 с.
Романьков В. А. О неразрешимости проблемы эндоморфной сводимости в свободных нильпотентных группах и в свободных кольцах // Алгебра и логика. 1977. Т. 16. №4. С.457-471.
Dehornoy P. Braid-based cryptography // Group theory, statistics and cryptography. Contemp. Math. V.360. Providence, RI: Amer. Math. Soc., 2004. P. 5-33.
Dehornoy P. Braids and self-distributivity. (Progress in Math. 192). Basel, Berlin, New York: Birkhauser Verlag, 2000. 623 p.
Лин В. Я. Косы Артина и связанные с ними группы и пространства // Итоги науки и техн. Алгебра. Геометрия. Топология. Т. 17. М.: ВИНИТИ, 1983. С. 159-227.
Марков А. А. Основы алгебраической теории кос // Труды Матем. ин-та АН СССР. 1945. Т. 16. С. 3-54.
www.grouptheory.info/PersonalPages/Shpilrain,Vladimir/CryptologyePrintArchive
AnshelI., AnshelM., and Goldfeld D. An algebraic method for public-key cryptography // Math. Res. Lett. 1999. V. 6. P. 287-291.
Myasnikov A., Shpilrain V., and Ushakov A. Non-commutative cryptography and complexity of group-theoretic problems. (Amer. Math. Soc. Surveys and Monographs). Providence, RI: Amer. Math. Soc., 2011. 385 p.
Myasnikov A., Shpilrain V., and Ushakov A. Group-based cryptography. (Advances courses in Math., CRM, Barselona). Basel, Berlin, New York: Birkhauser Verlag, 2008. 183 p.
Диофантова криптография на бесконечных группах | Прикладная дискретная математика. 2012. № 2(16).
Диофантова криптография на бесконечных группах | Прикладная дискретная математика. 2012. № 2(16).
Полнотекстовая версия