Регистрация Войти
Рейтинг:1
Henry avatar Crypto

Может ли злоумышленник отличить QROM от ROM одним запросом?

флаг eg
Henry

Я признаю, что QROM отличается от ROM (которое можно рассматривать как особый QROM, который выполняет измерение на входе). Например, можно найти прообраз для произвольного значения с помощью $О(Н)$ запросы к ПЗУ при $O(\sqrtN)$ запросы к QROM по алгоритму Гровера. Однако для этого требуется более $O(\sqrt N)$ запросы. Что делать, если требуется только один запрос? В более общем смысле, существует ли верхняя граница преимущества их различения, связанная с (полиномиальным) количеством запросов? $q$?

51
0 + 0
Рейтинг:1
Daniel S avatar Crypto
флаг ru
Daniel S

Только $O(1)$ запросы необходимы, чтобы отличить оракул QROM от оракула измерения и ПЗУ.

Нет необходимости применять алгоритм Гровера ко всему выходному пространству. Мы можем выполнить Гровера для одного выходного бита (скажем, для старшего бита 1), и после одной итерации с большой вероятностью мы измерим вход, который даст результат с ведущим битом 1.

С другой стороны, если у нас есть фальшивый оракул, который измеряет ввод и возвращает классический вывод, мы будем измерять ввод, который в половине случаев дает вывод с ведущим битом 0.

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.