Криптография и машинное обучение
Материал из MachineLearning.
(→Начальное сравнение) |
(→Секретные ключи и целевые функции) |
||
| Строка 11: | Строка 11: | ||
=== Секретные ключи и целевые функции === | === Секретные ключи и целевые функции === | ||
| + | Понятие секретного ключа в криптографии связано с понятием целевой функции в машинном обучении или, более обще, понятие ключевого пространства в криптографии связано с понятием класса возможных целевых функций. Для криптографических целей данные функции должны быть легко инвертируемы, в то время как в теории машинного обучения нет такого требования. Есть и другой аспект, в котором эти области отличаются: в то время как в криптографии обычно предполагается, что размер ключа известен атакующему, существует масса интересных исследований в теории машинного обучения, которые предполагают неизвестность сложности (размера) целевой гипотезы. Простой пример этого явления --- проблема привязки полинома у набору информационных точек (при наличии шума), при неизвестной степени искомого полинома. Необходим некоторый метод "сброса" "сложности гипотезы" для соответствия данным такой, как Russanen's Description Length Principle. Дальнейшие исследования в крипторафических схемах с ключами переменной длины должны только выиграть от исследования литературы по машинному обучению, касающейся этой области. | ||
=== Типы атак и протоколы обучения === | === Типы атак и протоколы обучения === | ||
Версия 20:42, 2 января 2010
Содержание |
Введение
Активное развитие информатики началось в 40-х и 50-х гг. прошлого столетия и было в основном основано на научных достижениях 30-х гг. С самого начала и машинное обучение, и криптография были тесно связаны с этой областью знания. Криптография играла важную роль в течение Второй Мировой Войны и некоторые из первых компьютеров были предназначены для решения криптографических задач. Возможность компьютеров "обучаться" делать вещи, которые, как считалось доступны только людям (например, игра в шахматы), стала активно изучаться в 50-е гг. Тьюрингом, Самюэлем и др.
Начальное сравнение
машинное обучение и криптоанализ можно рассматривать как родственные области, так они содержат много общих понятий и вопросов. В типичной криптоаналитической ситуации криптоаналитик желает взломать некоторую криптосистему. Обычно это означает, что он хочет найти секретный ключ, примененный пользователями криптосистемы, когда известно устройство системы. Таким образом, описание функции берется из известного семейства таких функций (индексируемых по ключу), а цель криптоанализа заключается в точном определении использованной функции. Обычно криптоаналитику предоставлено некоторое количество соответствующих друг другу открытых и шифрованных текстов. Данная проблема также может быть описана, как проблема "обучения вычислению неизвестной функции" на основе примеров входных/выходных данный и знании класса, из которого функция выбрана.
Валиант отмечает, что «хорошая» криптография может предоставить классы «сложных» для анализа функций. Отдельно он ссылается на работу Гольдрайха, Гольвассер и Микали, которые показали (предположив существование односторонней функции), как построить семейство псевдослучайных функций : для каждого
таких, что
1) Каждая функция
описывается
битовым индексом
.
2) Существует полиномиальный алгоритм, который по входу
и
вычисляет
. То есть каждая функция из
вычислима схемой полиномиального размера.
3) Не существует полиномиального вероятностного алгоритма, способного отличить случайно выбранную функцию из
, от функций, случайно выбранных из всех функций осуществляющих преобразование
, даже если алгоритм будет иметь возможность динамически полиномиально вычислять большое количество неизвестной функции на выбранных им аргументах.
Теперь перейдем к короткому сравнению терминологии и концепций, проведению естественных связей, некоторые из которых были проиллюстрированы примером выше.
Секретные ключи и целевые функции
Понятие секретного ключа в криптографии связано с понятием целевой функции в машинном обучении или, более обще, понятие ключевого пространства в криптографии связано с понятием класса возможных целевых функций. Для криптографических целей данные функции должны быть легко инвертируемы, в то время как в теории машинного обучения нет такого требования. Есть и другой аспект, в котором эти области отличаются: в то время как в криптографии обычно предполагается, что размер ключа известен атакующему, существует масса интересных исследований в теории машинного обучения, которые предполагают неизвестность сложности (размера) целевой гипотезы. Простой пример этого явления --- проблема привязки полинома у набору информационных точек (при наличии шума), при неизвестной степени искомого полинома. Необходим некоторый метод "сброса" "сложности гипотезы" для соответствия данным такой, как Russanen's Description Length Principle. Дальнейшие исследования в крипторафических схемах с ключами переменной длины должны только выиграть от исследования литературы по машинному обучению, касающейся этой области.
