Возможно ли правильно расшифровать другой ключ?

Я думаю о CPA-безопасности для симметричного шифрования.

Так $А$ получает доступ к оракулу шифрования и может продолжать задавать запросы (фаза обучения). На этом этапе обучения он спрашивает $m_i$ и получает обратно $y_i$. Он также может проверить, может ли он найти ключ, который расшифровывает то же самое сообщение, которое он зашифровал, просто проверьте, может ли он $\Pi.\mathsf{Dec}(k, y_i) = m_i$ для некоторых $к$ что $А$ догадки. Он также может сделать то же самое во время фазы вызова и посмотреть, $у^*$ он получил обратно расшифровывает любой из $м_0,м_1$.

Теперь я могу предположить, что это трудно найти $к$ (выбирается равномерно случайным образом), но можно ли найти другой ключ $к'$ что происходит с некоторыми обучающими запросами? Я думаю, это не должно происходить с более чем незначительной вероятностью, если $\Пи$ является CPA-безопасным, но это может случиться, верно?

Мой вопрос может быть похож на: Можно ли расшифровать зашифрованный текст другим закрытым ключом?

В симметричной криптографии то, что вы описали, может произойти, по крайней мере, теоретически. Это называется атакой Consistent Key Recovery, в отличие от более распространенной атаки Target Key Recovery. Восстановление согласованного ключа — это когда злоумышленник находит ключ, который согласуется с любой парой ввода-вывода. Восстановление целевого ключа — это когда злоумышленник находит фактический ключ (который будет соответствовать всем парам ввода-вывода). Если злоумышленник проводит атаку с исчерпывающим поиском ключа, он, скорее всего, встретит согласованный ключ (который будет работать для одного или нескольких запросов) до того, как он встретит фактический ключ (который будет работать для всех запросов).

Вопрос заключался в том, насколько велик разрыв между преимуществом нахождения последовательного ключа и преимуществом в нахождении целевого ключа. Я нашел одну лекцию Белларе, в которой говорится об этой проблеме (но ничего в письменном виде). В этой лекции Белларе упоминает, что пробела почти нет (то есть почти такое же преимущество), если блочный шифр является настоящим блочным шифром (например, AES). Он сказал, что такой вывод основан на эвристических или эмпирических данных. Если преимущества почти одинаковы, это означает, что целевой ключ является ЕДИНСТВЕННЫМ ключом, совместимым с запросами ввода-вывода. Но теоретически непротиворечивый ключ (отличный от целевого ключа) возможен и может быть восстановлен задолго до восстановления целевого ключа. Вы можете посмотреть весь лекция поскольку я уверен, что Белларе может объяснить это НАМНОГО лучше, чем я.