Семантическая безопасность может быть определена с помощью эксперимента/игры по различимости, которую мы помним следующим образом:
Позволять $(Э,Д)$ быть схема шифрования. После того, как претендент выбирает параметр безопасности $n$ и случайный ключ $к$, противник (семантическая безопасность) выбирает два сообщения $m_0, m_1$ которые зависят от $n$. Претендент случайным образом выбирает бит $b \in \{0,1\}$, обеспечивает $E_k(m_b)$ противнику, который затем должен решить, $b$ является $0$ или же $1$.
Вопрос: Сообщения $m_0$ и $m_1$ имеют полиномиальную длину в $n$, но являются ли они на самом деле вычислимыми функциями $n$? т. е. вычисляет ли противник $m_0$ и $m_1$ с помощью какой-нибудь машины Тьюринга, работающей за полиномиальное время?
Подозреваю, что ответа нет, они не вычислимы (но все же полиномиальной длины). Я основываю это на попытке доказать свойства семантической безопасности, такие как невозможность угадывания битов и восстановления сообщений и т. д. Я также думаю, что это точно указано в книге Гольдрейха, где нет генерации сообщений, а только спецификация их полиномиальной длины (но он вместо этого используются семейства схем, с которыми я не знаком), но в Katz-Lindell кажется, что в этом определении есть двусмысленность.
