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

Найбільш консервативний підхід до квантово-стійких цифрових підписів.

Технічне пояснення

Підписи на основі хешування еволюціонували з Одноразові підписи Лампорта (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 — офіційна назва NIST для SPHINCS+
• SPHINCS+ — Основний алгоритм
• Криптографія на основі хешу — Ширша категорія
• WOTS+ — Winternitz One-Time Signature Plus
• Дерево Меркле — Ключова структура даних
• FIPS 205 — Стандартний документ NIST