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

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

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

Предположения о вычислительной сложности также полезны для руководства разработчиками алгоритмов: простой алгоритм вряд ли опровергнет хорошо изученное предположение о вычислительной сложности, такое как 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 п = п \ cdot q}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle p_ {1}, \ dots, p_ {k}}$${\ displaystyle n = \ prod _ {i} p_ {i}}$${\ Displaystyle \ журнал (п)}$, Проблемы остаточности и фи-сокрытие .

Проблема RSA [ править ]

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

Проблемы остаточности [ править ]

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

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

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

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

Предположение о сокрытии фи [ править ]

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

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

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

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

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

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

• Схема Боне-Франклина (блинеарная схема Диффи-Хеллмана)
• Boneh – Lynn – Shacham (блинеарная система Диффи-Хеллмана)
• Гарг-Джентри-Халеви-Райкова-Сахай-Уотерс кандидат на неразличимость обфускации и функционального шифрования (многолинейные головоломки) ^[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]

${\displaystyle C}$-сложные проблемы [ править ]

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

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

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

Допущения средней твердости [ править ]

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

Уникальные игры [ править ]

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

Расширение небольшого набора [ править ]

С проблемой уникального покрытия меток тесно связана проблема расширения малого множества (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}$

См. Также [ править ]

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

Ссылки [ править ]