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

Нерешенная задача в информатике :

Существуют ли односторонние функции?

(еще нерешенные проблемы по информатике)

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

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

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

Теоретическое определение

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

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

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

Обратите внимание, что согласно этому определению функцию должно быть «трудно инвертировать» в среднем, а не в худшем случае . Это отличается от большей части теории сложности (например, 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. Для Лучшие известные алгоритмы факторинга работают в $O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)$ время, где b — количество битов, необходимых для N. представления

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

Функция Рабина (модульное возведение в квадрат)

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

\operatorname {Rabin} _{N}(x)\triangleq x^{2}{\bmod {N}}

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

Дискретная экспонента и логарифм

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

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

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

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

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

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

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

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

Другие кандидаты

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

Универсальная односторонняя функция

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

См. также

Ссылки

^ Перейти обратно: ^а ^б Одед Гольдрайх (2001). Основы криптографии: Том 1, Основные инструменты ( проект доступен на сайте автора). Издательство Кембриджского университета. ISBN 0-521-79172-3 . См. также мудрость.weizmann.ac.il .
^ Гольдвассер, С. и Белларе, М. «Конспекты лекций по криптографии» . Летний курс по криптографии, Массачусетский технологический институт, 1996–2001 гг.
^ Многие авторы рассматривают это определение как сильную одностороннюю функцию. Слабая односторонняя функция может быть определена аналогичным образом, за исключением того, что вероятность того, что каждая состязательная функция $F$ не удается инвертировать f, это заметно. Однако можно построить сильные односторонние функции на основе слабых. Грубо говоря, сильная и слабая версии односторонней функции теоретически эквивалентны. См. «Основы криптографии» Гольдрайха, том. 1, гл. 2.1–2.3.
^ Рассел, А. (1995). «Необходимые и достаточные условия бесконфликтного хеширования». Журнал криптологии . 8 (2): 87–99. дои : 10.1007/BF00190757 . S2CID 26046704 .
^ Левин, Леонид А. (январь 2003 г.). «Сказка об односторонних функциях». Проблемы передачи информации (39): 92–103. arXiv : cs.CR/0012023 . дои : 10.1023/A:1023634616182 .

Дальнейшее чтение

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

[Goldreich-1] Перейти обратно: ^а ^б Одед Гольдрайх (2001). Основы криптографии: Том 1, Основные инструменты ( проект доступен на сайте автора). Издательство Кембриджского университета. ISBN 0-521-79172-3 . См. также мудрость.weizmann.ac.il .

[2] Гольдвассер, С. и Белларе, М. «Конспекты лекций по криптографии» . Летний курс по криптографии, Массачусетский технологический институт, 1996–2001 гг.

[3] Многие авторы рассматривают это определение как сильную одностороннюю функцию. Слабая односторонняя функция может быть определена аналогичным образом, за исключением того, что вероятность того, что каждая состязательная функция $F$ не удается инвертировать f, это заметно. Однако можно построить сильные односторонние функции на основе слабых. Грубо говоря, сильная и слабая версии односторонней функции теоретически эквивалентны. См. «Основы криптографии» Гольдрайха, том. 1, гл. 2.1–2.3.

[4] Рассел, А. (1995). «Необходимые и достаточные условия бесконфликтного хеширования». Журнал криптологии . 8 (2): 87–99. дои : 10.1007/BF00190757 . S2CID 26046704 .

[HCPred-5] Левин, Леонид А. (январь 2003 г.). «Сказка об односторонних функциях». Проблемы передачи информации (39): 92–103. arXiv : cs.CR/0012023 . дои : 10.1023/A:1023634616182 .

[1]

[2]

[3]

[4]

[5]