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

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

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

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

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

Существование таких односторонних функций до сих пор остается открытой гипотезой . Их существование доказывало бы, что классы сложности 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 тоже . Поскольку эта функция была первой продемонстрированной комбинаторной полной односторонней функцией, она известна как «универсальная односторонняя функция». Таким образом, проблема нахождения односторонней функции сводится к доказательству — возможно, неконструктивному — того, что одна такая функция существует.

См. также [ править ]

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б Одед Гольдрейх (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] Jump up to: Перейти обратно: ^а ^б Одед Гольдрейх (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]

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