PPAD и Quantum

Сегодня в Нью-Йорке и во всем мире отмечается день рождения Христоса Пападимитриу. Это хорошая возможность задать вопрос об отношениях между классом сложности Christos PPAD (и его смежными классами) и квантовыми компьютерами. В своей знаменитой работе 1994 года Пападимитриу представил и систематически изучил несколько важных классов сложности, таких как PLS, PPAD и другие. (Документ Пападимитриу опирался на некоторые более ранние статьи и, в частности, как отметил Авиад, PLS был представлен Джонсоном-Пападимитриу-Яннакакисом в 1988 году.)

Мой главный вопрос:

Дают ли квантовые компьютеры какое-то преимущество для проблем в $PPAD$ ? или в $PLS$ ? или в $PLS \cap PPAD$ ? так далее...

Другой вопрос, есть ли какие-то квантовые аналоги PLS и PPAD и других классов Кристоса.

Я отмечаю, что недавние замечательные связи PPAD с криптографией были обнаружены в этих статьях: « О криптографической стойкости определения равновесия Нэша по Н. Битанскому, О. Панету, А. Розену». Может ли твердость PPAD основываться на стандартных криптографических предположениях? от A Розен, G Segev, I Shahaf, и находя Равновесие Нэша не легче , чем ломать Fiat-Шамира по Arka Раи Чоудхури, Павел Hubáček, Chethan Kamath, Кшиштоф Pietrzak, Алон Розен, Guy Rothblum. Я также отмечаю, что, по моему мнению, классы Христоса особенно близки к математике и математическим доказательствам.

Обновление: Рон Ротблум прокомментировал (через FB), что результаты Choudhuri, Hubacek, Kamath, Pietrzak, Rosen и G. Rothblum предполагают, что PPAD, вероятно, находится за пределами возможностей квантовых компьютеров. (Я буду рад видеть подробный ответ, объясняющий это.)

Еще один комментарий: связанный с этим хороший вопрос заключается в том, имеет ли эффективный квантовый алгоритм поиск поглотителя в уникальной одиночной ориентации $n$ куба. (Я думаю, что эта задача проще, чем $PLS$ но я не уверен, как она связана с $PPAD$ ) Это связано с поиском найти квантовое преимущество для $LP$ см. Https://cstheory.stackexchange.com. / а / 767/712 .

С днем ​​рождения, Христос!

Два ответа, которые я узнал, когда писал в блоге об этом вопросе

1. Нет : в вариантах черного ящика сложность квантового запроса / связи обеспечивает квадратичное ускорение Гровера, но не более того. Как указывает Рон, это распространяется на вычислительную сложность при вероятных предположениях.

2. Возможно : равновесие по Нэшу является, пожалуй, главной проблемой "классов Христоса". Здесь предоставление игрокам доступа к квантовой запутанности предлагает новую концепцию решения «квантового коррелированного равновесия», которая обобщает равновесие Нэша. Его сложность все еще открыта. Посмотрите эту классную статью Алана Декельбаума.

И одно историческое примечание: PLS был фактически представлен Джонсоном-Пападимитриу-Яннакакисом в 1988 году .

$\mathsf{PPAD}$

На высоком уровне CHKPRR создает распределение по экземплярам в конце строки, где для поиска решения требуется либо:

• нарушить надежность системы доказательства, полученной путем применения эвристики Fiat-Shamir к известному протоколу sumcheck, или
• $\sharp \mathsf{P}$

$\sharp \mathsf{SAT}$$\mathsf{PPAD}$

$\sum_{\vec z \in \{0,1\}^n} f(\vec z) = x$$f$$n$$\mathbb{F}$, который будет отлично работать в этой настройке: протокол sumcheck . Преобразование интерактивного доказательства в неинтерактивное (поддержание публичной проверяемости и компактности) - это именно то, что делает эвристика Fiat-Shamir.

Создание Fiat-Shamir

Эвристика Fiat-Shamir очень проста: исправьте некоторую хеш-функцию, начните с публичного интерактивного доказательства и замените каждое случайное сообщение верификатора хэшем всей расшифровки. Тогда возникает вопрос, при каком свойстве хеш-функции мы можем доказать, что полученный протокол все еще является надежным (обратите внимание, что он больше не может быть статистически достоверным; надежда состоит в том, что он остается вычислительно надежным).

Прежде чем подробно остановиться на этом, позвольте мне обратиться к вашему комментарию:

Я до сих пор не понимаю 1. Конечно, есть предположения криптографической твердости, которые не применяются в квантовом случае. Что делает «сломать Fiat-Shamir» для КК непохожим, скажем, «сломать RSA».

Я надеюсь, что описание высокого уровня должно прояснить, что «сломать Fiat-Shamir» и «сломать RSA» не совсем сопоставимые проблемы. RSA - это конкретное, конкретное допущение твердости, и если вы можете вычислить большие целые числа, вы можете нарушить его.

$\mathsf{PPAD}$основной хэш-функции. На интуитивном уровне это не то, в чем хороши квантовые компьютеры, потому что это проблема, которая не обязательно имеет сильную структуру, которую она могла бы использовать (в отличие, например, от дискретного логарифма и RSA): хэш-функции обычно могут быть очень "неструктурированный".

В более конкретном смысле, есть две естественные альтернативы при выборе хеш-функции для создания экземпляра Fiat-Shamir:

Эвристический, конкретно эффективный подход:

выберите свою любимую хеш-функцию, скажем, SHA-3. У нас, конечно, нет доказательств того, что создание экземпляра Fiat-Shamir с SHA-3 доставляет нам трудную проблему; но мы также не знаем ни о какой нетривиальной атаке на надежность систем доказательства, полученной при применении Fiat-Shamir с SHA-3 к невырожденной интерактивной системе доказательства. Это распространяется и на квантовую настройку: мы не знаем ни о какой квантовой атаке, которая лучше, чем обычное квадратичное ускорение, заданное алгоритмом Гровера. После десятилетий попыток криптоанализа, консенсус в криптографическом сообществе в том , что квантовый алгоритм не кажется , насколько мы можем видеть, чтобы обеспечить суперполиномиальные ускорения для «Minicrypt стиле» примитивов (хэш - функцию, PRGS, блочные шифры, и т.д.) без некоторая сильная алгебраическая структура - например, SHA-2, SHA-3, AES и т. д.

Подходящий подход к безопасности:

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

$R$$K$$x$$(x, H_K(x)) \in R$$R$$R$

Теперь вопрос состоит в том, как построить неразборчивые хеш-функции для отношений, которые нас интересуют, и в этом конкретном контексте для отношений, связанных с протоколом sumcheck. Здесь недавнее направление работы (по существу 1 , 2 , 3 , 4 , 5 , 6 ) показало, что для многих интересующих отношений можно фактически построить корреляционные неразрешимые хеш-функции при предположениях на основе решетки.

$\mathsf{PPAD}$

Мы не совсем там, на самом деле. Недавний прорывный результат Пейкерта и Шихиана (последняя статья в списке, который я дал ранее) показал, что для важных отношений мы можем построить корреляционно-неразрешимую хеш-функцию в хорошо известных задачах решетки, таких как обучение с ошибкой или проблема SIS. ; однако, отношение sumcheck не охватывается этой работой.

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

Давайте разберем это предположение:

• Полностью гомоморфное шифрование (FHE) является примитивом, который мы знаем, как построить при различных предположениях решетки. Если схема должна оценивать только схемы ограниченного размера, мы фактически знаем, как построить ее в соответствии со стандартным обучением с допущением ошибки.
• Циркуляр безопасности утверждает, что FHE должно быть трудно взломать, даже если он используется для шифрования своего собственного секретного ключа. Это сильнее, чем обычное понятие безопасности, которое не допускает сообщений, зависящих от ключа. Это серьезная и давняя открытая проблема - построить FHE с круговой безопасностью при стандартном предположении решетки, таком как LWE. Тем не менее, спустя десятилетие после первого построения GHTR и большого количества попыток криптоанализа, круговая безопасность установленных кандидатов FHE сама по себе стала относительно безопасным предположением (даже в отношении квантовых компьютеров), и мы не знаем ни о какой атаке, использующей ключевые шифрование нетривиальным способом.
• $2^{\omega(\log \lambda) - \lambda}$$\lambda$$2^{c\lambda}$$c < 1$$2^{-c \lambda}$$c < 1$
• Наконец, мы хотим, чтобы все вышеперечисленное сохранялось, если мы разрешаем атакующему суперполиномиальное время выполнения. Это все еще соответствует тому, чего могут достичь известные алгоритмы.

$\mathsf{PPAD}$

Конечно, одним из главных открытых вопросов, оставленных CHKPRR, является построение коррелируемой хеш-функции для отношения суммирования при лучшем предположении на основе решетки - в идеале, предположении LWE. Это кажется нетривиальным, но не неправдоподобным, учитывая, что это очень недавнее направление работы, где многие удивительные результаты уже были достигнуты для других интересных отношений.