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

Доказательство эквивалентности двух определений совершенной безопасности

флаг cn
Anon

Я пытаюсь доказать, что следующие два определения эквивалентны:

$\forall m\in M $ и $c\в C$ $\Pr[C=c \mid M=m]=\Pr[C=c]$

$\forall m_1,m_2 \in M $, $E_k(m_1)=E_k(m_2)$, куда $E_k(m_i)$ означает распределение по $к$ зашифрованного сообщения $m_i$.

Во-первых, просто чтобы убедиться, что я действительно должен показывать два направления, верно? (т.е. первый $\Rightarrow$ второй и второй $\Rightarrow$ первый). Это мое понимание относительно демонстрации эквивалентности любых двух определений.

Если это так, я могу сначала доказать направление $\Rightarrow$ второй, но я не могу сделать второе направление. Как мне использовать тот факт, что для каждого пара сообщений у меня есть какой-то вывод о любом не замужем общее сообщение $м$?

Спасибо.

54
0 + 0
Titanlord avatar
флаг tl
Titanlord
Я не очень понимаю второе определение. Вы имеете в виду что-то вроде $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$
1
Ответить
Marc Ilunga avatar
флаг tr
Marc Ilunga
Второе утверждение как-то покажет, что шифрование неверное? Поскольку вы не можете расшифровать, зашифрованный текст одинаков для всех сообщений. С другой стороны, очень безопасно!
0
Ответить
Anon avatar
флаг cn
Anon
@Titanlord да, точно.
1
Ответить
Рейтинг:1
Titanlord avatar Crypto
флаг tl
Titanlord

Да, вы правы, нужно доказывать оба направления. В Учебник Каца и Линделла (2-е издание) вы можете найти доказательство для первого $\Rightarrow$ второй. Другое направление оставлено для упражнений. Я стараюсь изо всех сил, чтобы дать правильное решение для этого.

Прежде всего, мы должны знать, что выполняется следующее:

$$ Pr[Enc_k(m) = c] = Pr[C = c | М = м] $$

Первый $\Rightarrow$ Второе доказывает, что если предположить $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$ правильно, то $Pr[C = с | M = m] = Pr[M = m]$ держит.

Мы хотим показать, что если предположить $Pr[C = с | M = m] = Pr[M = m]$ правильно, то $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$ держит.

Мое решение:

$$Pr[Enc_k(m_1) = c] = Pr[C = c | M = m_1] = \frac{Pr[M = m_1 | C = c] \cdot Pr[C = c]}{Pr[M=m_1]} $$

Потому что мы предполагали, что $Pr [ M = m_1 | С = с] = Pr[M=m_1]$ мы получили:

$$ \Rightarrow Pr[C = c] = Pr[C = c | M = m_2] = Pr[Enc_k(m_2) = c]$$

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

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

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