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

Гипотеза теории сложности вычислений

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

проблема с RSA

Задача RSA состоит в том, чтобы найти составное число , показатель степени и число . Предполагается , что проблема сложна, но становится простой при факторизации . В криптосистеме RSA — открытый ключ — шифрование сообщения , а факторизация — секретный ключ, используемый для дешифрования. ${\displaystyle n}$ ${\displaystyle e}$ ${\displaystyle c:=m^{e}(\mathrm {mod} \;n)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\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 (задача квадратичного невязки)
• Криптосистема Пайе (решающая сложная задача невязки)
• Криптосистема Бенало (проблема с более высокой остаточностью)
• Криптосистема Наккаша – Штерна (проблема с более высокой остаточностью)

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

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

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

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

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

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

Полилинейное отображение — это функция (где группы ) такая, что для любых и , ${\displaystyle e:G_{1},\dots ,G_{n}\rightarrow G_{T}}$ ${\displaystyle G_{1},\dots ,G_{n},G_{T}}$ ${\displaystyle g_{1},\dots ,g_{n}\in G_{1},\dots G_{n}}$ ${\displaystyle a_{1},\dots ,a_{n}}$

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

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

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

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

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

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

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

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

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

Некоторые криптосистемы, основанные на сложности задач решетки, включают:

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

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

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

C – сложные задачи

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

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

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

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

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

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

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

Небольшое расширение набора

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

Гипотеза 3SUM

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

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

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

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

1. Браверман, Марк ; Ко, Янг Кун; Вайнштейн, Омри (2015). «Приближение наилучшего равновесия Нэша во времени нарушает гипотезу экспоненциального времени». Симпозиум по дискретным алгоритмам (SODA) . Общество промышленной и прикладной математики . стр. 970–982. дои : 10.1137/1.9781611973730.66. ISBN ${\displaystyle n^{o(\log(n))}}$ 978-1-61197-374-7.
2. Дж. Кац и Ю. Линделл, Введение в современную криптографию (Чепмен и Холл / Серия CRC «Криптография и сетевая безопасность»), Чепмен и Холл / CRC, 2007.
3. Гольдвассер, Шафи ; Калай, Яэль Тауман (2016). «Криптографические предположения: позиционный документ». Конференция по теории криптографии (TCC) 2016 . Спрингер. стр. 505–522. дои : 10.1007/978-3-662-49096-9_21 .
4. Наор, Мони (2003). «О криптографических предположениях и проблемах». В Боне, Дэн (ред.). Достижения в криптологии – CRYPTO 2003: 23-я ежегодная международная конференция по криптологии, Санта-Барбара, Калифорния, США, 17–21 августа 2003 г., материалы . Конспекты лекций по информатике. Том. 2729. Берлин: Шпрингер. стр. 96–109. дои : 10.1007/978-3-540-45146-4_6 . МР  2093188.
5. Кашен, Кристиан; Микали, Сильвио; Стадлер, Маркус (1999). «Вычислительный поиск конфиденциальной информации с помощью полилогарифмической связи». В Штерне, Жак (ред.). Достижения в криптологии — EUROCRYPT '99 . Конспекты лекций по информатике. Том. 1592. Спрингер. стр. 402–414. дои : 10.1007/3-540-48910-X_28. ISBN 978-3-540-65889-4. S2CID  29690672.
6. Боне, Дэн ; Сильверберг, Алиса (2002). «Применение полилинейных форм в криптографии». Архив электронной печати по криптологии .
7. Дутта, Ратна; Баруа, Рана; Саркар, Палаш (2004). «Криптографические протоколы на основе спаривания: обзор». Архив электронной печати по криптологии .
8. Альбрехт, Мартин Р. «Схема градуированного кодирования уже нарушена?» . Проверено 22 марта 2018 г.
9. Гарг, Санджам; Джентри, Крейг; Халеви, Шай; Райкова, Мариана; Сахай, Амит; Уотерс, Брент (2016). «Кандидат на неотличимость, обфускация и функциональное шифрование для всех схем» (PDF) . SIAM Journal по вычислительной технике . СИАМ. 45 (3): 882–929. дои : 10.1137/14095772X.
10. Пейкерт, Крис (2009). «Криптосистемы с открытым ключом из наихудшего случая задачи кратчайшего вектора: расширенная аннотация». Труды 41-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 333–342. дои : 10.1145/1536414.1536461.
11. Айтай, Миклош ; Дворк, Синтия (1997). «Криптосистема с открытым ключом с эквивалентностью наихудшего/среднего случая». Труды 29-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 284–293. дои : 10.1145/258533.258604.
12. Регев, Одед (2010). «Проблема обучения с ошибками (приглашенный опрос)». Конференция по сложности вычислений (CCC) 2010 . стр. 191–204. дои : 10.1109/CCC.2010.26.
13. Пейкерт, Крис (2016). «Десятилетие решетчатой ​​криптографии». Основы и тенденции теоретической информатики . 10 (4): 283–424. дои : 10.1561/0400000074.
14. Фортнау, Лэнс (2009). «Состояние проблемы P и NP» (PDF) . Коммуникации АКМ . 52 (9): 78–86. дои : 10.1145/1562164.1562186. S2CID  5969255. Архивировано из оригинала (PDF) 24 февраля 2011 г..
15. Вегингер, Герхард (2003). «Точные алгоритмы для NP-трудных задач: обзор». Комбинаторная оптимизация — Эврика, ты уменьшаешься! . Том. 2570. Шпрингер-Верлаг. стр. 185–207. дои : 10.1007/3-540-36478-1_17. S2CID  289357..
16. Хот, Субхаш (2010). «О гипотезе об уникальных играх». Учеб. 25-я конференция IEEE по сложности вычислений (PDF) . стр. 99–121. дои : 10.1109/CCC.2010.19..
17. Импальяццо, Рассел ; Патури, Рамамохан (1999). «Сложность k-SAT». Учеб. 14-я конференция IEEE. по вычислительной сложности . стр. 237–240. дои : 10.1109/CCC.1999.766282.
18. Аббуд, Амир; Василевска-Уильямс, Вирджиния ; Вейманн, Орен (2014). «Последствия более быстрого выравнивания последовательностей». Автоматы, языки и программирование — 41-й международный коллоквиум, ICALP 2014 . стр. 39–51. дои : 10.1007/978-3-662-43948-7_4.
19. Локштанов, Даниэль; Маркс, Дэниел; Саураб, Сакет (2011). «Нижние границы на основе гипотезы экспоненциального времени». Бюллетень ЕАТКС . 105 : 41–72.
20. Арора, Санджив ; Барак, Вооз (2009). Вычислительная сложность: современный подход. Издательство Кембриджского университета. стр. 362–363. ISBN 9780521424264..
21. Файги, Уриэль (2002). «Связь между средней сложностью случая и сложностью аппроксимации». Труды 34-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 534–543. дои : 10.1145/509907.509985.
22. Берте, Квентин; Риголе, Филипп (2013). «Нижние границы теории сложности для обнаружения разреженных главных компонентов». КОЛТ 2013. стр. 1046–1066.
23. Хазан, Элад; Краутгеймер, Роберт (2011). «Насколько сложно приблизить лучшее равновесие Нэша?». SIAM Journal по вычислительной технике . 40 (1): 79–91. CiteSeerX 10.1.1.139.7326 . дои : 10.1137/090766991. 
24. Рагхавендра, Прасад (2008). «Оптимальные алгоритмы и результаты неаппроксимируемости для каждого CSP?». 40-й ежегодный симпозиум ACM по теории вычислений (STOC), 2008 г. стр. 245–254. дои : 10.1145/1374376.1374414.
25. Рагхавендра, Прасад; Стойрер, Дэвид (2010). «Расширение графа и гипотеза уникальных игр». 42-й ежегодный симпозиум ACM по теории вычислений (STOC), 2010 г. стр. 755–764. дои : 10.1145/1806689.1806792.
26. Ву, Ю; Острин, Пер; Питасси, Тонианн; Лю, Дэвид (2014). «Неаппроксимируемость ширины дерева и связанные с этим проблемы». Журнал исследований искусственного интеллекта . 49 : 569–600. дои : 10.1613/jair.4030 .
27. Василевска Уильямс, Вирджиния (2018). «О некоторых мелких вопросах алгоритмов и сложности». ICM 2018 (PDF) .