Введение
Схема цифровой подписи
In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm that was described by Claus Schnorr. It is a digital signature scheme known for its simplicity, among the first whose security is based on the intractability of certain discrete logarithm problems. It is efficient and generates short signatures. In the case of Schnorr signatures, this simply requires subtracting values:
В криптографии, подпись Шнорра — это цифровая подпись, созданная алгоритмом подписи Шнорра, описанным Клаусом Шнорром. Это схема цифровой подписи, известная своей простотой, и одна из первых, безопасность которой основана на вычислительной сложности определенных задач о дискретных логарифмах. Она эффективна и генерирует короткие подписи. В случае подписей Шнорра, для этого достаточно просто вычесть значения: если, но тогда можно просто выделить . Фактически, даже незначительные отклонения в значении или частичная утечка могут раскрыть секретный ключ после сбора достаточного количества подписей и решения задачи о скрытом числе, связанной с протоколом идентификации Шнорра. Поэтому (согласно аргументам Фиата и Шамира), она безопасна, если рассматривается как случайный оракул. Её безопасность также может быть обоснована в общей групповой модели при условии, что она обладает свойством устойчивости к случайным префиксам первого образа и устойчивости к случайным префиксам второго образа. В частности, устойчивость к коллизиям не требуется. В 2012 году Сеурин предоставил точное доказательство безопасности схемы подписи Шнорра. В частности, Сеурин показал, что доказательство безопасности с использованием леммы ветвления является наилучшим возможным результатом для любых схем подписей, основанных на односторонних групповых гомоморфизмах, включая подписи типа Шнорра и схемы подписи Гийу-Квискатера. А именно, при условии ROMDL, любое алгебраическое сведение должно потерять фактор в своем отношении времени выполнения к вероятности успеха, где — функция, остающаяся близкой к 1, пока «заметно меньше 1», где — вероятность совершения ошибки при выполнении не более запросов к случайному оракулу.
Короткие подписи Шнорра
Вышеупомянутый процесс обеспечивает t-битный уровень безопасности с использованием 4t-битных подписей. Например, для 128-битного уровня безопасности потребуются 512-битные (64 байта) подписи. Безопасность ограничена атаками на основе дискретного логарифма по группе, сложность которых пропорциональна квадратному корню от размера группы. В оригинальной статье Шнорра 1991 года было предложено, что поскольку устойчивость к коллизиям в хеш-функции не требуется, более короткие хеш-функции могут быть столь же безопасными. Действительно, недавние разработки показывают, что t-битный уровень безопасности можно достичь с помощью 3t-битных подписей. Таким образом, для 128-битного уровня безопасности потребуется всего 384 бита (48 байт) подписи, что можно реализовать, усекая размер значения *e* до половины длины битполя *s*.