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

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

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

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

Проблема RSA

Основная статья: Проблема 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},dots ,G_{n}ightarrow 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}}}$.

Для криптографических приложений хотелось бы построить группы ${displaystyle G_{1},dots ,G_{n},G_{T}}$ и карта ${displaystyle e}$ такие, что отображение и групповые операции на ${displaystyle G_{1},dots ,G_{n},G_{T}}$ могут быть вычислены эффективно, но проблема дискретного журнала на ${displaystyle G_{1},dots ,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-varepsilon )}$-доля для любой постоянной ${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

Основная статья: 3SUM

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

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

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

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

1. Браверман, Марк; Ко, Ён Кун; Вайнштейн, Омри (2015). "Приближение наилучшего равновесия по Нэшу в ${displaystyle n^{o(log(n))}}$-время нарушает гипотезу экспоненциального времени ". Симпозиум по дискретным алгоритмам (SODA). Общество промышленной и прикладной математики. С. 970–982. Дои:10.1137/1.9781611973730.66. ISBN  978-1-61197-374-7.
2. Дж. Кац и Ю. Линделл, Введение в современную криптографию (серия Chapman and Hall / Crc Cryptography and Network Security Series), Chapman and Hall / CRC, 2007.
3. Гольдвассер, Шафи; Калаи, Яэль Тауман (2016). «Криптографические предположения: документ с изложением позиции». Конференция по теории криптографии (TCC) 2016. Springer. С. 505–522. Дои:10.1007/978-3-662-49096-9_21.
4. Наор, Мони (2003). «О криптографических предположениях и проблемах». В Боне, Дэн (ред.). Достижения в криптологии - CRYPTO 2003: 23-я ежегодная международная конференция по криптологии, Санта-Барбара, Калифорния, США, 17-21 августа 2003 г., Труды. Конспект лекций по информатике. 2729. Берлин: Springer. С. 96–109. Дои:10.1007/978-3-540-45146-4_6. МИСТЕР  2093188.
5. Качин, Кристиан; Микали, Сильвио; Стадлер, Маркус (1999). Стерн, Жак (ред.). «Вычислительный поиск частной информации с полилогарифмической связью». Конспект лекций по информатике. Springer. 1592: 402–414. Дои:10.1007 / 3-540-48910-X. ISBN  978-3-540-65889-4. S2CID  29690672.
6. Бонех, Дэн; Сильверберг, Алиса (2002). «Применение полилинейных форм в криптографии». Архив криптологии ePrint.
7. Дутта, Ратна; Баруа, Рана; Саркар, Палаш (2004). «Криптографические протоколы на основе пар: обзор». Архив криптологии ePrint.
8. Альбрехт, Мартин Р. "Схема градуированного кодирования еще не нарушена?". Получено 22 марта 2018.
9. Гарг, Санджам; Джентри, Крейг; Халеви, Шай; Райкова, Марьяна; Сахай, Амит; Уотерс, Брент (2016). «Возможное запутывание неразличимости и функциональное шифрование для всех схем» (PDF). SIAM Журнал по вычислениям. СИАМ. 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). Коммуникации ACM. 52 (9): 78–86. Дои:10.1145/1562164.1562186. S2CID  5969255. Архивировано из оригинал (PDF) 24 февраля 2011 г..
15. Woeginger, Герхард (2003). «Точные алгоритмы для NP-сложных задач: обзор». Комбинаторная оптимизация - Эврика, сжимайся!. 2570. Springer-Verlag. С. 185–207. Дои:10.1007/3-540-36478-1_17..
16. Хот, Субхаш (2010). «О гипотезе об уникальных играх». Proc. 25-я конференция IEEE по вычислительной сложности (PDF). С. 99–121. Дои:10.1109 / CCC.2010.19..
17. Импальяццо, Рассел; Патури, Рамамохан (1999). «Сложность k-SAT». Proc. 14-я конференция IEEE Conf. по вычислительной сложности. С. 237–240. Дои:10.1109 / CCC.1999.766282.
18. Аббуд, Амир; Василевска-Уильямс, Вирджиния; Вейманн, Орен (2014). «Последствия более быстрого совмещения последовательностей». Автоматы, языки и программирование - 41-й международный коллоквиум, ICALP 2014. С. 39–51. Дои:10.1007/978-3-662-43948-7_4.
19. Локштанов Даниил; Маркс, Даниил; Саураб, Сакет (2011). «Нижние оценки на основе гипотезы экспоненциального времени». Бюллетень EATCS. 105: 41–72.
20. Арора, Санджив; Варак, Вооз (2009). Вычислительная сложность: современный подход. Издательство Кембриджского университета. С. 362–363. ISBN  9780521424264..
21. Файги, Уриэль (2002). «Связь между сложностью среднего случая и сложностью аппроксимации». Материалы 34-го ежегодного симпозиума ACM по теории вычислений (STOC). С. 534–543. Дои:10.1145/509907.509985.
22. Бертет, Квентин; Риголе, Филипп (2013). "Теоретические нижние оценки сложности для обнаружения разреженных главных компонент". COLT 2013. С. 1046–1066.
23. Хазан, Элад; Krauthgamer, Роберт (2011). «Насколько сложно приблизиться к наилучшему равновесию по Нэшу?». SIAM Журнал по вычислениям. 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. Ву, Ю; Austrin, Per; Питасси, Тониан; Лю, Дэвид (2014). «Неприблизимость ширины дерева и связанные с этим проблемы». Журнал исследований искусственного интеллекта. 49: 569–600. Дои:10.1613 / jair.4030.
27. Василевска Уильямс, Вирджиния (2018). «О некоторых тонких вопросах алгоритмов и сложности». ICM 2018 (PDF).