В теории сложности вычислений предположение о вычислительной сложности — это гипотеза о том, что конкретная проблема не может быть решена эффективно (где эффективно обычно означает «за полиномиальное время »). Неизвестно, как доказать (безусловную) сложность практически любой полезной задачи. Вместо этого ученые-компьютерщики полагаются на сокращения , чтобы формально связать сложность новой или сложной проблемы с предположением о вычислительной сложности проблемы, которая лучше понята.
Предположения о вычислительной стойкости имеют особое значение в криптографии . Основная цель криптографии — создание криптографических примитивов с доказуемой безопасностью . В некоторых случаях обнаруживается, что криптографические протоколы обладают теоретической безопасностью ; одноразовый блокнот является распространенным примером. Однако теоретическая информационная безопасность не всегда может быть достигнута; в таких случаях криптографы прибегают к вычислительной безопасности. Грубо говоря, это означает, что эти системы безопасны при условии, что любые злоумышленники ограничены в вычислительном отношении , как и все злоумышленники на практике.
Предположения о вычислительной сложности также полезны для разработчиков алгоритмов : простой алгоритм вряд ли сможет опровергнуть хорошо изученное предположение о вычислительной сложности, такое как P ≠ NP .
Ученые-компьютерщики по-разному оценивают, какие предположения о твердости более надежны.
Мы говорим, что предположение сильнее предположения , когда оно подразумевает (и обратное неверно или неизвестно). Другими словами, даже если предположение было ложным, оно все равно может быть истинным, и криптографические протоколы, основанные на предположении, все равно могут быть безопасными в использовании. Таким образом, при разработке криптографических протоколов надеются доказать безопасность, используя самые слабые предположения.
Допущение среднего случая говорит, что конкретная проблема сложна для большинства случаев из некоторого явного распределения, тогда как предположение наихудшего случая говорит, что проблема сложна только в некоторых случаях. Для данной задачи сложность в среднем случае подразумевает сложность в наихудшем случае, поэтому предположение о сложности в среднем случае является более сильным, чем предположение о сложности в наихудшем случае для той же задачи. Более того, даже для несравнимых задач такое предположение, как гипотеза экспоненциального времени, часто считается более предпочтительным, чем предположение среднего случая, такое как гипотеза о посеваемой клике . [1] Однако для криптографических приложений знание того, что у проблемы есть какой-то сложный экземпляр (в худшем случае проблема сложна), бесполезно, поскольку не дает нам способа генерировать жесткие экземпляры. [2] К счастью, многие предположения о среднем случае, используемые в криптографии (включая RSA, дискретный журнал и некоторые проблемы с решетками), могут быть основаны на предположениях о наихудшем случае посредством приведения от наихудшего случая к среднему. [3]
Желаемой характеристикой предположения о вычислительной сложности является фальсифицируемость , т.е. если бы предположение было ложным, его можно было бы доказать. В частности, Наор (2003) ввел формальное понятие криптографической фальсифицируемости. [4] Грубо говоря, предположение о вычислительной сложности называется фальсифицируемым, если его можно сформулировать в терминах задачи: интерактивного протокола между противником и эффективным проверяющим, где эффективный противник может убедить проверяющего принять его тогда и только тогда, когда предположение неверно.
Существует множество предположений о криптографической стойкости. Это список некоторых наиболее распространенных из них и некоторых криптографических протоколов, которые их используют.
Учитывая составное целое число и, в частности, то, которое является продуктом двух больших простых чисел , проблема целочисленной факторизации состоит в том, чтобы найти и (в более общем смысле, найти простые числа такие, что ). Это основная открытая проблема — найти алгоритм факторизации целых чисел, который работает за время, полиномиальное по размеру представления ( ). Безопасность многих криптографических протоколов основана на предположении, что факторизация целых чисел сложна (т. е. не может быть решена за полиномиальное время). Криптосистемы, безопасность которых эквивалентна этому предположению, включают криптосистему Рабина и криптосистему Окамото-Утиямы . Многие другие криптосистемы полагаются на более сильные предположения, такие как RSA, проблемы остаточности и сокрытие Phi.
Задача RSA состоит в том, чтобы найти составное число , показатель степени и число . Предполагается , что проблема сложна, но становится простой при факторизации . В криптосистеме RSA — открытый ключ — шифрование сообщения , а факторизация — секретный ключ, используемый для дешифрования.
Учитывая составное число и целые числа , проблема с остатком состоит в том, чтобы определить, существует ли (или найти) такое, что
Важные частные случаи включают проблему квадратичной невязки и сложную проблему невязкости по решению . Как и в случае с RSA, эта проблема (и ее частные случаи) предположительно сложна, но становится проще при факторизации . Некоторые криптосистемы, которые полагаются на сложность проблем остаточности, включают:
Для составного числа неизвестно, как эффективно вычислить его функцию Эйлера . Предположение о сокрытии Фи постулирует, что его трудно вычислить , и, более того, даже вычислить любые простые множители сложно . Это предположение используется в протоколе PIR Кашена-Микали-Штадлера . [5]
Для заданных элементов и группы задача дискретного журнала требует целое число такое, что . Проблема дискретного журнала не может быть сравнима с факторизацией целых чисел, но их вычислительная сложность тесно связана .
Большинство криптографических протоколов, связанных с проблемой дискретного журнала, на самом деле полагаются на более сильное предположение Диффи-Хеллмана : учитывая элементы группы , где — генератор и — случайные целые числа, их трудно найти . Примеры протоколов, использующих это предположение, включают исходный обмен ключами Диффи-Хеллмана , а также шифрование Эль-Гамаля (которое основано на еще более надежном варианте Диффи-Хеллмана (DDH) ).
Полилинейное отображение — это функция (где группы ) такая, что для любых и ,
Для криптографических приложений хотелось бы построить группы и карту так, чтобы карта и групповые операции могли быть эффективно вычислены, но проблема дискретного журнала по -прежнему остается сложной. [6] Некоторые приложения требуют более сильных предположений, например, полилинейные аналоги предположений Диффи-Хеллмана.
Для частного случая билинейные карты с достоверной безопасностью были построены с использованием спаривания Вейля и спаривания Тейта . [7] В последние годы было предложено множество конструкций, но многие из них также были сломаны, и в настоящее время нет единого мнения о безопасном кандидате. [8]
Некоторые криптосистемы, основанные на предположениях о полилинейной стойкости, включают:
Самая фундаментальная вычислительная задача на решетках — это задача о кратчайшем векторе (SVP) : по заданной решетке найти кратчайший ненулевой вектор . Большинство криптосистем требуют более строгих предположений относительно вариантов SVP, таких как задача кратчайших независимых векторов (SIVP) , GapSVP , [10] или Unique-SVP. [11]
Наиболее полезное предположение о жесткости решетки в криптографии относится к задаче обучения с ошибками (LWE): учитывая выборки для некоторой линейной функции , ее легко изучить с помощью линейной алгебры . В задаче LWE входные данные алгоритма содержат ошибки, т.е. для каждой пары с некоторой малой вероятностью . Считается, что ошибки делают проблему неразрешимой (при соответствующих параметрах); в частности, известно снижение показателей от наихудшего до среднего при вариантах СВП. [12]
Для квантовых компьютеров задачи факторинга и дискретного журнала несложны, но задачи решетки предполагаются сложными. [13] Это делает некоторые решетчатые криптосистемы кандидатами на роль постквантовой криптографии .
Некоторые криптосистемы, основанные на сложности задач решетки, включают:
Помимо криптографических приложений, предположения о твердости используются в теории сложности вычислений для предоставления доказательств математических утверждений, которые трудно доказать безоговорочно. В этих приложениях доказывается, что предположение о жесткости подразумевает некоторое желаемое утверждение теории сложности, вместо того, чтобы доказывать, что это утверждение само по себе истинно. Самым известным предположением этого типа является предположение, что P ≠ NP , [14] , но другие включают гипотезу экспоненциального времени , [15] гипотезу установленной клики и гипотезу уникальных игр . [16]
Известно, что многие вычислительные задачи наихудшего случая являются трудными или даже полными для некоторого класса сложности , в частности NP-hard (но часто также PSPACE-hard , PPAD-hard и т. д.). Это означает, что они по крайней мере так же сложны, как и любая задача в классе . Если проблема является трудной (по отношению к полиномиальному сокращению времени), то она не может быть решена с помощью алгоритма с полиномиальным временем, если только предположение о вычислительной сложности не является ложным.
Гипотеза экспоненциального времени (ETH) — это усиление предположения о жесткости, которое предполагает, что задача булевой выполнимости (SAT) не только не имеет алгоритма с полиномиальным временем, но, кроме того, требует экспоненциального времени ( ). [17] Еще более сильное предположение, известное как Сильная экспоненциальная гипотеза времени (SETH), предполагает, что -SAT требует времени, где . ETH, SETH и связанные с ними предположения о вычислительной сложности позволяют получать более детальные результаты по сложности, например, результаты, которые различают полиномиальное время и квазиполиномиальное время , [1] или даже по сравнению с . [18] Такие предположения также полезны в параметризованной сложности . [19]
Предполагается, что некоторые вычислительные задачи в среднем сложны для определенного распределения экземпляров. Например, в задаче о посаженной клике входными данными является случайный граф , выбранный путем выборки случайного графа Эрдёша – Реньи, а затем «посадки» случайной -клики, т.е. соединения равномерно случайных узлов (где ), и цель состоит в том, чтобы найти посаженная -клика (которая является уникальной WhP). [20] Другим важным примером является гипотеза Файги , которая представляет собой предположение о вычислительной сложности случайных экземпляров 3-SAT (выборка осуществляется для поддержания определенного соотношения предложений и переменных). [21] Предположения о вычислительной сложности в среднем случае полезны для доказательства средней сложности в таких приложениях, как статистика, где существует естественное распределение по входным данным. [22] Кроме того, предположение о жесткости посаженной клики также использовалось для различения полиномиальной и квазиполиномиальной временной сложности в худшем случае других задач, [23] аналогично гипотезе экспоненциального времени.
Задача уникального покрытия меток — это проблема удовлетворения ограничений, где каждое ограничение включает в себя две переменные , и для каждого значения существует уникальное значение, которое удовлетворяет . Определить, могут ли быть удовлетворены все ограничения, легко, но гипотеза уникальной игры (UGC) постулирует, что определение того, могут ли быть удовлетворены почти все ограничения ( -fraction, для любой константы ) или почти ни одно из них ( -fraction) не может быть удовлетворено. является NP-трудным. [16] Часто известно, что задачи аппроксимации являются NP-сложными, если принять во внимание UGC; такие проблемы называются UG-hard. В частности, если предположить, что UGC существует полуопределенный алгоритм программирования , который обеспечивает оптимальные гарантии аппроксимации для многих важных задач. [24]
С проблемой покрытия уникальными метками тесно связана проблема расширения малого набора (SSE) : для данного графа найдите небольшой набор вершин (размера ), расширение ребер которого минимально. Известно, что если SSE сложно оценить, то и Unique Label Cover тоже. Следовательно, гипотеза расширения малого множества , которая постулирует, что SSE трудно аппроксимировать, является более сильным (но тесно связанным) предположением, чем гипотеза уникальной игры. [25] Некоторые задачи аппроксимации, как известно, являются SSE-трудными [26] (т.е., по крайней мере, такими же сложными, как аппроксимация SSE).
Для заданного набора чисел задача 3SUM спрашивает, существует ли тройка чисел, сумма которых равна нулю. Существует алгоритм с квадратичным временем для 3SUM, и было высказано предположение, что ни один алгоритм не может решить 3SUM за «истинно субквадратичное время»: гипотеза 3SUM представляет собой предположение о вычислительной сложности, согласно которому не существует алгоритмов с квадратичным временем для 3SUM (для любого постоянный ). Эта гипотеза полезна для доказательства почти квадратичных нижних оценок для нескольких задач, в основном из вычислительной геометрии . [27]