Подписи на основе хеша

Самый консервативный подход к квантовоустойчивым цифровым подписям.

Техническое объяснение

Подписи на основе хеша произошли от Одноразовые подписи Лэмпорта (1979) — удивительно простая конструкция, в которой подпись раскрывает прообразы хеш-значений. Задача заключалась в расширении одноразовых схем для поддержки нескольких подписей.

Эволюция подписей на основе хеша

Почему безопасность на основе хэша консервативна

Подписи на основе хеша основаны на минимальных предположениях:

• Устойчивость к столкновениям — Найти H(x) = H(y) для x ≠ y сложно.
• Сопротивление второму прообразу — Учитывая x, найти y, где H(x) = H(y), сложно.
• Сопротивление прообразу — Учитывая H(x), найти x сложно

Квантовое сопротивление

Против квантовых компьютеров:

• Алгоритм Shor — НЕ применяется (нет групповой структуры, которую можно было бы использовать)
• Алгоритм Grover — Обеспечивает только √n ускорение поиска прообразов.
• смягчение последствий — Двойной размер вывода хэша сводит на нет ускорение Grover.

SPHINCS+ (SLH-DSA) — Стандарт NIST

SPHINCS+ (стандартизован как SLH-DSA/FIPS 205) решает проблему сохранения состояния с помощью умной конструкции гипердерева:

SPHINCS+ Architecture:
├── Hypertree (d layers of XMSS trees)
│   └── Each tree authenticates the next layer
├── WOTS+ One-Time Signatures
│   └── Signs inter-layer roots
└── FORS Few-Time Signatures
    └── Signs actual message

Опции параметров SPHINCS+

SynX Актуальность

Подписи на основе хэша и подписи на основе решетки

Связанные термины

• SLH-DSA - Официальное название SPHINCS+ от NIST.
• SPHINCS+ — Базовый алгоритм
• Криптография на основе хеша — Более широкая категория
• ВОТС+ — Одноразовая подпись Winternitz Plus
• Дерево Меркла — Ключевая структура данных
• FIPS 205 — Стандартный документ NIST