Криптография и машинное обучение

Материал из MachineLearning.

(Различия между версиями)

Перейти к: навигация, поиск

Текущая версия

Данная статья является непроверенным учебным заданием.

Студент: Участник:Лошкарёв Сергей

Преподаватель: Участник:Константин Воронцов

Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Содержание

1 Введение
2 Начальное сравнение
3 Влияние криптографии на машинное обучение
4 Влияние машинного обучения на криптографию
- 4.1 Криптоанализ шифра обратной связи
- 4.2 Другие возможности
5 Ссылки

Введение

Активное развитие информатики началось в 40-х и 50-х гг. прошлого столетия и было в основном основано на научных достижениях 30-х гг. С самого начала и машинное обучение, и криптография были тесно связаны с этой областью знания. Криптография играла важную роль в течение Второй Мировой Войны и некоторые из первых компьютеров были предназначены для решения криптографических задач. Возможность компьютеров "обучаться" делать вещи, которые, как считалось, доступны только людям (например, игра в шахматы), стала активно изучаться в 50-е гг. Тьюрингом, Самюэлем и др.

Начальное сравнение

Машинное обучение и криптоанализ можно рассматривать как родственные области, так как они содержат много общих понятий и вопросов. В типичной криптоаналитической ситуации криптоаналитик желает взломать некоторую криптосистему. Обычно это означает, что он хочет найти секретный ключ, примененный пользователями криптосистемы, когда известно устройство системы. Таким образом, описание функции берется из известного семейства таких функций (индексируемых по ключу), а цель криптоанализа заключается в точном определении использованной функции. Обычно криптоаналитику предоставлено некоторое количество соответствующих друг другу открытых и шифрованных текстов. Данная проблема также может быть описана, как проблема "обучения вычислению неизвестной функции" на основе примеров входных/выходных данный и знании класса, из которого функция выбрана. Валиант отмечает, что «хорошая» криптография может предоставить классы «сложных» для анализа функций. Отдельно он ссылается на работу Гольдрайха, Гольвассер и Микали, которые показали (предположив существование односторонней функции), как построить семейство псевдослучайных функций : $F_k:\{0,1\}^k\rightarrow\{0,1\}^k$ для каждого $k\geq 0$ таких, что

1) Каждая функция $f_i \in F_k$ описывается $k$ битовым индексом $i$ ;

2) Существует полиномиальный алгоритм, который по входу $i$ и $x$ вычисляет $f_i(x)$ . То есть каждая функция из $F_k$ вычислима схемой полиномиального размера;

3) Не существует полиномиального вероятностного алгоритма, способного отличить случайно выбранную функцию из $F_k$ , от функций, случайно выбранных из всех функций осуществляющих преобразование $\{0,1\}^k\rightarrow\{0,1\}^k$ , даже если алгоритм будет иметь возможность динамически полиномиально вычислять большое количество значений неизвестной функции на выбранных им аргументах.

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

Секретные ключи и целевые функции

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

Типы атак и протоколы обучения

Ключевой аспект в любом криптографическом сценарии или сценарии машинного обучения --- это спецификация того, как криптоаналитик (обучающийся алгоритм) может получать информацию о неизвестной целевой функции.

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

Исследователи в области машинного обучения изучали сходные сценарии. Например, обучающемуся может быть дозволено узнавать значение неизвестной функции на некотором заданном входе или узнавать, действительно ли некоторая предполагаемая гипотеза эквивалентна неизвестной целевой гипотезе (в случае отрицательного ответа обучающемуся предоставляется контрпример --- вход, на котором предполагаемая и целевая гипотезы дают разные ответы). К примеру, Англуин показал, что данных запросов достаточно для точного определения любого регулярного языка, в то время как проблема обучения распознаванию регулярного языка по случайным примерам NP-полна.

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

Точный и приближенный выводы

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

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

Вычислительная сложность

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

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

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

Другие отличия

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

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

Влияние криптографии на машинное обучение

После работы Гольдрайха, Гольдвассер и Микали, утверждавшей существование класса функций, который невозможно алгоритмически воспроизводить (при условии существовании односторонней функции), даже позволив обучающемуся алгоритму делать произвольные запросы значений целевой функции, исследователи в области машинного обучения сфокусировались на описании простейших классов функций, обучение которым возможно. Например, основным вопросом является возможность эффективного обучения классу булевых функций, представленных в виде дизъюнктивной нормальной формы, по случайным примерам.

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

Одним из классов "неподатливых" в теории машинного обучения задач являются задачи, зависящие от представления, то есть показано, что имея набор примеров, вычислительно сложно найти булеву функцию, соответствующую этим примерам и имеющую определенный вид. Например, Питт и Валиант показали, что нахождение 2-ДНФ формулы по парам входных и выходных значений является NP-полной задачей. Это означает, что обучение 2-ДНФ формуле (учитывая, что P $\neq$ NP) нереализуемо, но только если обучающийся алгоритм должен представить результат в виде 2-ДНФ. При этом аналогичная задача для 2-КНФ решается эффективно.

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

Более того, чтобы доказать сложностные результаты для сравнительно простых классов функций, Кернсу и Валианту потребовалось показать, что требуемые криптографические операции могут быть определены в рамках выбранного класса функций. Это они реализовали используя технику расширенного входа, когда к основным входам добавляются промежуточные результаты вычислений. В результате было получено следующее утверждение: если обучающийся алгоритм может успешно обучиться одному из перечисленных в статье классов функций (например, класс булевых функций с n входами и размера не более p(n)), то есть может предсказать классификацию новых примеров с вероятностью существенно выше 1/2, то данный алгоритм можно использовать для успешного взлома одной из криптографических задач, считаемых сложными.

Можно задаться вопросом, могут ли криптографические методы быт использованы для доказательства необучаемости конкретных классов функций даже в том случае, когда обучаемому алгоритму позволено осуществлять произвольные запросы к целевой функции. Англуин и Харитонов показали (с учетом обычных криптографических предположений, касающихся RSA, разложения на множители чисел Блюма или квадратичных вычетов), что не существует полиномиальных алгоритмов (даже в случае допустимости произвольных запросов к целевой функции) для следующих классов функций:

1. Булевы формулы.

2. Пороговые схемы фиксированной глубины.

3. Булевы формулы, в которых каждая переменная встречается не более трех раз.

4. Конечные объединения и пересечения детерминированных конечных автоматов, двусторонних конечных автоматов, контекстно-свободных грамматик, недетерминированных конечных автоматов.

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

Влияние машинного обучения на криптографию

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

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

Криптоанализ шифра обратной связи

Режим обратной связи шифра работает следующим образом:

$C_i=E_k(C_{i-1})\oplus P_i$

$P_i=E_k(C_{i-1})\oplus C_i$

$C_0=IV$

где IV - вектор инициализации, $C_i$ - блок шифрованного текста, $P_i$ - блок открытого текста.

Вероятно, наиболее явное применение результатов теории машинного обучения в криптографии --- это криптоанализ нелинейного шифра с обратной связью. Функция f известна только получателю и отправителю и использует их секретный ключ.

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

Отметим, что в данной ситуации подходит и понятиее "приблизительного" обучения. Если алгоритм возвращает правильное значение, например, в 99 % случаев, то криптоаналитик сможет дешифровать 99 % блоков текста.

Сперва предположим, что мы используем атаку с известным открытым текстом. Принципы криптографии предполагают, что в данном случае вероятность на выходе получить 1 совпадает с вероятностью получить 0. Обычно это приводит к возможности рассматривать результат сдвига, как случайно и равномерно выбранный вектор из $\{0,1\}^n$ . Данное условие является молореалистичным и ограничивающим в теории обучения, но отлично подходит для криптографических целей.

Шапир получил ряд результатов для различных функций f. В частности, он показал, что функция f, построенная исключительно из операций AND, OR и NOT может быть эффективно воспроизведена за полиномиальное время по случайным примерам входных данных.

Линиал, Мансор и Нисан показали, как использовать спектральный (основанных на преобразовании Фурье) метод для обучения функциям, представимым в виде схем фиксированной длины, с блоками AND, OR и NOT с произвольным количеством входов, по случайным примерам входных данных. Данный результат был расширен Кушелевичем и Мансором, а затем Фурстом, Джексоном и Смитом на более широкие классы функций.

Хэнкок и Монсор показали, что функции, представимые в виде монотонных k-ДНФ (то есть ДНФ, в которые каждая переменная входит не более k раз), доступны для обучения по случайным примерам. Тем не менее функции, представимые в виде монотонных ДНФ редко используются.

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

Другие возможности

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

Ссылки

Ronald L. Rivest Cryptography And Machine Learning, Proceedings ASIACRYPT '91 (Springer 1993), 427 – 439

Источник — «http://www.recognition.su/wiki/index.php?title=%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F_%D0%B8_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5»

Категории: Непроверенные учебные задания | Машинное обучение | Криптография | Популярные и обзорные статьи

@@ Строка 1: / Строка 1: @@
+{{Задание|Лошкарёв Сергей|Константин Воронцов|8 января 2010}}
 ==Введение==
-Активное развитие информатики началось в 40-х и 50-х гг. прошлого столетия и было в основном основано на научных достижениях 30-х гг. С самого начала и машинное обучение, и криптография были тесно связаны с этой областью знания. Криптография играла важную роль в течение Второй Мировой Войны и некоторые из первых компьютеров были предназначены для решения криптографических задач. Возможность компьютеров "обучаться" делать вещи, которые, как считалось доступны только людям (например, игра в шахматы), стала активно изучаться в 50-е гг. Тьюрингом, Самюэлем и др.
+Активное развитие информатики началось в 40-х и 50-х гг. прошлого столетия и было в основном основано на научных достижениях 30-х гг. С самого начала и [[машинное обучение]], и [[криптография]] были тесно связаны с этой областью знания. Криптография играла важную роль в течение Второй Мировой Войны и некоторые из первых компьютеров были предназначены для решения криптографических задач. Возможность компьютеров "обучаться" делать вещи, которые, как считалось, доступны только людям (например, игра в шахматы), стала активно изучаться в 50-е гг. Тьюрингом, Самюэлем и др.
 == Начальное сравнение ==
-Машинное обучение и криптоанализ можно рассматривать как родственные области, так они содержат много общих понятий и вопросов. В типичной криптоаналитической ситуации криптоаналитик желает взломать некоторую криптосистему. Обычно это означает, что он хочет найти секретный ключ, примененный пользователями криптосистемы, когда известно устройство системы. Таким образом, описание функции берется из известного семейства таких функций (индексируемых по ключу), а цель криптоанализа заключается в точном определении использованной функции. Обычно криптоаналитику предоставлено некоторое количество соответствующих друг другу открытых и шифрованных текстов. Данная проблема также может быть описана, как проблема "обучения вычислению неизвестной функции" на основе примеров входных/выходных данный и знании класса, из которого функция выбрана.
+Машинное обучение и криптоанализ можно рассматривать как родственные области, так как они содержат много общих понятий и вопросов. В типичной криптоаналитической ситуации криптоаналитик желает взломать некоторую криптосистему. Обычно это означает, что он хочет найти секретный ключ, примененный пользователями криптосистемы, когда известно устройство системы. Таким образом, описание функции берется из известного семейства таких функций (индексируемых по ключу), а цель криптоанализа заключается в точном определении использованной функции. Обычно криптоаналитику предоставлено некоторое количество соответствующих друг другу открытых и шифрованных текстов. Данная проблема также может быть описана, как проблема "обучения вычислению неизвестной функции" на основе примеров входных/выходных данный и знании класса, из которого функция выбрана.
 Валиант отмечает, что «хорошая» криптография может предоставить классы «сложных» для анализа функций. Отдельно он ссылается на работу Гольдрайха, Гольвассер и Микали, которые показали (предположив существование односторонней функции), как построить семейство псевдослучайных функций : <tex> F_k:\{0,1\}^k\rightarrow\{0,1\}^k</tex> для каждого <tex>k\geq 0</tex> таких, что
-) Каждая функция <tex>f_i \in F_k</tex> описывается <tex>k</tex> битовым индексом <tex>i</tex>.
+) Каждая функция <tex>f_i \in F_k</tex> описывается <tex>k</tex> битовым индексом <tex>i</tex>;
-) Существует полиномиальный алгоритм, который по входу <tex>i</tex> и <tex>x</tex> вычисляет <tex>f_i(x)</tex>. То есть каждая функция из <tex>F_k</tex> вычислима схемой полиномиального размера.
+) Существует полиномиальный алгоритм, который по входу <tex>i</tex> и <tex>x</tex> вычисляет <tex>f_i(x)</tex>. То есть каждая функция из <tex>F_k</tex> вычислима схемой полиномиального размера;
 ) Не существует полиномиального вероятностного алгоритма, способного отличить случайно выбранную функцию из <tex>F_k</tex>, от функций, случайно выбранных из всех функций осуществляющих преобразование <tex>\{0,1\}^k\rightarrow\{0,1\}^k</tex>, даже если алгоритм будет иметь возможность динамически полиномиально вычислять большое количество значений неизвестной функции на выбранных им аргументах.
@@ Строка 15: / Строка 16: @@
 === Секретные ключи и целевые функции ===
-Понятие секретного ключа в криптографии связано с понятием целевой функции в машинном обучении или, более обще, понятие ключевого пространства в криптографии связано с понятием класса возможных целевых функций. Для криптографических целей данные функции должны быть легко инвертируемы, в то время как в теории машинного обучения нет такого требования. Есть и другой аспект, в котором эти области отличаются: в то время как в криптографии обычно предполагается, что размер ключа известен атакующему, существует масса интересных исследований в теории машинного обучения, которые предполагают неизвестность сложности (размера) целевой гипотезы. Простой пример этого явления --- проблема привязки полинома у набору информационных точек (при наличии шума), при неизвестной степени искомого полинома. Необходим некоторый метод "сброса" "сложности гипотезы" для соответствия данным такой, как Russanen's Description Length Principle. Дальнейшие исследования в крипторафических схемах с ключами переменной длины должны только выиграть от исследования литературы по машинному обучению, касающейся этой области.
+Понятие секретного ключа в криптографии связано с понятием целевой функции в машинном обучении или, более общо, понятие ключевого пространства в криптографии связано с понятием класса возможных целевых функций. Для криптографических целей шифрующие функции должны быть легко инвертируемы, в то время как в теории машинного обучения нет такого требования. Есть и другой аспект, в котором эти области отличаются: в то время как в криптографии обычно предполагается, что размер ключа известен атакующему, существует масса интересных исследований в теории машинного обучения, которые предполагают неизвестность сложности (размера) целевой гипотезы. Дальнейшие исследования в крипторафических схемах с ключами переменной длины должны только выиграть от исследования литературы по машинному обучению, касающейся этой области.
 === Типы атак и протоколы обучения ===
+Ключевой аспект в любом криптографическом сценарии или сценарии машинного обучения --- это спецификация того, как криптоаналитик (обучающийся алгоритм) может получать информацию о неизвестной целевой функции.
+Криптографические атаки могут проводиться в  различных условиях, таких как известный шифрованный текст, известный открытый текст (и соответствующий шифрованный текст), выбранный открытый текст и выбранный шифрованный текст. Криптосистемы, защищенные от атак в одних из данных условий, могут не быть защищены от атак в остальных.
+Исследователи в области машинного обучения изучали сходные сценарии. Например, обучающемуся может быть дозволено узнавать значение неизвестной функции на некотором заданном входе или узнавать, действительно ли некоторая предполагаемая гипотеза эквивалентна неизвестной целевой гипотезе (в случае отрицательного ответа обучающемуся предоставляется контрпример --- вход, на котором предполагаемая и целевая гипотезы дают разные ответы). К примеру, Англуин показал, что данных запросов достаточно для точного определения любого регулярного языка, в то время как проблема обучения распознаванию регулярного языка по случайным примерам NP-полна.
+Даже если информация собрана из случайных примеров, криптоаналитические сценарии/сценарии обучения могут отличаться в априорном знании атакующего/обучающегося о распределении этих примеров. Например, некоторые криптосистемы могут быть успешно атакованы зная только устройство системы и языка открытых текстов (который определяет распределение примеров). В то же время в теории машинного обучения часто предполагается, что примеры выбираются в соответствии с произвольным, но фиксированным вероятностным распределением, неизвестным обучающемуся.
 === Точный и приближенный выводы ===
+В сфере практической криптографии атакующий обычно нацелен на "полный взлом", под которым подразумевается получение неизвестного секретного ключа. Приблизительное определение неизвестной функции обычно не является целью, так как набор возможных криптографических функций, используемых в обычном режиме, не допускает хорошего приближения. С другой стороны теоретическое развитие криптографии привело к определению защищенности, которое исключает даже приблизительное вычисление ключа криптоаналитиком. Такие теоретические определения и соответствующие результаты, таким образом, оказываются применимы к получению результатов, касающихся сложности обучения.
+Литература по машинному обучению касается и точного, и приблизительного результата. Так как точный результат часто очень сложно получить эффективно, значительное внимание было уделено приблизительным результатам. Приблизительное обучение является обычно целью, когда входные данные состоят из случайно выбранных примеров. С другой стороны, когда обучающийся может динамически запрашивать значение неизвестной функции, как правило ожидается точное обучение.
 === Вычислительная сложность ===
+[[вычислительная сложность|Вычислительная сложность]] --- это основной объект интереса и в криптографии, и в машинном обучении. В криптографии основной целью является доказательство защищенности в условиях наиболее широкого определения защищенности и наислабейших теоретико-сложностных предположений. Например, предположение существования односторонней функции --- одно из таких предположений. В условиях данного предположения можно доказать, что существуют криптосистемы, которые невозможно взломать, используя полиномиальный алгоритм.
+В машинном обучении полиномиальные по времени обучающиеся алгоритмы --- это цель, и существует много таких алгоритмов для отдельных задач. Иногда, в условиях определенных криптографических предположений можно показать невозможность существования полиномиального алгоритма для конкретной задачи. Иногда обучающийся алгоритм не знает, какого размера будет целевая гипотеза, и ему позволяется работать некоторое полиномиальное время. Часто от обучающегося алгоритма требуют лишь построить гипотезу, которая будет согласовываться с имеющимися примерами.
+И в случае криптографии, и в случае машинного обучения определенный интерес представляет сложность по памяти. В области криптографии Хэллман, Шрёппель и Шамир изобрели алгоритмы снижения сложности по памяти для конкретных криптосистем. В машинном же обучении есть результат Шапира, утверждающий, что если существует эффективный обучающийся алгоритм для класса функций, то существует алгоритм, чья сложность по памяти растет лишь логарифмически по отношению ко входным данным.
 === Другие отличия ===
+Эффект шума во входных данных в криптографии и в машинном обучении основательно изучался лишь в последней области, вероятно потому что даже небольшой шум может сделать ситуацию в криптоанализе совершенно безнадежной. Тем не менее существуют криптографические системы, которые используют шум для увеличения стойкости, и есть криптосистемы, которые пытаются работать несмотря на шум.
+Часто в машинном обучении проблемы исследуются с более общих позиций, чем в криптографии. Например, в машинном обучении существуют алгоритмы, которые постепенно меняются с течением времени, в криптографии такие изменения редки (пользователи меняют ключи шифрования, но эта смена происходит единовременно, а не постепенно).
 ==Влияние криптографии на машинное обучение==
+После работы Гольдрайха, Гольдвассер и Микали, утверждавшей существование класса функций, который невозможно алгоритмически воспроизводить (при условии существовании односторонней функции), даже позволив обучающемуся алгоритму делать произвольные запросы значений целевой функции, исследователи в области машинного обучения сфокусировались на описании простейших классов функций, обучение которым возможно. Например, основным вопросом является возможность эффективного обучения классу булевых функций, представленных в виде дизъюнктивной нормальной формы, по случайным примерам.
+Основное влияние криптографии на машинное обучение естественно (и негативно): доказательство того, что отдельные задачи обучения неразрешимы (нереализуемы). Конечно, существуют другие причины, по которым задача обучения может быть неразрешимой; например, обучение классу всех булевых функций  невозможно, так как число примеров, необходимых для обучения экспоненциально больше числа входных булевых переменных.
+Одним из классов "неподатливых" в теории машинного обучения задач являются задачи, зависящие от представления, то есть показано, что имея набор примеров, вычислительно сложно найти булеву функцию, соответствующую этим примерам и имеющую определенный вид. Например, Питт и Валиант показали, что нахождение 2-ДНФ формулы по парам входных и выходных значений является NP-полной задачей. Это означает, что обучение 2-ДНФ формуле (учитывая, что P <tex>\neq</tex> NP) нереализуемо, но только если обучающийся алгоритм должен представить результат в виде 2-ДНФ. При этом аналогичная задача для 2-КНФ решается эффективно.
+С целью получения сложностных результатов Кернс и Валиант обратились к предположениям криптографии (а именно сложности обращения RSA, сложности поиска квадратичных вычетов по модулю чисел Блюма, сложности факторизаци чисел Блюма). Конечно, им также требовалось объяснить, насколько сложным может быть обучение в виде, независимом от представления, что они и проделали, требуя от обучаемого алгоритма не выходную гипотезу в некотором представлении, а, скорее, предсказание классификации нового примера с высокой вероятностью.
+Более того, чтобы доказать сложностные результаты для сравнительно простых классов функций, Кернсу и Валианту потребовалось показать, что требуемые криптографические операции могут быть определены в рамках выбранного класса функций. Это они реализовали используя технику расширенного входа, когда к основным входам добавляются промежуточные результаты вычислений.
+В результате было получено следующее утверждение: если обучающийся алгоритм может успешно обучиться одному из перечисленных в статье классов функций (например, класс булевых функций с n входами и размера не более p(n)), то есть может предсказать классификацию новых примеров с вероятностью существенно выше 1/2, то данный алгоритм можно использовать для успешного взлома одной из криптографических задач, считаемых сложными.
+Можно задаться вопросом, могут ли криптографические методы быт использованы для доказательства необучаемости конкретных классов функций даже в том случае, когда обучаемому алгоритму позволено осуществлять произвольные запросы к целевой функции. Англуин и Харитонов показали (с учетом обычных криптографических предположений, касающихся RSA, разложения на множители чисел Блюма или квадратичных вычетов), что не существует полиномиальных алгоритмов (даже в случае допустимости произвольных запросов к целевой функции) для следующих классов функций:
+. Булевы формулы.
+. Пороговые схемы фиксированной глубины.
+. Булевы формулы, в которых каждая переменная встречается не более трех раз.
+. Конечные объединения и пересечения детерминированных конечных автоматов, двусторонних конечных автоматов, контекстно-свободных грамматик, недетерминированных конечных автоматов.
+Эти результаты базируются на криптосистемы с открытым ключом Наора и Юнга, которая доказуемо стойка против атаки с выбранным шифротекстом.
 ==Влияние машинного обучения на криптографию==
+В то время как большинство отрицательных результатов в теории обучения зависят от криптографических предположений, в настоящее время не найдено примеров влияния отрицательных результатов в теории машинного обучения на криптографические схемы.
+С другой стороны, положительные результаты в теории обучения обычно не зависят от криптографических предположений и в принципе могут быть применены в криптоанализе сравнительно простых криптосистем. Существует очень моло упоминаний в публикациях по этому поводу, поэтому более глубокий анализ возможностей, предоставляемых использовнием теории машинного обучения в криптографии, остается открытым вопросом.
+=== Криптоанализ шифра обратной связи ===
+Режим обратной связи шифра работает следующим образом:
+<tex>C_i=E_k(C_{i-1})\oplus P_i</tex>
+<tex>P_i=E_k(C_{i-1})\oplus C_i</tex>
+<tex>C_0=IV</tex>
+где IV - вектор инициализации, <tex>C_i</tex> - блок шифрованного текста, <tex>P_i</tex> - блок открытого текста.
+Вероятно, наиболее явное применение результатов теории машинного обучения в криптографии --- это криптоанализ нелинейного шифра с обратной связью. Функция f  известна только получателю и отправителю и использует их [[криптография|секретный ключ]].
+Если у криптоаналитика есть набор пар открытого/шифрованного текста, то у него есть набор пар входов/выходов неизвестной функции f. Обучающийся алгоритм, который сможет восстановить данную функцию по входам/выходам может использоваться как криптоаналитический инструмент. Дополнительные возможности для обучающегося алгоритма предоставляет атака с выбранным шифротекстом.
+Отметим, что в данной ситуации подходит и понятиее "приблизительного" обучения. Если алгоритм возвращает правильное значение, например, в 99 % случаев, то криптоаналитик сможет дешифровать 99 % блоков текста.
+Сперва предположим, что мы используем атаку с известным открытым текстом. Принципы криптографии предполагают, что в данном случае вероятность на выходе получить 1 совпадает с вероятностью получить 0. Обычно это приводит к возможности рассматривать результат сдвига, как случайно и равномерно выбранный вектор из <tex>\{0,1\}^n</tex>. Данное условие является молореалистичным и ограничивающим в теории обучения, но отлично подходит для криптографических целей.
+Шапир получил ряд результатов для различных функций f. В частности, он показал, что функция f, построенная исключительно из операций AND, OR и NOT может быть эффективно воспроизведена за полиномиальное время по случайным примерам входных данных.
+Линиал, Мансор и Нисан показали, как использовать спектральный (основанных на преобразовании Фурье) метод для обучения функциям, представимым в виде схем фиксированной длины, с блоками AND, OR и NOT с произвольным количеством входов, по случайным примерам входных данных. Данный результат был расширен Кушелевичем и Мансором, а затем Фурстом, Джексоном и Смитом на более широкие классы функций.
+Хэнкок и Монсор показали, что функции, представимые в виде монотонных k-ДНФ (то есть ДНФ, в которые каждая переменная входит не более k раз), доступны для обучения по случайным примерам. Тем не менее функции, представимые в виде монотонных ДНФ редко используются.
+Применение атаки с выбором шифрованного текста позволяет еще более расширить класс функций, которых необходимо избегать при построении криптосистемы.
+=== Другие возможности ===
+Другими общими для теории машинного обучения и криптографии областями может стать сжатие данных, хотя на данный момент в публикациях данной тематике практически не уделено внимание, и [[нейрокриптография]], которая является расширением подхода, рассмотренного в предыдущем разделе.
 ==Ссылки==
+* Ronald L. Rivest [http://people.csail.mit.edu/rivest/Rivest-CryptographyAndMachineLearning.pdf Cryptography And Machine Learning], Proceedings ASIACRYPT '91 (Springer 1993), 427 – 439
 [[Категория:Машинное обучение]]
 [[Категория:Криптография]]
 [[Категория:Популярные и обзорные статьи]]