ГЧП (сложность)
В теории сложности вычислений класс сложности PPP ( принцип полиномиальной ячейки ) является подклассом TFNP . Это класс задач поиска, целостность которых можно доказать, применив принцип группировки . Христос Пападимитриу представил его в той же статье, в которой были представлены PPAD и PPA. [1] PPP содержит как PPAD , так и PWPP (полиномиальный слабый принцип группировки) в качестве подклассов. Эти классы сложности представляют особый интерес в криптографии, поскольку они тесно связаны с криптографическими примитивами, такими как односторонние перестановки и устойчивые к коллизиям хэш-функции .
Определение
[ редактировать ]PPP - это набор всех задач вычисления функций, которые допускают полиномиальное сведение к задаче PIGEON , определяемой следующим образом:
- Дана логическая схема имеющий тот же номер входных битов в качестве выходных битов, найдите либо входной который отображается на выходе или два разных входа которые сопоставлены с одним и тем же выходом .
Задача является PPP- полной , если PIGEON также сводится к ней за полиномиальное время. Обратите внимание, что принцип «ячейки» гарантирует, что PIGEON является полным. Мы также можем определить WEAK-PIGEON , для которого слабый принцип группировки гарантирует целостность. PWPP — это соответствующий класс задач, сводимых к нему за полиномиальное время. [2] WEAK-PIGEON — это следующая проблема:
- Дана логическая схема имея входные биты и выходные биты, найти такой, что .
Здесь образ схемы строго меньше ее области определения, поэтому схема гарантированно неинъективна . WEAK-PIGEON сокращается до PIGEON путем добавления одного бита к выходу схемы, поэтому PWPP ППС.
Подключение к криптографии
[ редактировать ]Мы можем рассматривать схему в PIGEON как хэш-функцию, вычислимую за полиномиальное время. Следовательно, PPP — это класс сложности, который отражает сложность инвертирования или обнаружения коллизий в хеш-функциях. В более общем смысле, связь подклассов FNP с классами сложности с полиномиальным временем может использоваться для определения существования определенных криптографических примитивов и наоборот.
Например, известно, что если FNP = FP , то односторонних функций не существует. Аналогично, если ППС = FP, тогда односторонних перестановок не существует. [3] Следовательно, PPP (который является подклассом FNP) более точно отражает вопрос существования односторонних перестановок. Мы можем доказать это, сократив задачу обращения перестановки на выходе ГОЛУБНИ . Построить схему который вычисляет . С является перестановкой, решение PIGEON должно вывести такой, что , что подразумевает .
Отношения с PPAD
[ редактировать ]PPP содержит PPAD в качестве подкласса (строгое ограничение — открытая проблема). Это связано с тем, что End-of-the-Line , определяющий PPAD, допускает прямое полиномиальное сокращение времени до PIGEON . В End-of-the-Line входными данными является начальная вершина. в ориентированном графе где каждая вершина имеет не более одного преемника и не более одного предшественника, представленного функцией-преемником, вычислимой за полиномиальное время. . Определить схему чьи входные данные являются вершиной и чей вывод является его преемником, если таковой имеется, или если это не так. Если мы представим исходную вершину как битовая строка , эта схема является прямым сокращением End-of-the-Line до Pigeon , поскольку любое столкновение в обеспечивает погружение в .
Известные проблемы
[ редактировать ]Проблема равных сумм
[ редактировать ]Задача о равных суммах представляет собой следующую задачу. Данный целые положительные числа, сумма которых меньше , найдите два различных подмножества целых чисел, имеющих одинаковую сумму. Эта проблема содержится в PPP, но неизвестно, является ли он PPP-полным.
Проблема ограниченной SIS
[ редактировать ]Было показано , что проблема SIS с ограничениями (короткое целочисленное решение), которая является обобщением проблемы SIS из решетчатой криптографии, является полной для PPP. [4] До этой работы единственными задачами, которые были известны для PPP, были варианты PIGEON .
Целочисленная факторизация
[ редактировать ]Существуют рандомизированные сокращения за полиномиальное время от задачи факторизации целых чисел до WEAK-PIGEON . [5] Кроме того, согласно обобщенной гипотезе Римана также существуют детерминированные полиномиальные редукции. Однако до сих пор остается открытой проблема безусловного доказательства того, что факторизация целых чисел осуществляется в PPP.
Ссылки
[ редактировать ]- ^ Христос Пападимитриу (1994). «О сложности аргумента четности и других неэффективных доказательствах существования» (PDF) . Журнал компьютерных и системных наук . 48 (3): 498–532. дои : 10.1016/S0022-0000(05)80063-7 . Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 11 декабря 2009 г.
- ^ Эмиль Ержабек (2016). «Целочисленный факторинг и модульные квадратные корни». Журнал компьютерных и системных наук . 82 (2): 380–394. arXiv : 1207.5220 . дои : 10.1016/j.jcss.2015.08.001 .
- ^ Христос Пападимитриу (1994). «О сложности аргумента четности и других неэффективных доказательствах существования» (PDF) . Журнал компьютерных и системных наук . 48 (3): 498–532. дои : 10.1016/S0022-0000(05)80063-7 . Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 11 декабря 2009 г.
- ^ К. Сотираки, М. Зампитакис и Г. Зирделис (2018). «PPP-полнота со связью с криптографией». Учеб. 59-го симпозиума по основам информатики . стр. 148–158. arXiv : 1808.06407 . дои : 10.1109/FOCS.2018.00023 .
{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Эмиль Ержабек (2016). «Целочисленный факторинг и модульные квадратные корни». Журнал компьютерных и системных наук . 82 (2): 380–394. arXiv : 1207.5220 . дои : 10.1016/j.jcss.2015.08.001 .