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

В информатике односторонняя функция — это функция , которую легко вычислить на каждом входе, но трудно инвертировать , имея изображение случайного входа. Здесь «легко» и «сложно» следует понимать в смысле теории вычислительной сложности , в частности теории задач полиномиального времени . Это не имеет ничего общего с тем, является ли функция однозначной ; нахождение любого одного входа с желаемым изображением считается успешной инверсией. (См. § Теоретическое определение ниже.)

Существование таких односторонних функций все еще остается открытой гипотезой . Их существование доказало бы, что классы сложности P и NP не равны , тем самым разрешив самый главный нерешенный вопрос теоретической информатики. ^{[1] : ex. 2.2, page 70} Обратное утверждение, как известно, не является верным, то есть существование доказательства того, что P ≠ NP, не будет напрямую подразумевать существование односторонних функций. ^[2]

В прикладном контексте термины «легкий» и «сложный» обычно интерпретируются относительно некоторой конкретной вычислительной сущности; как правило, «достаточно дешевый для законных пользователей» и «непомерно дорогой для любых вредоносных агентов ». ^{[ требуется цитата ]} Односторонние функции в этом смысле являются основополагающими инструментами для криптографии , персональной идентификации , аутентификации и других приложений безопасности данных . Хотя существование односторонних функций в этом смысле также является открытой гипотезой, есть несколько кандидатов, которые выдержали десятилетия интенсивного изучения. Некоторые из них являются неотъемлемыми компонентами большинства систем телекоммуникаций , электронной коммерции и электронного банкинга по всему миру.

Функция f  : {0, 1} ^* → {0, 1} ^* является односторонней, если f может быть вычислена с помощью полиномиального алгоритма, но любой полиномиальный рандомизированный алгоритм , который пытается вычислить псевдообратную функцию для f, преуспевает с пренебрежимо малой вероятностью. (Верхний индекс * означает любое количество повторений, см. звезду Клини .) То есть для всех рандомизированных алгоритмов , всех положительных целых чисел c и всех достаточно больших n = length( x ),${\displaystyle F}$${\displaystyle F}$

${\displaystyle \Pr[f(F(f(x)))=f(x)]<n^{-c},}$

где вероятность зависит от выбора x из дискретного равномерного распределения на {0, 1}  ⁿ , а случайность . ^[3]${\displaystyle F}$

Обратите внимание, что по этому определению функция должна быть «трудно инвертируемой» в среднем случае, а не в худшем . Это отличается от большей части теории сложности (например, NP-трудности ), где термин «трудно» подразумевается в худшем случае. Вот почему, даже если некоторые кандидаты на односторонние функции (описанные ниже) известны как NP-полные , это не подразумевает их односторонность. Последнее свойство основано только на отсутствии известных алгоритмов для решения задачи.

Недостаточно сделать функцию «потеряющей» (не взаимно однозначной), чтобы иметь одностороннюю функцию. В частности, функция, которая выводит строку из n нулей на любом входе длины n, не является односторонней функцией, потому что легко придумать вход, который даст тот же самый выход. Точнее: для такой функции, которая просто выводит строку нулей, алгоритм F , который просто выводит любую строку длины n на входе f ( x ), «найдет» правильный прообраз выхода, даже если это не тот вход, который изначально использовался для поиска выходной строки.

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

Односторонняя функция с люком или перестановка с люком — это особый вид односторонней функции. Такую функцию трудно инвертировать, если неизвестна некоторая секретная информация, называемая люком .

Функция хеширования без коллизий f является односторонней функцией, которая также устойчива к коллизиям ; то есть никакой рандомизированный алгоритм полиномиального времени не может найти коллизию — различные значения x , y, такие, что f ( x ) = f ( y ) — с существенной вероятностью. ^[4]

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

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

• Генераторы псевдослучайных чисел
• Семейства псевдослучайных функций
• Схемы битовых обязательств
• Схемы шифрования с закрытым ключом, защищающие от атак с адаптивным выбранным шифротекстом
• Коды аутентификации сообщений
• Схемы цифровой подписи (защищены от атак с адаптивным выбором сообщений)

Ниже приведены несколько кандидатов на односторонние функции (по состоянию на апрель 2009 г.). Очевидно, неизвестно, являются ли эти функции действительно односторонними; но обширные исследования до сих пор не смогли создать эффективный алгоритм инвертирования для любой из них. ^{[ необходима цитата ]}

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

Эту функцию можно обобщить, позволив p и q варьироваться в подходящем наборе полупростых чисел . Обратите внимание, что f не является односторонней для случайно выбранных целых чисел p , q > 1 , поскольку произведение будет иметь 2 в качестве множителя с вероятностью 3/4 (потому что вероятность того, что произвольное p нечетно, равна 1/2, и то же самое касается q , поэтому если они выбраны независимо, вероятность того, что оба нечетны, равна 1/4; следовательно, вероятность того, что p или q четны, равна 1 − 1/4 = 3/4 ).

Функция Рабина , ^{[1] : 57} или возведение в квадрат по модулю , где p и q — простые числа, считается набором односторонних функций. Запишем${\displaystyle N=pq}$

${\displaystyle \operatorname {Рабин} _{N}(x)\triangleq x^{2}{\bmod {N}}}$

для обозначения возведения в квадрат по модулю N : конкретный член набора Рабина . Можно показать, что извлечение квадратных корней, т. е. обращение функции Рабина, вычислительно эквивалентно факторизации N (в смысле полиномиальной редукции ). Следовательно, можно доказать, что набор Рабина является односторонним тогда и только тогда, когда факторизация является сложной. Это также справедливо для особого случая, в котором p и q имеют одинаковую длину в битах. Криптосистема Рабина основана на предположении, что эта функция Рабина является односторонней.

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

Пусть G — конечная абелева группа мощности n . Обозначим ее групповую операцию умножением. Рассмотрим примитивный элемент α ∈ G и другой элемент β ∈ G. Задача дискретного логарифмирования состоит в том, чтобы найти положительное целое число k , где 1 ≤ k ≤ n , такое, что:

${\displaystyle \alpha ^{k}=\underbrace {\alpha \cdot \alpha \cdot \ldots \cdot \alpha } _{k\;\mathrm {times} }=\beta }$

Целое число k , которое решает уравнение α ^k = β, называется дискретным логарифмом β по основанию α . Записывается k = log _α β .

Популярным выбором для группы G в дискретной логарифмической криптографии являются циклические группы ( Z _p ) ^× (например, шифрование Эль-Гамаля , обмен ключами Диффи–Хеллмана и алгоритм цифровой подписи ) и циклические подгруппы эллиптических кривых над конечными полями ( см. криптография на эллиптических кривых ).

Эллиптическая кривая — это набор пар элементов поля, удовлетворяющих y 2 ⁼ x 3 ⁺ ax + b . Элементы кривой образуют группу при операции, называемой «сложение точек» (которая не совпадает с операцией сложения поля). Умножение kP точки P на целое число k ( т. е . групповое действие аддитивной группы целых чисел) определяется как повторное сложение точки с собой. Если известны k и P , легко вычислить R = kP , но если известны только R и P , предполагается, что трудно вычислить k .

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

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

Существует явная функция f, которая, как было доказано, является односторонней, тогда и только тогда, когда существуют односторонние функции. ^[5] Другими словами, если какая-либо функция является односторонней, то f также является односторонней . Поскольку эта функция была первой комбинаторно полной односторонней функцией, которая была продемонстрирована, она известна как «универсальная односторонняя функция». Таким образом, задача нахождения односторонней функции сводится к доказательству — возможно, неконструктивному — того, что одна такая функция существует.

Также существует функция, которая является односторонней, если полиномиально ограниченная сложность Колмогорова в среднем умеренно сложна. Поскольку существование односторонних функций подразумевает, что полиномиально ограниченная сложность Колмогорова в среднем умеренно сложна, функция является универсальной односторонней функцией. ^[6]

• Функция одностороннего сжатия
• Криптографическая хэш-функция
• Геометрическая криптография
• Функция люка

• Джонатан Кац и Йехуда Линделл (2007). Введение в современную криптографию . CRC Press. ISBN 1-58488-551-3 . 
• Майкл Сипсер (1997). Введение в теорию вычислений . PWS Publishing. ISBN 978-0-534-94728-6.Раздел 10.6.3: Односторонние функции, стр. 374–376.
• Христос Пападимитриу (1993). Computational Complexity (1-е изд.). Эддисон Уэсли. ISBN 978-0-201-53082-7.Раздел 12.1: Односторонние функции, стр. 279–298.