Безопасность схем подписи в многопользовательской настройке

Я часто читал о безопасности схемы подписи в многопользовательской настройке. Ссылка1 Ссылка2, но я не мог найти реального определения. Я хотел бы быть уверен, что я правильно понимаю. Итак, мой вопрос: если мы рассмотрим Def 1, будет ли Def 2 иметь смысл для многопользовательской настройки?

Защита 1: Схема подписи дает k-бит безопасности в однопользовательской настройке если вероятность того, что злоумышленник сможет подделать подпись, не более $т/2^к$ и это справедливо для $t \leq 2^k$.

Защита 2: Схема подписи дает k-бит безопасности в многопользовательской настройке если вероятность того, что злоумышленник, получивший N открытых ключей, сможет подделать подпись для любого из N открытых ключей, не превышает $т/2^к$ и это справедливо для $t \leq 2^k$.

Переход от многопользовательского к однопользовательскому

Во-первых, обратите внимание, что существует сокращение между многопользовательской безопасностью и стандартной однопользовательской схемой безопасности для подписи: это было доказано в 2002 году Гэлбрейтом, Мэлоун-Ли и Смарт (GSM), что для любой системы подписи, атакуя схему в многопользовательской настройке с $N$ открытые ключи не могут увеличить коэффициент успеха злоумышленника (который является отношением его вероятности успеха и его времени выполнения) более чем в 1 раз. $N$ по сравнению с атакой схемы в однопользовательской настройке.

Это сильный результат, используя ваши обозначения, это примерно означает, что в настройке MU ваша граница ограничена $\frac{Nt}{2^k}$ у тебя есть $\frac{t}{2^k}$ в настройках СУ. НО мы не знаем ни одной практической атаки, которая достигла бы такой границы для схем подписи. Обратите внимание: если бы это было так, если бы у нас было большое N, такое как, например, 2^32, влияние на безопасность схем подписи было бы огромным!

Обычно мы предпочитаем крепче сокращения.

Обратите внимание, что атаки против схем подписи в многопользовательской среде не следует смешивать с атаками на MAC в той настройке, которые не обязательно так хороши, как схемы подписи, как обсуждалось в отличном "Еще один взгляд на герметичность«Статья Чаттерджи, Менезеса и Саркара и ее продолжение»Еще один взгляд на Tightness II". Оба отлично читаются по такого рода проблемам.

Рекомендую также прочитать "Безопасность схем подписи в многопользовательской среде" Menezes and Smart от 2004, так как это касается определений безопасности в настройках MU для схем подписи:

мы утверждаем, что общепринятое определение безопасности для схем подписи (экзистенциальная невозможность подделки против адаптивных атак с использованием выбранного сообщения) Goldwasser et al. [18] не подходит для многопользовательской настройки. К счастью, оказывается, что это определение можно легко расширить для учета этих атак в многопользовательской среде.

Они также обеспокоены так называемыми «атаками подмены ключей», которые охватываются их определениями.

В частности (выделено мной):

В разделе 2.2 мы утверждали, что противник схемы подписи в многопользовательской среде добьется успеха, если он произведет экзистенциальную подделку или подмену ключа. В любом случае атака направлена ​​против одного конкретного открытого ключа.. Поэтому достаточно рассмотреть многопользовательскую настройку, в которой изначально имеется только один открытый ключ. Это без потери общности, потому что противник, атакующий один объект, может имитировать другие объекты, выбирая их открытые ключи, чтобы он знал соответствующие закрытые ключи..

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

И они заключают также, что нет реального необходимость беспокоиться о многопользовательской настройке схем подписи, как только мы сможем привязать их к открытому ключу и получить очень интересный результат:

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

NB: это, в частности, объясняет, почему мы добавляем открытый ключ в дайджест сообщения в «шнорровской» схеме подписи».ЭдДСА". (На самом деле это может быть и потому, что DJB нашел недостаток в переходе от однопользовательской настройки к многопользовательской, которая была предоставлена ​​GSM в 2002 году, но тем временем мы еще одно доказательство это показывает, что это не нужно для подписей Шнорра ... Но, я думаю, DJB закурил, когда создал EdDSA ;))

Модель многопользовательской атаки для схем подписи

Также обратите внимание, что модель атаки на подделки в многопользовательской настройке заключается в том, что противнику дается $n$ подписание оракулов, по одному на каждый открытый ключ, и разрешено сделать не более $q$ запросы к этим оракулам. По окончании атаки противник должен вывести (с вероятностью не более $\эпсилон$) кортеж, содержащий:

• один из $n$ открытые ключи, $у$
• сообщение $м$
• подпись $\сигма$, так что подпись $\сигма$ действительно для сообщения $м$ под открытым ключом $у$. Где $м$ не должен был быть запросом к подписывающему оракулу, соответствующему этому ключу $у$.

Затем безопасность такой схемы определяется в зависимости от $q$, $n$. Это известно как модель «многопользовательской неподделки против атак с выбранными сообщениями» (MU-UF-CMA).

О значении безопасности для схем подписи

Кроме того, прежде чем «определять» безопасность для схемы подписи в любых настройках, нам нужно знать, «какой безопасности» мы пытаемся достичь. Приятно сказать, что «схема подписи дает k-бит безопасности в однопользовательской настройке», но от каких атак? По той теме, основополагающая статья Goldwasser, Micali и Rivest — хорошее чтение, хотя оно немного устарело и ему явно не хватает многопользовательской настройки.

Наиболее распространенное понятие безопасности для схемы подписи называется «EUF-CMA», что означает «экзистенциальная невозможность подделки при адаптивных атаках с выбранным сообщением», то есть злоумышленнику должно быть трудно придумать «поддельное» сообщение для предоставлен открытый ключ. (Существует также понятие SUF-CMA «Сильная экзистенциальная неподделка при атаке выбранного сообщения», которое пытается уменьшить гибкость схем подписи)

Но в многопользовательской среде есть еще одно интересное понятие, а именно "Атаки с заменой ключей" (KSA), где мы можем сгенерировать новый открытый ключ, который также будет проверять заданную пару (сообщение, подпись). И есть атаки подменой ключа в доказуемо безопасных схемах подписи EUF-CMA! (например, в NTRUSign или в "Short подписи без схемы случайных оракулов) Что действительно интересно в KSA, так это то, что злонамеренный подписывающий тоже может быть актером в такой постановке!

О k-битах безопасности

Наконец, «иметь k-бит безопасности» на самом деле против некоторой модели атаки (но какой именно?) и на самом деле является для нас способом сравнивать Криптография с открытым ключом с симметричным ключом, крипто/грубая атака. Это способ, которым мы пользуемся, чтобы иметь метрику, позволяющую нам сравнивать их, но иногда довольно сложно оценить в абсолютном выражении. Есть такие бумаги, как те, что на https://www.keylength.com/ которые позволяют вам увидеть различные способы, которыми мы должны «оценивать» безопасность асимметричного шифрования по сравнению с безопасностью симметричного шифрования, и, как вы можете видеть, значения меняются от одной статьи к другой.

В конце концов, с помощью k-битной метрики мы пытаемся оценить сложность взлома какой-либо схемы по сравнению с атакой полным перебором. (рекомендую прочитать это эссе от DJB при брутфорс-атаках.) Но это использование лучших известен атак против этих схем с открытым ключом, поэтому это не абсолютная, а относительная мера.

Ваше определение, используя $т/2^к$ примерно соответствует атаке грубой силы: количество попыток, деленное на «максимальное число».

Итак, то, что вы говорите, в основном состоит в том, что мы определяем «наличие k-бит безопасности» как «так же сложно, как атака грубой силы на k-битный ключ», с чем я полностью согласен. Мы делаем.

Но типичное «правильное определение безопасность" для схем подписи с открытым ключом не будет полагаться на это понятие "биты безопасности". Он по-прежнему имеет понятие параметра безопасности $к$ и он все еще использует значение $\mathbb{1}^k$ обычно в качестве входных данных, но он используется как способ ограничить злоумышленника делать меньше, чем простая атака грубой силы, и, таким образом, также является входными данными для злоумышленника, но он будет определен с использованием некоторой модели атаки, такой как выше.

Вот почему я обсуждал «модель атаки» ранее и не могу дать вам лучшего определения, чем «Да, конечно: в идеале брутфорс должен быть такой же сложности, как и в однопользовательской настройке для подделок в многопользовательской».

Но так как у нас нет более «жесткой» общей редукции, чем эта, мы не можем с уверенностью сказать, так ли это на самом деле или нет вообще. Но это, безусловно, относится к подписям Шнорра в соответствии с обоими выше связанный документы.

Обратите внимание, что ответ Фгриё тоже намекает на это понятие герметичности, но с обратной точки зрения.

я предполагаю $t$ - количество «операций» (например, групповых операций), совершаемых противником; и количество таких операций, которые законные пользователи должны выполнить для подписи и проверки, невелико (например, несколько раз $к$; или в самом полиномиальном $к$).

Вопрос Def 2 предназначен для безопасность для $N$ пользователи. Для истинного безопасность в многопользовательской настройке, нам нужно определить $N$ от $к$, но я не могу процитировать источник, как это сделать. я бы заменил $N$ к $ 2 ^ {\ альфа к} $ для некоторых разумных $\альфа>0$. Практикующий обычно удовлетворяется $\альфа=1/4$ (уступая $N=2^{32}$ за $к=128$ ), теоретик может захотеть поднять это до $\альфа=1$.