Бумага с подписью Fujisaki & Suzuki's Traceable Ring Signature, что позволяет подписывать одним закрытым ключом из кольца открытых ключей, а также для любого, чтобы проверить, что один член кольца подписал, не раскрывая, какой член кольца подписал, если только тот же член кольца не подписывает два разных сообщения под одним и тем же тегом («двойные траты»), и в этом случае можно идентифицировать двойного транжира.
Для кольца $n$ подписантов, как протокол подписи, так и протокол проверки зависят от $\sigma_j$ за $i \in [1..n]$. Где $я$ это позиция истинного подписавшего на ринге, $\sigma_i$ определяется на основе закрытого ключа, членов кольца и проблемы. Таким образом, отслеживаемость основывается на идее, что при наличии только одного сообщения для тройки закрытого ключа/звонка/проблемы должно быть трудно определить, какой $\sigma_j$ является ограниченным без закрытого ключа. Однако, если один и тот же подписывающий подписывает два сообщения для одного и того же звонка/проблемы, то $\sigma_i$ будет одинаковым для двух сообщений, идентифицируя, что оба сообщения пришли от подписавшего $я$. В документе, однако, отмечается, что если бы протокол предоставлял подписавшему свободу выбора $\sigma_j$ за $j \neq i$, подписывающая сторона может представить другую подписывающую сторону как имеющую двойную подпись.
Чтобы преодолеть это, в документе вместо этого описывается схема выражения всех $\sigma_j$ в виде линии с точкой пересечения, зафиксированной алгоритмом на основе хэша входных данных, и наклоном (определяемым подписывающей стороной на основе $я$, перехват и $\sigma_i$).
В документе выражается $\sigma_j$ значения как член «мультипликативной группы G простого порядка q» без дополнительной информации о том, что они имели в виду для этой группы. Поэтому я хотел бы выбрать $G$ как эллиптическая кривая Curve25519, что, кажется, укладывается в предположения авторов.
Тем не менее, это вызывает проблему с этой схемой размещения $\sigma_j$ значения в строке. В документе говорится:
Установлен $A_0 = H'(L, м)$ и $A_1 = ({\sigma_i \over A_0})^{1/i}$
Существует несколько возможных интерпретаций того, как вычислить $A_1$ из этого. По-видимому, кодовый домен $H'$ это также $G$. Интерпретируя это как выражение в $G$ (о котором кто-то еще спрашивал ранее: Как вычислить $x^{1/y}$?), однако, означало бы решение проблемы дискретного логарифмирования эллиптических кривых. Безопасность всей схемы на бумаге зависит от ее неразрешимости при любых обстоятельствах. $G$ выбран, поэтому я думаю, что интерпретация выполнения этого с использованием полевых операций, вероятно, не имеет смысла - и я думаю, что авторы, должно быть, предполагали, что операция будет выполняться над необработанным числом, которое идентифицирует точку в группе вариант.
Поэтому мой вопрос: поскольку Curve25519 использует сжатые эллиптические точки, которые можно идентифицировать одним целым числом $х$, будет ли безопасная и правильная реализация вычислять $A_1 = ({\sigma_i \over A_0})^{1/i}$ на $х$ координата точки?
Одна проблема, которую я вижу в этом, заключается в том, что только $1/8$ всех значений являются точками на кривой для Curve25519, и если алгоритм подписи гарантирует, что $\sigma_i$ выходит как на кривой но не $\sigma_j$ за $i \neq j$, тогда это может исключить 7/8 возможных участников кольца как источник подписи (что было бы недопустимой утечкой информации).
Было бы разумным решением для этого сделать так, чтобы протокол проверки вычислял $\sigma_j^{'}$ от $A_0$ и $A_1$, а затем увеличить Икс
координаты до тех пор, пока точка на кривой ($\sigma_j$) получается? И тогда подписывающий может уменьшить $х$ координата $\sigma_i$ многократно для получения наибольшего $X < \sigma_i$ которая не находится на кривой, а затем случайным образом выбрать равновероятно координату x $x \leftarrow [X+1..\sigma_i]$, и используйте это для вычисления $A_1$. Таким образом, противник не сможет сказать, является ли данный $j$ значение $я$, но $\sigma_i$ значения будут ограничены, чтобы предотвратить атаку в документе. Есть ли какие-то очевидные проблемы с этой реализацией, которые мне не хватает?