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

Требования к хэш-функции для короткой подписи Шнорра

флаг st
einsteinwein

Невен и др. указано в их документе Требования к хэш-функциям для подписей Шнорра следующая теорема (используя лемму о разветвлении): $\mathbb{G}$ является общей группой (раздел 2), $s \приблизительно \log_2q$, хэш-функция $H: \lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^n$.

Теорема 1 Если задача дискретного логарифмирования в $\mathbb{G}$ является $(t_\text{dlog}, \epsilon_\text{dlog}$-hard, то подпись Шнорра $(t_\text{uf-cma}, q_S,q_H, \epsilon_\text{uf-cma})$-безопасный для $ \epsilon_\text{uf-cma} = \sqrt{(q_H+q_S+1)\epsilon_\text{dlog}} + \frac{q_H+q_S+1}{2^n} + \frac{q_S( q_H+q_S+1)}{q}$ и $t_\text{uf-cma}= t_\text{tdlog}/2 â q_S t_\text{exp} + \mathcal{O}(q_H + q_S + 1)$, куда $t_\text{exp}$ стоимость возведения в степень в группе $\mathbb{G}$.

Они заключают, что эта граница ясно указывает на то, что хеш-функция с $n = с/2$ выходные биты должно быть достаточно для получения уровня безопасности $s/2$ биты. Термин формы $q_H^2/2^n$ посоветовал бы s-битную хеш-функцию.

Может ли кто-нибудь объяснить мне это немного подробнее?

169
0 + 0
Рейтинг:2
Ievgeni avatar Crypto
флаг cn
Ievgeni

Здесь, $к$ биты безопасности означают, что преимущество не более $ O \ влево (\ frac {T ^ \ alpha} {2 ^ {\ alpha k}} \ right) $, после выполнения $Т$ действия (всех видов), совершаемые противником. Этот формализм позволяет нам заключить, что противнику необходимо сделать $ О (2 ^ к) $ "операции" по взлому системы ($ T ^ \ alpha \ приблизительно 2 ^ {\ alpha k} \ подразумевает T \ приблизительно 2 ^ k $).

Затем мы подробно рассмотрим все условия в сумме.

Когда мы смотрим третий член: $\frac{q_S(q_H+q_S+1)}{q}\leq\frac{T}{q}$, это нормально.

Второй срок $\frac{q_H+q_S+1}{2^n}=O(T2^{-n})$: И если мы хотим иметь этот термин в $O(T2^{-s/2})$, нам нужно иметь $n\geq с/2$, (отзывать $n$ — выходной размер хеш-функции).

Что касается первого термина, это немного сложнее: $\sqrt{(q_H+q_S+1)\epsilon_\text{dlog}}\leq\sqrt{T2^{-s/2}}$, но тоже нормально (с $\alpha=\frac{1}{2}$).

0 + 0
einsteinwein avatar
флаг st
einsteinwein
И, может быть, вы знаете, где я могу найти доказательство этой теоремы? В статье только сказано, что это не новый результат, но источник не указан.
0
Ответить
Ievgeni avatar
флаг cn
Ievgeni
Они говорят, что это следствие мультиподписей в простом открытом ключе. модель и общая лемма о разветвлениях.
1
Ответить
einsteinwein avatar
флаг st
einsteinwein
Хорошо. Большое спасибо за ваши ответы!
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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