В теории сложности вычислений , Вычислительный предположение Жесткость является гипотеза о том , что конкретная проблема не может быть решена эффективно (где эффективно , как правило , означает , что «в полиномиальное время »). Неизвестно, как доказать (безусловную) трудность практически любой полезной задачи. Вместо этого ученые-информатики полагаются на редукции, чтобы формально соотнести трудность новой или сложной проблемы с предположением о вычислительной сложности проблемы, которую лучше понять.
Допущения о вычислительной надежности имеют особое значение в криптографии . Основная цель криптографии - создание криптографических примитивов с доказанной безопасностью . В некоторых случаях оказывается, что криптографические протоколы обладают теоретической информационной безопасностью ; одноразовый блокнот является типичным примером. Однако теоретическая безопасность информации не всегда может быть достигнута; в таких случаях криптографы прибегают к вычислительной безопасности. Грубо говоря, это означает, что эти системы безопасны при условии, что любые противники ограничены в вычислительном отношении , как и все злоумышленники на практике.
Допущения о вычислительной сложности также полезны для руководства разработчиками алгоритмов: простой алгоритм вряд ли опровергнет хорошо изученное предположение о вычислительной сложности, такое как P ≠ NP .
Сравнение предположений твердости
У компьютерных ученых есть разные способы оценки того, какие предположения о твердости более надежны.
Сила предположений о твердости
Мы говорим, что предположение является более сильным , чем предположения когда подразумевает (и обратное неверно или неизвестно). Другими словами, даже если предположение были ложными, предположение все еще может быть правдой, и криптографические протоколы, основанные на предположении все еще может быть безопасным для использования. Таким образом, при разработке криптографических протоколов можно надеяться на возможность доказать безопасность, используя самые слабые возможные предположения.
Предположения среднего и наихудшего случая
В среднем случае предположение говорит , что проблема в конкретной трудно в большинстве случаев из некоторых явного распределения, в то время как наихудшее предположение говорит только о том , что проблема трудно на некоторых случаях. Для данной проблемы твердость в среднем случае подразумевает твердость в наихудшем случае, поэтому предположение о твердости в среднем случае сильнее, чем предположение о твердости в наихудшем случае для той же проблемы. Более того, даже для несравнимых проблем предположение, подобное гипотезе об экспоненциальном времени, часто считается предпочтительным, чем предположение среднего случая, такое как гипотеза обсаженной клики . [1] Обратите внимание, однако, что в большинстве криптографических приложений знание того, что проблема имеет некоторый жесткий экземпляр (т. Е. Проблема сложна в худшем случае), бесполезно, потому что оно не дает нам способа создания жестких экземпляров. [2] К счастью, многие предположения о среднем случае, используемые в криптографии (включая RSA , дискретный журнал и некоторые проблемы с решеткой ), могут быть основаны на предположениях наихудшего случая посредством редукции от наихудшего случая к среднему. [3]
Фальсифицируемость
Желательной характеристикой предположения о вычислительной сложности является опровержимость , т. Е. Если бы предположение было ложным, то его можно было бы доказать. В частности, Наор (2003) ввел формальное понятие криптографической фальсифицируемости. [4] Грубо говоря, предположение о вычислительной сложности считается опровергнутым, если оно может быть сформулировано в терминах задачи: интерактивный протокол между противником и эффективным проверяющим, где эффективный противник может убедить проверяющего принять его тогда и только тогда, когда предположение неверно.
Общие предположения о криптографической стойкости
Используется множество предположений о криптостойкости. Это список некоторых из наиболее распространенных и некоторых криптографических протоколов, которые их используют.
Целочисленная факторизация
Учитывая составное число , и в частности тот, который является произведением двух больших простых чисел , задача целочисленной факторизации состоит в том, чтобы найти а также (в общем, найти простые числа такой, что ). Основная открытая проблема - найти алгоритм для целочисленной факторизации, который работает за время, полиномиальное от размера представления (). Безопасность многих криптографических протоколов основывается на предположении, что целочисленная факторизация сложна (т.е. не может быть решена за полиномиальное время). Криптосистемы безопасность которых эквивалентна этому предположению включают криптосистемы Рабина и криптосистемы Окамото-Учияма . Многие другие криптосистемы полагаются на более сильные предположения, такие как RSA , проблемы остаточности и скрытие Phi .
Проблема RSA
Учитывая составное число , экспонента и номер , проблема RSA состоит в том, чтобы найти . Предполагается, что проблема сложна, но становится легче, если учесть факторизацию. В RSA криптосистемы ,является открытым ключом , это шифрование сообщения , а факторизация - секретный ключ, используемый для дешифрования.
Проблемы остаточности
Учитывая составное число и целые числа , проблема остаточности состоит в том, чтобы определить, существует ли (или найти) такой, что
Важные частные случаи включают в себя задачу квадратичного residuosity и проблемы композита residuosity принятия решения . Как и в случае с RSA, эта проблема (и ее частные случаи) предполагается трудной, но становится легкой с учетом факторизации. Некоторые криптосистемы, которые полагаются на твердость проблем остаточности, включают:
- Криптосистема Гольдвассера – Микали (квадратичная проблема редифференциальности)
- Генератор Блюма-Блюма-Шуба (квадратичная задача повторности)
- Криптосистема Пайе (решающая проблема составной остаточности)
- Криптосистема Бенало (проблема более высокой остаточности)
- Криптосистема Наккаша – Стерна (проблема более высокой остаточности)
Предположение о сокрытии фи
Для составного числа , неизвестно, как эффективно вычислить его функцию Эйлера . Предположение о сокрытии фи предполагает, что трудно вычислить, и, более того, даже вычисляя любые простые множители трудно. Это предположение используется в протоколе Cachin – Micali – Stadler PIR . [5]
Проблема дискретного журнала (DLP)
Данные элементы а также из группы , задача дискретного журнала запрашивает целое число такой, что . Проблема дискретного журнала не может быть сопоставима с целочисленной факторизацией, но их вычислительные сложности тесно связаны .
Большинство криптографических протоколов, связанных с проблемой дискретного журнала, фактически полагаются на более сильное предположение Диффи – Хеллмана : данные элементы группы, где генератор и случайные целые числа, трудно найти . Примеры протоколов, использующих это предположение, включают исходный обмен ключами Диффи-Хеллмана , а также шифрование Эль-Гамаля ( которое опирается на еще более надежный вариант Решающего Диффи-Хеллмана (DDH) ).
Многолинейные карты
Полилинейная карта является функцией (где являются группы ) , такие , что для любого а также ,
- .
Для криптографических приложений хотелось бы построить группы и карта такие, что отображение и групповые операции на могут быть вычислены эффективно, но проблема дискретного журнала на все еще сложно. [6] Некоторые приложения требуют более сильных предположений, например, полилинейные аналоги предположений Диффи-Хеллмана.
В частном случае , билинейные карты с достоверной безопасностью были построены с использованием пар Вейля и Тейта . [7] Дляв последние годы было предложено много конструкций, но многие из них также были сломаны, и в настоящее время нет единого мнения о безопасном кандидате. [8]
Некоторые криптосистемы, которые полагаются на предположения полилинейной жесткости, включают:
- Схема Боне-Франклина (блинеарная схема Диффи-Хеллмана)
- Boneh – Lynn – Shacham (блинеарная система Диффи-Хеллмана)
- Гарг-Джентри-Халеви-Райкова-Сахай-Уотерс кандидат на неразличимость обфускации и функционального шифрования (многолинейные головоломки) [9]
Проблемы с решеткой
Самая фундаментальная вычислительная проблема на решетках - это задача кратчайших векторов (SVP) : задана решетка, найти кратчайший ненулевой вектор . Большинство криптосистем требуют более строгих предположений о вариантах SVP, таких как задача кратчайших независимых векторов (SIVP) , GapSVP , [10] или Unique-SVP. [11]
Наиболее полезное предположение о твердости решетки в криптографии относится к проблеме обучения с ошибками (LWE): даны образцы для, где для некоторой линейной функции , легко научиться используя линейную алгебру. В задаче LWE на входе алгоритма есть ошибки, т.е. для каждой парыс некоторой малой вероятностью. Считается, что ошибки делают проблему неразрешимой (для соответствующих параметров); в частности, известны сокращения от худшего случая к среднему по сравнению с вариантами SVP. [12]
Для квантовых компьютеров задачи разложения на множители и дискретного логарифма просты, но проблемы с решеткой считаются сложными. [13] Это делает некоторые криптосистемы на основе решеток кандидатами для постквантовой криптографии .
Некоторые криптосистемы, которые полагаются на твердость проблем решетки, включают:
- NTRU (как NTRUEncrypt, так и NTRUSign )
- Большинство кандидатов на полностью гомоморфное шифрование
Допущения некриптографической стойкости
Помимо их криптографических приложений, предположения о твердости используются в теории вычислительной сложности, чтобы предоставить доказательства математических утверждений, которые трудно доказать безоговорочно. В этих приложениях доказывается, что предположение о сложности подразумевает некое желаемое теоретико-сложное утверждение, вместо того, чтобы доказывать, что само утверждение истинно. Самым известным предположением этого типа является предположение, что P ≠ NP , [14], но другие включают гипотезу экспоненциального времени , [15] гипотезу о заложенной клике и гипотезу об уникальных играх . [16]
-сложные проблемы
Известно, что многие вычислительные задачи наихудшего случая являются сложными или даже завершенными для некоторого класса сложности. , В частности , NP-трудной (но часто также PSPACE-жесткий , PPAD твердости и т.д.). Это означает, что они по крайней мере так же сложны, как любая проблема в классе.. Если проблема-жесткий (относительно полиномиального сокращения времени), то он не может быть решен с помощью алгоритма полиномиального времени, если только предположение вычислительной сложности ложно.
Гипотеза экспоненциального времени (ETH) и варианты
Экспоненциальные гипотезы времени (ETH) является усилением изпредположение твердости, которое предполагает, что задача булевой выполнимости не только не имеет алгоритма полиномиального времени, но, кроме того, требует экспоненциального времени (). [17] Еще более сильное предположение, известное как сильная гипотеза экспоненциального времени (SETH), предполагает, что k {\ displaystyle k} -SAT требует время, где . ETH, SETH и связанные с ними допущения о вычислительной сложности позволяют выводить мелкозернистые результаты сложности, например результаты, которые различают полиномиальное время и квазиполиномиальное время , [1] или даже против . [18] Такие предположения также полезны при параметризованной сложности . [19]
Допущения о средней твердости
Предполагается, что некоторые вычислительные проблемы являются сложными в среднем для определенного распределения экземпляров. Например, в задаче с установленной кликой входом является случайный граф, выбранный путем выборки случайного графа Эрдеша – Реньи, а затем « вставки» случайного графа.-clique, т.е. соединительный равномерно случайные узлы (где ), а цель - найти посаженный -clique (уникальный whp). [20] Еще одним важного примером является Фейга «ы Гипотеза, которая представляет собой вычислительная твердость предположение о случайных экземплярах 3-SAT (дискретизированных поддерживать соотношение удельного из пунктов к переменным). [21] Допущения о вычислительной сложности в среднем случае полезны для доказательства твердости в среднем случае в таких приложениях, как статистика, где существует естественное распределение по входным данным. [22] Кроме того, предположение о жесткости клики также использовалось, чтобы различать полиномиальную и квазиполиномиальную временную сложность других задач в наихудшем случае [23], аналогично гипотезе экспоненциального времени .
Уникальные игры
Проблема уникального покрытия этикетки - это проблема удовлетворения ограничений, где каждое ограничение включает две переменные , и для каждого значения есть уникальная ценность это удовлетворяет . Определить, могут ли быть выполнены все ограничения, несложно, но гипотеза уникальной игры (UGC) постулирует, что определение того, являются ли почти все ограничения (-доля для любой постоянной ) могут быть удовлетворены или почти ни один из них (-fraction) можно удовлетворить NP-hard. [16] Часто известно, что проблемы аппроксимации NP-трудны в предположении UGC; такие проблемы называются UG-hard. В частности, если предположить, что UGC существует полуопределенный алгоритм программирования , который обеспечивает гарантии оптимального приближения для многих важных проблем. [24]
Расширение небольшого набора
С проблемой уникального покрытия этикеток тесно связана проблема расширения малого набора (SSE) : задан график., найдите небольшой набор вершин (размером ), рёберное расширение которого минимально. Известно, что если SSE трудно подобрать, то и Unique Label Cover - тоже. Следовательно, гипотеза о расширении малого множества , которая постулирует, что SSE трудно аппроксимировать, является более сильным (но тесно связанным) предположением, чем гипотеза уникальной игры. [25] Некоторые задачи аппроксимации известны как SSE-трудные [26] (то есть, по крайней мере, такие же сложные, как аппроксимация SSE).
Гипотеза 3SUM
Учитывая набор чисел, задача 3SUM спрашивает, существует ли тройка чисел, сумма которых равна нулю. Существует алгоритм квадратичного времени для 3SUM, и было высказано предположение, что ни один алгоритм не может решить 3SUM за «действительно субквадратичное время»: гипотеза 3SUM - это предположение о вычислительной сложности, что нет-временные алгоритмы для 3SUM (для любой константы ). Эта гипотеза полезна для доказательства почти квадратичных нижних оценок для нескольких задач, в основном из вычислительной геометрии . [27]
Смотрите также
- Уровень безопасности
Рекомендации
- ^ а б Браверман, Марк ; Ко, Ён Кун; Вайнштейн, Омри (2015). "Приближение наилучшего равновесия по Нэшу в-время нарушает гипотезу экспоненциального времени ". Симпозиум по дискретным алгоритмам (SODA) . Общество промышленной и прикладной математики . стр. 970–982. doi : 10.1137 / 1.9781611973730.66 . ISBN 978-1-61197-374-7.
- ^ Дж. Кац и Ю. Линделл, Введение в современную криптографию (серия Chapman and Hall / Crc Cryptography and Network Security Series), Chapman and Hall / CRC, 2007.
- ^ Гольдвассер, Шафи ; Калаи, Яэль Тауман (2016). «Криптографические предположения: документ с изложением позиции». Конференция по теории криптографии (TCC) 2016 . Springer. С. 505–522. DOI : 10.1007 / 978-3-662-49096-9_21 .
- ^ Наор, Мони (2003). «О криптографических предположениях и проблемах». В Боне, Дэн (ред.). Достижения в криптологии - CRYPTO 2003: 23-я ежегодная международная конференция по криптологии, Санта-Барбара, Калифорния, США, 17-21 августа 2003 г., Материалы . Конспект лекций по информатике. 2729 . Берлин: Springer. С. 96–109. DOI : 10.1007 / 978-3-540-45146-4_6 . Руководство по ремонту 2093188 .
- ^ Качин, Кристиан; Микали, Сильвио; Стадлер, Маркус (1999). Стерн, Жак (ред.). «Вычислительный поиск частной информации с полилогарифмической связью». Конспект лекций по информатике . Springer. 1592 : 402–414. DOI : 10.1007 / 3-540-48910-X . ISBN 978-3-540-65889-4. S2CID 29690672 .
- ^ Бонех, Дэн ; Сильверберг, Алиса (2002). «Применение полилинейных форм в криптографии» . Архив криптологии ePrint .
- ^ Дутта, Ратна; Баруа, Рана; Саркар, Палаш (2004). «Криптографические протоколы на основе пар: обзор» . Архив криптологии ePrint .
- ^ Альбрехт, Мартин Р. "Схема градуированного кодирования уже нарушена?" . Проверено 22 марта 2018 .
- ^ Гарг, Санджам; Джентри, Крейг; Халеви, Шай; Райкова, Марьяна; Сахай, Амит; Уотерс, Брент (2016). «Возможное запутывание неразличимости и функциональное шифрование для всех схем» (PDF) . SIAM Journal on Computing . СИАМ. 45 (3): 882–929. DOI : 10.1137 / 14095772X .
- ^ Пайкерт, Крис (2009). «Криптосистемы с открытым ключом из наихудшей задачи кратчайшего вектора: расширенная аннотация». Материалы 41-го ежегодного симпозиума ACM по теории вычислений (STOC) . С. 333–342. DOI : 10.1145 / 1536414.1536461 .
- ^ Айтай, Миклош ; Дворк, Синтия (1997). «Криптосистема с открытым ключом с эквивалентностью наихудшего и среднего случая». Материалы 29-го ежегодного симпозиума ACM по теории вычислений (STOC) . С. 284–293. DOI : 10.1145 / 258533.258604 .
- ^ Регев, Одед (2010). «Проблема обучения с ошибками (Приглашенный опрос)». Конференция по вычислительной сложности (CCC) 2010 . С. 191–204. DOI : 10,1109 / CCC.2010.26 .
- ^ Пайкерт, Крис (2016). «Десятилетие решетчатой криптографии» . Основы и направления теоретической информатики . 10 (4): 283–424. DOI : 10.1561 / 0400000074 .
- ^ Фортноу, Лэнс (2009). «Статус проблемы P против NP» (PDF) . Коммуникации ACM . 52 (9): 78–86. DOI : 10.1145 / 1562164.1562186 . S2CID 5969255 . Архивировано из оригинального (PDF) 24 февраля 2011 года..
- ^ Woeginger, Герхард (2003). «Точные алгоритмы для NP-сложных задач: обзор». Комбинаторная оптимизация - Эврика, сжимайся! . 2570 . Springer-Verlag. С. 185–207. DOI : 10.1007 / 3-540-36478-1_17 ..
- ^ а б Хот, Субхаш (2010). «О гипотезе об уникальных играх». Proc. 25-я конференция IEEE по вычислительной сложности (PDF) . С. 99–121. DOI : 10,1109 / CCC.2010.19 ..
- ^ Impagliazzo, Рассел ; Патури, Рамамохан (1999). «Сложность k-SAT». Proc. 14-я конференция IEEE. по вычислительной сложности . С. 237–240. DOI : 10,1109 / CCC.1999.766282 .
- ^ Аббуд, Амир; Василевска-Уильямс, Вирджиния ; Вейманн, Орен (2014). «Последствия более быстрого совмещения последовательностей». Автоматы, языки и программирование - 41-й международный коллоквиум, ICALP 2014 . С. 39–51. DOI : 10.1007 / 978-3-662-43948-7_4 .
- ^ Локштанов Даниил; Маркс, Даниил; Саураб, Сакет (2011). «Нижние оценки на основе гипотезы экспоненциального времени» . Бюллетень EATCS . 105 : 41–72.
- ^ Арора, Санджив ; Варак, Вооз (2009). Вычислительная сложность: современный подход . Издательство Кембриджского университета. С. 362–363. ISBN 9780521424264..
- ^ Файги, Уриэль (2002). «Связь между сложностью среднего случая и сложностью аппроксимации». Труды 34-го ежегодного симпозиума ACM по теории вычислений (STOC) . С. 534–543. DOI : 10.1145 / 509907.509985 .
- ^ Бертет, Квентин; Риголе, Филипп (2013). "Теоретические нижние оценки сложности для обнаружения разреженных главных компонент". COLT 2013 . С. 1046–1066.
- ^ Хазан, Элад; Krauthgamer, Роберт (2011). «Насколько сложно приблизиться к наилучшему равновесию по Нэшу?». SIAM Journal on Computing . 40 (1): 79–91. CiteSeerX 10.1.1.139.7326 . DOI : 10.1137 / 090766991 .
- ^ Рагхавендра, Прасад (2008). «Оптимальные алгоритмы и результаты непроксимируемости для каждого CSP?». 40-й ежегодный симпозиум ACM по теории вычислений (STOC) 2008 . С. 245–254. DOI : 10.1145 / 1374376.1374414 .
- ^ Рагхавендра, Прасад; Steurer, Дэвид (2010). «Расширение графа и гипотеза уникальных игр». 42-й ежегодный симпозиум ACM по теории вычислений (STOC) 2010 . С. 755–764. DOI : 10.1145 / 1806689.1806792 .
- ^ Ву, Ю; Austrin, Per; Питасси, Тониан; Лю, Дэвид (2014). «Неприблизимость ширины дерева и связанные с этим проблемы» . Журнал исследований искусственного интеллекта . 49 : 569–600. DOI : 10.1613 / jair.4030 .
- ^ Василевска Уильямс, Вирджиния (2018). «О некоторых тонких вопросах алгоритмов и сложности». ICM 2018 (PDF) .