Ten post został po raz pierwszy opublikowany na Medium.
Rozproszone generowanie klucza (DKG) to protokół kryptograficzny, który umożliwia wielu stronom wspólne generowanie wspólnego klucza tak, aby żadna ze stron nie poznała całego klucza. Zwiększa bezpieczeństwo w różnych aplikacjach poprzez dystrybucję zaufania pomiędzy wieloma uczestnikami, zmniejszając ryzyko naruszenia kluczowych zabezpieczeń. Wprowadzamy weryfikowalny i pozbawiony dealerów DKG, który można zastosować w blockchainach.
Udostępnianie sekretów Shamira (SSS)
Shamir’s Secret Sharing (SSS) to metoda kryptograficzna, która umożliwia podzielenie sekretu na części, przy czym każdy uczestnik przechowuje część sekretu, zwaną udziałem. Kluczową cechą SSS jest to, że sekret można odtworzyć tylko wtedy, gdy zdefiniowana liczba udziałów, zwana progiem, zostanie połączona razem. Jest to schemat progowy, oznaczony jako (t,n), gdzie n jest całkowitą liczbą rozdzielonych udziałów, a t jest minimalną liczbą udziałów wymaganą do odtworzenia tajemnicy.
Sercem schematu SSS jest koncepcja matematyczna, która wskazuje, że punkty jednoznacznie definiują wielomiany. W szczególności potrzeba dwóch punktów, aby zdefiniować linię, trzech punktów, aby zdefiniować parabolę i tak dalej. Zatem wielomian stopnia (t-1) jest jednoznacznie określony przez t punktów. W tym schemacie wielomian stopnia (t-1) jest skonstruowany w taki sposób, że każdy z n
uczestnicy są powiązani z jednym punktem tego wielomianu, który koduje tajemnicę. Aby odzyskać wielomian, a tym samym sekret, potrzeba tylko t tych punktów. Dowolna grupa t uczestników, z których każdy ma swój udział, może zrekonstruować pierwotny wielomian stopnia (t-1). Sekret jest osadzony w wielomianie jako punkt przecięcia y, co oznacza wartość wielomianu przy x=0, co w rzeczywistości czyni go stałym wyrazem wielomianu. Dzięki tej metodzie sekret można bezpiecznie i dokładnie odzyskać.
Przeanalizujmy (3, 4) schemat udostępniania sekretów. Podmiot odpowiedzialny za podzielenie tajemnicy, zwany dealerem, konstruuje wielomian stopnia 2, czyli (t-1):
f(x) = s + a₁x + a₂x²
s reprezentuje tajną wartość w punkcie przecięcia z y (tj. f(0)), podczas gdy a₁ i a₂ są liczbami losowymi.
SSS składa się z dwóch podstawowych procesów:
dystrybucja tajnych udziałów: w fazie dystrybucji krupier dzieli sekret na kilka części, czyli udziałów, i rozdziela je pomiędzy grupę n (tj. 4) uczestników. Każdy uczestnik Pᵢ otrzymuje udział sᵢ = f(I).
rekonstrukcja tajemnicy: proces rekonstrukcji pozwala tylko t (tj. 3) uczestnikom połączyć swoje udziały i odzyskać pierwotną tajemnicę, podczas gdy żadna inna grupa mniejsza niż t udziałów nie może wywnioskować niczego istotnego na temat tajemnicy. Na przykład pierwszych 3 uczestników może utworzyć zbiór punktów (1, s₁), (2, s₂) i (3, s₃) i zrekonstruować unikalny wielomian f(x), zwykle stosując metodę interpolacji Lagrange’a. Sekret s to po prostu f(0).
Weryfikowalne udostępnianie sekretów (VSS)
W Shamir Secret Sharing uczestnik nie wie, czy udział, który otrzymuje, jest zgodny z udziałami, które otrzymali inni uczestnicy. Na przykład złośliwy handlarz przyznaje P₁, P₂ i P₃ prawidłowe udziały f(1), f(2) i f(3), ale daje P₄ zły udział, tj. nie f(4). Jeżeli P₄ zostanie wybrane później, tajnej wartości nie będzie można poprawnie odzyskać.
Verible Secret Sharing (VSS) to rozszerzenie schematu Shamir’s Secret Sharing, które umożliwia weryfikację udostępnień sekretu pod kątem ich poprawności. Odbywa się to bez ujawniania samych udziałów, w przeciwnym razie każdy zna wszystkie udziały i w ten sposób może odzyskać sam sekret, pokonując cały cel dzielenia się sekretem.
W VSS dealer wysyła każdemu uczestnikowi zobowiązania dotyczące wszystkich współczynników wielomianu, oprócz udziału. Jednym ze sposobów zatwierdzenia jest użycie krzywej eliptycznej:
c₀ = sG
c₁ = a₁G
c₂ = a₂G
cᵢ zobowiązuje się do aᵢ. G jest punktem generatora.
Pᵢ może samodzielnie zweryfikować ważność swojego udziału, sprawdzając, czy zachodzi równość:
f(i)G =? c₀ + c₁i + c₂i²
To dlatego, że
f(i)G = (s + a₁i + a₂i²)G = sG + a₁iG + a₂i²G = c₀ + c₁i + c₂i²
Zauważ, że zna wszystkie informacje potrzebne w równaniu. Jeśli równanie nie jest spełnione, wie, że sprzedawca jest nieuczciwy i może po prostu zakończyć współpracę.
Rozproszone generowanie kluczy
Na tym etapie opanowaliśmy technikę dystrybucji naszego klucza, tak aby wszyscy uczestnicy go otrzymali i mogli go zweryfikować. Mamy jednak problem – dealer zna pierwotny sekret.
Rozproszone generowanie kluczy (DKG) rozwiązuje ten problem, umożliwiając każdemu uczestnikowi udział w ogólnej losowości klucza. Dealerless DKG zasadniczo prowadzi n niezależnych przebiegów VSS. W i-tym biegu Pᵢ pełni rolę dealera, który rozprowadza tajne sᵢ. Każdy uczestnik zbiera tajne udziały od pozostałych uczestników, a ostateczny udział jest sumą udziałów w każdym biegu. Ostatni sekret to suma sekretów we wszystkich seriach.
Aby zobaczyć dlaczego, rozważmy następujące dwa wielomiany reprezentujące tajemnicę aib:
f₁(x) = a + a₁x + a₂x² + …
f₂(x) = b + b₁x + b₂x² + …
Te dwa wielomiany można zsumować, tworząc końcowy wielomian tajnego klucza:
f(x) = (a+b) + (a₁+b₁)x + (a₂+b₂)x² + …
f(x) koduje sekret a+b, który jest sumą dwóch indywidualnych sekretów. Jego udziały są również sumą dwóch indywidualnych udziałów pierwotnych dwóch wielomianów.
Autor : BitcoinSV.pl
Źródło : Distributed Key Generation: Verifiable and dealerless – CoinGeek
