Регистрация Войти
Рейтинг:2
paul lacher avatar Crypto

Должны ли Enc и Dec быть псевдослучайными функциями, чтобы схема была безопасной CPA?

флаг br
paul lacher

В настоящее время я просматриваю прошлые финальные вопросы в качестве упражнений для своего экзамена, и решений нет.

Вопрос, который я сейчас делаю:

Пусть = (Enc, Dec, Gen) будет CPA-безопасной схемой шифрования. Докажите или опровергните следующие два утверждения: а) Enc должна быть псевдослучайной функцией. б) Dec должен быть псевдослучайной функцией.

Для а) интуитивно я знаю, что это должно быть псевдослучайным, но я не уверен, как доказать это формальным способом. Поскольку злоумышленник имеет доступ к оракулу шифрования, мы хотим убедиться, что он не может различать разные сообщения и не узнает никакой полезной информации о схеме. А раз псевдослучайность неотличима от случайной, то она необходима?

Для б) я не думаю, что это правда, просто потому, что на основе CPA-атак они на самом деле не включают дешифрование, поэтому нет смысла использовать псевдослучайную функцию. Однако, если Enc является псевдослучайным, разве не потребуется псевдослучайная функция для расшифровки?

Может ли кто-нибудь сообщить мне, правильно ли это мышление, если нет, не могли бы вы дать объяснение?

Спасибо.

61
0 + 0
Morrolan avatar
флаг ng
Morrolan
Ваша интуиция относительно а) в значительной степени верна. Я предполагаю, что вы формализовали IND-CPA-безопасность с помощью «игры», в которую играет противник? Если да, то считайте, что функция шифрования вашей схемы полностью детерминирована, то есть $Enc_{k}(m)$ (с помощью оракула шифрования) всегда будет давать один и тот же результат для фиксированного ключа $k$ и сообщения $m$. Можете ли вы тогда определить противника $A$, который имеет значительное преимущество в победе в игре?
0
Ответить
Morrolan avatar
флаг ng
Morrolan
Для b) подумайте, что произошло бы, если бы функция дешифрования схемы была недетерминированной. То есть $Dec_k(c)$ не всегда будет давать один и тот же результат для фиксированного ключа $k$ и зашифрованного текста $c$. Будет ли полезна такая схема? В частности, как это повлияет, например. свойство правильности схемы?
0
Ответить
paul lacher avatar
флаг br
paul lacher
@Morrolan Мы определили это как P (успех)
0
Ответить
paul lacher avatar
флаг br
paul lacher
@Morrolan Ооо, имеет смысл б), спасибо!
0
Ответить
paul lacher avatar
флаг br
paul lacher
@Morrolan Может ли то же самое относиться к безопасности IND-CCA? Я не уверен, поскольку для CCA у противника есть доступ к оракулу дешифрования, должен ли Dec быть PRF, но это на самом деле не имеет смысла, поскольку мы не хотим получать перепутанное сообщение. Таким образом, Enc все равно потребуется PRF, поскольку в контексте безопасности CCA мы видели его в настройке открытого ключа, и если случайности нет, то он становится детерминированным.
0
Ответить
Morrolan avatar
флаг ng
Morrolan
«Если бы это было детерминировано, то [...] у злоумышленника было бы более 1/2 шансов различить разные открытые тексты». Да, в значительной степени. :) Для экзамена вы можете точно описать шаги, предпринимаемые противником $A$, например. каким образом $A$ вызывает оракул шифрования и как они используют этот вывод, чтобы отличить, является ли полученный ими зашифрованный текст $c$ шифрованием $m_0$ или $m_1$, которое они предоставили. Сделав это, вы также можете легко определить точный шанс $A$ правильно различить это.
0
Ответить
Morrolan avatar
флаг ng
Morrolan
Для безопасности IND-CCA вы можете рассуждать точно так же, как и для IND-CPA.
0
Ответить
paul lacher avatar
флаг br
paul lacher
@Morrolan Спасибо! Это действительно помогло мне прояснить ситуацию.
0
Ответить
Рейтинг:1
Chris Peikert avatar Crypto
флаг in
Chris Peikert

Некоторые подсказки:

Псевдослучайная функция должна быть детерминированный функции от его ключа и входа к его выходу. Более того, выходные данные должны «представляться случайными и независимыми», когда ключ выбирается случайным образом (и фиксируется), а входы выбираются злоумышленником.

Для (а): может ли Enc быть таким детерминированным в схеме шифрования с защитой CPA? Почему или почему нет?

Для (b): в схеме шифрования CPA-secure со случайным $ск$, должны быть выходы $\text{дек}_{ск}(\cdot)$ кажутся случайными и независимыми, когда атакующий изменяет входные данные? Почему или почему нет?

0 + 0
paul lacher avatar
флаг br
paul lacher
ооо, ок спасибо!
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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