Я самостоятельно изучаю «Введение в современную криптографию (2-е издание)».
Я пытаюсь понять, насколько верно решение следующей проблемы:
Докажите, что схема, удовлетворяющая определению 2.5, должна иметь $|К| \geq |M|$ без использования леммы 2.4. В частности, пусть $\Пи$ быть произвольной схемой шифрования с $|К| < |М|$ Показать $А$ для которого $Pr[PrivK^{eav}_{A,\Pi} = 1] > \frac{1}{2}$
Некоторые обозначения:
Определение 2.5:
Схема шифрования $\Pi = (Gen, Enc, Dec)$ с местом для сообщения $ млн $ совершенно неразличимы, если для каждого $А$ он считает, что
$$
Pr[Priv^{eav}_{A,\Pi} = 1] = \frac{1}{2}
$$
Обозначение говорит, что вероятность того, что противник правильно угадает входное сообщение, должна быть равна $\фракция{1}{2}$ для совершенной неразличимости держать.
Однако решение не имеет смысла для меня.
Решение:
Учитывая следующее $А$: выходная форма $m_0, m_1 \in M$. При получении зашифрованного текста $с$, проверить (исчерпывающим перебором), существует ли ключ $к$ такой, что $Dec_k(c) = m_0$. Если да, выведите 0; иначе вывод 1.
Это решение кажется проблематичным, потому что оно говорит, что злоумышленник может выполнять исчерпывающий поиск по ключевому пространству. Но если бы это было так, для любого эксперимента с неразличимостью у нас мог бы быть противник, который просто выполняет изнурительный поиск в пространстве ключей, чтобы определить, во что дешифруется зашифрованный текст.
Кто-нибудь понимает, что происходит?
