Тема 4: TSS: Пороговые подписи

Основные составные механизмы и их свойства, особенности обеспечения безопасности, атака на частный случай протокола ICE FROST.

Алексей Курочкин, криптограф-исследователь в лаборатории блокчейн Сбера, преподаватель кафедры высшей математики и магистратуры блокчейн в МФТИ

Transcript

1. СБЕР - Лабратория блокчейн 5 апреля 2025 г. Механизмы пороговой подписи: 1 / 31
2. «Понять - значит упростить» Что такое пороговая подпись «простым» языком? Пусть есть n P N участников протокола, и параметр t P 1, n порог. Тогда пороговой (n, t) подписью называется такая подпись которую может сформировать любая группа, состоящая из t или более участников протокола. Проверить подпись может любой желающий. ⌣1 jj ""  ⌣4 Sig ⌣2 oo ⌣3 tt ... tt yy Пороговая (3, 4) подпись 2 / 31
3. О дивный новый мир: «Как бы интересно стало жить на свете, если бы можно было отбросить заботу о .... криптографии» Ситуация в Российской Федерации в области пороговых механизмов. 02.2019 ЦБ РФ - Рекомендации 01.2020 ЦБ РФ - Требования 08.2020 ЦИК, Ростелеком 2024 НИР § рекомендуется использовать аппаратные модули безопасности (HSM) сертифицированные ФСБ РФ; § требуется использовать пороговые механизмы для защиты ключей в HSM; § дистанционное голосование в котором реализовано проверяемое разделение секрета; § НИР Академии криптографии РФ. 3 / 31
4. О дивный новый мир: «Как бы интересно стало жить на свете, если бы можно было отбросить заботу о .... криптографии» Ситуация за рубежом в области пороговых механизмов. 2019-2020 NIST - Начало 2021 NIST - Призыв 2021 ITF - инициатива 2023 NIST - Будущий конкурс 2024 RFC § документ «Threshold Schemes for Cryptographic Primitives Challenges and Opportunities in Standardization and Validation of Threshold Cryptography»; § документ «Call 2021a for Feedback on Criteria for Threshold Schemes»; § C.Komlo, I.Goldberg, T.Wilson-Brown. «Two-Round Threshold Signatures with FROST»; § документ «NIST First Call for Multi-Party Threshold Schemes»; § документ «The Flexible Round-Optimized Schnorr Threshold (FROST) Protocol for Two Round Schnorr Signatures. RFC 9591.». 4 / 31
5. Трудно быть богом: «Назад идти нельзя» Общая модель пороговой подписи:
6. Трудно быть богом: «Назад идти нельзя» Общая модель пороговой подписи: - проверяемое разделение секрета
7. Трудно быть богом: «Назад идти нельзя» Общая модель пороговой подписи: - проверяемое разделение секрета - выявление нарушителей
8. Трудно быть богом: «Назад идти нельзя» Общая модель пороговой подписи: - проверяемое разделение секрета - выявление нарушителей - формирование подписи 5 / 31
9. «В отделе Вечной Молодости после долгой и продолжительной болезни скончалась модель бессмертного человека.» Общая модель пороговой подписи: Децентрализованная генерация ключа Схема разделения секрета Шамира Проверяемое разделение секрета Фелдмана Генерация ключа Педерсена
10. «В отделе Вечной Молодости после долгой и продолжительной болезни скончалась модель бессмертного человека.» Общая модель пороговой подписи: Децентрализованная генерация ключа Схема разделения секрета Шамира Проверяемое разделение секрета Фелдмана Генерация ключа Педерсена Выявление нарушителей Проверяемое разделение секрета Фелдмана Доказательства с нулевым разглашением
11. «В отделе Вечной Молодости после долгой и продолжительной болезни скончалась модель бессмертного человека.» Общая модель пороговой подписи: Децентрализованная генерация ключа Схема разделения секрета Шамира Проверяемое разделение секрета Фелдмана Генерация ключа Педерсена Выявление нарушителей Проверяемое разделение секрета Фелдмана Доказательства с нулевым разглашением Формирование подписи Проверяемые случайные функции Адаптированные крипто-подписи 6 / 31
12. «Понять - значит упростить» Пороговая схема разделения секрета? Протокол (с n участниками) в котором множество из более, чем t участников протокола могут восстановить разделённый секрет. Схема разделения секрета, как правило, состоит из двух фаз: § фаза разделения секрета; § фаза восстановления секрета. 7 / 31
13. «Понять - значит упростить» Обозначим: – дилер, т.е. участник протокола обмена который делится секретом S; ⌣ – честный участник протокола, получает долю секрета si , i = 1, m; – нарушитель. 8 / 31
14. «Понять - значит упростить» Фаза разделение секрета схематично S ~~ s1 ww  22 sm 99 ⌣ m ⌣ . . . ⌣ ⌣ 9 / 31
15. «Понять - значит упростить» Фаза восстановления секрета схематично ⌣s1 RR ØØ jj ""  ⌣sm GG S ⌣s2 oo ⌣ CC …… ss ... tt yy 10 / 31
16. «Понять - значит упростить» Фаза разделение секрета Шаг 1: Дилер случайным образом выбирает многочлен (коэффициенты многочлена ai, i = 1, t степени t ´ 1 над полем P = Zq: f(x) = a0 + a1 ¨ x + . . . + at´1xt´1, значение s = a0 секрет который впоследствии необходимо восстановить. Шаг 2: Дилер вычисляет значения si = f(i), i = 1, n и передает их участнику с соответствующим номером. Значения si это доля секрета участника с номером i. 11 / 31
17. «Понять - значит упростить» Фаза восстановления секрета Восстановить секрет можно двумя способами: § Решить систему линейных уравнений. § С помощью интерполяционной формулы Лагранжа. Пусть tj1, j2, . . . , jtu Ă t1, 2, . . . , nu. f(x) = t ÿ k=1 ź i=1 i‰k x ´ ji jk ´ ji ¨ sk s =f(0) = t ÿ k=1 ź i=1 i‰k ´ji jk ´ ji ¨ sk = t ÿ k=1 λk ¨ sk 12 / 31
18. Сказка о тройке: «Говорят, говорят, и сами не знают, что говорят. . . » Свойства § данная схема является идеальной; 13 / 31
19. Сказка о тройке: «Говорят, говорят, и сами не знают, что говорят. . . » Свойства § данная схема является идеальной; § данная схема является совершенной; 13 / 31
20. Сказка о тройке: «Говорят, говорят, и сами не знают, что говорят. . . » Свойства § данная схема является идеальной; § данная схема является совершенной; § возможность динамической замены долей секрета; 13 / 31
21. Сказка о тройке: «Говорят, говорят, и сами не знают, что говорят. . . » Свойства § данная схема является идеальной; § данная схема является совершенной; § возможность динамической замены долей секрета; § возможность неравномерного распределения долей секрета; 13 / 31
22. Сказка о тройке: «Говорят, говорят, и сами не знают, что говорят. . . » Свойства § данная схема является идеальной; § данная схема является совершенной; § возможность динамической замены долей секрета; § возможность неравномерного распределения долей секрета; § может в фазе обмена делиться неправильной долей секрета, тем самым нарушая выполнение протокола. При этом не ясно кто нарушает протокол. 13 / 31
23. Проблема в фазе восстановления секрета схематично ⌣s1 RR ØØ jj ""  ⌣sm GG S ⌣s2 oo CC …… ss ... tt yy 14 / 31
24. Сказка о тройке: «Говорят, говорят, и сами не знают, что говорят. . . » Проверяемая (верифицируемая) пороговая схема разделения секрета? Следующий шагом развития области разделения секрета стала концепция проверяемого совместного использования секрета (VSS). Новизна заключается в том, что участники протокола могут проверить, что они получили достоверную часть секрета. § фаза разделения секрета; § фаза верификации и восстановления секрета. 15 / 31
25. Часть I (Распределение секрета) Дилер P совершает следующие действия: Шаг 1: Формирует многочлен f : Zq Ñ Zq со случайно выбранными коэффициентами коэффициентами a1, . . . , at´1, а a0 = s это секрет: f(x) = a0 + a1 ¨ x + . . . + at´1 ¨ xt´1. Шаг 2: Дилер вычистляет доли секрета для участников si = f(i) и следующие элементы группы (пусть циклическая подгруппа группы точек эллиптической кривой) Gq которые необходимы для проверки секрета: Cj = gcj , где j = 1, n. Набор tCiu задаёт следующее отображение F : Zq Ñ Gq, где F(x) = gf(x) = C0 ¨ Cx 1 ¨ . . . ¨ Cxt . 16 / 31
26. Часть I (Распределение секрета) Дилер P совершает следующие действия: Шаг 3: Дилер передаёт участнику Pi долю секрета si , где i = 1, n. Шаг 4: Дилер передаёт всем участникам протокола набор значений (C1, C2, . . . , Cn). 17 / 31
27. Часть II (Верификация и восстановление секрета) Шаг 5: Для проверки корректности секрета участнику Pi необходимо установить справедливость равенства: gsi = F(i) = gf(i). 18 / 31
28. Часть III Shnorr - ZKP Пусть есть два участника протокола: – участник протокола, который хочет доказать, что доказать, что знает дискретный логарифм y = gx по основанию g, где g примитивный элемент группы G; 19 / 31
29. Часть III Shnorr - ZKP Пусть есть два участника протокола: – участник протокола, который хочет доказать, что доказать, что знает дискретный логарифм y = gx по основанию g, где g примитивный элемент группы G; – участник протокола которому доказывает знание дискретного логарифма, т.е. x. 19 / 31
30. Шаг 1. (Подготовка) совершает следующие действия: Шаг 1: Выбирает случайно число v P Zq, и вычисляет t = gv; Значения t, c, r называются обязательством, вызовом и ответом соответственно. 20 / 31
31. Шаг 1. (Подготовка) совершает следующие действия: Шаг 1: Выбирает случайно число v P Zq, и вычисляет t = gv; Шаг 2: Вычисляет c = H(g, y, t), где H – некоторая криптографическая хэш-функция; Значения t, c, r называются обязательством, вызовом и ответом соответственно. 20 / 31
32. Шаг 1. (Подготовка) совершает следующие действия: Шаг 1: Выбирает случайно число v P Zq, и вычисляет t = gv; Шаг 2: Вычисляет c = H(g, y, t), где H – некоторая криптографическая хэш-функция; Шаг 3: Вычисляет r = v ´ c ¨ x mod q. Значения t, c, r называются обязательством, вызовом и ответом соответственно. 20 / 31
33. Шаг 1. (Подготовка) совершает следующие действия: Шаг 1: Выбирает случайно число v P Zq, и вычисляет t = gv; Шаг 2: Вычисляет c = H(g, y, t), где H – некоторая криптографическая хэш-функция; Шаг 3: Вычисляет r = v ´ c ¨ x mod q. Шаг 4: Публикует пару (c, r). Значения t, c, r называются обязательством, вызовом и ответом соответственно. 20 / 31
34. Шаг 2 (Доказательство знания) совершает следующие действия: Шаг 1: Вычисляет значение t1 = gr ¨ yc = gv´c¨x + c ¨ x = gv = t; 21 / 31
35. Шаг 2 (Доказательство знания) совершает следующие действия: Шаг 1: Вычисляет значение t1 = gr ¨ yc = gv´c¨x + c ¨ x = gv = t; Шаг 2: Проверяет справедливость равентсва: c = H(g, y, t1). 21 / 31
36. Формирование пороговой подписи на основе подписи Шнорра. В данный момент предположим, что все участники P1, P2, . . . , Pm, где t ď m ă n удачно сформировали: § секретные доли ключа s1, s2, . . . , sm; § публичные доли ключей p1, p2, . . . , pm; § общий публичный ключ P, который соответсвует общему секретному ключу, но при этом общий секретный ключ никогда явно не «собирается» ; § хотят подписать сообщение Text. 22 / 31
37. Формирование пороговой подписи на основе подписи Шнорра. Шаг 1 § Каждый участник Pi случайно формирует значение (в общем случае список значений) ri и публикует значение Ri = gri ; Далее для простоты положим, что только t участников формируют подпись. 23 / 31
38. Формирование пороговой подписи на основе подписи Шнорра. Шаг 2 § Каждый участник Pi вычиляет значение R = t ś j=1 Ri; § Вычисляется значение S1 = Hash(R||P||Text); § Вычисляется значение S2i: S2i = ri + λi ¨ si ¨ S1 (mod q); § Итоговое подпись имеет вид: (S1, t ř j=1 S2j ), где t ÿ j=1 S2j = t ÿ j=1 rj + λj ¨ sj ¨ S1 = t ÿ j=1 ri + s ¨ S1. 24 / 31
39. Протокол генерации ключей. Шаг 1 § Каждый участник Pi формирует многочлен fi (x) = a0i + ¨ ¨ ¨ , вектор обязательств ⃗ Ci = (ga0i , . . .), пару секретный, открытый ключ ski, pki, доказательства знания секретного ключа zkp(ski ) и знания секрета zkp(ga0i ); § Каждый участник транслирует остальным значения ⃗ Ci, pki, zkp(ski ), zkp(ga0i ); § затем все участники проверяют zkp и переходят на следующий шаг; 25 / 31
40. Протокол генерации ключей. Шаг 2 § Каждый участник Pi отправляет остальным участникам зашифрованную в режиме гаммирования долю ключа fi (j) ‘ γ, по каналу защищенному каналу; § Каждый участник проверяет кореектность долей; § В случае ошибок участники инициируют протокол решения споров; § Если ошибок нет, то участники формирую общий публичный ключ и завершают протокол. 26 / 31
41. 27 / 31
42. Атака на протокол генерации ключей для трех участников. ⃗ C1 = (ga01 , . . . ⃗ C1 = (ga01 ¨ g, . . . 28 / 31
43. Атака на протокол генерации ключей для трех участников. f1 (2) ‘ γ f1 (2) ‘ γ ‘ 1 29 / 31
44. Выводы § С вероятностью 1 2 некорректная доля ключа будет принята: gf1(2)‘1 = gf12+1; § Ключ подписи участника который действовал честно будет некорректным. 30 / 31
45. 31 / 31