BLS podpis (Boneh-Lynn-Shacham) je elektronický podpis založený na křivkách , které se snadno spárují a podporuje neinteraktivní agregační vlastnosti. To znamená, že pro skupinu podpisů (σ 1 , …, σ n ) lze sestavit krátký podpis σ, který autentizuje celou sbírku podpisů. Podpisové schéma je jednoduché, efektivní a lze jej použít v různých síťových protokolech a systémech ke kompresi podpisů nebo řetězců certifikátů. Protože je výpočetní problém Diffie-Hellman neřešitelný, bezpečnost obvodu byla prokázána.
Jelikož signatura BLS pracuje s eliptickými křivkami, je nutné upravit standardní hašovací funkce tak, aby výstupem nebylo číslo, ale souřadnice bodu [1] . Vezměme si za základ standardní hašovací funkci, ale výsledek její práce budeme považovat nikoli za konečné číslo, ale za x-ovou souřadnici bodu. Každé nalezené x může mít nulu nebo dvě hodnoty y, takže ne každé x má platné y. Proto budeme hashovat (msg || i), dokud nedostaneme správný výsledek, kde || je funkce zřetězení a i je nezáporné číslo. Zbývá pouze určit zákon pro výběr jednoho ze získaných bodů (např. bude bod s největší hodnotou y).
Chcete-li vytvořit podpis, potřebujete funkci, která spojí dva body křivky s určitým číslem. Uveďme abstraktní definici párování. Nechť G, G T jsou cyklické skupiny prvořadého řádu r generované prvkem g. Párování je efektivně vyčíslitelná funkce e : G 1 × G 2 → G T , pro kterou platí následující vlastnosti:
Nejběžnější v kryptografii jsou párovací funkce Tate, Weil a optimální párování Ait [2] . Ten je považován za nejúčinnější a v praxi se nejčastěji používá.
Pokud je párovací funkce definována pro cyklickou skupinu, pak výpočetní Diffie-Hellmanův problém a problém diskrétního logaritmu jsou pro tuto skupinu neřešitelné , ale existuje efektivní řešení Diffieho-Hellmanova rozhodovacího problému. Takové skupiny se nazývají Diffie-Hellmanovy skupiny [3] a implikují podpisové schéma zvané Bonet-Lynn-Shahamův podpis.
Nechť G je Diffie-Hellmanova grupa prvořadého řádu r, kde g ∈ G je generující prvek grupy, m je daná zpráva.
Soukromý klíč SK je náhodné celé číslo vybrané z intervalu [0, r-1]. Veřejný klíč se nazývá PK = g SK
Předpokládejme, že máme podpisovou skupinu, která obsahuje n párů ( Si , PKi ), kde i = [0,n]. Souhrnný podpis systému je součet S i nad i. Pro potvrzení podpisu je nutné zkontrolovat rovnost e(g, S) = e(PK 1 , H 1 ) ⋅ e(PK 2 , H 2 ) ⋅ … ⋅ e(PK n , H n ).
Pro ověření není nutné znát zprávy odpovídající jednotlivým podpisům, ale je nutné znát všechny veřejné klíče a provést párovací operaci n + 1x.
Kontrola (g, S) = e(g, S 1 + S 2 + …+ S n ) = e (g, S 1 )⋅ e(g, S 2 ) ⋅ … ⋅ e(g, S n ) = e (g, H 1 PK 1 ) ⋅ … ⋅ e(g, H n PK n ) = e (g PK 1 , H 1 ) ⋅ … ⋅ e (g PK n , H n ) = e (SK 1 , H 1 ) ⋅ e(SK 2 , H 2 )⋅…⋅e (SK n , H n )
Pro vytvoření vícenásobného podpisu podepíšeme stejnou transakci různými klíči. Poté můžeme pro optimalizaci paměti spojit všechny podpisy a klíče do páru, který definuje celý systém – podpis, klíč.
Nejjednodušší způsob kombinace je sčítání. Proto budeme signaturu nazývat S = S 1 + S 2 + ... + S n a klíč PK = PK 1 + PK 2 + ... + PK n . Pro tento případ lze snadno dokázat správnost zvolených hodnot: e(g, S) = e(P, H)
e(g, S) = e(g, S 1 + S 2 + … + S n ) = e (g, H SK 1 + SK 2 + … + SK n ) = e (g SK 1 + SK 2 + … + SKn , H) = e(PK 1 + PK 2 + … + PKn , H) = e(PK, H)
Dodejme do obvodu nelinearitu, abychom zabránili útoku falešných klíčů. Namísto pouhého sčítání klíčů a podpisů vynásobme každý výraz nějakým deterministickým číslem a pak najdeme součet každé skupiny:
S = a 1 × S 1 + a 2 × S 2 + … + a n × S n
PK = a 1 × PK 1 + a 2 × PK 2 + … + a n × PK n
Zde jsou koeficienty podpisu a klíče vypočteny pomocí hašovací funkce a berou v úvahu všechny veřejné klíče PK n : a i = hash (PK i , {PK 1 ,PK 2 , …, PK n }), hash je regulární hashovací funkce, jejímž výsledkem je číslo.
Jednou z těchto funkcí je zřetězení veřejného klíče podepisujícího a celé sady veřejných klíčů používaných k podepisování: a i = hash(P i || P 1 || P 2 || P 3 ). Pro složitější schéma platí stejná rovnice pro ověření (logika důkazu se nemění i přes dodatečné koeficienty a i ).
Často se upřednostňuje n-out-n více podpisů k-out-n. Protože v tomto případě, pokud dojde ke ztrátě jednoho nebo více klíčů, může systém fungovat správně. Pro podepisování BLS funguje agregace klíčů i v tomto scénáři.
Uveďme příklad konstrukce schématu k-out-n více podpisů pomocí klíčů (k < n) uložených na n různých zařízeních.
Každé ze zařízení má číslo podepisujícího i = 1,2, …, n, které určuje sériové číslo v sadě, soukromý klíč SK i a veřejný klíč PK i = g SK i .
Vypočítejte agregovaný veřejný klíč PK = a 1 × PK 1 + a 2 × PK 2 + … + a n × PK n , kde a i = hash (PK i , {PK 1 ,PK 2 , …, PK n }).
Od každého zařízení obdržíme členský klíč MK i , který potvrdí, že číslo i je obsaženo v PK. Každý členský klíč musí být uložen na příslušném zařízení.
MK i = H(PK, i) a 1 ⋅SK 1 + H(PK, i) a 2 ⋅SK 2 + … + H(PK, i) a n ⋅SK n
Každý účastnický klíč je n-out-n účinným podpisem zprávy H(PK,i). Proto pro každý MK i , e(g, MKi ) =e(PK, H(PK,i))
Předpokládejme, že chceme podepsat zprávu pouze klíči SK 1 , SK 2 , …, SK k . Vygenerujeme m podpisů S 1 , S 2 , …, S k :
S1 = H(PK, m ) SK1 + MK1
S2 = H(PK, m ) SK2 + MK2
…
S k = H(PK, m) SK k + MK k
Sečteme je, abychom získali jeden pár podpis-klíč, který bude popisovat celý systém:
(S', PK') = (S 1 + S 2 + … + Sk , PK 1 + PK 2 + …+ PK k )
Klíč PK' a podpis S' se liší od páru PK, S. První závisí pouze na podmnožině podepisujících, zatímco druhý je určen všemi páry výchozího systému.
Chcete-li ověřit přijatý podpis k-out-n, zkontrolujte podmínku:
e(g, S') = e(PK', H(PK, m))⋅e(PK, H(PK, 1)+H(PK, 2)+ … + H(PK, k))
Protože členské klíče MK 1 , MK 2 , ... MK k jsou platnými podpisy pro zprávy H(PK, 1), H(PK, 2) ... H(PK, k) podepsané agregovaným klíčem PK, proto:
e(g, S') = e(g, S1 + S2 + … + Sn ) = e(g, H(PK, m) SKi + H(PK, m) SK2 + … + H( PK, m) SK k + MK 1 + MK 2 + … + MK k ) = e(g, H(PK, m) SK 1 + H(PK, m) SK 2 + … H(PK, m) SK k ) ⋅ e(g, MK 1 + MK 2 + … + MK k ) = e(g SK 1 + g SK 2 + … + g SK k , H(PK, m)) ⋅ e(PK, H(PK, 1) + H(PK, 2) + … + H(PK, k)) = e(PK', H(PK, m)) ⋅ e(PK, H(PK, 1) + H(PK, 2) + … + H(PK, k))
Podobné schéma je použitelné pro jakékoli hodnoty k a n. A místo 1, 2, ... k lze zvolit libovolných neopakujících se k podepisovačů s čísly patřícími do intervalu [1, n].
Hlavní nevýhodou tohoto typu podpisu je proces párování.
Za prvé, výpočet párování nějakou dobu trvá, takže kontrola podpisu jednoho bloku může někdy trvat déle než kontrola všech podpisů zpráv z bloku. Při velkém počtu transakcí v bloku však bude výhoda na straně BLS podpisu.
Za druhé, ne všechny křivky mohou zajistit jak bezpečnost tajného klíče, tak účinnost párovací funkce [4] . Navíc existuje MOV - útok (útok na kryptosystémy s eliptickými křivkami), zaměřený na snížení bezpečnosti systému ovlivněním párovací funkce.