Я пытаюсь проанализировать игру «уникальность» вокруг подписей Шнорра. Игра описана в $\textbf{Б.}$ и я пытаюсь обеспечить в $\textbf{1.}$ и $\textbf{2.}$ некоторые неполные ответы, чтобы решить эту проблему. Можно ли ее полностью решить? Я не использовал в своем анализе сведение к задаче DL; может есть способ свести игру к нему? Приносим извинения за отсутствие криптографической строгости и большое спасибо за чтение
$ \textbf{А. Криптографическая гипотеза:}$
Мы будем использовать безопасную криптографическую хэш-функцию. $Ч$ вывод в $\mathbb Z_n$, куда $n$ - порядок кривой, предполагаемый простым. Мы предполагаем, что простым порядком является простое число $256$ цифры при записи в основе $2$.
$\textbf{Б. Криптографическая игра:}$
Предполагая точку эллиптической кривой $S$ вычисляется после выбора кортежа $\{R,X,м\}$, куда $S := R + H(X,R,m).X$ как в подписи Шнорра, можем ли мы практически найти кортеж $\{R',X',m'\}$ такие как $\{R',X',m'\} \neq \{R,X,m\}$ (по крайней мере, один из элементов отличается в двух наборах) проверка $R' + H(X',R',m').X' = S = R + H(X,R,m).X$ ?
Сделаем дополнительное предположение, что кортеж $\{Х,R,м\}$ может быть выбран противником до игры, т.е. кортеж $\{Х,R,м\}$ не предоставляется ему проверяющим.
$\textbf{1. Предполагая знание дискретного логарифма до $S$:} $
Если вышеупомянутая игра также требует предоставить верификатору доказательство знания дискретного логарифма для S (т. е. знание $s$ такой, что $s.G = S$, или, другими словами, начав с одной действительной подписи Шнорра), похоже, что ответ отрицательный.
Временно предположим, что $\{Х,R, м\}$ и соответствующий $s$ непосредственно предоставляются верификатором противнику, используя естественные обозначения, противник должен найти $г', х'$ и $м'$ такой, что $r' + H(X',R',m').x' = s$. Кажется, это единственный способ сделать это, учитывая, что добавление двух случайных целых чисел по модулю $n$ вместе (здесь $г'$, выбранный случайным образом, и $H(X',R',m').x'$, случайное целое по модулю $n$ из-за того, что хэш-функция по предположению является криптографически безопасной) приводит к случайному целому модулю $n$, как результат суммы 2 равномерно распределенных случайных целых чисел по модулю $n$ представляет собой равномерно распределенное случайное целое число по модулю $n$. Мы можем игнорировать сообщение $м$ для этой игры и брутфорс на входах $г'$, $х'$ (или, что то же самое, просто перебор на $г'$) кажется единственным решением для победы в игре, что делает ее приятной. $256$-бит безопасности и, следовательно, быть неразрешимым. Интересно, правильно ли рассуждение или это неверно?
Возвращаясь к исходной гипотезе $\textbf{Б.}$, кажется, что на самом деле можно ограничить игру сверху $128$-битовая безопасность (тоже непреодолимая трудность, но здесь это только верхняя граница) вместо $256$ когда $\{Х, R, м\}$ могут быть выбраны противником (а не предоставлены ему). Фиксация $х'=х$ и $г$ и $г'$, противник может решить задачу «День рождения» и найти $м$ и $м'$ (применив алгоритм «День рождения»), проверяя приведенное ниже соотношение, которое является решением игры:
$H(X,R,m) - H(X,R',m') = (r' - r).x^{-1}$.
$\textbf{2. Не предполагая знания дискретного логарифма для $S$:} $
Я не уверен, что приведенные выше аргументы в $\textbf{1.}$ были приблизительно правильными, но эта ситуация кажется несколько более сложной для изучения.
$\текстит{2. а) Предполагая знание дискретного логарифма одноразовых номеров:}$
Чтобы победить в этой игре, нужно также предоставить доказательства знания дискретных логарифмов обоим участникам. $R$ и $R'$ (достаточно одного такого доказательства знания, если $ Р' = Р $). Чтобы попытаться решить этот вопрос, мы предположим, что кто-то выиграл игру, что означает, вычитая два соотношения, которые должен знать победитель игры $u$ так что:
$$u.G = H(X, R, m).X - H(X',R', m').X'.$$
Предположим, что игра выиграна с $Х = Х'$, то это означает, что дискретный логарифм $Х$ должно быть известно, поскольку должно быть верным, что $u.G = (H(X, R, m) - H(X, R', m')).X$, и, следовательно, мы находимся в случае $\textbf{1.}$.
Если $R = R'$ ($Х'$ может быть равно или не равно $Х$), то мы возвращаемся к частному случаю, когда $и=0$, а у нас так $X' = H(X, R, m).H(X',R, m')^{-1}.X$, т. е. дискретный логарифм $а$ из $Х'$ в отношении $Х$ должен проверить $a = H(X, R, m).H(X',R, m')^{-1}$. Фиксация $Х$ и $Х'$ такой, что $X' = а.Х$ для некоторых $а$, лучшим алгоритмом для решения этой проблемы снова кажется алгоритм дня рождения с вводом около $2^{128}$ различные сообщения в задачах, чтобы в конечном итоге найти некоторые $м$ и $м'$ которые подтверждают $a.H(X',R, m') - H(X, R, m) = 0$.
Если оба $X \neq X'$, и $R \neq R'$, мне не удается найти какой-либо потенциальный вывод. Кто-нибудь знает ответ или ссылку на этот случай?
$\текстит{2. б) Предполагая знание дискретного логарифма для открытых ключей:}$
Кажется, мы возвращаемся к делу $R = R'$ из $\текстит{2. а)}$ если $R = R'$, но мне не удается сделать вывод, если $R \neq R'$.
$\текстит{2. c) Предполагая знание ни дискретного логарифма одноразовых номеров, ни ключей:}$
Мы снова можем сделать вывод, если $R = R'$ используя тот же аргумент, что и в случае $\текстит{2. а)}$ для случая $R = R'$, но опять же кажется, что труднее сделать иной вывод (т.е. если $R \neq R'$).
