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

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

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

Содержание

Введение

Активное развитие информатики началось в 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, даже если алгоритм будет иметь возможность динамически полиномиально вычислять большое количество значений неизвестной функции на выбранных им аргументах.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

  • Rivest "Cryptography And Machine Learning"