Группы унитреугольных автоморфизмов относительно свободных групп и алгебраические схемы построения односторонних функций тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

Ерофеев Степан Юрьевич

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

01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 5 НОЯ 2012

Омск - 2012

005055114

Работа выполнена на кафедре информационных систем института математики и информационных технологий ФГБОУ ВПО "Омский государственный университет им. Ф. М. Достоевского"

Научный руководитель:

доктор физико-математических наук, профессор Романьков Виталий Анатольевич

Официальные оппоненты:

доктор физико-математических наук, профессор Романовский Николай Семенович кандидат физико-математических наук, Трейер Александр Викторович

Ведущая организация:

ФГБОУ ВПО "Новосибирский государственный технический университет"

Защита состоится б декабря 2012 года в 14 ч. 00 мин. на заседании диссертационного совета ДМ 212.179.07 при Омском государственном университете им. Ф. М. Достоевского, расположенном по адресу: 644099 Омск, ул. Певцова, 13, к. 15.

С диссертацией можно ознакомиться в библиотеке Омского государственного университета им. Ф. М. Достоевского.

Автореферат разослан октября 2012 г.

Ученый секретарь диссертационного совета

А. М. Семенов

Общая характеристика работы

Постановка задачи и актуальность темы диссертации.

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

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

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

Группа унитреугольных автоморфизмов. Группам автоморфизмов относительно свободных групп как конечного, так и бесконечного, рангов посвящено немало работ (см. обзоры1' 2' 3).

Обозначим через Fn свободную группу ранга п с базисом Хп — {х\,..., хп}, через F\i0 свободную группу бесконечного счетного ранга с базисом = {.xi,.т2,...}, группа Fn0 рассматривается как объединение = U^ijF,,.. Также обозначим через Gn относительно свободную группу ранга п некоторого многообразия групп С, через G#0 относительно свободную группу бесконечного счетного ранга многообразия С.

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

1 Roman'kov V. A. Automorphisms of groups // Acta Appl. Math. 1992. Vol. 29. P. 241-280.

2Носков Г. А., Ремесленников В. H-, Романьков В. А. Бесконечные группы // Итоги науки и техники. Алгебра. Топология. Геометрия. 1079. Т. 17. С. (i5-158.

3Bachmuth S. Automorphisms of solvable groups I // Proceedings of Groups — St. Andrews. 1985. P. 1-14.

Из результатов Д. Крамера4 следует линейность группы AutF2. Э. Формапек и К. Прочези5 доказали, что при п > 3 группа AutFn не линейна.

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

А. Ю. Ольшанский7 доказал, что если относительно свободная группа Gn не свободна и не почти нилыштентна, то ее группа автоморфизмов Aut,Gn не линейна. В этой же работе отмечалось, что близкие но формулировке результаты содержатся в статьях О. М. Матейко и А. И. Тавгеня8, А. А. Коробова9. Однако, обе эти статьи содержат неточности в формулировках и существенные ошибки в доказательствах (см. работу А. Ю. Ольшанского).

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

"Krammer D. The hyperceriter of linear groups // Invent. Math. 2000. Vol. 142, no. 3. P. 451-580.

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

6Auslandcr L., Daumslafi G. Automorphism groups of finitely generated nilpotent groups // Bull. Amer. Math. Soc. 1907. Vol. 73. P. 710-717.

701shanskii A. Y. Linear automorphism groups of relatively free groups // Turk. J. Math. 2007. Vol. 31. P. 105-111.

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

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

нелинейна.

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

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

Относительно общей теории односторонних функций см. монографии М. Сипссра10, X. Пападимитриу11, О. Гольдрейха12. В работах Л. Левина13,14 приведена универсальная функция, которая автоматически является односторонней, если существует хотя бы одна односторонняя функция. Такие функции названы полными односторонними функциями. Для их построения Л. Левин использовал нумерацию всех машин Тыоринга и комбинаторный тайлинг. Отсюда видно, что такое построение имеет чисто теоретическое значение. В работе А. А. Кожевникова, С. И. Николенко15 приведены другие примеры полных односторонних функций.

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

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

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

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

14Levin L. A. One-way Functions and Pseudorandom Generators // CombinaLorica. 1987. Vol. 7, no. 4. P. 357-3G3.

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

Новые конструкции односторонних функций, предложенные в диссертации, относятся к "криптографии основанной па rpynnax"("group-based cryptography") — современному направлению, возникшему на рубеже 20-го и 21-го столетий. Основными объектами в нем являются абстрактные бесконечные группы, а основной целыо — построение на этих группах криптографических схем и протоколов. Исследования ведутся методами теории групп, теории сложности и теории вычислений. Современное состояние полученных в этой области результатов отражено в монографиях А. Мясникова, В. Шпильрайпа, А. Ушакова 16, 17.

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

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

Основные результаты диссертации.

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

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

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

мальную форму элементов.

2. Доказано, что группа унитрсугольных автоморфизмов относительно свободной группы ранга п многообразия групп отличного от многообразия всех групп допускает точное представление матрицами тогда и только тогда, когда относительно свободная группа ранга га — 1 почти нильпотента.

3. Дана точная оценка длины обратного к упитреуголыгаму автоморфизму в случае свободной абелевой группы и абсолютно свободной группы.

4. Приведено явное диофантого представление дискретного логарифма.

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

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

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

Апробация результатов. Основные результаты диссертации докладывались на алгебраическом семинаре ОмГУ им. Ф. М. Достоевского и ОФ ИМ им. С. Л. Соболева СО РАН; Сибирской научной школе-конференции с международным участием "Компьютерная безопасность и криптография" ЗШЕПСНУРТ'П (Томск, 2011 г.); международной конференции по алгебре и математической логике "Мальцсвские чтения "(Новосибирск, 2011 г.).

Публикации. По теме диссертации опубликованы работы [1-8]. Статьи [1-5] опубликованы в изданиях, входящих в перечень ВАК. Работы [3-5, 7, 8] выполнены в соавторстве с В. А. Романьковым при равном вкладе соавторов.

Структура диссертации. Диссертация состоит из оглавления, введения, трех глав и списка литературы, который включает 73 наименования. Объем диссертации 65 страииц.

Содержание работы

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

Определяется естественная подгруппа иТАиЮп группы АиЮп, которая называется группой унитреуголг>ных автоморфизмов. Исследуется вопрос о се структуре и точной представимости матрицами над полем, то есть линейности. Также вводится естественное понятие длины автоморфизма и рассматривается вопрос оценки длины обратного автоморфизма через длину данного автоморфизма.

Определение 1. Унитреуголъным автоморфизмом группы Сп относительно базиса Уп, называется любой автоморфизм </?, задаваемый отображением вида:

Ч> '■ У\ 2/1. Уi игУг для1 = 2,...,п, (1)

где щ = щ(у\,... , 2Л-1) произвольный элемент группы 1.

Определение 2. Длина 1(<р) автоморфизма <р группы Сп, определяется следующим образом

п

*М = £|¥>М I. (2)

¿=1

где |д| означает наименьшую длину записи элемента д группы С?„ в базисе

В первой главе диссертации доказывается следующая структурная теорема.

Теорема 1.2.1. Пусть Сп относительно свободная группа ранга п > 2 произвольного многообразия групп С. Тогда группа 17п = \JTAulGn унитреуголь-ных автоморфизмов группы йп допускает нормальный ряд

1 = ЛГ„ < N < • • • < ЛГ„-1 = ип, (3)

в котором, факторы изоморфны относительно свободным группам многообразия С, а именно:

N¡/N1-1 ^ для ¿=1,...,т1 1. (4)

Более того, факторы данного ряда отщепляются, поэтому группа [/„ есть произведение непересекающихся подгрупп

ип = иР-...-иР^Сп-1-...-С1, (5)

где подгруппа 11$ ~ G¡-l состоит, из однострочных унитреуголъных автоморфизмов, соответствующих у,;, то есть унитреуголъных автоморфизмов тождественных на всех базисных элементах у1 кроме, возмоэ/сно, у,;. В частности, группа 11п принадлежит, многообразию С7'"1.

Также в этой главе доказываются две теоремы о линейности групп упит-реугольных автоморфизмов относительно свободных групп.

Теорема 1.2.2. Пусть Сп относительно свободная, группа ранга п > 2 произвольного многообразия групп С. Тогда верны следующие утверждения:

Группа и\ тривиальна, группа £/2 циклическая порядка равного экспоненте многообразия С. Эти группы допускают точное представление матрицами.

При п > 3, если группа Сп-1 нилъпотентна, то и группа 11п нильпо-тентиа.

Почти нильпотентность группы £?п_1 влечет существование точной матричной представимости группы 17п над кольцом целых чисел 2.

Теорема 1.2.3. Пусть (7П относительно свободная группа ранга п > 3 произвольного нетривиального многообразия С групп отличного от многообразия всех групп. Тогда, если группа Сп-\ не почти нилъпотентна, то группа ип = иТАиЮп унитпреугольных автоморфизмов группы Сп не допускает точного представления матрицами над полем.

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

Относительно длины автоморфизмов получены следующие результаты.

Теорема 1.3.1. Пусть Ап свободная абелева группа ранга п. Тогда для любого автоморфизма € Аи1Ап выполнено неравенство 1(<р~1) < 1{<р)п~1, причем степень п — 1 понизить нельзя.

Пусть Рп — абсолютно свободная группа ранга п. Тогда для любого уиитреугольного автоморфизма (р £ IIАиЬРп выполнено неравенство К^1) — '(у)™-1) причем степень п — 1 понизить нельзя.

Во второй главе приводятся основные определения и теоремы из обзоров

Ю. В. Матиясевича18, М. Девиса19, касающиеся неразрешимости Диофанто-вой проблемы. Далее приводятся известные результаты, о связанных с Дио-фантовой проблемой вопросах, которые понадобятся в дальнейшем.

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

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

Рассмотрим следующую систему диофантовых уравнений:

х2 - (а2 - 1)у2 = 1, и2-(а2-1У = 1, s2 - (б2 - l)í2 = 1, V2 = ту2, Ъ = 1 + Ayo, b = а + qu, s = х + cu, t = к + 4 (d — 1 )y, x - y(a - n) - m)2 = (/ - l)2(2an - n2 - l)2, (6)

m + g = 2 an — n2 — 1, y = к + e — 1,

a2 — (w2 — 1)(ги — l)2z2 = 1, w = n + h, w = к + l, m = i + pj.

Теорема 3.2.2. Пусть daubin,i,p G N, гдер - простое. Тогда если система

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

19Davis М. Hilbert's tenth problem is uiisolvable // Amer. Math. Monthly. 1973. Vol. 80, no. 3. P. 233-2G9.

диофантоеых уравнений (6) имеет решение в натуральных числах в оставшихся аргументах, то пк = i (modp).

Верно и обратное, если пк' = i(modp), для некоторого k' € N, то система (6) имеет решение в натуральных числах в оставшихся аргументах. Причем если i ф О (modp), то к = к' (modp — 1), иначе к любое.

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

Пусть F € Z\xi,... ,.хп] диофантов многочлен. По любому диофантову многочлену F определяется функция F : Zn —» Z,

F : (ai,..., an) i-> F (ai,... ,a„). (7)

Результаты, приведенные в главе 2, дают основания рассматривать функцию F в качестве претендента в односторонние функции. Действительно, любое ее значение вычислимо за полиномиальное время от |ai| + ... + |a„|. В то же время, из-за неразрешимости 10-й проблемы Гильберта мы не можем указать полиномиальный по времени алгоритм, вычисляющий аргумент этой функции с заданным значением.

Более того, для повышения надежности, например, чтобы нивелировать выбор неподходящего многочлена, можно строить более стойкие схемы односторонних функций па основе функций вида (7).

В диссертации предложены 5 схем построения двушагово односторонних функций, рассмотрены предпосылки криптостойкости предложенных схем. Здесь приведем для примера одну из этих схем. Схема 2

По любому набору диофантовых многочленов F 6 Z[x\,... ,хт], Pi 6 Z[xi,..., хп] (г — I,... ,т) определяется функция

Н-х : —> Z. Для вычисления значений функции используется следую-

щий алгоритм.

Шаг 1. Найдем значения диофантовых многочленов Р^ в точках хц,...

Р1(хп,...,хы) = Сх

р2(х21, ■ ■ ■ ,Х2п) = С2, (8)

Р'т ' • • > ЗС'тп) Ст

Шаг 2. Найдем двоичное представление значений с,.

С; = Ьа + 2 • Ьа + ... + 2*-1 • Ъ1к, (9)

где е {0,1} для любых { = 1,... ,т, j = 1,..., к.

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

Шаг 3. Вычислим входной набор функции F. Для этого формируется строка чисел, выписыванием элементов полученных в (9), по столбцам: ¿>11, Ь21, • • •, Ьт1, Ь12, • • •, ьт2,..., Ь1к,..., Ьтк. Данная строка разбивается на тп подстрок по к элементов. Разбиение на подстроки происходит без каких-либо перестановок элементов строго по порядку следования элементов в начальной строке. Пусть Ьг = Ь( - г-ая подстрока из предложенного разбиения. Для каждой такой подстроки вычисляется

1ц = Ьц + 2 • Ь{2 + ... + 2к'г • (г = 1,..., т). (10)

Шаг 4. Значение односторонней функция Н2 определяется так

Н2(Х) = Р(Н'1,...,Кп), (П)

где последовательность ,..., Ыт является упорядоченной по возрастанию последовательностью ..., Нт.

В параграфе 3.4 предлагается новый кандидат на роль односторонней функции. В качестве платформы рассматривается бесконечная группа с разрешимой проблемой равенства и неразрешимой проблемой эндоморфной сводимости. Конкретное предложение — свободная метабелева группа достаточно большого ранга. Теоретическая база в данном случае дана в работе

B. А. Романькова20, где доказана соответствующая неразрешимость. Более точно, В. А. Романьков в работе21 ввел в рассмотрение интерпретацию дио-фантовых уравнений в свободных нильпотентных группах ступени > 9 и в свободных метабслевых группах достаточно большого ранга, позволяющую перенести неразрешимость Диофантовой проблемы, доказанную Ю. В. Ма-тияеевичем22, на неразрешимость проблемы эндоморфной сводимости в рассматриваемых группах.

Говорят, что в эффективно заданной группе (7 разрешима проблема эндоморфной сводимости, если существует алгоритм, определяющий по любой паре элементов д, / 6 б, является ли / эндоморфным образом элемента д. Общая схема построения односторонних функций на основе неразрешимости проблемы эндоморфной сводимости. Пусть С? эффективно заданная группа, в которой разрешима проблема равенства и неразре-

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

21Романьков В. А. Об уравнениях в свободных метабелевых группах // Сиб. мат. журн. 1979. Т. 20, Л*' 3.

C. 671-573.

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

шима проблема эндоморфной сводимости. Допустим, что нам необходимо построить на группе С одностороннюю функцию со значением также в С. Как правило, эффективно заданные группы конечно порождены. Поэтому мы предполагаем, что в существует конечное порождающее множество Хп = ..., хп}. Произвольный элемент д группы б записывается как групповое слово д = д(х\,..., хп) от фиксированных порождающих элементов. Каждый эндоморфизм (р : (3 —» С однозначно определяется своими значениями на элементах порождающего множества Хп. Представляется перспективным выбирать в качестве группы С? свободную группу конечного ранга некоторого многообразия групп Е. Тогда любое отображение </? : Хп —» С, где Хп — базис группы (7 (т.е. множество свободных порождающих группы С в многообразии 1.) однозначно определяет эндоморфизм <р : С —> С. Для его задания достаточно определить образы базисных элементов, записав их в виде групповых слов от этих элементов.

Определим функцию (р : й —> С, сопоставляющую элементам группы, записанным в нормальной форме, нормальные формы их значений относительно эндоморфизма </?. Для эффективности соответствующих вычислений необходимо, чтобы в группе С существовал эффективный алгоритм записи элемента в нормальной форме по его представлению в виде группового слова от порождающих элементов или в каком-то другом виде, отвечающем эффективности задания группы (3. Также необходима эффективная процедура вычисления нормальных форм обратного элемента и произведения элементов. Если группа б удовлетворяет этим требованиям, то мы получаем эффективно вычислимую функцию, определенную на множестве нормальных форм элементов группы (3 со значениями в этом же множестве. Если определить для элементов группы (3 некоторую функцию длины, например, ввести на ней словарную метрику, то не существует полиномиального алгоритма, ограничивающего длину прообраза по длине образа для данной функции. Более

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

Как отмечалось выше, в диссертации предлагается использовать свободную метабелеву группу Мп в качестве платформы построения возможно односторонней функции. В работе "Диофантова криптография"23 отмечено, что свободные метабелевы группы отвечают описанным требованиям. В параграфе 3.4 описан явный способ нахождения элементов д, / группы Мп, для которых неразрешима проблема эндоморфной сводимости.

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

"Установка. В качестве платформы используется свободная метабелева группа М„. Абонент А фиксирует публичный элемент д и секретный эндоморфизм <р, вычисляет и публикует образ / = <р(д)- Элементы д и / выбираются таким образом, чтобы проблема эндоморфной сводимости для пары (д, /) была трудна. Это означает, что по / трудно вычислить эндоморфизм <р, переводящий д в /.

Алгоритм аутентификации.

1. В качестве сессионного ключа выбирается эндоморфизм ф, вычисляется элемент v = ф(/) и передается в систему С, в которой осуществляется аутентификация пользователя А.

2. Система С с равной вероятностью выбирает случайный бит и отсылает его А.

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

3. Если А получаст 0, то он просто публикует ф, а С проверяет, что действительно V — образ / относительно гр. Если А получает 1, то он вычисляет композицию х = передает ее С, который проверяет справедливость равенства V = х{д)-

В диссертации также рассматриваются предпосылки криптостойкости данного протокола.

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

Опубликованные работы по теме диссертации

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

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

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

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

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

6. Ерофеев С. Ю. Диофантовость дискретного логарифма // Тезисы докладов X Сибирской научной школы-семинара с международным участием "Компьютерная безопасность и криптография— БШЕСКУРТ'П. 2011. № 4. С. 31-32.

7. Ерофеев С. Ю., Романьков В. А. Построение односторонних функций на основе неразрешимости проблемы эндоморфной сводимости в группах // Тезисы докладов X Сибирской научной школы-семинара с международным участием "Компьютерная безопасность и криптография— БШЕСКУРТ'И. 2011. № 4. С. 32-33.

8. Ерофеев С. Ю., Романьков В. А. О группах унитреугольных автоморфизмов относительно свободных групп // Тезисы докладов международной концеренции "Мальцевские чтения". 2011. С. 40. http://www.inath.nsc.ru/conference/malmeet/ll/malmeet2011.pdf.

Подписано в печать 18.10.2012 Формат 60x84/16. Бумага писчая.

Усл. печ. л. 1,25. Тираж 100 экз. Заказ № 591

Отпечатано в «Полиграфическом центре КАН» тел. (3812) 24-70-79, 8-904-585-98-84.

E-mail: pc_kan@mail.ru 644050, г. Омск, ул. Красный Путь, 30 Лицензия ПЛД № 58-47 от 21.04.97

Введение

Глава 1. О группах унитреугольных автоморфизмов относительно свободных групп.

1.1. Введение.

1.2. О структуре и матричной представимости групп IIп.

1.3. Об оценке длины обратного автоморфизма.

Глава 2. Диофантова проблема.

2.1. Введение.

2.2. Диофантовы множества.

2.3. Диофантовость перечислимых множеств.

2.4. Диофантово представление показательной функции.

2.5. Универсальные диофантовы уравнения.

Глава 3. Диофантовы уравнения и односторонние функции

3.1. Односторонние функции. Определения.

3.2. Диофантовость дискретного логарифма

3.3. Схемы построения двушагово односторонних функций.

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

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

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

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

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

Обозначим через Fn свободную группу ранга п с базисом Хп = {х\,., хп}, через F$Q свободную группу бесконечного счетного ранга с базисом Хк0 = {xi, Х2, ■ ■ •}, группа Fx0 рассматривается как объединение F^0 = 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.