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

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

Версия 20:14, 4 января 2010

Введение

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

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

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

1) Каждая функция описывается битовым индексом .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С целью

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

Ссылки

• Rivest "Cryptography And Machine Learning"