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

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

(Различия между версиями)
Перейти к: навигация, поиск
(категория)
(Начальное сравнение)
Строка 2: Строка 2:
Активное развитие информатики началось в 40-х и 50-х гг. прошлого столетия и было в основном основано на научных достижениях 30-х гг. С самого начала и машинное обучение, и криптография были тесно связаны с этой областью знания. Криптография играла важную роль в течение Второй Мировой Войны и некоторые из первых компьютеров были предназначены для решения криптографических задач. Возможность компьютеров "обучаться" делать вещи, которые, как считалось доступны только людям (например, игра в шахматы), стала активно изучаться в 50-е гг. Тьюрингом, Самюэлем и др.
Активное развитие информатики началось в 40-х и 50-х гг. прошлого столетия и было в основном основано на научных достижениях 30-х гг. С самого начала и машинное обучение, и криптография были тесно связаны с этой областью знания. Криптография играла важную роль в течение Второй Мировой Войны и некоторые из первых компьютеров были предназначены для решения криптографических задач. Возможность компьютеров "обучаться" делать вещи, которые, как считалось доступны только людям (например, игра в шахматы), стала активно изучаться в 50-е гг. Тьюрингом, Самюэлем и др.
-
==Начальное сравнение==
+
== Начальное сравнение ==
 +
машинное обучение и криптоанализ можно рассматривать как родственные области, так они содержат много общих понятий и вопросов. В типичной криптоаналитической ситуации криптоаналитик желает взломать некоторую криптосистему. Обычно это означает, что он хочет найти секретный ключ, примененный пользователями криптосистемы, когда известно устройство системы. Таким образом, описание функции берется из известного семейства таких функций (индексируемых по ключу), а цель криптоанализа заключается в точном определении использованной функции. Обычно криптоаналитику предоставлено некоторое количество соответствующих друг другу открытых и шифрованных текстов. Данная проблема также может быть описана, как проблема "обучения вычислению неизвестной функции" на основе примеров входных/выходных данный и знании класса, из которого функция выбрана.
 +
Валиант отмечает, что «хорошая» криптография может предоставить классы «сложных» для анализа функций. Отдельно он ссылается на работу Гольдрайха, Гольвассер и Микали, которые показали (предположив существование односторонней функции), как построить семейство псевдослучайных функций : <tex> F_k:\{0,1\}^k\rightarrow\{0,1\}^k</tex> для каждого <tex>k\geq 0</tex> таких, что
 +
1) Каждая функция <tex>f_i \in F_k</tex> описывается <tex>k</tex> битовым индексом <tex>i</tex>.
 +
2) Существует полиномиальный алгоритм, который по входу <tex>i</tex> и <tex>x</tex> вычисляет <tex>f_i(x)</tex>. То есть каждая функция из <tex>F_k</tex> вычислима схемой полиномиального размера.
 +
3) Не существует полиномиального вероятностного алгоритма, способного отличить случайно выбранную функцию из <tex>F_k</tex>, от функций, случайно выбранных из всех функций осуществляющих преобразование <tex>\{0,1\}^k\rightarrow\{0,1\}^k</tex>, даже если алгоритм будет иметь возможность динамически полиномиально вычислять большое количество неизвестной функции на выбранных им аргументах.
 +
Теперь перейдем к короткому сравнению терминологии и концепций, проведению естественных связей, некоторые из которых были проиллюстрированы примером выше.
-
===Секретные ключи и целевые функции===
+
=== Секретные ключи и целевые функции ===
-
===Типы атак и протоколы обучения===
+
=== Типы атак и протоколы обучения ===
-
===Точный и приближенный выводы===
+
=== Точный и приближенный выводы ===
-
===Вычислительная сложность===
+
=== Вычислительная сложность ===
-
===Другие отличия===
+
=== Другие отличия ===
==Влияние криптографии на машинное обучение==
==Влияние криптографии на машинное обучение==

Версия 20:18, 2 января 2010

Содержание

Введение

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

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

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

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

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

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

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

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

Ссылки

Личные инструменты