Jednosměrná funkce - One-way function

Ve vědě o počítačích , je jednosměrná funkce je funkce , která je snadno spočítat na každém vstupu, ale těžko obrácení vzhledem k image náhodného vstupu. Zde je třeba „snadné“ a „tvrdé“ chápat ve smyslu teorie výpočetní složitosti , konkrétně teorie polynomiálních časových problémů. Nebýt jeden na jednoho není považováno za dostačující pro to, aby byla funkce nazývána jednosměrná (viz níže Teoretická definice ).

Existence takových jednosměrných funkcí je stále otevřenou domněnkou . Ve skutečnosti by jejich existence dokázala, že třídy složitosti P a NP nejsou stejné , a vyřešila by tak především nevyřešenou otázku teoretické informatiky. O opaku není známo, že je pravdivý, tj. O existenci důkazu, že P ≠ NP by přímo neimplementoval existenci jednosměrných funkcí.

V aplikovaných kontextech jsou termíny „snadný“ a „tvrdý“ obvykle interpretovány relativně k nějaké konkrétní výpočetní entitě; obvykle „dostatečně levné pro legitimní uživatele“ a „neúměrně drahé pro všechny škodlivé agenty “. Jednosměrné funkce jsou v tomto smyslu základními nástroji pro kryptografii , osobní identifikaci , autentizaci a další aplikace pro zabezpečení dat . Zatímco existence jednosměrných funkcí v tomto smyslu je také otevřenou domněnkou, existuje několik kandidátů, kteří vydrželi desetiletí intenzivního zkoumání. Některé z nich jsou základními složkami většiny telekomunikačních , elektronických obchodů a systémů elektronického bankovnictví po celém světě.

Teoretická definice

Funkce f  : {0,1} ^* → {0,1} ^* je jednosměrný , pokud f je možné vypočítat pomocí polynomu času algoritmu, ale jakýkoliv polynomiální čas náhodně algoritmus , že pokusy o vypočítat pseudo-inverzní k f uspěje s zanedbatelná pravděpodobnost. (Horní index * znamená libovolný počet opakování, viz Kleeneova hvězda .) To znamená, že pro všechny randomizované algoritmy jsou všechna kladná celá čísla c a všechna dostatečně velká n = délka ( x ), ${\ displaystyle F}$ ${\ displaystyle F}$

${\ Displaystyle \ Pr [f (F (f (x))) = f (x)] <n^{-c},}$

kde pravděpodobnost převyšuje volbu x z diskrétního rovnoměrného rozdělení na {0,1} ⁿ a náhodnost . ${\ displaystyle F}$

Všimněte si, že podle této definice musí být funkce „obtížně invertovatelná“ v průměrném případě než v nejhorším smyslu. To se liší od většiny teorií složitosti (např. NP-tvrdost ), kde je termín „tvrdý“ míněn v nejhorším případě. Proto i když je známo, že někteří kandidáti na jednosměrné funkce (popsané níže) jsou NP-kompletní , neznamená to jejich jednosměrnost. Druhá vlastnost je založena pouze na nedostatku známého algoritmu k vyřešení problému.

Nestačí, aby funkce byla „ztrátová“ (ne jedna k jedné), aby měla jednosměrnou funkci. Zejména funkce, která výstupy řetěz n nul jakéhokoliv vstupu délky n je to funkce jednosměrná, protože je snadné přijít na vstupu, který bude mít za následek stejný výstup. Přesněji: Pro takovou funkci, která jednoduše vydává řetězec nul, „algoritmus F, který na výstupu f ( x ) pouze vygeneruje libovolný řetězec délky n, „ najde “správný předobraz výstupu, i když to není vstup který byl původně použit k nalezení výstupního řetězce.

Související pojmy

Jednosměrná permutace je jednosměrná funkce, která je také permutace, to znamená, že jednosměrný funkce, která je bijective . Jednosměrné permutace jsou důležitým kryptografickým primitivem a není známo, zda je jejich existence implikována existencí jednosměrných funkcí.

Padací dveře jednosměrná funkce nebo poklop permutace je speciální druh jednosměrné funkce. Takovou funkci je těžké převrátit, pokud nejsou známy nějaké tajné informace, nazývané padací dveře .

Bezkolizní hašovací funkce f je jednosměrná funkce, která je také kolize odolná ; to znamená, že žádný randomizovaný polynomiální časový algoritmus nemůže najít kolizi- odlišné hodnoty x , y tak, že f ( x ) = f ( y )-s nezanedbatelnou pravděpodobností.

Teoretické implikace jednosměrných funkcí

Pokud f je jednosměrná funkce, pak by inverze f byla problémem, jehož výstup je obtížné spočítat (podle definice), ale snadno zkontrolovat (pouze výpočtem f na něm). Existence jednosměrné funkce tedy znamená, že FP ≠ FNP , což zase znamená, že P ≠ NP. P ≠ NP však neznamená existenci jednosměrných funkcí.

Existence jednosměrné funkce předpokládá existenci mnoha dalších užitečných konceptů, včetně:

• Pseudonáhodné generátory
• Rodiny pseudonáhodných funkcí
• Bitová schémata závazků
• Schémata šifrování soukromých klíčů jsou zabezpečena proti adaptivnímu zvolenému šifrovanému útoku
• Ověřovací kódy zpráv
• Schémata digitálního podpisu (zabezpečené proti adaptivnímu útoku na vybrané zprávy)

Existence jednosměrných funkcí také znamená, že neexistuje žádný přirozený důkaz pro P ≠ NP.

Kandidáti na jednosměrné funkce

Následuje několik kandidátů na jednosměrné funkce (od dubna 2009). Je zřejmé, že není známo, zda jsou tyto funkce skutečně jednosměrné; ale rozsáhlý výzkum zatím nedokázal vytvořit účinný invertující algoritmus pro žádný z nich.

Násobení a faktoring

Funkce f bere jako vstupy dvě prvočísla p a q v binárním zápisu a vrací jejich součin. Tuto funkci lze "snadno" vypočítat v čase O ( b ² ) , kde b je celkový počet bitů vstupů. Inverting tuto funkci vyžaduje hledání faktorů daného celého čísla N . Nejlepší factoring algoritmy známé spuštěn v čase, kde B je počet bitů potřebných pro reprezentaci N . ${\ Displaystyle O \ left (\ exp {\ sqrt [{3}] {{\ frac {64} {9}} b (\ log b)^{2}}} \ right)}$

Tuto funkci lze zobecnit tím, že se p a q nechá pohybovat po vhodné sadě semiprime . Všimněte si, že f není jednosměrné pro náhodně vybraná celá čísla p , q > 1 , protože součin bude mít 2 jako faktor s pravděpodobností 3/4 (protože pravděpodobnost, že libovolné p je liché, je 1/2, a podobně pro q , takže pokud jsou vybráni nezávisle, pravděpodobnost, že oba jsou liché, je tedy 1/4; tedy pravděpodobnost, že p nebo q je sudý, je 1 - 1/4 = 3/4 ).

Rabinova funkce (modulární kvadratura)

Funkce Rabin nebo kvadratura modulo , kde p a q jsou prvočísla se předpokládá, že sbírka jednosměrné funkce. Píšeme ${\ displaystyle N = pq}$

${\ displaystyle \ operatorname {Rabin} _ {N} (x) \ triangleq x^{2} {\ bmod {N}}}$

označovat kvadratický modul N : konkrétní člen Rabinovy ​​kolekce . Lze ukázat, že extrahování odmocnin, tj. Invertování Rabinovy ​​funkce, je výpočetně ekvivalentní faktoringu N (ve smyslu redukce polynomiálního času ). Proto je možné dokázat, že kolekce Rabin je jednosměrná právě tehdy, když je faktoring těžký. To platí také pro speciální případ, ve kterém p a q mají stejnou bitovou délku. Rabin kryptografický systém je založen na předpokladu, že tato funkce Rabin je jednosměrný.

Diskrétní exponenciální a logaritmus

Modulární umocnění lze provést v polynomiálním čase. Invertování této funkce vyžaduje výpočet diskrétního logaritmu . V současné době existuje několik populárních skupin, pro které není znám žádný algoritmus pro výpočet základního diskrétního logaritmu v polynomiálním čase. Tyto skupiny jsou všechny konečné abelianské skupiny a obecný problém diskrétního logaritmu lze popsat takto.

Nechť G je konečná abelianská skupina mohutnosti n . Označte jeho skupinový provoz vynásobením. Uvažujme primitivní prvek alfa ∈ G a další prvek p ∈ G . Problém diskrétního logaritmu je najít kladné celé číslo k , kde 1 ≤ k ≤ n , takové, že:

${\ Displaystyle \ alpha ^{k} = \ underbrace {\ alpha \ cdot \ alpha \ cdot \ ldots \ cdot \ alpha} _ {k \; \ mathrm {times}} = \ beta}$

Celé číslo k , že řeší rovnice α ^k = β se nazývá diskrétního logaritmu o p k základně alfa . Jeden píše k = log _α β .

Oblíbenými možnostmi pro skupinu G v diskrétní logaritmové kryptografii jsou cyklické skupiny ( Z _p ) ^× (např. Šifrování ElGamal , výměna klíčů Diffie – Hellman a algoritmus digitálního podpisu ) a cyklické podskupiny eliptických křivek nad konečnými poli ( viz kryptografie eliptické křivky ).

Eliptická křivka je sada párů prvků pole splňující y ² = x ³ + ax + b . Prvky křivky tvoří skupinu pod operací zvanou „přidání bodu“ (což není totéž jako operace sčítání pole). Násobení kP bodu P celým číslem k ( tj . Skupinová akce aditivní skupiny celých čísel) je definována jako opakované přidání bodu k sobě. Pokud jsou známy k a P , je snadné vypočítat R = kP , ale pokud jsou známy pouze R a P , předpokládá se, že je těžké vypočítat k .

Kryptograficky zabezpečené hashovací funkce

Existuje řada kryptografických hashovacích funkcí, které lze rychle vypočítat, například SHA 256 . Některé z jednodušších verzí prošly složitou analýzou, ale nejsilnější verze nadále nabízejí rychlá a praktická řešení pro jednosměrné výpočty. Většina teoretické podpory funkcí je více technik pro maření některých dříve úspěšných útoků.

Ostatní kandidáti

Další kandidáti na jednosměrné funkce byly založeny na tvrdosti dekódování náhodných lineárních kódů , problému s podmnožinovým součtem ( kryptosystém Naccache – Stern s batohem na zádech ) nebo na jiných problémech.

Univerzální jednosměrná funkce

Existuje explicitní funkce f , která byla prokázána jako jednosměrná, pokud existují pouze jednosměrné funkce. Jinými slovy, je-li jakákoli funkce jednosměrná, je tomu tak i f . Protože tato funkce byla první kombinatorickou kompletní jednosměrnou funkcí, která byla předvedena, je známá jako „univerzální jednosměrná funkce“. Problém nalezení jednosměrné funkce se tak redukuje na prokázání, že jedna taková funkce existuje.

Viz také

• Jednosměrná funkce komprese
• Kryptografická hashovací funkce
• Geometrická kryptografie
• Funkce Trapdoor

Reference

Další čtení

• Jonathan Katz a Yehuda Lindell (2007). Úvod do moderní kryptografie . Stiskněte CRC. ISBN  1-58488-551-3 .
• Michael Sipser (1997). Úvod do teorie výpočtů . Publikování PWS. ISBN 978-0-534-94728-6. Oddíl 10.6.3: Jednosměrné funkce, s. 374–376.
• Christos Papadimitriou (1993). Výpočetní složitost (1. vyd.). Addison Wesley. ISBN 978-0-201-53082-7. Oddíl 12.1: Jednosměrné funkce, s. 279–298.