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

Настоящая диссертация посвящена двум основным темам:

1. Исследование структуры и возможности точного представления матрицами (линейности) группы унитреугольных автоморфизмов относительно свободных групп.

2. Построение новых конструкций возможно односторонних функций на основе алгоритмической неразрешимости проблемы эндоморфной сводимости в группах и Диофантовой проблемы.

Группа унитреугольных автоморфизмов. Группам автоморфизмов относительно свободных групп как конечного, так и бесконечного, рангов посвящено немало работ. См., например, обзоры [20, 32, 65].

Обозначим через Fn свободную группу ранга п с базисом Хп = {х,., хп}, через F$Q свободную группу бесконечного счетного ранга с базисом Хк0 = {xi, Х2, ¦ ¦ •}, группа Fx0 рассматривается как объединение F⁰ = U™=lFn. Также обозначим через Gn относительно свободную группу ранга п некоторого многообразия групп С, через относительно свободную группу бесконечного счетного ранга многообразия С.

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

Крамер в работе [50] доказал линейность группы AutF2.

Форманек и Прочези в работе [39] доказали, что при п > 3 группа AutFn не линейна.

Ауслендер и Баумслаг в работе [31] доказали, что группа автоморфизмов любой конечно порожденной почти нильпотентной группы линейна. Более того, голоморф такой группы (значит и ее группа автоморфизмов) допускают точное представление матрицами над кольцом целых чисел Z. Отсюда следует в частности, что группы автоморфизмов относительно свободных групп конечного ранга почти нильпотентных многообразий групп допускают точное представление матрицами.

Ольшанский в работе [61] доказал, что если относительно свободная группа Сп не свободна и не почти нильпотентна, то ее группа автоморфизмов АЫСп не линейна. В этой же работе отмечалось, что близкие по формулировке результаты содержатся в статьях [10, 15]. Однако, обе эти статьи содержат неточности в формулировках и существенные ошибки в доказательствах.

Заметим также, что группа автоморфизмов АЫСц0 для любого нетривиального многообразия С содержит подгруппу, определяемую всеми подстановками бесконечного счетного множества свободных порождающих которая изоморфна группе подстановок 5к0. Последняя, как хорошо известно, нелинейна.

Никакие из приведенных работ не дают представление о линейности достаточно естественной подгруппы унитрегольных автоморфизмов.

Новые конструкции возможно односторонних функций. Односторонние (в другой терминологии однонаправленные) функции являются неотъемлемой частью криптографических схем и протоколов. Теоретически их существование при формальном определении до сих пор не установлено. В то же время, односторонние функции являются основным инструментом во многих разделах и приложениях криптографии, в частности, они применяются в электронных подписях, протоколах аутентификации, алгоритмах генерации псевдослучайных последовательностей и т. п. Конечно, используемые с указанной целью функции можно назвать только возможно односторонними.

Относительно общей теории односторонних функций см. монографии [40, 62, 71]. В работах JI. Левина [12, 53] приведена универсальная функция, которая автоматически является односторонней, если существует хотя бы одна односторонняя функция. Такие функции названы полными односторонними функциями. Для их построения JI. Левин использовал нумерацию всех машин Тьюринга [53] и комбинаторный тайлинг [12]. Отсюда видно, что такое построение имеет чисто теоретическое значение. В работе А. Кожевникова, С. Николенко [9] приведены другие примеры полных односторонних функций.

Новые конструкции односторонних функций, предложенные в диссертации, относятся к «криптографии основанной на группах «(«group-based cryptography») — современному направлению, возникшему на рубеже 20-го и 21-го столетий. Основными объектами в нем являются абстрактные бесконечные группы, а основной целью — построение на этих группах криптографических схем и протоколов. Исследования ведутся методами теории групп, теории сложности и теории вычислений. Современное состояние полученных в этой области результатов отражено в монографиях [59, 60].

Диссертация состоит из трех глав.

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

Мы определяем естественную подгруппу UTAutGn группы AutGn, которую мы называем группой унитреугольных автоморфизмов. Нас интересуют вопрос о ее структуре и точной представимости матрицами над полем, то есть линейности. Также мы вводим естественное понятие длины автоморфизма и рассматриваем вопрос оценки длины обратного автоморфизма через длину данного автоморфизма.

В доказательстве А. Ю. Ольшанского основного результата работы [61], отмеченного выше, использованы следующие соображения. Для произвольной группы определен гомоморфизм о: (7 —> АЫС, сопоставляющий элементу д внутренний автоморфизм ад: / д$д~1. Ядром гомоморфизма, а является центр С© группы (7, а образом — группа /ппС внутренних автоморфизмов группы С. Последняя нормальна в АиЮ. Это означает, что фактор группа (?/С (С7) ~ /ппС может рассматриваться как нормальная подгруппа группы АЫС. А. Ю. Ольшанский показал в [61], что в случае не свободной и не ПОЧТИ нильпотентной относительно свободной группы Сп существует такой автоморфизм в группы Сп, что расширение Р группы Сп/С (Сп) посредством в не линейно. Выбор в осуществлялся таким образом, что индуцируемое им линейное преобразование абеализации (Сп)аь = Сп/Сп) которая в данном случае при предположении о линейности группы АиЮп есть свободная абе-лева группа ранга п, не имело в качестве характеристических чисел корни из 1. Заметим, что автоморфизм в заведомо не унитреуголен, так как все характеристические числа последнего равны 1. Группа /ппСп ~ СП/С (СП) также не состоит из унитреугольных автоморфизмов. Таким образом, результат А. Ю. Ольшанского и примененный им способ доказательства не дают информации о возможной линейности группы ип = иТАиЮп. Кроме этого в работе [61] использована теорема из [21], по которой любое (не обязательно точное) представление матрицами над полем группы АиЬМп автоморфизмов свободной метабелевой группы Мп ранга п переводит группу Мп ~ 1ппМп в почти нильпотентную подгруппу. При доказательстве результатов, формулируемых ниже, данная теорема не применяется.

В параграфе 1.2 дано описание структуры группы унитреугольных автоморфизмов ип относительно свободной группы Сп конечного ранга п произвольного многообразия групп С, позволяющее ввести эффективное понятие нормальной формы элемента и представить группу ]п через порождающие элементы и определяющие соотношения. Случаи п = 1,2 очевидны: группа 11 тривиальна, группа II2 циклическая. При п > 3 доказано следующее. Если группа нильпотентна, то группа унитреугольных автоморфизмов 11п также нильпотентна. Если группа 1 почти нильпотентна, то группа ип допускает точное представление матрицами. Если же многообразие С отлично от многообразия всех групп и группа (?п 1 не почти нильпотентна, то группа ип не допускает точного представления матрицами ни над каким полем. Таким образом, дана исчерпывающая классификация точной матричной представимости групп унитреугольных автоморфизмов относительно свободных групп конечного ранга собственных многообразий групп, что дополняет известные результаты А. Ю. Ольшанского о точной матричной представимости полных групп автоморфизмов АиЬСп.

Параграф 1.3 посвящен оценке длины обратного автоморфизма произвольной относительно свободной группы Сп в случае его унитреугольности.

Вначале второй главы приводятся основные определения и теоремы из обзоров [14, 18, 37], касающиеся неразрешимости Диофантовой проблемы. Далее приводятся известные результаты, о связанных с Диофантовой проблемой вопросах, которые понадобятся в дальнейшем.

Третья глава посвящена построению функций, на основе неразрешимости Диофантовой проблемы и неразрешимости проблемы эндоморфной сводимости в группах, которые могут рассматриваться в качестве кандидатов в односторонние функции.

В параграфе 3.1 приводятся определения слабо и сильно односторонних функций. Цель параграфа 3.2 — дать представление дискретного логарифма как диофантова множества. Тогда проблема нахождения дискретного логарифма будет эквивалентна проблеме нахождения решения соответствующего диофантова многочлена. Заметим, что данное представление может быть основанием протоколов разделения ключа, аутентификации, цифровой подписи и т. п. Кроме того, оно может быть использовано е целью организации атаки на дискретный логарифм.

В параграфе 3.3 предлагаются схемы построения двушагово односторонних функций на основе неразрешимости Диофантовой проблемы и сложности нахождения дискретного логарифма. Рассматриваются предпосылки крипто-стойкости предложенных схем.

В параграфе 3.4 приводится новый кандидат на роль односторонней функции. В качестве платформы рассматривается бесконечная группа с неразрешимой проблемой эндоморфной сводимости. Конкретное предложение — свободная метабелева группа достаточно большого ранга. Теоретическая база в данном случае дана в работе В. А. Романькова [23], где доказана соответствующая неразрешимость. Более точно, В. А. Романьков в работах [22, 23] ввел в рассмотрение интерпретацию диофантовых уравнений в свободных нильпотентных группах ступени > 9 и в свободных метабелевых группах достаточно большого ранга, позволяющую перенести неразрешимость Диофантовой проблемы, доказанную Ю. В. Матиясевичем [16], на неразрешимость проблемы эндоморфной сводимости в рассматриваемых группах.

В работе [25] дан обзор исследований по криптографии основанной на группах. Объяснены возможности использования неразрешимых и трудноразрешимых алгоритмических проблем теории групп в качестве основы для построения криптографических протоколов. Об этих возможностях и их реализациях см. также [34, 51, 59, 60, 67−69].

В работе [25] введено понятие диофантовой криптографии. Показана универсальность диофантова языка, позволяющая записывать на нем функции многих известных схем и протоколов криптографии. Подчеркнута объединяющая роль диофантовой криптографии. Описаны ее возможности, вытекающие из неразрешимости 10-й Проблемы Гильберта. Параграф 3.4 также основан на представленном в [25] материале. Более того, в [25] подробно обоснованы достоинства свободных метабелевых групп как платформ для построения криптографических схем и протоколов, что также лежит в основе предлагаемой конкретной реализации протокола аутентификации с нулевым разглашением.

Все результаты являются новыми, носят теоретический характер и могут найти применения в дальнейших исследованиях.

Основные результаты диссертации докладывались на алгебраическом семинаре ОмГУ им. Ф. М. Достоевского и ОФ ИМ им. С. Л. Соболева СО РАНсибирской научной школе-конференции с международным участием «Компьютерная безопасность и криптография» БШЕЯСКУРТ'11 (Томск, 2011 г.) — международной конференции по алгебре и математической логике «Маль-цевские чтения» (Новосибирск, 2011 г.). По теме диссертации опубликованы работы [1−5].

Автор выражает огромную благодарность своему научному руководителю Виталию Анатольевичу Романькову за постановку задач, понимание и постоянную помощь в ходе подготовки диссертации.

1. Ерофеев С. Ю., Романьков В. А. О возможности построения односторонних функций на основе проблемы однросторонней сводимости в группах // Вестник Омского университета. 2012. № 2. С. 28−34.

2. Ерофеев С. Ю., Романьков В. А. О группах унитреугольных автоморфизмов относительно свободных групп // Сиб. мат. журн. 2012. Т. 53, № 5. С. 991−1000.

3. Ерофеев С. Ю., Романьков В. А. О построении возможно односторонних функций на основе алгоритмической неразрешимости проблемы эндо-морфной сводимости в группах // Прикладная дискретная математика. 2012. № 3. С. 13−24.

4. Ерофееев С. Ю. Диофантовость дискретного логарифма // Вестник Омского университета. 2010. № 4. С. 13−15.

5. Ерофееев С. Ю. Схемы построения двушагово односторонних функций // Вестник Омского университета. 2011. № 4. С. 15−18.

6. Кабанов А. Н. Гиперцентральная структура группы унитреугольных автоморфизмов свободной метабелевой алгебры Ли // Сиб. мат. журн. 2007. Т. 50, № 2. С. 329−333.

7. Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. Москва: Наука, 1972.

8. Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. Москва: Лань, 2009.

9. Кожевников А. А., Николенко С. И. О полных односторонних функциях // Проблемы передачи информации. 2009. Т. 45, № 2. С. 101−118.

10. Коробов А. А. Разделенные разности в теории дифференциально-разностных уравнений и в теории групп // Вестник Новосибирского гос. университета, серия матем., мех., информ. 2006. Т. 6, № 3. С. 25−48.

11. Курош А. Г. Теория групп. Москва: ФИЗМАТГИЗ, 2008.

12. Левин Л. А. Односторонние функции // Проблемы передачи информации. 2003. Т. 39, № 1. С. 103−117.

13. Маканин Г. С. Уравнения в свободной группе // Изв. АН СССР. Сер. мат. 1982. Т. 46, № б. С. 1199−1273.

14. Манин Ю. И. Десятая проблема Гильберта // Современные проблемы математики. 1972. Т. 1. С. 5−37.

15. Матейко О. М., Тавгень А. И. Линейность групп автоморфизмов относительно свободных групп // Матем. заметки. 1995. Т. 58, № 3. С. 465−467.

16. Матиясевич Ю. В. Диофантовость перечислимых множеств // Докл. Академия наук СССР. 1970. Т. 191, № 2. С. 279−282.

17. Матиясевич Ю. В. Диофантово представление перечислимых предикатов // Академия наук СССР. Серия математическая. 1971. Т. 35. С. 3−30.

18. Матиясевич Ю. В. Десятая проблема Гильберта. Москва: Наука, 1993.

19. Нейман X. Многообразия групп. Москва: Мир, 1969.

20. Носков Г. А., Ремесленников В. Н., Романьков В. А. Бесконечные группы // Итоги науки и техники. Алгебра. Топология. Геометрия. 1979. Т. 17. С. 65−158.

21. Платонов В. П. Линейные представления групп автоморфизмов свободных разрешимых групп // Докл. РАН. 2006. Т. 406, № 4. С. 462−463.

22. Романьков В. А. О неразрешимости проблемы эндоморфной сводимости в свободных нильпотентных группах и в свободных кольцах // Алгебра и логика. 1977. Т. 16, № 4. С. 457−471.

23. Романьков В. А. Об уравнениях в свободных метабелевых группах // Сиб. мат. журн. 1979. Т. 20, № 3. С. 671−673.

24. Романьков В. А.

Введение

в криптографию. Курс лекций. Москва: Форум, 2012.

25. Романьков В. А. Диофантова криптография // Прикладная дискретная математика. 2012. № 2. С. 15−42.

26. Романьков В. А., Чирков И. В., Шевелин М. А. Матричная непредставимость групп автоморфизмов некоторых свободных алгебр // Сиб. мат. журн. 2004. Т. 45, № 5. С. 1184−1188.

27. Рыбалов А. Н. О генерической неразрешимости десятой проблемы Гильберта // Вестник Омского университета. 2011. № 4. С. 19−22.

28. Сосновский Ю. В. Описание гиперцентрального строения группы унитре-угольных автоморфизмов алгебры многочленов // Сиб. мат. журн. 2007. Т. 48, № 3. С. 689−693.

29. Холл М. Теория групп. Москва: Гос. изд-во ин. лит., 1962.

30. A. J. Menezes S. А. V., Р. С. van Oorschot. Handbook of Applied Cryptography. CRC Press, 1996.

31. Auslander L., Baumslag G. Automorphism groups of finitely generated nilpotent groups // Bull. Amer. Math. Soc. 1967. Vol. 73. P. 716−717.

32. Bachmuth S. Automorphisms of solvable groups I // Proceedings of Groups St. Andrews. 1985. P. 1−14.

33. Bardakov V. G., Neshchadim M. V., Sosnovsky Y. V. Groups of triangular automorphisms of a free associative algebra and a polynomial algebra // arXiv: 1007.271 lvl math.GR. 2010. P. 1−19.

34. Birget J. C., Magliveras S., Sramka M. On public-key cryptosystems based on combinatorial group theory // Tatra Mountains Math. Publ. 2006. Vol. 33. P. 137−148.

35. Davis M. Arithmetical problems and recursively enumerable predicates //J. Symb. Logic. 1953. Vol. 18, no. 1. P. 33−41.

36. Davis M. An Explicit Diophantine Definition of the Exponential Function // Communications on Pure and Applied Math. 1971. Vol. 24. P. 137−145.

37. Davis M. Hilbert’s tenth problem is unsolvable // Amer. Math. Monthly. 1973. Vol. 80, no. 3. P. 233−269.

38. Davis M., Putnam H., Robinson J. The decision problem for exponential Diophantine equations // Ann. Math. 1961. Vol. 74, no. 2. P. 425−436.

39. Formanek E., Procesi C. The automorphism group of a free group is not linear //J. Algebra. 2002. Vol. 149. P. 494−499.

40. Goldreich O. Computational Complexity: Volume 1, Basic Tools. Cambridge: Cambridge University Press, 2001.

41. Grigoriev D., Shpilrain V. Zero-knowledge authentication schemes from actions on graphs, groups or rings // Ann. Pure Appl. Logic. 2010. Vol. 162. P. 194−200.

42. Groves J. R. J. On varieties of solvable groups II // Bull. Austral. Math. Soc. 1972. Vol. 7. P. 437−441.

43. Hall P. Nilpotent groups // Canad. Math. Cong. Summer Sem. Vankuver: University of Alberta. 1957. P. 12−30.

44. Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers, Fourth edition. Oxford University Press, 1960.

45. Jones J. P. Three universal representations of r.e. sets //J. Symb. Logic. 1978. Vol. 43. P. 335−351.

46. Jones J. P. Undecidable diophantine equations // Amer. Math. Soc. 1980. Vol. 3, no. 2. P. 859−862.

47. Jones J. P. Universal diophantine equation // J. Symb. Logic. 1982. Vol. 47. P. 549−571.

48. Kapovich I., Myasnikov A., Shupp P., Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. Vol. 264. P. 665−694.

49. Krammer D. The hypercenter of linear groups // Invent. Math. 2000. Vol. 142, no. 3. P. 451−586.

50. Kurt Y. A new key exchange primitive based on the triple decomposition problem // Preprint: http://eprint.iacr.org/2006/378.

51. Lennox J. C., Robinson D. J. S. The theory of infinite soluble groups. Oxford: Oxford Science Publications, 2004.

52. Levin L. A. One-way Functions and Pseudorandom Generators // Combina-torica. 1987. Vol. 7, no. 4. P. 357−363.

53. Lohrey M. Word problems on compressed words // Automata, Languages and Programming. Lect. Notes in Comput. Sci. Vol. 3142. Berlin: Springer Verlag, 2004. P. 906−918.

54. Matijasevic J. V. Some purely mathematical results inspired by mathematical logic // Proc. Fifth Intern. Congr. Logic, Methodology and Philos. of Sci.(London, Ont.). Dordrecht, Reidel, Holland. 1977. P. 121−127.

55. Matijasevic J. V., Robinson J. Reduction of an arbitrary diophantine equation to one in 13 unknowns // Acta Arith. 1975. Vol. 27. P. 521−553.

56. Myasnikov A., Roman’kov V. A. Selected questions in cryptography //в печати.

57. Myasnikov A., Shpilrain V., Ushakov A. Group-based cryptography (Advanced Courses in Mathematics CRM Barcelona). Birkhauser Basel, 2008.

58. Myasnikov A., Shpilrain V., Ushakov A. Non-commutative cryptography and complexity of group-theoretic problemsc (Amer. Math. Soc. Surveys and Monographs). Amer. Math. Soc., 2011.

59. Olshanskii A. Y. Linear automorphism groups of relatively free groups // Turk. J. Math. 2007. Vol. 31. P. 105−111.

60. Papadimitriou С. H. Foundations of Cryptography. Section 12.1: One-way functions. Addison Wesley, 1993. P. 279−298.

61. Putnam H. An unsolvable problem problem in number theory //J. Symb. Logic. 1960. Vol. 25. P. 220−232.

62. Robinson J. Existential definability in arithmetic // Trans. Amer. Math. Soc. 1952. Vol. 72. P. 437−449.

63. Roman’kov V. A. Automorphisms of groups // Acta Appl. Math. 1992. Vol. 29. P. 241−280.

64. Scheimer S. Polynomial-time word problems // Comment. Math. Helv. 2008. Vol. 83. P. 741−765.

65. Shpilrain V., Zapata G. Combinatorial group theory and public key cryptography // Applicable Algebra in Engineering Communication and Computing. 2006. Vol. 17. P. 291−302.

66. Shpilrain V., Zapata G. Using the subgroup membership problem in public key cryptography // Contemp. Math. 2006. Vol. 418. P. 169−179.

67. Shpilrain V., Zapata G. Using decision problems in public key cryptography // Groups.Complexity. Cryptology. 2009. Vol. 1. P. 33−40.

68. Siegel C. L. Zur Theorie der quadratischen Formen // Nachr. Akad. Wiss. Gottingen Math.-Phys. 1972. Bd. 2. S. 21−46.

69. Sipser M. Introduction to the theory of computation. Section 10.6.3: One-way functions. PWS Publishing, 1997. P. 374−376.

70. Skolem T. Uber die Nicht-charakterisierbarkeit der Zahlenreinhe mittels endlich order abzahlbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen // Fund. Math. 1934. Bd. 23. S. 150−161.

71. Tits J. Free subgroups of linear groups //J. Algebra. 1972. Vol. 20.P. 250−270.