Here, a short survey is presented on the group-based cryptography that is a contemporaryarea of an activity which explores how abstract innite groups can be used asplatforms for constructing cryptographic primitives, systems and protocols. Studying in thearea is developed by the methods of group theory, complexity theory and theory of computations.Undecidable and allegebly hard algorithmic problems from group theory are thebase of the constructing. Dierent complexity aspects of the algorithmic problems and thecorresponding search problems are discussed. The universality of the diophantine languagein cryptography is explained, and its combining role is noted. The free metabelian groups asplatforms for constructing cryptographic systems and protocols is suggested. Some reasonsfor the suggestion including a decidability of the word problem and existing normal forms ofelements are stated. One more reason is a non-decidability of the equation solvability problemand non-decidability of the endomorphism problem in these groups that follow from anon-decidability of the 10-th Hilbert Problem. It is promised that the considerations of thepaper will be used in the forthcoming paper by the author and S. Y. Erofeev for constructinga possibly one-way function and an autentication protocol with zero knowledge on afree metabelian group.
Download file
Counter downloads: 73
- Title Diophantine cryptography over innite groups
- Headline Diophantine cryptography over innite groups
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(16)
- Date:
- DOI
Keywords
endomorphism problem, free metabelian group, diophantine cryptography, diophantine language, generic complexity, search problem, algorithmic problem, group-based cryptography, проблема эндоморфной сводимости, свободная метабелева группа, диофантова криптография, диофантов язык, генерическая сложность, проблема поиска, алгоритмическая проблема, основанная на группах, криптографияAuthors
References
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.
Diophantine cryptography over innite groups | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 2(16).
Download full-text version
Download fileCounter downloads: 211