Введение
1 Введение 4
1.1 Криптография как раздел информатики 4
1.2 Модели вычислений 8
1.3 Основные определения современной криптографии . 14
2 Новые конструкции полных односторонних функций 20
2.1 Введение 20
2.2 Задача достижимости с распределением для полусистем Туэ 24
2.3 Задача Поста 26
2.4 Полная односторонняя функция, основанная на задаче поиска замощения 28
2.5 Полная односторонняя функция, основанная на полусистемах Туэ 32
2.6 Полная односторонняя функция на базе задачи Поста . 36
2.7 Полные односторонние функции и DistNP-трудные комбинаторные задачи 39
2.8 Полные односторонние функции в большей общности . 42
3 Новые конструкции криптографических примитивов, доказуемо надёжных в слабом смысле 46
3.1 Введение 46
3.2 Определения 48
3.3 Матрицы сложных функций 52
3.4 Исключение гейтов 57
3.5 Две конструкции 67 -
3.6 Семейство функций с секретом, надёжных в слабом смысле 69
3.7 Функция с секретом с экспоненциальной гарантией надёжности 72
Новые алгебраические конструкции криптографических примитивов 75
4.1 Алгебраическая криптография 75
4.2 Ослабленные результаты современной криптографии . 79
4.3 Доказуемый взлом 81
4.4 Определения 83
4.5 Криптосистемы, основанные на инвариантах групп, и их доказуемый взлом 85
4.6 Дерево групп 90
4.7 Листья дерева 95
4.8 Атаки на криптосистемы, основанные на инвариантах . 99
4.9 Схема согласования ключа Аншель-Аншеля-Голдфельда и её устойчивость против взлома с доказательством 102
Литература 105
