Progowy ECDSA: podpisywanie wielostronne

Podpisy ECDSA wymagają obliczenia losowego nonce k, punktu krzywej R = k*G oraz podpisu s = k^{-1}(h + r*x) mod n, gdzie x jest kluczem prywatnym, a r współrzędną x punktu R. Konieczność obliczenia odwrotności k i mnożenie przez klucz prywatny sprawiają, że ECDSA jest z natury nieliniowy, w przeciwieństwie do podpisów Schnorra, w których odpowiedź jest prostą kombinacją liniową. Ta nieliniowość sprawia, że rozdzielenie obliczeń między strony jest niezwykle trudne.

Protokół GG18 autorstwa Gennaro i Goldfedera (2018) był pierwszą praktyczną konstrukcją dwu- i wielostronnego podpisu ECDSA w modelu progowym, bezpieczną bez zaufanego dealera. Kluczowym pomysłem jest użycie homomorficznego szyfrowania Pailliera do przeprowadzenia konwersji z mnożenia na dodawanie (MtA), niezbędnej w nieliniowych obliczeniach ECDSA. GG18 zapewnia bezpieczeństwo w modelu symulacyjnym wobec statycznych przeciwników półuczciwych.

GG20 (Gennaro i Goldfeder 2020) udoskonalił GG18, dowodząc bezpieczeństwa wobec złośliwych przeciwników bez zaufanej konfiguracji początkowej. GG20 dodał dowody z wiedzą zerową, aby zagwarantować, że każda strona prawidłowo wykonuje protokół. Dowody te uniemożliwiają złośliwej stronie manipulowanie wartością nonce lub podpisem w celu wydobycia informacji o udziałach kluczy innych stron. GG20 stał się podstawą wielu produkcyjnych implementacji portfeli MPC.

CGGMP21 (Canetti, Gennaro, Goldfeder, Makriyannis, Peled, 2021) to obecnie najnowocześniejszy protokół progowego ECDSA. Zapewnia identyfikowalne przerwanie, co oznacza, że jeśli protokół podpisywania zakończy się niepowodzeniem z powodu złośliwego działania, można ustalić, która strona ponosi za to odpowiedzialność. Ma to kluczowe znaczenie we wdrożeniach korporacyjnych, w których istotna jest rozliczalność. CGGMP21 zaimplementowano w popularnych bibliotekach MPC, w tym tss-lib i multi-party-sig.

Głównym wyzwaniem w progowym ECDSA jest obliczenie iloczynu udziałów w sekrecie bez ich ujawniania. Konwersja MtA (z postaci multiplikatywnej na addytywną) przekształca iloczyn a*b udziałów dwóch stron w udziały addytywne: strona 1 otrzymuje alpha, a strona 2 beta, przy czym alpha + beta = a*b. Osiąga się to za pomocą szyfrowania Pailliera: strona 1 szyfruje a, strona 2 wykonuje homomorficzne mnożenie przez b i dodaje losowość, a następnie strona 1 odszyfrowuje wynik, uzyskując udziały addytywne.

Szyfrowanie Pailliera to częściowo homomorficzny schemat szyfrowania obsługujący zarówno dodawanie, jak i mnożenie przez tekst jawny. Mając szyfrogram Enc(a), można obliczyć Enc(a*b) dla znanej wartości b bez odszyfrowywania. Ta właściwość umożliwia działanie protokołu MtA: strona 1 generuje parę kluczy Pailliera i wysyła Enc(k1) oraz Enc(x1) (udziały nonce i klucza prywatnego). Strona 2 korzysta z operacji homomorficznych, aby obliczyć swój wkład bez poznania k1 ani x1.

Podpisywanie w progowym ECDSA zazwyczaj obejmuje kilka rund komunikacji. W GG20 występuje faza przygotowawcza (2 rundy), w której obliczane są zobowiązania do nonce i losowych wartości maskujących, oraz faza podpisywania online (1 runda), w której łączone są częściowe podpisy. Fazę przygotowawczą można przeprowadzić przed poznaniem wiadomości, skracając opóźnienie podpisywania online do jednej rundy. CGGMP21 dodatkowo optymalizuje ten proces.

Identyfikowalne przerwanie oznacza, że jeśli protokół progowego podpisywania zakończy się niepowodzeniem (ponieważ jedna ze stron wysłała niepoprawną wiadomość lub nie przestrzegała protokołu), uczciwe strony mogą kryptograficznie ustalić, która strona zachowała się nieprawidłowo. Wymaga to dowodów z wiedzą zerową poprawnego wykonania obliczeń na każdym etapie. Bez identyfikowalnego przerwania złośliwa strona mogłaby spowodować odmowę usługi (odmówić ukończenia protokołu), pozostając niezidentyfikowana.

EdDSA (podpisy oparte na Schnorrze nad Ed25519) znacznie łatwiej zaadaptować do schematu progowego niż ECDSA, ponieważ podpisy Schnorra mają strukturę liniową: odpowiedź z = r + c*x jest sumą udziałów addytywnych. FROST (Flexible Round-Optimized Schnorr Threshold) autorstwa Komlo i Goldberga (2020) umożliwia dwu­rundowe progowe podpisywanie Schnorra bez zaufanej konfiguracji. FROST jest standaryzowany przez IETF (projekt dokumentu RFC) do zastosowania w protokołach chroniących prywatność i portfelach kryptowalut.

Progowy ECDSA wymaga większych nakładów obliczeniowych niż jednoosobowy ECDSA ze względu na protokół MtA i dowody z wiedzą zerową. Podpisywanie dwuosobowe w GG20 trwa około 1–2 sekund na nowoczesnym sprzęcie; w przypadku progowego ECDSA z większą liczbą uczestników trwa to dłużej z powodu większej liczby par wykonywanych operacji MtA. Optymalizacje CGGMP21 skracają ten czas do setek milisekund. W przypadku transakcji kryptowalutowych, gdzie opóźnienie podpisywania ma znaczenie, taka wydajność jest akceptowalna, ale nadal stanowi istotny czynnik.

Progowy ECDSA jest wdrażany na dużą skalę w instytucjach finansowych. Fireblocks korzysta z progowego ECDSA opartego na GG20, zabezpieczając transakcje o łącznym wolumenie przekraczającym 4 biliony dolarów. Coinbase Prime korzysta z powiernictwa MPC opartego na podpisach progowych. Qredo i Copper.co oferują progowy ECDSA do zarządzania aktywami instytucjonalnymi. Biblioteka tss-lib dla języka Go (używana przez Binance) oraz multi-party-sig (używana przez Coinbase) to najważniejsze implementacje open source.

Jaką rolę odgrywa homomorficzne szyfrowanie Pailliera w progowym ECDSA?

Progowy ECDSA pozwala t uczestnikom podpisywać wiadomości bez ujawniania pełnego klucza któremukolwiek z nich. Nieliniowa struktura ECDSA wymaga konwersji MtA z użyciem homomorficznego szyfrowania Pailliera. GG18 zapoczątkował to podejście, GG20 dodał bezpieczeństwo w obecności złośliwych uczestników, a CGGMP21 wprowadził identyfikowalne przerwanie. EdDSA/Schnorr łatwiej zaadaptować do schematu progowego za pomocą FROST (2 rundy, bez zaufanej konfiguracji). Wdrożenia produkcyjne w Fireblocks i Coinbase zabezpieczają aktywa o wartości bilionów.