Войти
 | Нерешенная проблема в информатике :. Существуют ли односторонние функции? (больше нерешенных проблем в информатике) |
В информатике односторонняя функция - это функция, которую легко вычислить для каждого ввода, но трудно инвертировать с учетом изображения случайного ввода. Здесь "легкий" и "сложный" следует понимать в смысле теории вычислительной сложности, в частности теории задач с полиномиальным временем. Отсутствие взаимно однозначного не считается достаточным для того, чтобы функция вызывалась односторонней (см. Теоретическое определение ниже).
Существование таких односторонних функций все еще остается открытым гипотезой. Фактически, их существование могло бы доказать, что классы сложности P и NP не равны, тем самым разрешив главный нерешенный вопрос теоретической информатики. Неизвестно обратное, т. Е. Наличие доказательства того, что P ≠ NP не подразумевает прямо существование односторонних функций.
В прикладных контекстах термины «легкий» и «жесткий» обычно интерпретируются относительно некоторого конкретного вычислительного объекта; обычно «достаточно дешево для законных пользователей» и «непомерно дорого для любых вредоносных агентов ». Односторонние функции в этом смысле являются фундаментальными инструментами для криптографии, личной идентификации, аутентификации и других приложений безопасности данных. Хотя существование односторонних функций в этом смысле также является открытым предположением, есть несколько кандидатов, которые выдержали десятилетия тщательного изучения. Некоторые из них являются важными составляющими большинства систем телекоммуникаций, электронной коммерции и электронных банковских операций по всему миру.
Функция f: {0,1} → {0,1} является односторонней, если f может быть вычислена с помощью алгоритма полиномиального времени, но любой алгоритм с полиномиальным временем рандомизированный 
где вероятность превышает выбор x из дискретного равномерного распределения на {0,1}, а случайность
Обратите внимание, что согласно этому определению функция должна быть «трудно инвертируемой» в среднем случае, а не в худшем случае. Это отличается от большей части теории сложности (например, NP-твердость ), где термин «жесткий» означает наихудший случай. Вот почему даже если известно, что некоторые кандидаты в односторонние функции (описанные ниже) являются NP-полными, это не означает их односторонности. Последнее свойство основано только на отсутствии известного алгоритма решения проблемы.
Недостаточно сделать функцию «с потерями» (не взаимно однозначной), чтобы иметь одностороннюю функцию. В частности, функция, которая выводит строку из n нулей на любом входе длины n, не является односторонней функцией, потому что легко придумать ввод, который приведет к тому же выводу. Точнее: для такой функции, которая просто выводит строку нулей, алгоритм F, который просто выводит любую строку длины n на входе f (x), «найдет» правильный прообраз вывода, даже если это не вход который изначально использовался для поиска выходной строки.
A односторонняя перестановка - это односторонняя функция, которая также является перестановкой, то есть односторонняя функция, которая является биективной. Односторонние перестановки - важный криптографический примитив , и неизвестно, подразумевается ли их существование существованием односторонних функций.
A односторонняя функция лазейки или перестановка лазейки - это особый вид односторонней функции. Такую функцию трудно инвертировать, если не известна некоторая секретная информация, называемая лазейкой.
A хэш-функция без коллизий f - односторонняя функция, которая также устойчива к коллизиям; то есть ни один алгоритм рандомизированного полиномиального времени не может найти столкновение - разные значения x, y, такие, что f (x) = f (y) - с немалой вероятностью.
Если f - односторонняя функция, то инверсия f будет проблемой, выходные данные которой трудно вычислить (по определению), но легко проверить ( просто вычислив на нем f). Таким образом, существование односторонней функции означает, что FP ≠FNP, что, в свою очередь, означает, что P ≠ NP. Однако P ≠ NP не означает существования односторонних функций.
Существование односторонней функции подразумевает существование многих других полезных концепций, в том числе:
Существование односторонних функций также подразумевает, что для P ≠ NP не существует естественного доказательства.
Ниже приведены несколько кандидатов на односторонние функции (по состоянию на апрель 2009 г.). Ясно, что неизвестно, действительно ли эти функции односторонние; но обширные исследования пока не привели к созданию эффективного алгоритма инвертирования для любого из них.
Функция f принимает в качестве входных данных два простых числа p и q в двоичной записи и возвращает их продукт. Эта функция может быть «легко» вычислена за O (b) время, где b - общее количество битов входных данных. Для инвертирования этой функции требуется найти множители заданного целого числа N. Лучшие известные алгоритмы факторизации работают в ![{\ displaystyle O \ left (\ exp {\ sqrt [{3}] {{\ frac {64} {9}} b (\ log b) ^ {2}}} \ right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fce9dac980e9d4ef0d5ed82aa0172be61d7b57b2)
Эту функцию можно обобщить, разрешив p и q варьироваться в подходящем наборе полупростых чисел. Обратите внимание, что f не является односторонним для случайно выбранных целых чисел p, q>1, так как продукт будет иметь множитель 2 с вероятностью 3/4 (поскольку вероятность того, что произвольное p нечетное, равна 1/2, и то же самое для q, поэтому, если они выбраны независимо, вероятность того, что оба они нечетны, составляет 1/4; следовательно, вероятность того, что p или q четны, равна 1 - 1/4 = 3/4).
Функция Рабина или возведение в квадрат по модулю 
в обозначают возведение в квадрат по модулю N: конкретный член коллекции Рабина . Можно показать, что извлечение квадратных корней, т.е. инвертирование функции Рабина, в вычислительном отношении эквивалентно факторизации N (в смысле полиномиального сокращения ). Следовательно, можно доказать, что коллекция Рабина односторонняя тогда и только тогда, когда факторинг труден. Это также справедливо для особого случая, когда p и q имеют одинаковую длину в битах. Криптосистема Рабина основана на предположении, что это односторонняя.
Модульное возведение в степень может быть выполнено за полиномиальное время. Для инвертирования этой функции необходимо вычислить дискретный логарифм . В настоящее время существует несколько популярных групп, для которых не известен алгоритм вычисления базового дискретного логарифма за полиномиальное время. Все эти группы являются конечными абелевыми группами, и общая проблема дискретного логарифмирования может быть описана следующим образом.
Пусть G - конечная абелева группа мощности n. Обозначим его групповую операцию умножением. Рассмотрим примитивный элемент α ∈ G и другой элемент β ∈ G. Задача дискретного логарифмирования состоит в том, чтобы найти натуральное число k, где 1 ≤ k ≤ n, такое, что:
Целое число k, которое решает уравнение α = β, называется дискретным логарифмом числа β по основанию α. Пишут k = log α β.
Популярным выбором для группы G в дискретном логарифме криптографии являются циклические группы (Zp) (например, шифрование Эль-Гамаля, обмен ключами Диффи – Хеллмана, и алгоритм цифровой подписи ) и циклические подгруппы эллиптических кривых над конечными полями (см. криптография эллиптических кривых ).
Эллиптическая кривая - это набор пар элементов поля, удовлетворяющих y = x + ax + b. Элементы кривой образуют группу при операции, называемой «сложение точек» (что не то же самое, что операция сложения поля). Умножение kP точки P на целое число k (т. Е. групповое действие аддитивной группы целых чисел) определяется как повторное добавление точки к самой себе. Если k и P известны, легко вычислить R = kP, но если известны только R и P, предполагается, что вычислить k сложно.
Существует ряд криптографических хэш-функций, которые быстро вычисляются, например, SHA 256. Некоторые из более простых версий стали предметом сложного анализа, но самые надежные версии продолжают предлагать быстрые и практичные решения для односторонних вычислений. Большая часть теоретической поддержки функций - это больше техник для предотвращения некоторых из ранее успешных атак.
Другие кандидаты для односторонних функций были основаны на жесткости декодирования случайных линейных кодов, проблемы суммы подмножеств (Ранцевая криптосистема Наккэша-Стерна ) или другие проблемы.
Существует явная функция f, которая, как было доказано, является односторонней, тогда и только тогда, когда существуют односторонние функции. Другими словами, если какая-либо функция односторонняя, то и f тоже. Поскольку эта функция была первой продемонстрированной комбинаторной полной односторонней функцией, она известна как «универсальная односторонняя функция». Таким образом, проблема поиска односторонней функции сводится к доказательству существования одной такой функции.
