WikiDer > Предположение о вычислительной сложности

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

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

Допущения о вычислительной сложности также полезны для руководства разработчиками алгоритмов: простой алгоритм вряд ли опровергнет хорошо изученное предположение о вычислительной сложности, такое как P ≠ NP.

Сравнение предположений твердости

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

Сила предположений о твердости

Мы говорим это предположение ${displaystyle A}$ является сильнее чем предположение ${displaystyle B}$ когда ${displaystyle A}$ подразумевает ${displaystyle B}$ (и обратное неверно или неизвестно). Другими словами, даже если предположение ${displaystyle A}$ были ложными, предположение ${displaystyle B}$ все еще может быть правдой, и криптографические протоколы, основанные на предположении ${displaystyle B}$ может быть безопасным в использовании. Таким образом, при разработке криптографических протоколов можно надеяться, что удастся доказать безопасность с помощью самый слабый возможные предположения.

Предположения среднего и наихудшего случая

An средний случай предположение говорит, что конкретная проблема сложна в большинстве случаев из некоторого явного распределения, тогда как худший случай предположение говорит только о том, что проблема стоит немного экземпляры. Для данной задачи средняя твердость подразумевает наихудшую твердость, поэтому предположение о средней твердости сильнее, чем предположение о жесткости наихудшего случая для той же проблемы. Более того, даже для несравненных проблем такое допущение, как Гипотеза экспоненциального времени часто считается предпочтительнее среднее предположение словно насаждаемая клика гипотеза.^[1]Обратите внимание, однако, что в большинстве криптографических приложений знание того, что проблема имеет какой-то жесткий экземпляр (т.е. проблема сложна в худшем случае), бесполезно, потому что оно не дает нам способа создания жестких экземпляров.^[2] К счастью, многие предположения о среднем случае, используемые в криптографии (включая ЮАР, дискретный журнал, и немного проблемы решетки) могут быть основаны на предположениях наихудшего случая посредством редукции от наихудшего случая к среднему.^[3]

Фальсифицируемость

Желаемой характеристикой предположения о вычислительной сложности является фальсифицируемость, т.е. что если бы предположение было ложным, то его можно было бы доказать. Наор (2003) ввел формальное понятие криптографической фальсифицируемости.^[4]Грубо говоря, предположение о вычислительной сложности считается опровергнутым, если оно может быть сформулировано в терминах задачи: интерактивного протокола между противником и эффективным проверяющим, где эффективный противник может убедить проверяющего принять его тогда и только тогда, когда предположение является правильным. ложный.

Общие предположения о криптографической стойкости

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

Целочисленная факторизация

Учитывая составное число ${displaystyle n}$, и, в частности, один, который является произведением двух больших простых чисел ${displaystyle n = pcdot q}$, задача целочисленной факторизации состоит в том, чтобы найти ${displaystyle p}$ и ${displaystyle q}$ (в общем, найти простые числа ${displaystyle p_ {1}, точки, p_ {k}}$ такой, что ${displaystyle n = prod _ {i} p_ {i}}$Основная открытая проблема состоит в том, чтобы найти алгоритм для целочисленной факторизации, который работает за время, полиномиальное от размера представления (${displaystyle log (n)}$Безопасность многих криптографических протоколов основывается на предположении, что целочисленная факторизация сложна (т.е. не может быть решена за полиномиальное время). Криптосистемы, безопасность которых эквивалентна этому предположению, включают Криптосистема Рабина и Криптосистема Окамото – Учияма.Гораздо больше криптосистем полагаются на более сильные предположения, такие как ЮАР, Проблемы остаточности, и Фи-сокрытие.

Проблема RSA

Учитывая составное число ${displaystyle n}$, экспонента ${displaystyle e}$ и номер ${displaystyle c: = m ^ {e} (mathrm {mod}; n)}$, проблема RSA - найти ${displaystyle m}$Предполагается, что задача трудная, но становится легче, если учесть факторизацию ${displaystyle n}$. в Криптосистема RSA, ${displaystyle (n, e)}$ это открытый ключ, ${displaystyle c}$ это шифрование сообщения ${displaystyle m}$, а факторизация ${displaystyle n}$ - секретный ключ, используемый для дешифрования.

Проблемы остаточности

Учитывая составное число ${displaystyle n}$ и целые числа ${displaystyle y, d}$, проблема остаточности состоит в том, чтобы определить, существует ли (или найти) ${displaystyle x}$ такой, что

${displaystyle x ^ {d} Equiv y {pmod {n}}.}$

Важные особые случаи включают Проблема квадратичной остаточности и Решающая сложная проблема остаточностиКак и в случае с RSA, эта проблема (и ее частные случаи) предполагается трудной, но становится легкой с учетом факторизации ${displaystyle n}$.Некоторые криптосистемы, которые полагаются на твердость проблем остаточности, включают:

• Криптосистема Голдвассера – Микали (квадратичная проблема редискриминации)
• Генератор Blum Blum Shub (квадратичная проблема редискриминации)
• Криптосистема Пайе (решающая сложная проблема остаточности)
• Криптосистема Бенало (проблема более высокой остаточности)
• Криптосистема Наккаша – Стерна (проблема более высокой остаточности)

Предположение о сокрытии фи

Для составного числа ${displaystyle m}$, не известно, как эффективно вычислить его Функция Эйлера ${displaystyle phi (m)}$. Предположение о сокрытии фи постулирует, что трудно вычислить ${displaystyle phi (m)}$, и, более того, даже вычисляя любые простые множители ${displaystyle phi (m)}$ это трудно. Это предположение используется в модели Качена – Микали – Штадлера. PIR протокол.^[5]

Проблема дискретного журнала (DLP)

Данные элементы ${displaystyle a}$ и ${displaystyle b}$ из группа ${displaystyle G}$, задача дискретного журнала требует целого числа ${displaystyle k}$ такой, что ${displaystyle a = b ^ {k}}$Проблема дискретного журнала не может быть сопоставима с целочисленной факторизацией, но их вычислительные сложности тесно связанный.

Большинство криптографических протоколов, связанных с проблемой дискретного журнала, на самом деле полагаются на более сильные Предположение Диффи – Хеллмана: данные элементы группы ${displaystyle g, g ^ {a}, g ^ {b}}$, куда ${displaystyle g}$ генератор и ${displaystyle a, b}$ случайные целые числа, трудно найти ${displaystyle g ^ {acdot b}}$. Примеры протоколов, использующих это предположение, включают исходный Обмен ключами Диффи-Хеллмана, так же хорошо как Шифрование Эль-Гамаля (который опирается на еще более сильную Решающий Диффи – Хеллмана (DDH) вариант).

Многолинейные карты

А многолинейная карта это функция ${displaystyle e: G_ {1}, точки, G_ {n} ightarrow G_ {T}}$ (куда ${displaystyle G_ {1}, точки, G_ {n}, G_ {T}}$ находятся группы) такой, что для любого ${displaystyle g_ {1}, точки, g_ {n} в G_ {1}, точки G_ {n}}$ и ${displaystyle a_ {1}, точки, a_ {n}}$,

${displaystyle e (g_ {1} ^ {a_ {1}}, точки, g_ {n} ^ {a_ {n}}) = e (g_ {1}, точки, g_ {n}) ^ {a_ {1 } cdots a_ {n}}}$.

Для криптографических приложений хотелось бы построить группы ${displaystyle G_ {1}, точки, G_ {n}, G_ {T}}$ и карта ${displaystyle e}$ такие, что отображение и групповые операции на ${displaystyle G_ {1}, точки, G_ {n}, G_ {T}}$ могут быть вычислены эффективно, но проблема дискретного журнала на ${displaystyle G_ {1}, точки, G_ {n}}$ по-прежнему сложно.^[6]Некоторые приложения требуют более сильных предположений, например полилинейные аналоги предположений Диффи-Хеллмана.

Для особого случая ${displaystyle n = 2}$, билинейные карты с надежной безопасностью были построены с использованием Спаривание Вейля и Тейт-спаривание.^[7]За ${displaystyle n> 2}$ в последние годы было предложено много конструкций, но многие из них также были сломаны, и в настоящее время нет единого мнения о безопасном кандидате.^[8]

Некоторые криптосистемы, основанные на предположениях о многолинейной жесткости, включают:

• Схема Боне-Франклина (блинеарное письмо Диффи-Хеллмана)
• Бонех – Линн – Шахам (блинеарное письмо Диффи-Хеллмана)
• Гарг-Джентри-Галеви-Райкова-Сахай-Уотерс кандидат в неразличимость обфускации и функциональное шифрование (многолинейные пазлы)^[9]

Проблемы с решеткой

Наиболее фундаментальной вычислительной проблемой на решетках является Кратчайшая векторная задача (SVP): заданная решетка ${displaystyle L}$, найти кратчайший ненулевой вектор ${displaystyle vin L}$.Большинство криптосистем требуют более строгих предположений о вариантах SVP, таких как Задача кратчайших независимых векторов (SIVP), GapSVP,^[10] или Unique-SVP.^[11]

Наиболее полезное предположение о твердости решетки в криптографии для Обучение с ошибками (LWE) проблема: переданы образцы в ${displaystyle (x, y)}$, куда ${displaystyle y = f (x)}$ для некоторой линейной функции ${displaystyle f (cdot)}$, легко научиться ${displaystyle f (cdot)}$ с помощью линейной алгебры. В задаче LWE на входе алгоритма есть ошибки, т.е. для каждой пары ${displaystyle yeq f (x)}$ с некоторой малой вероятностью. Считается, что ошибки делают проблему неразрешимой (для соответствующих параметров); в частности, известны сокращения от худшего до среднего по сравнению с вариантами SVP.^[12]

Для квантовых компьютеров задачи разложения на множители и дискретного логарифма являются простыми, но проблемы с решеткой считаются сложными.^[13]Это заставляет некоторых криптосистемы на основе решеток кандидаты на постквантовая криптография.

Некоторые криптосистемы, которые полагаются на твердость проблем решетки, включают:

• НТРУ (обе NTRUEncrypt и NTRUSign)
• Большинство кандидатов на полностью гомоморфное шифрование

Допущения некриптографической стойкости

Помимо их криптографических приложений, предположения о твердости используются в теория сложности вычислений предоставить доказательства математических утверждений, которые трудно доказать безоговорочно. В этих приложениях вместо того, чтобы доказывать, что само утверждение истинно, доказывается, что предположение о сложности подразумевает некое желаемое утверждение из теории сложности. Наиболее известным предположением этого типа является предположение, что P ≠ NP,^[14] но другие включают гипотеза экспоненциального времени,^[15] в насаждаемая клика гипотеза, а догадка уникальных игр.^[16]

${displaystyle C}$-сложные проблемы

Много худший случай вычислительные проблемы известны как сложные или даже полный для некоторых класс сложности ${displaystyle C}$, особенно NP-жесткий (но часто также PSPACE-жесткий, PPAD-жесткий, так далее.). Это означает, что они по крайней мере так же сложны, как и любая проблема в классе. ${displaystyle C}$. Если проблема ${displaystyle C}$-жесткий (относительно полиномиального сокращения времени), то он не может быть решен с помощью алгоритма с полиномиальным временем, если только предположение вычислительной сложности ${displaystyle Peq C}$ ложно.

Гипотеза экспоненциального времени (ETH) и варианты

Гипотеза экспоненциального времени (ETH) - это укрепление из ${displaystyle Peq NP}$ предположение о твердости, которое предполагает, что не только Проблема логической выполнимости не имеют алгоритма полиномиального времени, кроме того, он требует экспоненциального времени (${displaystyle 2 ^ {Omega (n)}}$).^[17] Еще более сильное предположение, известное как Сильная экспоненциальная гипотеза времени (SETH) предполагает, что ${displaystyle k}$-СИДЕЛ требует ${displaystyle 2 ^ {(1-varepsilon _ {k}) n}}$ время, где ${displaystyle lim _ {kightarrow infty} varepsilon _ {k} = 0}$. ETH, SETH и связанные с ними допущения о вычислительной надежности позволяют выводить мелкозернистые результаты сложности, например результаты, которые различают полиномиальное время и квазиполиномиальное время,^[1] или даже ${displaystyle n ^ {1.99}}$ против ${displaystyle n ^ {2}}$.^[18]Такие предположения также полезны в параметризованная сложность.^[19]

Допущения о средней твердости

Предполагается, что некоторые вычислительные проблемы в среднем являются сложными для определенного распределения экземпляров. посаженная клика проблема, вход - это случайный граф, выбранный путем выборки Случайный граф Эрдеша – Реньи а затем "сажает" случайный ${displaystyle k}$-clique, т.е. соединяющий ${displaystyle k}$ равномерно случайные узлы (где ${displaystyle 2log _ {2} nll kll {sqrt {n}}}$), а цель - найти посаженный ${displaystyle k}$-clique (который является уникальным для w.h.p.).^[20]Другой важный пример: Feigeгипотезы, которая представляет собой предположение о вычислительной сложности случайных экземпляров 3-СБ (выбрано для поддержания определенного соотношения пунктов и переменных).^[21]Допущения о вычислительной сложности в среднем случае полезны для доказательства устойчивости в среднем случае в таких приложениях, как статистика, где существует естественное распределение по входным данным.^[22]Кроме того, предположение о жесткости насаждаемой клики также использовалось, чтобы различать полиномиальную и квазиполиномиальную временную сложность других задач в наихудшем случае,^[23]аналогично Гипотеза экспоненциального времени.

Уникальные игры

В Уникальная крышка этикетки проблема - это проблема удовлетворения ограничений, где каждое ограничение ${displaystyle C}$ включает две переменные ${displaystyle x, y}$, и для каждого значения ${displaystyle x}$ Существует уникальный значение ${displaystyle y}$ это удовлетворяет ${displaystyle C}$. Определить, могут ли быть выполнены все ограничения, легко, но Уникальная игровая гипотеза (UGC) постулирует, что определение того, являются ли почти все ограничения (${displaystyle (1-варепсилон)}$-доля для любой постоянной ${displaystyle varepsilon> 0}$) могут быть удовлетворены или почти ни один из них (${displaystyle varepsilon}$-fraction) можно удовлетворить NP-hard.^[16]Часто известно, что проблемы аппроксимации NP-трудны в предположении UGC; такие проблемы называются UG-hard. В частности, если предположить, что UGC существует полуопределенное программирование алгоритм, который обеспечивает оптимальное приближение, гарантирует решение многих важных проблем.^[24]

Расширение небольшого набора

С проблемой уникального покрытия этикеток тесно связана проблема Расширение малого набора (SSE) проблема: задан график ${displaystyle G = (V, E)}$, найдите небольшой набор вершин (размером ${displaystyle n / log (n)}$) чей расширение края минимально. Известно, что если SSE сложно подобрать, то и Unique Label Cover - тоже. Следовательно Гипотеза расширения малого множества, который постулирует, что SSE трудно аппроксимировать, является более сильным (но тесно связанным) предположением, чем гипотеза уникальной игры.^[25]Известно, что некоторые задачи аппроксимации трудны для SSE.^[26] (т.е. по крайней мере так же сложно, как приближение SSE).

Гипотеза 3SUM

Учитывая набор ${displaystyle n}$ чисел, задача 3SUM спрашивает, существует ли тройка чисел, сумма которых равна нулю. Существует алгоритм квадратичного времени для 3SUM, и было высказано предположение, что ни один алгоритм не может решить 3SUM за "действительно субквадратичное время": Гипотеза 3SUM является предположением о вычислительной сложности, что нет ${displaystyle O (n ^ {2-varepsilon})}$-временные алгоритмы для 3SUM (для любой постоянной ${displaystyle varepsilon> 0}$Эта гипотеза полезна для доказательства почти квадратичных нижних оценок для нескольких задач, в основном из вычислительная геометрия.^[27]

Смотрите также

• Уровень безопасности

Рекомендации