Рейтинг:2

Вопрос о стилях редукционных доказательств

флаг tl

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

Скажем, у нас есть схема $В$ на основе $А$. Мы знаем $А$ безопасно. Если кто-то хочет доказать безопасность $В$ сводя его к безопасности $А$ он может действовать следующим образом:

  1. Стиль: Предположим, что противник может сломаться. $В$ $\Rightarrow$ Для сокращения можно построить нового противника, ломающего $А$ используя взлом противника $В$ $\Rightarrow$ Результатом является противоречие, которое показывает, что нет серьезного противника против $В$
  2. Стиль: Предположим, против произвольного ppt противника $В$ $\Rightarrow$ Показать (например, с помощью стохастического анализа эксперимента), что нарушение $В$ так же сложно, как сломать $А$, поэтому уменьшите сложность взлома $В$ по сложности взлома $А$ $\Rightarrow$ Потому что есть только незначительные противники против $А$ нет несущественного противника против $В$

Конечно, это упрощенно, но я хотел дать вам представление о том, что я заметил.

Мои вопросы: Эти стили действительно существуют? Могут ли они оба (правильно формально записанные) доказать одно и то же? Являются ли они оба (особенно стиль 1.) полными? Для каких доказательств следует использовать какой стиль?

Редактировать: Более точное определение стиля 2.: Во «Введении в современную криптографию» докажите криптосистему на PRG: в стохастическом анализе утверждается, что взлом криптосистемы так же вероятен, как и взлом PRG.Они используют это, чтобы подразумевать, что любой произвольный противник должен быть пренебрежимо мал по моде: поскольку это пренебрежимо мало, а вероятность у них одинаковая, то и другое должно быть пренебрежимо мало.

(Примечание. Вкратце я бы описал 1. как: $B \rightarrow A \rightarrow \unicode{x21af} \rightarrow B$ и 2. как: $B \rightarrow A \rightarrow (B = A) \rightarrow B$)

флаг us
В № 2: «Покажите, что сломать B так же сложно, как сломать A», чем это отличается от № 1? Как вы это продемонстрируете, кроме использования успешного B-противника для создания успешного A-противника? Что именно вы подразумеваете под «стохастическим анализом эксперимента»? У вас есть пример того, что вы подразумеваете под № 2?
Titanlord avatar
флаг tl
Я думаю, что [учебник Каца и Линделла (2-е издание)] (https://www.cs.umd.edu/~jkatz/imc.html)) использует стиль 2, например. чтобы доказать построенную ими криптосхему PRG.
флаг cn
@Mikero Отличие в том, что вы избегаете ненужного и сбивающего с толку аргумента от противного. Стиль 1 делает утверждение «*А* и *не В* подразумевает противоречие», из этого вы заключаете, что *В*, потому что предполагаете *А*. Стиль 2, с другой стороны, прямо делает утверждение «*A* подразумевает *B*», избегая ненужного обходного пути. Конечный результат тот же, если только у вас нет странных взглядов на логику.
флаг us
@ Махер, интересно.Я не считаю, что стиль № 1 обязательно влечет за собой доказательство от противного. Я интерпретирую это как «если А сломано, то и Б тоже сломано». Противоположным является то, что если B безопасно, то A безопасно. Существуют и другие стили доказательства (которые я на самом деле предпочитаю), которые позволяют избежать переключения между противоположными интерпретациями и полностью оставаться в мире «если B безопасно, то A безопасно», но я не распознал № 2 в этом вопрос как описание этого стиля.
kelalaka avatar
флаг in
Дело в том, что иногда $p \implis q$ не так очевидно, чтобы показать, и противопоставление может быть легче показать. Именно поэтому мы выбираем их. У CS есть некоторые вопросы о редукциях, где этот термин происходит от [1] (https://cs.stackexchange.com/q/11209/94479), и даже у них есть тег [recductions] (https://cs.stackexchange.com). /questions/tagged/reductions?tab=Голоса)
флаг cn
@Mikero Это, вероятно, не очень хорошее обсуждение в комментариях, но я читаю, что стиль 1 относится к доказательствам формы «Предположим, что существует машина PPT, которая ломает A с существенным преимуществом. Тогда есть существует машина PPT, которая взламывает B с существенным преимуществом. Это противоречит предположению, что B безопасен, поэтому A не существует». В то время как стиль 2 говорит: «Рассмотрите произвольную машину PPT. Тогда, предполагая, что B безопасен, преимущество этой машины незначительно».
kelalaka avatar
флаг in
Второй стиль нуждается в лучшем написании от Титанлорда.
Рейтинг:1
флаг ng

Единственная разница, которую я вижу между стилем 1 и правильной редакцией стиля 2, заключается в том, что в стиле 1 отсутствуют вещи, которые явно указаны в 2, о предполагаемом противнике/алгоритме для атаки B и полученном противнике/алгоритме, который будет атаковать A:

  1. Алгоритмы являются вероятностными полиномиальными временами; то есть иметь неявный ввод со случайными битами и работать в течение времени не более некоторого полинома $П(п)$ для всех значений параметра безопасности $n$ (или их входной размер) выше некоторой нижней границы.
  2. Они имеют непренебрежимо малую (или ненулевую) вероятность успеха, то есть: для некоторого полиномиального $P'$, для любой фиксированной границы $N\in\mathbb{N}$ существуют значения $n>N$ для параметра безопасности (или их входного размера), так что вероятность успеха не менее $1/P'(n)>0$.

Доказательство того, что «Взлом криптосистемы так же вероятен, как и взлом PRG». доказывает, что в 2 мы можем повторно использовать многочлен $P'$ и ценности $n$ для заданной границы $N$ которые подходят для гипотетической атаки B в доказательстве того, что атака A имеет незначительную вероятность успеха.

Другими словами, стиль 1 представляет собой упрощение стиля 2, часто за счет строгости. Для некоторых доказательств в стиле 1 необходимо освоить стиль 2, чтобы уверенно сказать, правильно ли доказательство.

Есть еще более сложные стили, например. где вероятность успеха количественная.В таком случае, «Взлом криптосистемы так же вероятен, как и взлом PRG». является так называемым жесткое доказательство. Некоторым другим количественным доказательствам труднее следовать.

флаг cn
Машина PPT работает за *строго* полиномиальное время, *не* ожидаемое полиномиальное время.
флаг cn
Кроме того, в 2. то, что вы описываете, является *заметной* вероятностью. Это *не* синоним слова "не пренебрежимо мал".
fgrieu avatar
флаг ng
@Maeher: Я верю вам на слово в определении PPT, и я думаю, что понял и исправил свою ошибку в определении незначительного значения. Спасибо за исправления!
флаг cn
Я попытался сделать этот момент более ясным. Просто откатите редактирование, если оно вам не нравится.

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

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