Нерешённые проблемы информатики: ''Существуют ли односторонние функции ?''

Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться также трудно обратимыми или необратимыми.

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

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

Пусть ${\displaystyle \{0,1\}^{n}}$ — множество всех двоичных строк длины n. Функция ${\displaystyle f:\{0,1\}^{*}\to \{0,1\}^{*}}$ является односторонней функцией, если она эффективно вычисляется за полиномиальное время на детерминированной машине Тьюринга, но не существует полиномиальной вероятностной машины Тьюринга, которая обращает эту функцию с более чем экспоненциально малой вероятностью. То есть для любой вероятностной полиномиальной машины ${\displaystyle M}$, для любого полинома ${\displaystyle p(n)}$ и достаточно большого ${\displaystyle n\in \mathbb {N} }$ выполняется

${\displaystyle \Pr[M(f(m))\in f^{-1}(m)]<1/p(n),}$

где строка ${\displaystyle m}$ выбирается случайным образом на множестве ${\displaystyle \{0,1\}^{n}}$ в соответствии с равномерным законом распределения. Время работы машины ${\displaystyle M}$ ограничено полиномом от длины искомого прообраза^[1].

Ни для одной функции, используемой как односторонняя на практике, не доказано, что она истинно односторонняя (то есть, что не существует быстрого алгоритма решения обратной задачи). Если f является односторонней функцией, то нахождение обратной функции является трудновычислимой (по определению), но легкопроверяемой задачей (путём вычисления f на ней). Таким образом, из существования односторонней функции следует, что P ≠ NP. Однако, неизвестно, влечёт ли за собой P ≠ NP существование односторонних функций.

Существование односторонних функций повлечёт за собой существование многих других полезных криптографических объектов, в том числе:

• генераторов псевдослучайных чисел;
• если существует односторонняя функция с трудным битом, то существует битовая схема обязательств;
• семейства псевдослучайных функций^[англ.];
• имитовставки;
• электронной цифровой подписи.

Говорят, что односторонняя функция сохраняет длину, если битовая длина значения функции равна битовой длине аргумента. Такие функции используются, например, в псевдослучайных генераторах. Если битовая длина значения односторонней функции постоянна при любой длине аргумента, то она называется хеш-функцией. Так, хеш-функция используется для хранения паролей или создания электронной подписи^[1].

Трудность задачи построения криптографических схем из односторонних функций можно пояснить на следующем примере. Пусть ${\displaystyle f}$ — односторонняя функция и нам требуется построить криптосистему с секретным ключом. В такой криптосистеме имеется только один ключ — секретный, который известен и отправителю, и получателю шифрованного сообщения. Алгоритмы шифрования ${\displaystyle E_{K}}$ и дешифрования ${\displaystyle D_{K}}$ оба зависят от этого секретного ключа ${\displaystyle K}$ и таковы, что ${\displaystyle D_{K}(E_{K}(m))=m}$ для любого открытого текста ${\displaystyle m}$. Ясно, что если криптограмму ${\displaystyle d}$ сообщения ${\displaystyle m}$ вычислять как ${\displaystyle d=f(m)}$, то противник, перехвативший ${\displaystyle d}$, может вычислить ${\displaystyle m}$ лишь с пренебрежимо малой вероятностью. Но во-первых, непонятно, каким образом сможет восстановить сообщение ${\displaystyle m}$ из криптограммы законный получатель? Во-вторых, из того, что функция ${\displaystyle f}$ односторонняя следует лишь, что противник не может вычислить все сообщение целиком. А это — весьма низкий уровень стойкости. Желательно, чтобы противник, знающий криптограмму ${\displaystyle d}$, не мог вычислить ни одного бита открытого текста.

Для решения первой задачи были придуманы односторонние функции с потайным входом. Это специальный тип односторонней функции для которой легко вычислить ${\displaystyle f(m)}$ по заданному ${\displaystyle m}$, но трудно по известному ${\displaystyle f(m)}$ вычислить ${\displaystyle m}$. Однако существует некоторая дополнительная секретная информация ${\displaystyle y}$, позволяющая при знании ${\displaystyle f(m)}$ и ${\displaystyle y}$ легко вычислить ${\displaystyle m}$.

Ещё одним примером использования односторонних функций в криптографических схемах является следующая схема аутентификации:

Абонент ${\displaystyle A}$ вырабатывает следующую последовательность сообщений: ${\displaystyle m_{0},m_{1}=f(m_{0}),m_{2}=f(m_{1})}$ и т. д. ${\displaystyle m_{100}=f(m_{99})}$, где ${\displaystyle f(m)}$ — односторонняя функция. Затем ${\displaystyle m_{100}}$ передаётся по секретному каналу (или при встрече) абоненту ${\displaystyle B}$. Когда ${\displaystyle A}$ необходимо подтвердить свою личность, он передаёт ${\displaystyle B}$ по открытому каналу сообщение ${\displaystyle m_{99}}$. ${\displaystyle B}$ проверяет: ${\displaystyle f(m_{99})=?m_{100}}$. В следующий раз ${\displaystyle A}$ передаст ${\displaystyle m_{98}}$, и ${\displaystyle B}$ проверит: ${\displaystyle f(m_{98})=?m_{99}}$ и т. д. Перехват сообщений на i-ом этапе в открытом канале ничего не даст злоумышленнику, так как он не сможет получить соответствующее значение ${\displaystyle m_{i-1}}$, чтобы в следующий раз идентифицировать себя как абонента ${\displaystyle A}$. Такие схемы применяются для идентификации «свой/чужой»^[2].

Для защиты компьютерных систем от злоупотребления услугами запрашивающей стороне предлагается решить задачу, на поиск решения которой тратится достаточно много времени, а результат легко и быстро проверяется обслуживающей стороной. Примером такой защиты от спама может служить система Hashcash^[3], которая запрашивает хеш частичной инверсии у отправляющей электронную почту стороне.

В системе «Биткойн» требуется, чтобы получаемая хеш-сумма была меньше специального параметра. Для поиска нужной хеш-суммы требуется её многократный пересчёт с перебором произвольных значений дополнительного параметра. На поиск одной хеш-суммы все компьютеры системы тратят примерно 10 минут, что регулирует скорость эмиссии новых биткойнов. Для проверки требуется лишь однократное вычисление хеша.

Существование односторонних функций является необходимым условием для стойкости многих типов криптографических схем. В некоторых случаях этот факт устанавливается достаточно просто. Рассмотрим функцию ${\displaystyle f}$ такую, что ${\displaystyle f(r)=K_{1}}$. Она вычислима с помощью алгоритма ${\displaystyle G}$ за полиномиальное время. Покажем, что если ${\displaystyle f}$ не односторонняя функция, то криптосистема нестойкая. Предположим, что существует полиномиальный вероятностный алгоритм ${\displaystyle A}$, который инвертирует ${\displaystyle f}$ с вероятностью по крайней мере ${\displaystyle 1/p(n)}$ для некоторого полинома ${\displaystyle p}$. Здесь ${\displaystyle n}$ — длина ключа ${\displaystyle K_{1}}$. Атакующий может подать на вход алгоритму ${\displaystyle A}$ ключ ${\displaystyle K_{1}}$ и получить с указанной вероятностью некоторое значение ${\displaystyle r'}$ из прообраза. Далее злоумышленник подаёт ${\displaystyle r'}$ на вход алгоритма ${\displaystyle G}$ и получает пару ключей ${\displaystyle (K_{1},K'_{2})}$. Хотя ${\displaystyle K'_{2}}$ не обязательно совпадает с ${\displaystyle K_{2}}$, тем не менее, по определению криптосистемы ${\displaystyle D_{K_{2}'}(E_{K_{1}}(m))=m}$ для любого открытого текста ${\displaystyle m}$. Поскольку ${\displaystyle K'_{2}}$ найден с вероятностью по крайней мере ${\displaystyle 1/p(n)}$, которая в криптографии не считается пренебрежимо малой, криптосистема нестойкая.

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

На настоящий момент^{[когда?]} доказано, что существование односторонних функций является необходимым и достаточным условием для существования стойких криптосистем с секретным ключом, а также стойких криптографических протоколов нескольких типов, включая протоколы электронной подписи. С другой стороны, имеется результат Импальяццо и Рудиха, который является достаточно сильным аргументом в пользу того, что для некоторых типов криптографических схем (включая протоколы распределения ключей типа Диффи-Хеллмана) требуются более сильные предположения, чем предположение о существовании односторонних функций^[4].

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

Функция ${\displaystyle f}$ принимает на вход два простых числа ${\displaystyle p}$ и ${\displaystyle q}$ в двоичном представлении и возвращает их произведение ${\displaystyle N=f(p,q)}$. Эта функция может быть вычислена за время порядка ${\displaystyle O}$${\displaystyle (n^{2})}$, где ${\displaystyle n}$ — общая длина (количество двоичных чисел) входных данных. Построение обратной функции требует нахождения множителей заданного целого числа ${\displaystyle N}$. Определение множителей является очень трудоёмкой вычислительной операцией. Для оценки сложности алгоритма, раскладывающего целое число ${\displaystyle N}$ на простые множители, часто используют функцию:

${\displaystyle L_{N}(\alpha ,\beta )=\exp((\beta +o(1)(\ln N)^{\alpha }(\ln \ln N)^{1-\alpha }))}$

Если алгоритм имеет сложность ${\displaystyle O(L_{N}(0,\beta ))}$, то ему требуется полиномиальное время на работу (размер задачи на входе, число бит числа, ${\displaystyle \ln N}$). При сложности ${\displaystyle O(L_{N}(1,\beta ))}$ ему потребуется уже экспоненциальное время. Таким образом скорость роста функции ${\displaystyle L_{N}(\alpha ,\beta )}$ при ${\displaystyle 0<\alpha <1}$ лежит между полиномиальной и экспоненциальной. Поэтому про алгоритмы с такой сложностью говорят, что они требуют суб-экспоненциального времени^[5].

Существует несколько методов факторизации числа ${\displaystyle N=p*q}$ с простыми ${\displaystyle p}$ и ${\displaystyle q}$. Некоторые из них:

• Пробное деление — в этом алгоритме для всех простых чисел ${\displaystyle p}$, не превосходящих ${\displaystyle {\sqrt {N}}}$, проверяется условие ${\displaystyle N/p\in \mathbb {Z} }$. Такой алгоритм близок к полному перебору и имеет экспоненциальную сложность ${\displaystyle O(L_{N}(1,1))}$.
• Метод эллиптической кривой хорошо работает, если один из простых множителей ${\displaystyle p}$ не превосходит ${\displaystyle 2^{50}}$. Его сложность оценивается как ${\displaystyle L_{p}(1/2,c)}$.
• Квадратичное решето, вероятно, наиболее быстрый способ разложения чисел, лежащих между ${\displaystyle 10^{80}}$ и ${\displaystyle 10^{100}}$. Его сложность — ${\displaystyle L_{p}(1/2,1)}$.
• Квадратичное решето в числовом поле. В настоящее время это наиболее успешный метод для чисел, насчитывающих 100 и более десятичных знаков. С его помощью можно разлагать на множители числа до ${\displaystyle 10^{155}}$, а его сложность оценивается как ${\displaystyle L_{N}(1/3,\;(64/9)^{\frac {1}{3}})}$^[5].

Функция может быть обобщена на диапазон полупростых чисел. Заметим, что ${\displaystyle f}$ не сможет быть односторонней для произвольных ${\displaystyle p,q>1}$, так как их произведение с вероятностью ¾ имеет множитель 2.

Заметим, что факторизация с полиномиальной сложностью возможна на квантовом компьютере с помощью алгоритма Шора (класс BQP).

Функция ${\displaystyle f}$ принимает два целых числа: ${\displaystyle x}$ и ${\displaystyle N}$, где ${\displaystyle N}$ — произведение двух простых ${\displaystyle p}$ и ${\displaystyle q}$. На выходе — остаток от деления ${\displaystyle x^{2}}$ на ${\displaystyle N}$. Нахождение обратной функции требует вычисления квадратного корня по модулю ${\displaystyle N}$, то есть нахождения ${\displaystyle x}$ если известно ${\displaystyle y}$ и то, что ${\displaystyle x^{2}{\bmod {N}}=y}$. Можно показать, что последняя задача вычислительно так же сложна, как и разложение ${\displaystyle N}$ на множители.

Криптосистема Рабина основывается на предположении, что функция Рабина является односторонней.

Функция дискретного экспоненцирования ${\displaystyle f}$ принимает в качестве аргументов простое число ${\displaystyle p}$ и целое ${\displaystyle x}$ в интервале от ${\displaystyle 0}$ до ${\displaystyle p-1}$ и возвращает остаток от деления некоторого ${\displaystyle A^{x}}$ на ${\displaystyle p}$. Эта функция может быть легко вычислена за время ${\displaystyle O}$${\displaystyle (n^{3})}$, где ${\displaystyle n}$ — количество битов в ${\displaystyle p}$. Обращение этой функции требует вычисления дискретного логарифма по модулю ${\displaystyle p}$. Пусть ${\displaystyle (G,*)}$ — конечная абелева группа, например мультипликативная группа конечного поля или эллиптическая кривая над конечным полем. Задача вычисления дискретных логарифмов состоит в определении целого числа ${\displaystyle x}$, которое при данных ${\displaystyle A,B}$ удовлетворяет соотношению

${\displaystyle A^{x}=B.}$

Для некоторых групп ${\displaystyle G}$ такая задача довольно проста. Например, если ${\displaystyle G}$ — группа целых чисел по модулю ${\displaystyle N}$ по сложению. Для других групп, однако, эта задача более сложная. Например, в мультипликативной группе конечного поля, наилучший из известных алгоритмов, решающий задачу дискретного логарифмирования, — это метод квадратичного решета в числовом поле. Сложность вычисления дискретных логарифмов в этом случае оценивается как ${\displaystyle L_{N}(1/3,c)}$. Схема Эль-Гамаля основывается на этой задаче^[6].

Для групп, подобных эллиптической кривой, задача дискретного логарифмирования ещё более трудна. Наилучший из доступных на сегодняшний день методов, вычисляющих дискретные логарифмы над общей эллиптической кривой над полем ${\displaystyle \mathbb {F} _{q}}$, называется ρ-метод Полларда. Его сложность ${\displaystyle O(L_{N}(1,1/2))}$. Это экспоненциальный алгоритм, поэтому криптосистемы, основанные на эллиптической кривой, как правило, работают с малым ключом, около 160 бит. В то время как системы, отталкивающиеся от разложения на множители или вычисления дискретных логарифмов в конечных полях, используют ключи в 1024 бита^[6].

С задачей дискретного логарифмирования так же связано несколько близких задач. Пусть дана конечная абелева группа ${\displaystyle (G,*)}$:

• Задача Диффи-Хеллмана, которая состоит в следующем: даны элементы ${\displaystyle A\in G,B=A^{x},C=A^{y}}$. Требуется вычислить ${\displaystyle D=A^{xy}}$.
• Задача выбора Диффи-Хеллмана. Дано: ${\displaystyle A\in G,B=A^{x},C=A^{y},D=A^{z}}$. Требуется определить, является ли ${\displaystyle z}$ произведением ${\displaystyle x}$ и ${\displaystyle y}$.

Можно показать, что задача выбора Диффи-Хеллмана не сложнее задачи Диффи-Хеллмана, а задача Диффи-Хеллмана не сложнее задачи вычисления дискретных логарифмов^[6].

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

Другие претенденты в односторонние функции основываются на сложности декодирования случайных линейных кодов и иных задачах.

• Криптографическая хеш-функция
• Односторонняя функция с потайным входом

• Oded Goldreich. Volume 1, Basic Tools // Foundations of Cryptography. — Cambridge University Press, 2001. — ISBN 0-521-79172-3.
• Jonathan Katz, Yehuda Lindell. Introduction to Modern Cryptography. — CRC Press, 2007. — ISBN 1-58488-551-3.
• Michael Sipser^[англ.]. Section 10.6.3: One-way functions // Introduction to the Theory of Computation (англ.). — PWS Publishing, 1997. — P. 374—376. — ISBN 0-534-94728-X.
• Christos Papadimitriou. Section 12.1: One-way functions // Computational Complexity. — 1st edition. — Addison Wesley, 1993. — С. 279—298. — ISBN 0-201-53082-1.
• Глава 2.3. Односторонние функции // Введение в криптографию / Под ред. В. В. Ященко.
• Глава 2.5.2 Односторонняя функция // Приложение теории детерминированного хаоса в криптографии / Птицын Н. — 2002. (недоступная ссылка)
• Глава 7.2 Односторонние функции // Криптография / Смарт Н. — 2005. — ISBN 5-94836-043-1.
• Глава 4.1 Односторонние функции (рус.). Дата обращения: 9 октября 2014. Архивировано 3 декабря 2016 года.