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

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

Версия от 20:18, 2 января 2010; Лошкарёв Сергей (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Введение
2 Начальное сравнение
3 Влияние криптографии на машинное обучение
4 Влияние машинного обучения на криптографию
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$ , даже если алгоритм будет иметь возможность динамически полиномиально вычислять большое количество неизвестной функции на выбранных им аргументах. Теперь перейдем к короткому сравнению терминологии и концепций, проведению естественных связей, некоторые из которых были проиллюстрированы примером выше.