Rozhodnutí Lineární předpoklad - Decision Linear assumption
The Předpoklad lineárního rozhodování (DLIN) je předpoklad výpočetní tvrdosti použito v kryptografie eliptické křivky. Předpoklad DLIN je zvláště užitečný v nastavení, kde rozhodný předpoklad Diffie – Hellman nedrží (jak se často stává v kryptografie založená na párování ). Předpoklad Lineární předpoklad byl zaveden Boneh, Boyen a Shacham.[1]
Neformálně předpoklad DLIN uvádí, že daný , s prvky náhodné skupiny a náhodných exponentů, je těžké rozlišit z nezávislého prvku náhodné skupiny .
Motivace
Symetricky kryptografie založená na párování skupina je vybaven párováním který je bilineární. Tato mapa poskytuje efektivní algoritmus pro řešení rozhodující Diffie-Hellman problém. [2] Daný vstup , je snadné zkontrolovat, zda je rovný . Toto následuje pomocí párování: všimněte si toho
Pokud tedy , pak hodnoty a bude se rovnat.
Protože tento kryptografický předpoklad je nezbytný pro budování Šifrování ElGamal a podpisy V tomto případě neplatí, jsou nutné nové předpoklady pro vytvoření kryptografie v symetrických bilineárních skupinách. Předpoklad DLIN je modifikací předpokladů typu Diffie-Hellman, aby zmařil výše uvedený útok.
Formální definice
Nechat být cyklická skupina z primární objednat . Nechat , , a být jednotně náhodný generátory z . Nechat být jednotně náhodné prvky . Definujte distribuci
Nechat být dalším jednotně náhodným prvkem . Definujte další distribuci
Předpoklad Lineární předpoklad uvádí, že a jsou výpočetně k nerozeznání.
Aplikace
Lineární šifrování
Boneh, Boyen a Shacham definují a šifrování veřejného klíče schéma analogicky k šifrování ElGamal.[1] V tomto schématu jsou veřejným klíčem generátory . Soukromý klíč jsou dva takové exponenty . Šifrování kombinuje zprávu s veřejným klíčem k vytvoření šifrovacího textu
- .
K dešifrování šifrovacího textu lze k výpočtu použít soukromý klíč
Chcete-li zkontrolovat, zda toto schéma šifrování je opravit, tj. pokud se obě strany řídí protokolem, uvědomte si to
Pak použijeme skutečnost, že výnosy
Dále toto schéma je IND-CPA zajistit za předpokladu, že platí předpoklad DLIN.
Krátké skupinové podpisy
Boneh, Boyen a Shacham také používají DLIN v schématu pro skupinové podpisy. [1] Podpisy se nazývají „krátké skupinové podpisy“, protože se standardem úroveň zabezpečení, mohou být zastoupeny pouze v 250 bajtů.
Jejich protokol nejprve používá lineární šifrování, aby definoval speciální typ důkaz nulových znalostí. Pak Fiat – Shamir heuristický se používá k transformaci systému kontroly na a digitální podpis. Dokazují, že tento podpis splňuje další požadavky neodpustitelnosti, anonymity a sledovatelnosti požadované od skupinového podpisu.
Jejich důkaz se opírá nejen o předpoklad DLIN, ale také o další předpoklad zvaný - silný předpoklad Diffie-Hellman. Je to prokázáno v náhodný věštecký model.
Další aplikace
Od své definice v roce 2004 předpoklad rozhodnutí lineární viděl řadu dalších aplikací. Patří mezi ně konstrukce a pseudonáhodná funkce který zobecňuje Naor-Reingoldova konstrukce, [3] an atributové šifrování systém, [4] a speciální třída neinteraktivní důkazy nulových znalostí. [5]
Reference
- ^ A b C Dan Boneh, Xavier Boyen, Hovav Shacham: Krátké skupinové podpisy. CRYPTO 2004: 41–55
- ^ John Bethencourt: Úvod do bilineárních map
- ^ Allison Bishop Lewko, Brent Waters: Efektivní pseudonáhodné funkce z rozhodovacího lineárního předpokladu a slabších variant. CCS 2009: 112-120
- ^ Lucas Kowalczyk, Allison Bishop Lewko: Bilineární expanze entropie z rozhodovacího lineárního předpokladu. CRYPTO 2015: 524-541
- ^ Benoît Libert, Thomas Peters, Marc Joye, Moti Yung: Kompaktní skrytí lineárních rozpětí. ASIACRYPT 2015: 681-707