Односторонние функции

Односторонняя функция

Функция \(f:X\to Y\), такая, что существует алгоритм вычисления \(f(x)\) за полиномиальное время. В то же время, любой рандомизированный алгоритм \(F\), работающий за полиномиальное время, успешно вычисляет значение обратной функции \(f^{-1}(y)\) с пренебрежимо малой вероятностью: \[\forall F, \forall c \in \mathbb N : P[f(F(f(x))) = f(x)] < |x|^{-c},\] где \(|x|\) – размер аргумента (в каком-либо смысле), \(P\) – вероятность.

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

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

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

Кандидаты в односторонние функции

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

Умножение и факторизация

Пусть функция \(f\) принимает на вход простые числа \(p\) и \(q\) и возвращает их произведение. Такая функция может быть вычислена за полиномиальное время \(O(b^2)\), где \(b\) – число бит, используемое для представления входных чисел. Обращение этой функции требует разложения числа на простые множители (факторизации). Лучшие известные на момент написания алгоритмы факторизации имеют сложность \(O\left( \exp\sqrt[3]{\frac{64}{9}b(\log b)^2} \right)\), где \(b\) – число бит, необходимое для представления факторизуемого числа.

Стоит отметить, что такая функция не является односторонней для случайных \(p\), \(q\). Действительно, половина всех чисел – чётные. Вероятность что \(p\) и \(q\) оба нечётные тогда – ¼. Тогда вероятность, что хотя бы одно чётное – ¾, и тогда ¾ всех чисел будут иметь фактор 2.

Отдельно стоит отметить, что существует алгоритм Шора, позволяющий производить факторизацию за полиномиальное время на квантовом компьютере.

Функция Рабина (квадрат по модулю)

Возведение в квадрат по модулю полупростого числа (т.е. произведения простых) \[f_{pq} (x) = x^2 \mod pq\]

Обращение функции Рабина вычислительно эквивалентно факторизации (в смысле сводится к факторизации за полиномиальное время). Таким образом, функция Рабина является односторонней iff таким является умножение простых.

Дискретное возведение в степень и логарифм

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

Рассмотрим конечную абелеву группу \((G, \bullet)\) размера \(n\). Пусть эта группа имеет примитивный элемент \(\alpha \in G\). Рассмотрим элемент \(\beta \in G\). Задача дискретного алгоритма формулируется тогда следующим образом: найти такое \(k\), что \[\alpha^k = \underbrace{\alpha\bullet\ldots\bullet\alpha}_{k \text{ раз}} = \beta\]

Популярными вариантами выбора групп являются мультипликативная группа над конечным полем целых чисел по простому модулю, либо циклические подгруппы на эллиптических кривых над конечными полями.

Следует отметить, что существует алгоритм дискретного логарифмирования Шора, дающий полиномиальное время на квантовом компьютере.

Криптографически безопасные хэш-функции

Существует некоторое количество “легко” вычислимых криптографических хэш-функций. Некоторые из более простых алгоритмов имеют слабые места, но многие остаются пока практически безопасными и не имеют “лёгких” алгоритмов обращения.

Случайные линейные коды

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

Криптостойкие ГПСЧ на односторонних функциях

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

ГПСЧ Шамира на основе факторизации

ГПСЧ Шамира¹ основан, по сути, на алгоритме RSA. ГПСЧ Шамира является генератором бит, т.е. на каждом шаге генератора выводится 1 бит.

Приведём описание алгоритма

1. Выбрать два простых числа \(p\) и \(q\). Вычислить \(n=pq\) и \(m=(p-1)(q-1)\). Выбрать случайное целое \(1<e<m\), взаимно простое с \(m\).
2. Выбрать случайное начальное состояние \(1 \le s_0 \le n-1\)
3. \(s_i = s_{i-1}^e \mod n\)
4. Вывод \(x_i = s_i \mod 2\)

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

ГПСЧ Блюма-Микали на основе дискретного логарифма

1. Выбираются числа \(g\) и \(p\), причём \(g\) – примитивный элемент мультипликативной группы по модулю \(p\), \(p\) – простое.
2. Генерируется секретное случайное число \(1 < s_0 < p-1\)
3. \(s_{i+1} = g^{s_i} \mod p\)
4. Вывод \(x_i = \left\lbrace\begin{align} 1, && s_{i} < (p-1)/2 \\ 0, && s_{i} \ge (p-1)/2 \\ \end{align}\right.\)

ГПСЧ Блюм-Блюма-Шуба на основе функции Рабина

1. Выбрать простые числа \(p\) и \(q\), конгруэнтные 3 по модулю 4, причём такие, что \(НОД(\varphi(p-1),\varphi(q-1))\) мал (\(\varphi\) – ф-я Эйлера). Вычислить \(n=pq\).
2. Выбрать начальное состояние \(s_0 > 1\), взаимно простое с \(n\).
3. \(s_{i+1} = s_i^2 \mod n\)
4. Вывод \(x_i = s_i \mod 2\)

Вообще говоря, вывод не обязательно по модулю 2.

Интересным свойством алгоритма является возможность прямо вычислить \(s_i\) по теореме Эйлера: \[s_i = s_0^{2^i \mod \lambda(n)} \mod n.\]

Здесь \(\lambda\) – функция Кармайкла, \[\lambda(n) = \min \{m | \forall a\in\mathbb N, 1<a<n-1 : a^m = 1 \mod n\}.\]

В данном случае, \(\lambda(n) = \lambda(pq) = НОК(p-1,q-1)\) (мы получили аналогичный результат в виде леммы 2 при доказательстве теоремы Халла-Добелла)