Problem współdzielenia sekretu

Masz klucz główny, który musi przetrwać, być dostępny w sytuacjach awaryjnych, a jednocześnie nigdy nie może zostać przejęty przez jedną osobę. Jak go przechowywać? Przekazanie pełnego klucza wielu osobom oznacza, że każda z nich może go niewłaściwie wykorzystać. Przechowywanie jednej kopii tworzy pojedynczy punkt awarii.

Podzielenie 128-bitowego klucza na dwie 64-bitowe połowy i przekazanie każdej z nich jednej z dwóch osób wydaje się sprytne, ale jest niebezpieczne: każda połowa obniża koszt brute force z 2^128 do 2^64. Przeciwnik, który przejmie kontrolę nad jedną osobą, zyskuje przewagę odpowiadającą 64 bitom.

Poprawny schemat dzielenia sekretu musi zapewniać: (1) Próg: dowolne k z n udziałów odtwarza sekret. (2) Bezpieczeństwo: dowolne (k-1) udziałów nie ujawnia żadnych informacji o sekrecie. (3) Doskonałość: nie są wymagane żadne założenia obliczeniowe.

Portfele Bitcoin, główne klucze HSM, klucze prywatne urzędów certyfikacji, kody uruchomienia broni jądrowej oraz zimne portfele giełd kryptowalutowych wymagają dostępu progowego. Utrata pojedynczego klucza oznacza katastrofę. Przejęcie klucza przez jednego insidera również oznacza katastrofę.

Aby podzielić sekret S między dwie strony: wygeneruj losowe R. Przekaż share1=R stronie 1, a share2=S XOR R stronie 2. Aby odtworzyć sekret: share1 XOR share2 = R XOR (S XOR R) = S. Każdy udział z osobna jest doskonale losowy — nie ujawnia nic o S.

Dzielenie XOR jest doskonałe dla schematu 2-z-2, ale nie uogólnia się na progowe schematy k-z-n. Nie można utworzyć schematu 3-z-5, w którym dowolne 3 udziały odtwarzają sekret, a dowolne 2 nie ujawniają nic. Interpolacja wielomianowa rozwiązuje ten problem.

Doskonała tajność oznacza, że udziały zawierają zero wzajemnej informacji o sekrecie, jeśli dostępnych jest mniej niż k udziałów. Jest to silniejsze niż bezpieczeństwo obliczeniowe — nawet przeciwnik dysponujący nieograniczoną mocą obliczeniową nie dowie się niczego z k-1 udziałów.

AWS CloudHSM używa uwierzytelniania kworum M-z-N. Depozyt kluczy PGP dzieli klucze główne. Dostawcy przechowywania kryptowalut (Fireblocks, BitGo) używają MPC lub schematu Shamira dla kluczy gorących portfeli. Klucze offline urzędów certyfikacji wykorzystują ceremonie 5-z-7.

Ceremonia klucza to formalny, audytowany proces generowania i dzielenia klucza głównego. Przykład: 7 posiadaczy klucza znajduje się w bezpiecznym pomieszczeniu, a każdy otrzymuje sprzętowy token z jednym udziałem. Proces jest nagrywany wideo, uczestniczy w nim dwóch audytorów, a każdy krok jest dokumentowany.

Dzielenie sekretu odtwarza pełny sekret (ryzyko: pojedynczy punkt awarii w chwili odtwarzania). Multisig rozdziela podpisywanie: każda strona podpisuje niezależnie, a podpisy są łączone. Podpisy progowe (TSS) to dzielenie sekretu zastosowane bezpośrednio do operacji podpisywania.

Bezpieczne obliczenia wielostronne (MPC) całkowicie eliminują etap odtwarzania — strony wspólnie wykonują obliczenia z użyciem swoich udziałów, nie ujawniając sekretu. Progowe ECDSA i progowe BLS są wdrażane w produkcyjnych systemach przechowywania kryptowalut.

Naiwny podział klucza jest niebezpieczny. Poprawne dzielenie sekretu wymaga dostępu progowego z doskonałą tajnością. XOR obsługuje schemat 2-z-2, a interpolacja wielomianowa schemat k-z-n. Dalej: matematyka schematu Shamir's Secret Sharing.