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

редактировать

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

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

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

Содержание

1 Сравнение предположений о твердости
- 1.1 Сила допущений о надежности
- 1.2 Среднее и худшее предположения
- 1.3 Фальсифицируемость
2 Общие предположения о криптографической стойкости
- 2.1 Целочисленная факторизация
  - 2.1.1 Проблема RSA
  - 2.1.2 Проблемы остаточной непрерывности
  - 2.1.3 Предположение о сокрытии фи
- 2.2 Проблема дискретного логарифма (DLP)
  - 2.2.1 Полилинейные карты
- 2.3 Проблемы с решеткой
3 Допущения некриптографической устойчивости
- 3.1 $C {\ displaystyle C}$ $C$ -сложные задачи
- 3.2 Экспоненциальная временная гипотеза (ETH) и варианты
- 3.3 Допущения твердости среднего случая
- 3.4 Unique Games
  - 3.4.1 Расширение малого набора
- 3.5 Гипотеза 3SUM
4 См. Также
5 Ссылки

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

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

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

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

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

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

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

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

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

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

Целочисленное разложение

Дано составное число $n {\ displaystyle n}$ $n$ , и, в частности, одно, которое является произведением двух большие простые числа $n = p ⋅ q {\ displaystyle n = p \ cdot q}$ ${\ displaystyle n = p \ cdot q}$ , задача целочисленной факторизации состоит в том, чтобы найти $p {\ displaystyle p}$ $p$ и $q {\ displaystyle q}$ $q$ (в общем, найти простые числа $p 1,…, pk {\ displaystyle p_ {1}, \ dots, p_ {k}}$ ${\ displaystyle p_ {1}, \ dots, p_ {k}}$ такое, что $n = ∏ ipi {\ displaystyle n = \ prod _ {i} p_ {i}}$ ${\ displaystyle n = \ prod _ {i} p_ {i}}$ ). Основная открытая проблема - найти алгоритм для целочисленной факторизации, который работает с полиномом времени от размера представления ( $log ⁡ (n) {\ displaystyle \ log (n)}$ $\ журнал (п)$ ). Безопасность многих криптографических протоколов основывается на предположении, что целочисленная факторизация сложна (т.е. не может быть решена за полиномиальное время). К криптосистемам, безопасность которых эквивалентна этому предположению, относятся криптосистема Рабина и криптосистема Окамото – Учияма. Многие другие криптосистемы полагаются на более сильные допущения, такие как RSA, проблемы остаточности и Phi-hiding.

RSA problem

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

Проблемы с непрерывностью

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

xd ≡ y (mod n). {\ displaystyle x ^ {d} \ Equiv y {\ pmod {n}}.}

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

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

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

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

Для составной число $m {\ displaystyle m}$ $m$ , неизвестно, как эффективно вычислить его тотализирующую функцию Эйлера $ϕ (m) {\ displaystyle \ phi (m) }$ $\ phi (m)$ . Предположение о сокрытии фи постулирует, что трудно вычислить $ϕ (m) {\ displaystyle \ phi (m)}$ $\ phi (m)$ и, кроме того, даже вычислить любые простые множители $ϕ (m) {\ displaystyle \ phi (m)}$ $\ phi (m)$ сложно. Это предположение используется в протоколе Cachin – Micali – Stadler PIR.

Задача дискретного журнала (DLP)

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

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

Мультилинейные карты

A Мультилинейные карты - это функция $e: G 1,…, G n → GT {\ displaystyle e: G_ {1}, \ dots, G_ {n} \ rightarrow G_ {T}}$ ${\ displaystyle e: G_ {1}, \ dots, G_ {n} \ rightarrow G_ {T}}$ (где $G 1,…, G n, GT {\ displaystyle G_ {1}, \ dots, G_ {n}, G_ {T}}$ ${ \ Displaystyle G_ {1}, \ точки, G_ {п}, G_ {T}}$ - это группы ) такие, что для любого $x 1,…, xn ∈ G 1,… G n {\ displaystyle x_ {1}, \ dots, x_ {n} \ in G_ {1}, \ dots G_ {n}}$ ${\ displaystyle x_ {1}, \ dots, x_ {n} \ in G_ {1}, \ dots G_ {n}}$ и $a 1,…, an {\ displaystyle a_ {1}, \ dots, a_ {n}}$ $a_ {1}, \ dots, a_ {n}$ ,

e (g 1 a 1,…, gnan) = e (g 1,…, gn) a 1 ⋯ an {\ displaystyle e (g_ {1} ^ {a_ {1}}, \ dots, g_ {n} ^ {a_ { n}}) = e (g_ {1}, \ dots, g_ {n}) ^ {a_ {1} \ cdots a_ {n}}}

{\ displaystyle e (g_ {1} ^ {a_ {1}}, \ dots, g_ {n} ^ {a_ {n}}) = e (g_ {1}, \ dots, g_ { n}) ^ {a_ {1} \ cdots a_ {n}}}

Для криптографических приложений нужно создать группы $G 1,…, G n, GT {\ displaystyle G_ {1}, \ dots, G_ {n}, G_ {T}}$ ${ \ Displaystyle G_ {1}, \ точки, G_ {п}, G_ {T}}$ и карта $e {\ displaystyle e}$ $e$ таким образом, что отображение и групповые операции над $G 1,…, G n, GT {\ displaystyle G_ {1}, \ dots, G_ {n}, G_ {T}}$ ${ \ Displaystyle G_ {1}, \ точки, G_ {п}, G_ {T}}$ можно вычислить эффективно, но задача дискретного журнала на $G 1,…, G n {\ dis стиль игры G_ {1}, \ dots, G_ {n}}$ ${\ displaystyle G_ {1}, \ dots, G_ {n}}$ по-прежнему сложно. Некоторые приложения требуют более сильных предположений, например полилинейные аналоги предположений Диффи-Хеллмана.

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

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

схему Боне-Франклина (блинейную диаграмму Диффи-Хеллмана)
Боне-Линн-Шахам (блинейную диаграмму Диффи-Хеллмана)
Гарг-Джентри- Кандидат Халеви-Райкова-Сахай-Уотерс для обфускации неразличимости и функционального шифрования (многолинейные головоломки)

Решеточные задачи

Самая фундаментальная вычислительная проблема на решетках - это Задача кратчайшего вектора (SVP) : для решетки $L {\ displaystyle L}$ $L$ найти кратчайший ненулевой вектор $v ∈ L {\ displaystyle v \ in L}$ ${\ displaystyle v \ in L}$ . Для большинства криптосистем требуется str общие допущения для вариантов SVP, такие как Задача кратчайших независимых векторов (SIVP), GapSVP или Unique-SVP.

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

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

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

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

Некриптографические предположения о надежности

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

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

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

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

Гипотеза экспоненциального времени (ETH) - это усиление $P ≠ NP {\ displaystyle P \ neq NP }$ $P \ neq NP$ предположение о твердости, которое предполагает, что проблема логической выполнимости не только не имеет алгоритма полиномиального времени, но, кроме того, требует экспоненциального времени ( $2 Ом (n) {\ displaystyle 2 ^ {\ Omega (n)}}$ ${\ displaystyle 2 ^ {\ Omega (n)}}$ ). Еще более сильное предположение, известное как Сильная экспоненциальная гипотеза времени (SETH), предполагает, что $k {\ displaystyle k}$ $k$ -SAT требует $2 (1 - ε К) n {\ displaystyle 2 ^ {(1- \ varepsilon _ {k}) n}}$ ${\ displaystyle 2 ^ {(1- \ varepsilon _ {k}) n}}$ время, где $lim k → ∞ ε k = 0 {\ displaystyle \ lim _ {k \ rightarrow \ infty} \ varepsilon _ {k} = 0}$ ${\ Displaystyle \ lim _ {к \ rightarrow \ infty} \ varepsilon _ {k} = 0}$ . ETH, SETH и связанные с ними допущения о вычислительной надежности позволяют выводить мелкозернистые результаты сложности, например результаты, которые различают полиномиальное время и квазиполиномиальное время или даже $n 1.99 {\ displaystyle n ^ {1.99}}$ ${\ displaystyle n ^ {1.99}}$ по сравнению с $n 2 {\ displaystyle n ^ {2}}$ $n ^ {2}$ . Такие предположения также полезны в параметризованной сложности.

Допущения твердости в среднем случае

Предполагается, что некоторые вычислительные проблемы являются сложными в среднем по определенному распределению экземпляров. Например, в задаче установленной клики входом является случайный граф, отобранный путем выборки случайного графа Эрдеша – Реньи и затем «посадки» случайного $k {\ displaystyle k}$ $k$ -clique, т.е. соединение $k {\ displaystyle k}$ $k$ равномерно случайных узлов (где $2 log 2 ⁡ n ≪ k ≪ n {\ displaystyle 2 \ log _ {2} n \ ll k \ ll {\ sqrt {n}}}$ ${\ displaystyle 2 \ журнал _ {2} n \ ll k \ ll {\ sqrt {n}}}$ ), и цель состоит в том, чтобы найти посаженный $k {\ displaystyle k}$ $k$ -clique (уникальный whp). Другой важный пример - это гипотеза Фейджа, которая представляет собой предположение о вычислительной сложности случайных экземпляров 3-SAT (отобранных для поддержания определенного соотношения предложений к переменным). Допущения о вычислительной сложности в среднем случае полезны для доказательства устойчивости в среднем случае в таких приложениях, как статистика, где существует естественное распределение по входным данным. Кроме того, предположение о жесткости клики также использовалось, чтобы различать полиномиальную и квазиполиномиальную временную сложность других задач в наихудшем случае, аналогично гипотезе экспоненциального времени.

Unique Games

Unique Label Cover проблема - это проблема удовлетворения ограничений, где каждое ограничение $C {\ displaystyle C}$ $C$ включает две переменные $x, y {\ displaystyle x, y}$ $x, y$ , и для каждого значения $x {\ displaystyle x}$ $x$ существует уникальное значение $y {\ displaystyle y}$ $y$ , которое удовлетворяет $С {\ Displaystyle C}$ $C$ . Определить, все ли ограничения могут быть выполнены, легко, но Уникальная игровая гипотеза (UGC) постулирует, что определяют, все ли ограничения ( $(1 - ε) {\ displaystyle (1- \ varepsilon))}$ $(1- \ varepsilon)$ -fraction для любой постоянной $ε>0 {\ displaystyle \ varepsilon>0}$ $\varepsilon>0$ ) не может быть удовлетворен или почти ни один из них ( $ε {\ displaystyle \ varepsilon}$ $\ varepsilon$ -fraction) может быть удовлетворено NP-трудным. Проблемы аппроксимации часто известны как NP-трудные при условии UGC; такие проблемы называются UG-трудными. В частности, предполагая, что UGC существует полуопределенное программирование алгоритм, который обеспечивает гарантии оптимальной аппроксимации для многих важных проблем.

Small Set Expansion

Тесно связанной с проблемой уникального покрытия этикеток является Small Set Expansion (SSE) проблема: Учитывая граф $G = (V, E) {\ displaystyle G = (V, E)}$ $G = (V, E)$ , найдите небольшой набор вершин (размером $n / log ⁡ (n) { \ displaystyle n / \ log (n)}$ $п / \ журнал (п)$ ), расширение края которого минимально. Известно, что если SSE сложно подобрать, то и Unique Label Cover - тоже. Следовательно, гипотеза о расширении малого множества, которая постулирует, что SSE трудно аппроксимировать, является более сильным (но тесно связанным) предположением, чем гипотеза уникальной игры. Известно, что некоторые задачи аппроксимации трудны для SSE (т.е. по крайней мере так же сложны, как и аппроксимация SSE).

Гипотеза 3SUM

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

См. Также

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