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

Нерешённые проблемы computer science: ''Существуют ли односторонние функции ?''

Односторонняя функция (англ. one-way function, OWF) это функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться также трудно обратимыми или необратимыми.

Существование односторонних функций до сих пор не доказано. Их существование докажет, что классы сложности P и NP не равны, попутно разрешив ряд вопросов теоретической информатики. Современная асимметричная криптография основывается на предположении, что односторонние функции все-таки существуют.

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

Определение

Функция f: {0, 1}^* → {0, 1}^* является односторонней функцией, если она эффективно вычисляется за полиномиальное время на детерминированной машине Тьюринга, но не существует полиномиальной вероятностной машины Тьюринга, которая обращает эту функцию с более чем экспоненциально малой вероятностью.

Существование

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

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

• генераторов псевдослучайных чисел;
• Если существует OWF с тяжёлым битом (англ.), то существует Протокол (схема) привязки к биту(англ. bit commitment protocol (schemes));
• PRF-псевдо случайного генератора функций на основе односторонних функций;
• Message authentication code;
• Электронная цифровая подпись.

Односторонние функции в криптографических схемах

Существование односторонних функций является необходимым условием для стойкости многих типов криптографических схем. В некоторых случаях этот факт устанавливается достаточно просто. Рассмотрим функцию f такую, что f(r) = K₁. Она вычислима с помощью алгоритма G за полиномиальное время. Покажем, что если f не односторонняя функция, то криптосистема нестойкая. Предположим, что существует полиномиальный вероятностный алгоритм A, который инвертирует f с вероятностью по крайней мере 1/p(n) для некоторого полинома p. Здесь n — длина ключа $K_1$. Атакующий может подать на вход алгоритму A ключ $K_1$ и получить с указанной вероятностью некоторое значение $r'$ из прообраза. Далее злоумышленник подает $r'$ на вход алгоритма G и получает пару ключей $(K_1, K'_2)$. Хотя $K'_2$ не обязательно совпадает с $K_2$, тем не менее, по определению криптосистемы $D_{K_2'}(E_{K_1}(m)) = m$ для любого открытого текста m. Поскольку $K'_2$ найден с вероятностью по крайней мере 1/p(n), которая в криптографии не считается пренебрежимо малой, криптосистема нестойкая.

Из всего сказанного следует, что предположение о существовании односторонних функций является самым слабым криптографическим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем различных типов. На выяснение того, является ли это условие и в самом деле достаточным, направлены значительные усилия специалистов. Трудность задачи построения криптографических схем из односторонних функций можно пояснить на следующем примере. Пусть f — односторонняя функция и нам требуется построить криптосистему с секретным ключом. В такой криптосистеме имеется только один ключ — секретный, который известен и отправителю, и получателю шифрованного сообщения. Алгоритмы шифрования $E_K$ и дешифрования $D_K$ оба зависят от этого секретного ключа $K$ и таковы, что $D_K(E_K(m)) = m$ для любого открытого текста m. Ясно, что если криптограмму d сообщения m вычислять как $d=f(m)$, то противник, перехвативший d, может вычислить m лишь с пренебрежимо малой вероятностью. Но во-первых, непонятно, каким образом сможет восстановить сообщение m из криптограммы законный получатель? Во-вторых, из того, что функция f односторонняя следует лишь, что противник не может вычислить все сообщение целиком. А это — весьма низкий уровень стойкости. Желательно, чтобы противник, знающий криптограмму d, не мог вычислить ни одного бита открытого текста.

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

Кандидаты в односторонние функции

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

Умножение и факторизация

Функция f принимает на вход два простых числа p и q в двоичном представлении и возвращает их произведение. Эта функция может быть вычислена за время порядка O(n²), где n — общая длина (количество двоичных чисел) входных данных. Построение обратной функции требует нахождения множителей заданного целого числа N. Лучший известный алгоритм разложения на множители выполняется за время $2^{O({(\log N)^{1/3} (\log \log N})^{2/3})}$ и является псевдополиномиальным.

Функция может быть обобщена на диапазон полупростых чисел. Заметим, что f не сможет быть односторонней для произвольных p, q > 1, так как их произведение с вероятностью ¾ имеет множитель 2.

Возведение в квадрат и извлечение квадратного корня по модулю

Функция f принимает два целых числа: x и N, где N — произведение двух простых p и q. На выходе — остаток от деления x² на N. Нахождение обратной функции требует вычисления квадратного корня по модулю N, то есть x если известно y и x² mod N = y. Можно показать, что последняя задача вычислительно так же сложна, как и разложение N на множители.

Криптосистема Рабина основывается на предположении, что функция Рабина является односторонней.

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

Функция дискретного экспоненцирования f принимает в качестве аргументов простое число p и целое x в интервале от 0 до p−1 и возвращает остаток от деления $2^x$ на p. Эта функция может быть легко вычислена за время O(n³), где n — количество битов в p. Обращение этой функции требует вычисления дискретного логарифма по модулю p. То есть, по заданному простому p и целому y между 0 и p−1 требуется найти такое x, что $2^x$ mod p = y. Схема Эль-Гамаля основывается на этой функции.

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

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

Другие претенденты

Другие претенденты в односторонние функции основываются на сложности декодирования случайных линейных кодов и иных задачах.

См. также

• Trapdoor function
• Криптографическая хеш-функция
• Односторонняя функция с потайным входом

Ссылки

• Oded Goldreich Volume 1, Basic Tools // Foundations of Cryptography. — Cambridge University Press, 2001. — ISBN 0-521-79172-3
• Jonathan Katz, Yehuda Lindell Introduction to Modern Cryptography. — CRC Press, 2007. — ISBN 1-58488-551-3
• Michael Sipser Section 10.6.3: One-way functions // Introduction to the Theory of Computation. — PWS Publishing, 1997. — P. 374—376. — ISBN 0-534-94728-X
• Christos Papadimitriou Section 12.1: One-way functions // Computational Complexity. — 1st edition. — Addison Wesley, 1993. — P. 279—298. — ISBN 0-201-53082-1
• Глава 2.3. Односторонние функции // Введение в криптографию / Под ред. В. В. Ященко.