Рейтинг:1

Что такое игра, претендент и противник?

флаг cn

Вот мое понимание концепции игр безопасности. Я выделил жирным шрифтом некоторые части, в которых не уверен.

Криптографический объект формально определяется своими алгоритмами и понятиями безопасности, которые он обеспечивает.Такие понятия отражают силу противника и показывают, как противник может «сломать криптосистему». «Взлом криптосистемы» означает победу в ИГРЕ, связанной с безопасностью криптосистемы. Игра (т. е. алгоритм) играется между противником и претендентом. И противник, и претендент компьютеры которые запускают вероятностные алгоритмы. Вероятность победы противника должна быть незначительной по сравнению с некоторой целевой вероятностью, чтобы схема была безопасной.

Например, в схеме шифрования сильный противник не должен быть в состоянии различать шифрования друг от друга, даже если они выбрать сообщения. Другими словами, противник угадывает, какой бит перевернулся. Целевая вероятность $\фракция{1}{2}$, так как злоумышленник может случайным образом угадать, какой бит был перевернут. Противник должен победить с вероятностью не более $\frac{1}{2} +negl(n)$, куда $n$ является параметр безопасности в схеме.

  1. Игра - это не алгоритм? Если нет, то что это? https://www.shoup.net/papers/games.pdf Шуп говорит, что это вероятностные процессы. Но есть ли разница между вероятностными процессами и вероятностными алгоритмами?
  2. Являются ли противники и претенденты компьютерами? Они выполняют некоторые вычисления (даже если процесс похож на случайный оракул). Правильно ли так говорить?
  3. Что $n$ должен быть параметром?
Рейтинг:2
флаг us

Рискуя показаться педантичным и придирчивым (вы все-таки задали вопрос о терминологии), предлагаю называть эти объекты «интерактивными программами», а не алгоритмами или компьютерами.

Игра не алгоритм

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

Технически интерактивную программу можно идентифицировать по ее «функции следующего действия», которая на самом деле является простым неинтерактивным алгоритмом. Например, претендент характеризуется алгоритмом, вычисляющим логику: «если противник делает своего рода запрос, то ответьте действием». На самом деле это может быть то, как вы бы выбрали определять что такое интерактивная программа с точки зрения неинтерактивных алгоритмов. Помимо таких очень формальных определений, редко действительно думают и говорят о претендентах и ​​противниках таким образом, но иногда полезно думать таким образом о спецификациях протоколов.

Являются противниками и претендентами компьютеры

Я думаю, что компьютер — это устройство, которое может делать то, что ему говорит программа. Противники и претенденты — это компьютеры, на которых работают определенные программы -- Претендент на конкретную игру безопасности запускает фиксированную программу, но мы считаем, что противник запускает произвольную программу.

Что $n$ должен быть параметром?

Быть параметром означает: это значение, которое выбирается извне и предоставляется публично как претенденту, так и противнику. Параметр безопасности задается как вход для всех алгоритмов в криптографической схеме (хотя этот вход часто не записывается явно). Обычно параметр безопасности указывает размер ключей и т. д.

Параметр безопасности подобен ручке, которую можно повернуть. Более высокое значение делает запуск криптографических алгоритмов немного дороже, но намного дороже их взлом. Поворачивайте ручку, пока не оцените, насколько сложно сломать схему, и это значение, которое вы используете при запуске этой схемы.

eternalmothra avatar
флаг cn
Это очень полезно! Я действительно хотел быть педантичным (ну, педагогическим) здесь. Единственное, в чем я не уверен: действительно ли $n$ является параметром безопасности или это размер ввода? Различие может заключаться в том, что вам нужны ключи длины X, например, для получения Y битов безопасности.

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

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