Рейтинг:2

Katz/Lindell 2.4 - Обобщение от 2 сообщений до любого пространства сообщений?

флаг fr

Я пытаюсь решить проблему 2.4 в «Введении в современную криптографию» (2-е издание) для самостоятельного изучения.

Задача требует доказать, что совершенная секретность $$ Пр[М = м | С = с] = Pr[M = m] $$

подразумевает

$$ Pr[Enc_k(m) = c] = Pr[Enc_k(m') = c] $$

Решение выглядит следующим образом:

Исправить два сообщения $ м, м $ и зашифрованный текст $с$ происходящее с ненулевой вероятностью, и рассмотрим равномерное распределение по $\{м, м'\}$. Полная секретность подразумевает, что $Pr[M = м | C = c] = \frac{1}{2} = Pr[M = m' | С = с]$ Так

$$ \frac{1}{2} = Pr[M = m| C = c] = \frac{Pr[C = c| M = m] * Pr[M = m]}{Pr[C = c]} $$

упрощается до

$$ \ frac {\ frac {1} {2} Pr [C = c | M = m]}{Pr[C = c]} $$

и другие $Pr[C = с | М = м]$ = $Pr[Enc_k(m) = c]$ = $Pr[C = c]$. Поскольку аналогичные вычисления справедливы для $м'$ также делаем вывод, что $Pr[Enc_k(m) = c]$ = $Pr[Enc_k(m') = c]$

Моя проблема в том, что это решение предполагает пространство для сообщений, равное 2, которое нельзя обобщить.

Есть ли что-то, что мне не хватает, что делает это решение обобщаемым?

Редактировать: Для ясности, вот полный текст задачи.

Лемма 2.4. Схема шифрования (Gen, Enc, Dec) с пространством сообщений $ млн $ является совершенно секретным тогда и только тогда, когда уравнение (2.1) выполняется для каждого $m,m' \in M$ и каждый $c \в C$. Где уравнение 2.1 — это 2-е равенство в этом посте.

Задача требует доказать «другое направление», что в данном случае означает доказательство полной секретности => уравнение 2.1. (В учебнике уже доказано обратное направление).

Myath avatar
флаг in
Что вы имеете в виду под "решением"? Предоставляет ли книга указанное решение?
Foobar avatar
флаг fr
Да, в книге есть.
kelalaka avatar
флаг in
Нет, у книги нет решения. Есть решение, которое можно приобрести отдельно. Как видите, в результате нет $1/2$, поэтому вы можете догадаться, что он отменится. Для работы с большим пространством для сообщений потребуется $1/n$, играть таким образом?
Рейтинг:3
флаг ru

Это не утверждение о «пространстве сообщений размера 2». Пространство сообщений может быть сколь угодно большим, а вторая характеристика просто говорит, что для каждого $м,м'$ вы выбираете из этого пространства сообщений и для каждого возможного зашифрованного текста $с$, вероятность того, что $м$ зашифрован как $с$ такое же, как у $м'$ зашифрован как $с$, который записывается как $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$.

Теперь, что касается наброска решения, которое вы даете, на самом деле неправда, что оно «предполагает» пространство для сообщений размером два. Вы хотите доказать утверждение о двух фиксированных сообщениях $м$ и $м'$ (а именно, вы хотите доказать, что $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$), и вы хотите сделать это, используя полную секретность, которая гласит, что для каждого сообщения $\му$ и каждый зашифрованный текст $\гамма$,$^*$ и очень важно, для каждого дистрибутива $ млн $ над полем сообщения, он считает, что $\Pr[M=\mu|C=\gamma] = \Pr[M=\mu]$.

Учитывая, что полная секретность сохраняется для любого распределения, мы можем произвольно выбрать любое распределение, которое поможет нам доказать наше утверждение. Решение, которое вы предлагаете, просто использует распределение вероятностей, которое сэмплирует $м$ с вероятностью $1/2$, $м'$ тоже с вероятностью $1/2$, а все остальные сообщения отбираются с вероятностью $0$. Можно также сказать, что пространство сообщений «ограничено» $\{м,м'\}$, но на самом деле происходит то, что я сказал только что. Теперь, когда мы зафиксировали распределение вероятностей, мы также зафиксируем $\му = м$ и $\гамма = с$ сначала примените полную секретность, затем исправьте $\му = м'$ и снова применить совершенную секретность, чтобы получить различные выражения, которыми можно манипулировать, чтобы получить то, что нам нужно.

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


$^*$ Обратите внимание, что я использую другие имена вместо $м$ и $с$, так как последние зафиксированы уже в нашем контексте.

Daniel avatar
флаг ru
@kelalaka Если я что-то не упустил, это не предположение как таковое, а скорее выбор, который вы *можете* сделать в доказательстве, чтобы оно сработало. Это не предположение в том смысле, что оно не работает для более «общих» настроек или что-то в этом роде. Само утверждение имеет дело с фиксированной парой сообщений $m,m'$. Если кто-то хочет чего-то более общего, то следует смотреть на изменение характеристики, а не на ее доказательство.
Daniel avatar
флаг ru
@kelalaka Я не уверен, что мы говорим об одном и том же здесь.Вы правы в том, что идеальная безопасность не ограничивается униформой, поскольку она применима для *любого* дистрибутива (как я уже упоминал в своем ответе), но доказываемая здесь характеристика говорит о *любой фиксированной* паре сообщений $m,m '$. Чтобы доказать, что эта характеристика эквивалентна совершенной безопасности, можно рассматривать пространство сообщений как $\{m,m'\}$ и затем применять идеальную безопасность, но это не упрощение и не предположение, это просто часть доказательство.
Daniel avatar
флаг ru
@kelalaka Тем не менее, чтобы конкретно ответить на то, что вы сказали: предлагаемая характеристика говорит о ** парах ** $ m, m' $, поэтому естественно рассмотреть доказательство, в котором абсолютная безопасность применяется к пространству сообщений $ \ { м, м'\}$. Я настаиваю, что это не упрощение, это *способ* продолжить доказательство. Если кто-то хочет «обобщения», то должен найти другую характеристику для доказательства, например: «для каждого $c$ значение $\Pr[\mathsf{Enc}_k(m) = c]$ постоянно, независимо от $ м$".
kelalaka avatar
флаг in
Я предпочитаю больше образования. Ответ книги упрощен как «рассмотреть равномерное распределение по {m1,m2}», это была моя точка зрения. Между первым и вторым абзацами вашего ответа отсутствует доказательство равномерного распределения большего пространства сообщения! После этого приятно поговорить о произвольном распределении.
Daniel avatar
флаг ru
@kelalaka Это «учитывать равномерное распределение по $\{m,m'\}$» является ** не ** упрощением, это ** способ продолжить доказательство. Я думаю, вы предполагаете, что это просто «базовый случай» для иллюстрации и что общий случай отсутствует, но я настаиваю на том, что это просто *не* так. Утверждение касается (фиксированной) пары сообщений $m,m'$, они уже фиксированы, как только вы приступаете к доказательству, и вы можете выбрать ЛЮБОЕ распределение в потенциально гораздо большем пространстве, чтобы доказать, что $\Pr [\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$....
Daniel avatar
флаг ru
@келалака ...вы выбираете распределение, которое назначает $1/2$ для $m$ и $1/2$ для $m'$ и $0$ для всех остальных сообщений, что можно сформулировать как распределение, равномерное по $\{m,m '\}$, а затем примените полную секретность к этому дистрибутиву, чтобы получить то, что вы хотите. На данный момент доказательство завершено на 100%, общие случаи рассматривать не нужно.
Foobar avatar
флаг fr
@Daniel Спасибо за подробное объяснение! Я добавил полный текст задачи, чтобы было понятнее. В нем говорится, что уравнение должно выполняться для каждого $m, m' \in M$ (не уверен, что это что-то меняет)
Foobar avatar
флаг fr
@Daniel Я также добавил полное решение
Daniel avatar
флаг ru
@Roymunson В упражнении вам предлагается доказать, что, предполагая полную секретность (что говорит о произвольном распределении по всему пространству сообщений), следует, что **для каждой пары** $m,m'$ и для каждого зашифрованного текста $c$ , $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$. Чтобы доказать такое утверждение, вы начинаете с фиксирования $m,m'$ и $c$, так что для остальной части доказательства эти значения являются просто константами, и вы можете применять полную секретность с *любым* распределением по вашему выбору, в частности, вы можно использовать тот, который присваивает $1/2$ как $m$, так и $m'$ и ноль всем остальным сообщениям.
Foobar avatar
флаг fr
@Daniel Разве не подразумевается, что $M$ может быть любым дистрибутивом?
Daniel avatar
флаг ru
@Roymunson Путаница здесь действительно связана с математикой и доказательствами, а не с криптографией.У вас есть два определения: схема абсолютно безопасна, если для каждого распределения $M$ по пространству сообщений $\mathcal{M}$, для каждого сообщения $m$ и каждого зашифрованного текста $c$ выполняется $\Pr[ М = м | С = с] = \Pr[M = m]$. С другой стороны, давайте дадим имя второму понятию, скажем, схема является «вариантной» совершенной защитой, если для каждой пары сообщений $m$ и $m'$ и каждого зашифрованного текста $c$ выполняется равенство $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$....
Daniel avatar
флаг ru
@Roymunson ... Обратите внимание, что это второе определение «вариантной» совершенной безопасности * вообще * не говорит о распределении по пространству сообщений, тогда как первое определение говорит. Эти два понятия эквивалентны, хотя, опять же, одно требует соблюдения определенного свойства для *любого* возможного распределения, а другое вообще не говорит о распределениях.

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

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