Введение
Функция, используемая в компьютерной криптографии
В информатике односторонняя функция — это функция, которую легко вычислить для любого входного значения, но сложно обратить, зная образ случайного входного значения. Здесь термины "легко" и "сложно" следует понимать в контексте теории вычислительной сложности, в частности теории задач, разрешимых за полиномиальное время. Неинъективности функции недостаточно для того, чтобы считать её односторонней (см. теоретическое определение ниже). Существование таких односторонних функций до сих пор остаётся открытой гипотезой. Доказательство их существования означало бы, что классы сложности P и NP не равны, тем самым решив важнейший нерешённый вопрос теоретической информатики. Обратное не доказано, то есть наличие доказательства того, что P ≠ NP, не подразумевает автоматически существование односторонних функций. В практических приложениях термины "легко" и "сложно" обычно интерпретируются относительно конкретного вычислительного устройства: как правило, "достаточно дёшево для легитимных пользователей" и "недопустимо дорого для злоумышленников". Односторонние функции, в этом смысле, являются фундаментальными инструментами для криптографии, идентификации личности, аутентификации и других приложений, связанных с обеспечением безопасности данных. Хотя существование односторонних функций в этом смысле также остаётся открытой гипотезой, существует несколько кандидатов, выдержавших десятилетия интенсивных исследований. Некоторые из них являются ключевыми компонентами большинства телекоммуникационных, электронных коммерческих и банковских систем по всему миру.
Теоретическое определение
Функция f : {0, 1}* → {0, 1}* называется односторонней, если f может быть вычислена алгоритмом за полиномиальное время, но любой полиномиальный рандомизированный алгоритм, пытающийся вычислить псевдообратную для f, преуспевает с пренебрежимо малой вероятностью. (Символ * означает любое количество повторений, см. звезду Клине.) То есть, для всех рандомизированных алгоритмов , всех положительных целых чисел c и всех достаточно больших n = длина(x),
где вероятность берется по выбору x из дискретного равномерного распределения на {0, 1}ⁿ, и по случайности . Следует отметить, что по этому определению функция должна быть "сложно инвертируема" в среднем случае, а не в худшем. Это отличается от большей части теории сложности (например, NP-трудности), где термин "трудный" подразумевает худший случай. Поэтому даже если некоторые кандидаты на односторонние функции (описанные ниже) известны как NP-полные, это не означает их односторонность. Последнее свойство основано исключительно на отсутствии известных алгоритмов для решения задачи. Недостаточно сделать функцию "необратимой" (не взаимно однозначной), чтобы она была односторонней. В частности, функция, которая на любом входе длины n выдает строку из n нулей, не является односторонней, поскольку легко найти вход, который приведет к тому же выходу. Более точно: для такой функции, которая просто выдает строку нулей, алгоритм F, который на вход f(x) просто выдает любую строку длины n, "найдет" корректный прообраз выхода, даже если это не тот вход, который изначально использовался для получения выходной строки.
Note that, by this definition, the function must be "hard to invert" in the average case, rather than worst case sense. This is different from much of complexity theory (e. g., NP hardness), where the term "hard" is meant in the worst case. That is why even if some candidates for one way functions (described below) are known to be NP complete, it does not imply their one wayness. The latter property is only based on the lack of known algorithms to solve the problem. It is not sufficient to make a function "lossy" (not one to one) to have a one way function. In particular, the function that outputs the string of n zeros on any input of length n is not a one way function because it is easy to come up with an input that will result in the same output. More precisely: For such a function that simply outputs a string of zeroes, an algorithm F that just outputs any string of length n on input f(x) will "find" a proper preimage of the output, even if it is not the input which was originally used to find the output string.
Связанные понятия
Односторонняя пермутация — это односторонняя функция, которая также является перестановкой, то есть биективной односторонней функцией. Односторонние пермутации являются важным криптографическим примитивом, и неизвестно, следует ли из существования односторонних функций существование односторонних перестановок. Односторонняя функция с секретным ключом, или пермутация с секретным ключом, — это особый вид односторонней функции. Инвертировать такую функцию сложно, если неизвестна некоторая секретная информация, называемая секретным ключом (ловушкой). Хеш-функция без коллизий — это односторонняя функция, которая также устойчива к коллизиям, то есть не существует рандомизированного алгоритма за полиномиальное время, способного найти коллизию — различные значения x и y, такие что f(x) = f(y) — с ненулевой вероятностью.
Кандидаты на односторонние функции
Ниже приведены несколько кандидатов в односторонние функции (на апрель 2009 года). Очевидно, что неизвестно, являются ли эти функции действительно односторонними; однако, обширные исследования до сих пор не позволили найти эффективный алгоритм для их инвертирования ни для одной из них.
these functions are indeed one way; but extensive research has so far failed to produce an efficient inverting algorithm for any of them.
Умножение и вычисление на множители
Функция f принимает на вход два простых числа p и q в двоичном формате и возвращает их произведение. Эту функцию можно "легко" вычислить за время O(b²), где b — общее количество бит входных данных. Обращение этой функции требует разложения данного целого числа N на множители. Лучшие известные алгоритмы факторизации работают за время, где b — количество бит, необходимых для представления N.
Эту функцию можно обобщить, позволив p и q принимать значения из подходящего множества полупростых чисел. Следует отметить, что f не является односторонней функцией для случайно выбранных целых чисел p, q > 1, поскольку произведение будет делиться на 2 с вероятностью 3/4 (потому что вероятность того, что произвольное p нечетно, равна 1/2, и то же самое для q, поэтому, если они выбираются независимо, вероятность того, что оба нечетны, равна 1/4; следовательно, вероятность того, что p или q четно, равна 1 − 1/4 = 3/4).
Функция Рабина (модульное квадратирование)
Функция Рабина, другими словами, если любая функция является односторонней, то и f также является односторонней. Поскольку эта функция была первой продемонстрированной комбинаторной полной односторонней функцией, она известна как "универсальная односторонняя функция". Таким образом, проблема поиска односторонней функции сводится к доказательству существования хотя бы одной такой функции, возможно, неконструктивным способом.