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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

проблема с RSA

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

Проблемы с остатками

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

x^{d}\equiv y{\pmod {n}}.

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

Криптосистема Гольдвассера – Микали (задача квадратичной невязки)
Генератор Blum Blum Shub (задача квадратичного невязки)
Криптосистема Пайе (решающая сложная задача невязкости)
Криптосистема Бенало (проблема с более высокой остаточностью)
Криптосистема Наккаша – Штерна (проблема с более высокой остаточностью)

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Гипотеза 3SUM

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

См. также

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

Ссылки

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

[BKW15-1] Перейти обратно: ^а ^б Браверман, Марк ; Ко, Янг Кун; Вайнштейн, Омри (2015). «Приближение лучшего равновесия Нэша в $n^{o(\log(n))}$ -время нарушает гипотезу экспоненциального времени». Симпозиум по дискретным алгоритмам (SODA) . Общество промышленной и прикладной математики . Стр. 970–982. doi : 10.1137/1.9781611973730.66 . ISBN 978-1-61197-374-7 .

[katz07-2] Дж. Кац и Ю. Линделл, Введение в современную криптографию (Чепмен и Холл / Серия CRC «Криптография и сетевая безопасность»), Чепмен и Холл / CRC, 2007.

[GK16-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 .

[BS02-6] Боне, Дэн ; Сильверберг, Алиса (2002). «Применение полилинейных форм в криптографии» . Архив электронной печати по криптологии .

[DBS04-7] Дутта, Ратна; Баруа, Рана; Саркар, Палаш (2004). «Криптографические протоколы на основе спаривания: обзор» . Архив электронной печати по криптологии .

[8] Альбрехт, Мартин Р. «Схема градуированного кодирования уже нарушена?» . Проверено 22 марта 2018 г.

[9] Гарг, Санджам; Джентри, Крейг; Халеви, Шай; Райкова, Мариана; Сахай, Амит; Уотерс, Брент (2016). «Кандидат на неотличимость, обфускация и функциональное шифрование для всех схем» (PDF) . SIAM Journal по вычислительной технике . 45 (3). СИАМ: 882–929. дои : 10.1137/14095772X .

[peikert09-10] Пейкерт, Крис (2009). «Криптосистемы с открытым ключом из наихудшего случая задачи кратчайшего вектора: расширенная аннотация». Труды 41-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 333–342. дои : 10.1145/1536414.1536461 .

[ad97-11] Айтаи, Миклош ; Дворк, Синтия (1997). «Криптосистема с открытым ключом с эквивалентностью наихудшего/среднего случая». Труды 29-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 284–293. дои : 10.1145/258533.258604 .

[regev10-12] Регев, Одед (2010). «Проблема обучения с ошибками (приглашенный опрос)». Конференция по сложности вычислений (CCC) 2010 . стр. 191–204. дои : 10.1109/CCC.2010.26 .

[peikert16-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 . .

[khot10-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 .

[LMS11-19] Локштанов Даниил; Маркс, Дэниел; Саураб, Сакет (2011). «Нижние границы на основе гипотезы экспоненциального времени» . Бюллетень ЕАТКС . 105 : 41–72.

[ab-20] Арора, Санджив ; Барак, Вооз (2009). Вычислительная сложность: современный подход . Издательство Кембриджского университета. стр. 362–363. ISBN 9780521424264 . .

[Feige02-21] Файги, Уриэль (2002). «Связь между средней сложностью случая и сложностью аппроксимации». Труды 34-го ежегодного симпозиума ACM по теории вычислений (STOC) . стр. 534–543. дои : 10.1145/509907.509985 .

[BR13-22] Берте, Квентин; Риголе, Филипп (2013). «Нижние границы теории сложности для обнаружения разреженных главных компонентов». КОЛЬТ 2013г . стр. 1046–1066.

[HK11-23] Хазан, Элад; Краутгеймер, Роберт (2011). «Насколько сложно приблизить лучшее равновесие Нэша?». SIAM Journal по вычислительной технике . 40 (1): 79–91. CiteSeerX 10.1.1.139.7326 . дои : 10.1137/090766991 .

[rag08-24] Рагхавендра, Прасад (2008). «Оптимальные алгоритмы и результаты неаппроксимируемости для каждого CSP?». 40-й ежегодный симпозиум ACM по теории вычислений (STOC), 2008 г. стр. 245–254. дои : 10.1145/1374376.1374414 .

[rs10-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) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

v т и Допущения о вычислительной сложности
Теория чисел	Целочисленная факторизация Фи-сокрытие проблема с RSA Сильная адаптивная поисковая оптимизация Квадратичная невязкость Решающий составной остаток Более высокая остаточность
Теория групп	Дискретный логарифм Диффи-Хеллман Решающий Диффи-Хеллман Вычислительный Диффи – Хеллман
Пейринги	Внешний Диффи-Хеллман Скрытие подгруппы Решение линейное
Решетки	Задача о кратчайшем векторе ( пробел ) Ближайшая векторная задача ( пробел ) Обучение с ошибками Кольцевое обучение с ошибками Короткое целочисленное решение
Некриптографический	Гипотеза экспоненциального времени Гипотеза об уникальных играх Гипотеза о посаженной клике