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

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

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

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

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

Сравнение допущений по твердости

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

Предположения о прочности

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

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

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

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

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

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

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

Факторизация целых чисел

Если задано составное целое число , и в частности то, которое является произведением двух больших простых чисел , задача факторизации целых чисел состоит в том, чтобы найти и (в более общем смысле, найти простые числа такие, что ). Это крупная открытая проблема — найти алгоритм факторизации целых чисел, который выполняется за время, полиномиальное по размеру представления ( ). Безопасность многих криптографических протоколов основана на предположении, что факторизация целых чисел сложна (т. е. не может быть решена за полиномиальное время). Криптосистемы, безопасность которых эквивалентна этому предположению, включают криптосистему Рабина и криптосистему Окамото–Учиямы . Многие другие криптосистемы основаны на более сильных предположениях, таких как RSA, проблемы остатков и сокрытие Фи. ${\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}$

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

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

Для составного числа неизвестно, как эффективно вычислить его функцию Эйлера . Предположение о сокрытии Фи постулирует, что трудно вычислить , и, более того, даже вычисление любых простых множителей является трудным. Это предположение используется в протоколе 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}}$

Большинство криптографических протоколов, связанных с проблемой дискретного журнала, на самом деле полагаются на более сильное предположение Диффи–Хеллмана : заданные элементы группы , где — генератор , а — случайные целые числа, трудно найти . Примерами протоколов, использующих это предположение, являются оригинальный обмен ключами Диффи–Хеллмана , а также шифрование Эль-Гамаля (которое опирается на еще более сильный вариант Decisional Diffie–Hellman (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 входные данные алгоритма содержат ошибки, т. е. для каждой пары с некоторой малой вероятностью . Считается, что ошибки делают проблему неразрешимой (для соответствующих параметров); в частности, известны сокращения от худшего случая к среднему из вариантов SVP. ^[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] .

С-сложные проблемы

Известно, что многие наихудшие вычислительные задачи являются сложными или даже полными для некоторого класса сложности , в частности NP-сложными (но часто также PSPACE-сложными , PPAD-сложными и т. д.). Это означает, что они по крайней мере столь же сложны, как и любая задача в классе . Если задача является -сложной (относительно полиномиальных сокращений времени), то ее нельзя решить с помощью алгоритма полиномиального времени, если только предположение о вычислительной сложности не является ложным. ${\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) постулирует, что определение того, могут ли быть удовлетворены почти все ограничения ( -дробь, для любой константы ) или почти ни одно из них ( -дробь) не может быть удовлетворено, является NP-трудным. ^[16] Часто известно, что задачи аппроксимации являются NP-трудными, предполагая UGC; такие задачи называются UG-трудными. В частности, предполагая UGC, существует алгоритм полуопределенного программирования , который обеспечивает оптимальные гарантии аппроксимации для многих важных задач. ^[24] ${\displaystyle C}$ ${\displaystyle x,y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle C}$ ${\displaystyle (1-\varepsilon )}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon }$

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

С задачей Unique Label Cover тесно связана задача Small Set Expansion (SSE) : для заданного графа найдите небольшой набор вершин (размера ), расширение ребер которого минимально. Известно, что если SSE трудно аппроксимировать, то и Unique Label Cover тоже. Следовательно, гипотеза Small Set Expansion , постулирующая, что SSE трудно аппроксимировать, является более сильным (но тесно связанным) предположением, чем гипотеза Unique Game. ^[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. Braverman, Mark ; Ko, Young Kun; Weinstein, Omri (2015). «Аппроксимация наилучшего равновесия Нэша в -time ломает гипотезу экспоненциального времени». Симпозиум по дискретным алгоритмам (SODA) . Общество промышленной и прикладной математики . стр. 970–982. doi :10.1137/1.9781611973730.66. ISBN ${\displaystyle n^{o(\log(n))}}$ 978-1-61197-374-7.
2. Дж. Кац и Й. Линделл, Введение в современную криптографию (серия «Криптография и сетевая безопасность» Чапмана и Холла/CRC), Чапман и Холл/CRC, 2007.
3. Голдвассер, Шафи ; Калай, Яэль Тауман (2016). «Криптографические предположения: позиционная статья». Конференция по теории криптографии (TCC) 2016. Springer. стр. 505–522. doi : 10.1007/978-3-662-49096-9_21 .
4. Naor, Moni (2003). «О криптографических предположениях и проблемах». В Boneh, Dan (ред.). Advances in Cryptology – CRYPTO 2003: 23-я ежегодная международная конференция по криптологии, Санта-Барбара, Калифорния, США, 17–21 августа 2003 г., Труды . Lecture Notes in Computer Science. Vol. 2729. Berlin: Springer. pp. 96–109. doi : 10.1007/978-3-540-45146-4_6 . MR  2093188.
5. Кашен, Кристиан; Микали, Сильвио; Штадлер, Маркус (1999). «Вычислительно приватный поиск информации с полилогарифмической связью». В Stern, Jacques (ред.). Advances in Cryptology — EUROCRYPT '99 . Lecture Notes in Computer Science. Vol. 1592. Springer. pp. 402–414. doi :10.1007/3-540-48910-X_28. ISBN 978-3-540-65889-4. S2CID  29690672.
6. Бонех, Дэн ; Сильверберг, Элис (2002). «Применение многолинейных форм в криптографии». Архив Cryptology ePrint .
7. Дутта, Ратна; Баруа, Рана; Саркар, Палаш (2004). «Криптографические протоколы на основе спаривания: обзор». Архив электронной печати по криптологии .
8. Альбрехт, Мартин Р. «Схема градуированного кодирования уже сломана?» . Получено 22 марта 2018 г.
9. Гарг, Санджам; Джентри, Крейг; Халеви, Шай; Райкова, Мариана; Сахай, Амит; Уотерс, Брент (2016). «Обфускация неразличимости кандидатов и функциональное шифрование для всех схем» (PDF) . Журнал SIAM по вычислениям . 45 (3). SIAM: 882–929. doi :10.1137/14095772X.
10. Peikert, Chris (2009). «Криптосистемы с открытым ключом из проблемы наихудшего кратчайшего вектора: расширенный реферат». Труды 41-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 333–342. doi :10.1145/1536414.1536461.
11. Ajtai, Miklós ; Dwork, Cynthia (1997). «Криптосистема с открытым ключом и эквивалентностью в худшем и среднем случаях». Труды 29-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 284–293. doi :10.1145/258533.258604.
12. Регев, Одед (2010). «Проблема обучения с ошибками (приглашенный опрос)». Конференция по вычислительной сложности (CCC) 2010. стр. 191–204. doi :10.1109/CCC.2010.26.
13. Peikert, Chris (2016). «Десятилетие решеточной криптографии». Основы и тенденции в теоретической информатике . 10 (4): 283–424. doi :10.1561/0400000074.
14. Fortnow, Lance (2009). "The status of the P versus NP problem" (PDF) . Communications of the ACM . 52 (9): 78–86. doi :10.1145/1562164.1562186. S2CID  5969255. Архивировано из оригинала (PDF) 24.02.2011..
15. Woeginger, Gerhard (2003). «Точные алгоритмы для NP-трудных задач: обзор». Комбинаторная оптимизация — Эврика, ты уменьшаешься!. Том 2570. Springer-Verlag. С. 185–207. doi :10.1007/3-540-36478-1_17. S2CID  289357..
16. Khot, Subhash (2010). «О гипотезе уникальных игр». Труды 25-й конференции IEEE по вычислительной сложности (PDF) . стр. 99–121. doi :10.1109/CCC.2010.19..
17. Импальяццо, Рассел ; Патури, Рамамохан (1999). «Сложность k-SAT». Труды 14-й конференции IEEE по вычислительной сложности . стр. 237–240. doi :10.1109/CCC.1999.766282.
18. Аббуд, Амир; Василевска-Уильямс, Вирджиния ; Вайман, Орен (2014). «Последствия более быстрого выравнивания последовательностей». Автоматы, языки и программирование — 41-й международный коллоквиум, ICALP 2014. стр. 39–51. doi :10.1007/978-3-662-43948-7_4.
19. Локштанов, Даниэль; Маркс, Даниэль; Саурабх, Сакет (2011). «Нижние границы на основе гипотезы экспоненциального времени». Бюллетень EATCS . ​​105 : 41–72.
20. Арора, Санджив ; Барак, Боаз (2009). Вычислительная сложность: современный подход. Cambridge University Press. С. 362–363. ISBN 9780521424264..
21. Фейге, Уриэль (2002). «Связь между средней сложностью случая и сложностью аппроксимации». Труды 34-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 534–543. doi :10.1145/509907.509985.
22. Берте, Квентин; Риголле, Филипп (2013). «Нижние границы теории сложности для обнаружения разреженных главных компонент». COLT 2013. С. 1046–1066.
23. Хазан, Элад; Краутгеймер, Роберт (2011). «Насколько сложно приблизить наилучшее равновесие Нэша?». Журнал SIAM по вычислениям . 40 (1): 79–91. CiteSeerX 10.1.1.139.7326 . doi :10.1137/090766991. 
24. Рагхавендра, Прасад (2008). «Оптимальные алгоритмы и результаты неаппроксимируемости для каждого CSP?». 40-й ежегодный симпозиум ACM по теории вычислений (STOC) 2008. стр. 245–254. doi :10.1145/1374376.1374414.
25. Рагхавендра, Прасад; Стейрер, Дэвид (2010). «Расширение графа и гипотеза уникальных игр». 42-й ежегодный симпозиум ACM по теории вычислений (STOC) 2010 г. С. 755–764. doi :10.1145/1806689.1806792.
26. Ву, Ю; Острин, Пер; Питасси, Тониан; Лю, Дэвид (2014). «Неаппроксимируемость ширины дерева и связанные с ней проблемы». Журнал исследований искусственного интеллекта . 49 : 569–600. doi : 10.1613/jair.4030 .
27. Василевска Уильямс, Вирджиния (2018). «О некоторых тонкозернистых вопросах в алгоритмах и сложности». ICM 2018 (PDF) .