Як біткоїн може протистояти квантовим комп'ютерам? Порівняння трьох схем підпису на основі решіток

Автор: Команда Blockstream

Переклад: Саорс, Foresight News

Дослідницький інститут Blockstream опублікував повний звіт про підписи на основі решіток для біткоїна. У цій статті підсумовано зміст дослідження, основні висновки та відповідні рекомендації, повний звіт можна переглянути за посиланням .

Цифровий підпис є основним механізмом авторизації транзакцій у біткоїні, і наразі цю функцію виконують підписи Schnorr та ECDSA, які мають дуже низькі витрати. У 1994 році Шор довів, що достатньо потужний квантовий комп'ютер може зламати ці два типи підписів. Хоча досі тривають широкі дискусії про те, коли такі машини можуть з'явитися, нам потрібно розробити практичний план впровадження постквантових підписів до того, як це питання стане актуальним.

Схеми підпису на основі решіток є популярними кандидатами для заміни існуючих підписів. Дослідження решіток триває вже понад століття, а їх криптографічні застосування розвиваються вже майже тридцять років. У постквантових криптосистемах підписи на основі решіток мають багато переваг: загальний розмір відкритого ключа та підпису може бути меншим за 1,6 кілобайта, а їх алгебраїчна структура має потенціал для підтримки мультипідписів, підписів з обмеженнями та компактних доказів у майбутньому.

У цьому звіті досліджуються три схеми: Dilithium, Falcon, Hawk. Для читачів, які не знайомі з решітками, ми пояснюємо концепцію кожної схеми, повністю представляємо алгоритмічні процеси та аналізуємо їх з точки зору безпеки, продуктивності та практичного впровадження (наприклад, похідні ключі гаманця). Які з цих схем насправді можуть бути впроваджені в біткоїн-мережу?

Оцінювальні критерії

Біткоїн має свої обмеження при виборі схем підпису, і ця оцінка базується на чотирьох основних критеріях:

• Вартість на ланцюгу: одним з найважливіших показників є загальний розмір відкритого ключа та підпису. Коли вихід витрачається, відкритий ключ та підпис записуються на ланцюзі, і всі вузли повинні завантажити та зберігати кожен байт. Витрати на верифікацію також є критично важливими: кожен підпис має бути перевірений всіма вузлами мережі, а повільна швидкість верифікації може створити навантаження на всю мережу.
• Складність реалізації: чи можна безпечно реалізувати схему, є критично важливим питанням. Якщо дизайн вимагає плаваючих операцій або точного гауссового відбору, помилки в реалізації або атаки на основі аналізу часу можуть призвести до витоку ключа. Для плавної міграції складність реалізації є важливим фактором.
• Ризики впровадження: під час фактичної інтеграції біткоїн стикається з різними реальними перешкодами: вибір хеш-функції на рівні консенсусу (більшість кандидатів використовують SHAKE, тоді як біткоїн використовує SHA-256), відтворюваність підписів на різних платформах та чи підходить програма підпису для обмежень пам'яті апаратних гаманців.
• Потенціал розвитку: більшість біткоїн-гаманців використовують механізм BIP-32 для ієрархічної детермінованості: за допомогою одного основного відкритого ключа, не торкаючись приватного ключа, можна похідно отримати безліч дочірніх відкритих ключів. Наразі стандартизовані постквантові схеми підпису не підтримують цю функцію, тому ми досліджуємо витрати на додавання цієї можливості; також ми розглядаємо різноманітні нестандартні варіанти схем, які можуть принести більше вигоди.

Який рівень безпеки слід обрати?

Перед тим, як порівнювати розміри, потрібно визначити цільовий рівень безпеки, і цей вибір не такий простий, як здається. NIST класифікує рівні безпеки на 1-5; чим вищий рівень, тим сильніша безпека, але відповідно ключі та підписи також будуть більшими.

Ми вважаємо, що біткоїн повинен принаймні використовувати 3-й рівень безпеки. Виходи біткоїна можуть не витрачатися десятиліттями, і якщо технології криптоаналізу покращаться, що призведе до зниження фактичного рівня безпеки схеми, активи можуть бути заблоковані ключами, які втратили свою силу, і залишатися під ризиком протягом тривалого часу. Гіпотеза решіток вже витримала майже тридцять років публічного криптоаналізу, а дослідження, пов'язані з прийняттям біткоїном еліптичних кривих, тривають ще довше. Але складна алгебраїчна структура решіток все ще має багато вразливих місць, які можуть бути використані для атак у майбутньому, і ми не повинні ставити всі свої ставки на безпеку віддаленого майбутнього.

Всі основні продукти також дійшли до такого ж висновку. Протокол PQ3 від Apple для iMessage відмовляється від параметрів решіток 1-го рівня, використовуючи виключно параметри 3-го та 5-го рівнів; Cloudflare використовує ML-KEM-768 (3-й рівень) у впровадженні постквантового TLS, зазначаючи, що хоча 1-й рівень наразі виглядає безпечним, потрібно залишити запас безпеки для криптоаналізу на наступні десятиліття. А безпека біткоїна має ще більший часовий горизонт.

Підвищення рівня безпеки вимагає витрат. Наприклад, Dilithium, підвищуючи з 2-го до 3-го рівня, загальний розмір збільшується приблизно на 1,5 кілобайта. Звіт порівнює параметри для всіх рівнів безпеки, читачі можуть самостійно зважити плюси і мінуси. Досвід Hawk доводить, що обережні міркування щодо безпеки не є лише теорією.

Детальний опис кандидатів

Dilithium: проста схема

Dilithium був стандартизований NIST як ML-DSA у стандарті FIPS 204, він переносить парадигму зобов'язання-виклику-відповіді підпису Schnorr на модульну решіткову арифметику.

Його найбільша особливість - це простота. Всі обчислення Dilithium є цілими: операції в кільцях, множення матриць, хешування, округлення, без плаваючих операцій і без необхідності дискретного гауссового відбору. Це полегшує написання безпечних реалізацій з постійним часом. Це також найбільш широко впроваджений кандидат, вже інтегрований в OpenSSL, BoringSSL, AWS-LC та Apple CryptoKit.

Недолік - це великий обсяг. Для 3-го рівня безпеки ML-DSA-65, відкритий ключ становить 1952 байти, підпис - 3309 байтів, загалом 5261 байт, що приблизно в 55 разів більше, ніж загальний розмір відкритого та закритого ключів біткоїна + підпис.

Для біткоїна найбільш цінним аспектом Dilithium є те, що це єдина з трьох схем, яка наближається до реалізації похідних ключів у стилі BIP-32. Конструкція ключа DilithiumRK, що повторно випадковизує, може бути створена з батьківського ключа лише на основі публічної інформації. Звіт аналізує три варіанти, включаючи наш запропонований DilithiumRKS, де логіка похідності повністю розміщена в програмному забезпеченні гаманця, а на ланцюзі лише потрібно обробити звичайні підписи ML-DSA. Але жоден з трьох варіантів ще не досяг стандарту для впровадження: два з варіантів потребують зміни верифікатора, а DilithiumRKS сам по собі ще не має повного доказу непідробності; всі схеми залежать від загального використання матриць у мережі, хоча формально безпечні за припущенням Module-LWE, але це пов'язує безпеку всіх ключів до одного екземпляра. Ми вважаємо, що на даному етапі похідність відкритих ключів на основі Dilithium є лише концептуальним доказом і не може бути впроваджена на практиці.

Falcon: компактна схема

Falcon був обраний NIST, його стандартизоване ім'я - FN-DSA, з усіх трьох він є найкомпактнішим. Відкритий ключ і підпис Falcon-512 для 1-го рівня безпеки в сумі становлять 1563 байти; для 5-го рівня безпеки Falcon-1024 в сумі становить 3073 байти. Falcon-1024, з вищим запасом безпеки, навіть менший за 3-й рівень Dilithium.

Falcon використовує інший підхід, ніж Dilithium: базується на хеш-підписній моделі NTRU решітки. Приватний ключ підписувача є коротким базисом решітки; повідомлення хешується та відображається в точку в просторі, підписувач використовує короткий базис, щоб знайти вектор, що близький до цієї точки. Точка та цей сусідній вектор разом формують підпис; верифікація лише перевіряє, чи належить вектор до цієї решітки і чи достатньо близький. Складність реалізації полягає в тому, щоб знайти вектор, не розкриваючи інформацію про базис. Ранні схеми GGH, NTRUSign безпосередньо брали точки з решітки, кожен підпис розкривав частину геометричної інформації. Falcon використовує структуру GPV, щоб вибрати сусідній вектор з гауссового розподілу, що дозволяє довести, що вихід відбору незалежний від базису, усуваючи ризик витоку, але реалізація відбору значно ускладнюється.

Відбір є слабким місцем Falcon на інженерному рівні. Він вимагає обчислень у комплексній Фур'є-області, що потребує плаваючих обчислень. Різні процесори, компілятори та параметри оптимізації компіляції можуть призвести до несумісності результатів плаваючих обчислень. Це не лише проблема сумісності, а й загроза безпеці: вимоги до безпеки GPV вимагають, щоб підписувач ніколи не видавав дві різні короткі вектори для одного й того ж хешу; якщо підпис стає детермінованим, різниця в округленні плаваючих чисел на платформі може порушити цю умову. Є можливе рішення: детермінований Falcon може використовувати цілі числа для заміни апаратних плаваючих чисел, щоб забезпечити повну узгодженість підписів на всіх платформах. Ціна - це зниження швидкості підпису приблизно в 15 разів, а швидкість генерації ключів знижується приблизно в 2 рази.

Важливо, що етап верифікації не підлягає впливу: верифікація Falcon проходить через цілі обчислення, результати є детермінованими, і це також найшвидший варіант верифікації серед кандидатів. Ця асиметрична характеристика є дуже вигідною для біткоїна: підпис виконується гаманцем під час витратної транзакції, тоді як кожен підпис має бути перевірений всіма вузлами мережі. Сповільнення підпису в 15 разів є низькочастотними витратами, які забезпечують відтворюваність на різних платформах та цілісні обчислення, на нашу думку, є розумним компромісом. Тому проблема плаваючих чисел є перешкодою, яку можна вирішити інженерними засобами, а не фатальним недоліком.

Два моменти, на які слід звернути увагу: через структурні обмеження Falcon не має параметрів 3-го рівня, можна вибрати лише 1-й або 5-й рівень. З огляду на запас безпеки, ми рекомендуємо Falcon-1024. По-друге, підпис споживає велику кількість пам'яті: відбір для параметрів 1024 залежить від попередньо обчисленого дерева, яке займає близько 90 кілобайт пам'яті. Апаратні гаманці можуть динамічно відновити це дерево по гілках, зменшуючи використання пам'яті до 16 кілобайт, але час підпису подвоюється. Сповільнення підпису на апаратних пристроях є реальними витратами, але все ще прийнятними.

Hawk: оголошена невдача

Мета Hawk полягає в об'єднанні переваг двох інших схем: підпис Hawk-512 має лише 555 байтів, що менше, ніж Falcon; всі обчислення на стороні підпису є цілими, а мінімальне використання пам'яті становить лише 6 кілобайт. Це також єдиний кандидат на основі решіток, що залишився в третьому раунді додаткового конкурсу NIST, про який у звіті йдеться багато.

Недолік полягає в безпекових припущеннях. Він не використовує перевірені NTRU та SIS проблеми, а покладається на проблеми ізоморфізму решіток та припущення one-more-SVP, які мають відносно коротку історію досліджень.

Напередодні завершення звіту команда Anthropic, Стразнікас і Вейс, виявила структурні недоліки в конструкції Hawk: для відновлення ключа фактично потрібно вирішити SVP-проблему, яка має лише половину від уявленого дизайнерами розміру. Безпека відновлення ключа для кандидатних параметрів значно знижена. Дослідники завершили повну атаку на відновлення ключа для параметрів HAWK-256, що використовуються для криптоаналізу; навіть під час атаки офіційні пропозиції HAWK-512 та HAWK-1024 все ще не можуть бути зламані в реальності. Команда Hawk підтвердила ефективність атаки та відкликала схему з процесу NIST; команда зазначила, що якщо виправити вразливість, подвоївши параметри, то гордість Hawk у вигляді компактності зникне.

Звіт все ще містить розділ про Hawk, оскільки ця атака стосується алгебраїчних властивостей певного числового поля, а не повністю заперечує цю конструкцію. Чи можна уникнути вразливостей при повторному дизайні, поки що невідомо. Інцидент з Hawk також наочно підтверджує нашу позицію щодо обережного запасу безпеки: навіть якщо схема має відмінний обсяг, хорошу швидкість і проходить кілька раундів стандартизації, одна стаття може значно знизити її оцінений рівень безпеки.

Таблиця порівняння схем

У таблиці всі схеми (включаючи SPHINCS+) є безстатевими підписами: підписувач не повинен зберігати попередні підписи. Станові хеш-підписи, такі як XMSS, можуть досягти ще менших розмірів підпису, але вимагають підтримки стану підпису; можна звернутися до спеціального звіту про хеш-підписи для порівняння.

Існує багато перешкод для впровадження

Falcon не має доступних схем похідності ключів. Наразі єдина публічна схема похідності Falcon у стилі BIP-32 передбачає повторну випадковізацію бази приватного ключа, що різко збільшує верхню межу норми підпису, і підпис на ланцюзі роздувається до приблизно 23,7 кілобайт. І параметри цієї схеми не відповідають власним вимогам безпеки; якщо виправити цю проблему, обсяг ще більше зросте. Наразі немає здійсненної реалізації похідності відкритих ключів Falcon, що є найбільш цінним питанням, яке потрібно вирішити у звіті.

Стандарт Falcon ще не затверджений. Хоча NIST обрав Falcon, проект FN-DSA ще не був офіційно опублікований. Лише після завершення стандартизації з'являться перевірені реалізації, тестові вектори та підтримка на апаратному рівні. Широке впровадження може знизити ризики та складність інтеграції на рівні консенсусу біткоїна. Ми рекомендуємо дочекатися офіційного випуску FN-DSA, до цього моменту Falcon залишається в стані змін.

Варіант Falcon-WS: цей варіант послаблює внутрішні параметри, покладаючись на відмову від відбору для компенсації, загальний розмір 1-го рівня зменшується до 1114 байтів, 5-го рівня - до 2387 байтів, що ще більше зменшує обсяг у порівнянні з оригінальним Falcon. Цей напрямок має дослідницьку цінність, але не буде включений до офіційного стандарту, оскільки потребує додаткових перевірок криптоаналізу. Вже були виявлені вразливості в доказах сильної непідробності для його похідних схем (звичайна непідробність не підлягає впливу).

Чи з'являться кращі схеми в майбутньому? Окрім вищезгаданих схем, серія Fiat-Shamir, що бере початок з BLISS 2013 року, останні результати, представлені на конференції CRYPTO 2025 Гартнером, базуються на зрілих припущеннях, а їх розміри можуть зрівнятися з Falcon. Основна проблема реалізації цих схем полягає в питаннях безпеки: BLISS вже зазнав атаки на основі бокового каналу через нестабільний час відбору Гауса; подальші схеми не вирішили цю проблему, а останні результати також вказують на те, що захист від відбору є ще складнішим. До вирішення цих проблем ці схеми мають лише теоретичну привабливість і не підходять для впровадження.

Підписи на основі решіток можуть доповнювати хеш-підписи. Підписи на основі решіток можуть бути компонентами змішаних схем. Наприклад, у SHRINCS безстатева відновлювальна траєкторія наразі використовує підпис SPHINCS+ розміром кілька кілобайт; заміна його на підпис Falcon (або Falcon-WS) зменшить обсяг, прискорить верифікацію, значно зменшить витрати на відновлення низької частоти, не впливаючи на щоденні витрати.

Висновки дослідження

Рейтинг кандидатів на основі решіток є дуже чітким: Hawk вийшов з конкуренції після атаки команди Anthropic; Dilithium має найнижчу складність реалізації і є єдиною схемою, що має дослідження, пов'язані з похідністю ключів, але обсяг не є дружнім до витрат у біткоїн-мережі; Falcon поєднує компактний обсяг, швидку верифікацію та зрілі припущення безпеки; його основний недолік - плаваючі обчислення на стороні підпису, для яких вже існують здійсненні інженерні рішення. Якщо зараз потрібно вибрати схему підпису на основі решіток для біткоїна, ми оберемо Falcon-1024.

На даний момент наша думка залишається такою ж, як і в звіті про хеш-підписи: короткостроковий обережний шлях - це все ще хеш-підписи, оскільки їх припущення безпеки є найбільш зрілими, ризики є найнижчими, і вони підходять як перехідне рішення. Після офіційного затвердження FN-DSA, з наявністю стабільних стандартів, перевірених кодових баз та підтримки апаратних гаманців, Falcon принесе значні покращення в порівнянні з чистими хеш-підписами; також можна використовувати змішане впровадження, щоб обидві системи підписів доповнювали одна одну.

Цей контент надано лише для загальних інформаційних цілей і не є фінансовою, інвестиційною, юридичною чи податковою консультацією. Події, нагороди, онлайн-акцій або пов’язану інформацію, згадана тут, не слід розглядати як рекомендацію, прохання чи запрошення до купівлі, продажу, торгівлі чи інших операцій з криптоактивами. Криптоактиви є дуже волатильними та можуть призвести до збитків. Доступність послуг, продуктів WEEX та пов’язаних із ними подій може відрізнятися залежно від регіону. Ви несете відповідальність за забезпечення відповідності вашої участі чинному місцевому законодавству та нормативним актам.