ML-DSA (FIPS 204) и SLH-DSA (FIPS 205)

ML-DSA (алгоритм цифровой подписи на основе модульных решёток), стандартизированный как FIPS 204, основан на CRYSTALS-Dilithium. Dilithium разработали Дюка, Кильтц, Лепуан, Любашевский, Швабе, Зайлер и Штеле и представили NIST в 2017 году. В нём схема Fiat-Shamir с прерываниями применяется к Module-LWE, создавая практичную схему подписи с убедительными доказательствами стойкости.

Классические преобразования Fiat-Shamir превращают интерактивные протоколы идентификации в схемы цифровой подписи. Для решёточных схем прямое применение раскрывает информацию о закрытом ключе через вектор ответа. Техника «с прерываниями», предложенная Любашевским, добавляет выборку с отбраковкой: подписывающая сторона проверяет, не раскроет ли ответ информацию, и прерывает процесс с повторной попыткой, если это возможно. Это немного увеличивает накладные расходы на создание подписи, но необходимо для безопасности.

Для создания подписи ML-DSA выбирает маскирующий вектор y из равномерного распределения, вычисляет обязательство w = Ay, хеширует (сообщение, w), чтобы получить полином-вызов c, и вычисляет ответ z = y + cs. Выборка с отбраковкой проверяет, не раскрывает ли z информацию о s. Если проверка пройдена, подписью становятся (c, z) вместе с подсказкой для эффективной проверки. В противном случае процесс повторяется.

ML-DSA определяет три набора параметров: ML-DSA-44 (уровень стойкости NIST 2, примерно 128 бит), ML-DSA-65 (уровень 3, примерно 192 бита) и ML-DSA-87 (уровень 5, примерно 256 бит). Числа обозначают ранги модулей в схеме. Размеры открытых ключей составляют соответственно 1312, 1952 и 2592 байта. Размер подписи ML-DSA-65 — 3293 байта по сравнению с 64 байтами у Ed25519 при 128-битовой стойкости.

Самый существенный недостаток ML-DSA по сравнению с ECDSA или EdDSA — размер подписи. Подписи ML-DSA-65 занимают 3293 байта против 64 байт у Ed25519. В протоколах, передающих множество подписей (цепочки сертификатов TLS, подписание кода), это увеличивает объём передаваемых данных. Однако создание и проверка подписей ML-DSA выполняются очень быстро (сопоставимо с ECDSA или быстрее), поэтому компромисс в основном касается стоимости передачи.

SLH-DSA (алгоритм цифровой подписи на основе бессостояния и хеш-функций), стандартизированный как FIPS 205, основан на SPHINCS+. В отличие от решёточных схем, стойкость SLH-DSA зависит только от устойчивости используемой хеш-функции к коллизиям и поиску второго прообраза (SHA-256 или SHAKE-256). Благодаря этому SLH-DSA отличается чрезвычайно консервативным подходом: он сохраняет стойкость даже в случае взлома решёточных предположений.

SLH-DSA использует WOTS+ (одноразовую подпись Винтерница), схему на основе хеш-функций, в которой закрытый ключ представляет собой набор случайных строк, а открытый ключ получается многократным хешированием каждой из них. При создании подписи выполняется частичное хеширование в соответствии с битами сообщения. Пару ключей WOTS+ безопасно использовать только один раз: повторное использование раскрывает информацию. SLH-DSA строит механизм многократной подписи поверх WOTS+ с помощью деревьев.

SLH-DSA использует гипердерево — дерево деревьев Меркла. Каждый лист является открытым ключом экземпляра WOTS+. Корень является открытым ключом SLH-DSA. Подпись состоит из подписи WOTS+ для сообщения и пути аутентификации от листа до корня. Структура гипердерева позволяет создавать множество подписей одной парой ключей, используя разные листья WOTS+.

SLH-DSA имеет 12 наборов параметров, сочетающих хеш-функцию (SHA-256 или SHAKE-256), уровень стойкости (128s/128f, 192s/192f, 256s/256f) и оптимизацию (s = маленькие подписи, f = быстрое создание подписей). Вариант 128f имеет подписи размером 7856 байт и обеспечивает быстрое создание подписей; вариант 128s также использует подписи размером 7856 байт, но работает медленнее. Все варианты значительно больше ML-DSA, но опираются на наиболее консервативное предположение о стойкости.

ML-DSA предпочтителен, когда важны производительность и пропускная способность, а решёточным предположениям доверяют. SLH-DSA предпочтителен для чрезвычайно консервативных развертываний, где доверяют только стойкости хеш-функций, а также для защиты от возможных будущих взломов решёточных схем. Центры сертификации и государственные системы, которые подписывают редко, но требуют максимальной гарантии, могут выбрать SLH-DSA, тогда как серверы TLS, часто создающие подписи, скорее выберут ML-DSA.

FN-DSA (FIPS 206, основанный на FALCON) предлагает подписи меньшего размера, чем ML-DSA (897 байт для FALCON-512 при 128-битовой стойкости), используя решётки NTRU и выборку по Гауссу. Однако FN-DSA требует тщательной реализации с постоянным временем выполнения, чтобы предотвратить атаки по побочным каналам на генератор выборки по Гауссу. Ожидается, что FIPS 206 будет стандартизирован после FIPS 203–205 и предоставит высокопроизводительный вариант для сред с ограниченными ресурсами.

Каково основное преимущество SLH-DSA с точки зрения стойкости по сравнению с ML-DSA?

ML-DSA (FIPS 204) использует схему Fiat-Shamir с прерываниями над Module-LWE и обеспечивает быстрое создание подписей размером 3 KB при 192-битовой стойкости. SLH-DSA (FIPS 205) использует хешированные деревья Меркла (WOTS+) и опирается только на стойкость хеш-функций, создавая подписи размером 7–50 KB. ML-DSA предпочтителен для приложений, чувствительных к производительности, а SLH-DSA — для максимально консервативного подхода. FN-DSA (FALCON, FIPS 206) добавит решёточный вариант с подписями меньшего размера.