Это законно?
Нет, и вы попали в причину — алгоритм преобразует сообщение в ряд из 16 значений от 1 до 128, а затем подписывает только на основе этого. Всего 112 бит; на самом деле, это несколько хуже, так как алгоритм, который они используют для преобразования хэша сообщения в серию из 16 значений, будет генерировать значения, которые всегда суммируются (по модулю 128) с 64;. Это означает, что с допустимой парой сообщение/подпись вы можете найти второе изображение, которое преобразуется в те же первые 15 значений [1] (и, таким образом, будет действительным сообщением для той же подписи) с ожидаемым $О(2^{105})$ усилие. Хуже того, поскольку перевод не включает рандомизацию, вы можете ожидать коллизии (а затем попросить подписать одно сообщение; второе сообщение с той же подписью будет подделкой) с ожидаемым $О(2^{52,5})$ усилие.
В документе также делается ряд ошибочных заявлений; вот те, что мне приглянулись:
Они утверждают, что «Другие типы схем OTS/FTS (кроме WOTS и ее
варианты) не позволяют вычислить
публичный ключ из подписей разве что огромный дополнительный набор
информации предоставляется верификатору». Это неверно. Для каждой схемы подписи на основе хеша, которую я видел, процесс проверки был, по сути, «брать сообщение, подпись и, возможно, некоторое небольшое количество данных из открытого ключа, вычислите серию хэшей, и если результат совпадет с тем, что в открытом ключе, вы выиграете». То есть все, что вам нужно для восстановления открытого ключа, — это «возможно небольшое количество данных», а не «огромный дополнительный набор информации». ". Незначительный момент, за исключением того, что они неоднократно подчеркивают это.
Их оценка, которая состоит из сравнения с некоторыми выбранными другими схемами подписи на основе хэшей (но ничего с большим параметром W); однако они настаивают на том, что используют конкурирующие схемы с нереально большим размером хеш-функции (значение n) — они отмечают, что их схема (которая имеет большой параметр W и меньшее значение n) приводит к меньшим подписям; неудивительно, когда они так сильно кладут большой палец на весы.
Они также заявляют, что «наконец, NOTS добился всех этих сокращений.
в размерах ключа и подписи без ущерба для уровня безопасности»; хотя взгляд на их таблицу показывает, что они утверждают, что NOTS имеет значительно более низкий уровень безопасности (не считая того, что я сделал выше о том, что он даже не достигает этого).
Что касается их доказательств безопасности, то они состоят из предоставляемых ими алгоритмов, которые принимают подделку и создают коллизию; однако прохождение алгоритма показывает, что даже в случае подделки он может дать сбой (то есть не вызвать столкновение); следовательно, оно недействительно в качестве доказательства.
[1]: Как только вы впервые найдете совпадение в первых 15, вы всегда получите совпадение в шестнадцатом.
