Předpoklad výpočetní tvrdosti - Computational hardness assumption

V teorii výpočetní složitosti je předpokladem výpočetní tvrdosti hypotéza, že konkrétní problém nelze efektivně vyřešit (kde efektivně obvykle znamená „v polynomiálním čase “). Není známo, jak prokázat (bezpodmínečnou) tvrdost v podstatě pro jakýkoli užitečný problém. Místo toho počítačoví vědci spoléhají na redukce, aby formálně spojili tvrdost nového nebo komplikovaného problému s předpokladem výpočetní tvrdosti o problému, který je lépe pochopen.

Předpoklady výpočetní tvrdosti jsou v kryptografii zvláště důležité . Hlavním cílem kryptografie je vytvořit kryptografické primitivy s prokazatelným zabezpečením . V některých případech bylo zjištěno, že kryptografické protokoly mají teoretické zabezpečení informací ; vycpávka je typickým příkladem. Informační teoretické bezpečnosti však nelze vždy dosáhnout; v takových případech kryptografové sáhnou zpět k výpočetnímu zabezpečení. Zhruba řečeno to znamená, že tyto systémy jsou zabezpečené za předpokladu, že všichni protivníci jsou výpočetně omezeni , protože všichni protivníci jsou v praxi.

Předpoklady výpočetní tvrdosti jsou také užitečné pro vedení návrhářů algoritmů: jednoduchý algoritmus pravděpodobně nevyvrátí dobře prostudovaný předpoklad výpočetní tvrdosti, jako je P ≠ NP .

Porovnání předpokladů tvrdosti

Počítačoví vědci mají různé způsoby, jak posoudit, které předpoklady tvrdosti jsou spolehlivější.

Pevnost předpokladů tvrdosti

Říkáme, že předpoklad je silnější než předpoklad, když implikuje (a opak je falešný nebo není znám). Jinými slovy, i kdyby byl předpoklad nepravdivý, předpoklad může být stále pravdivý a použití kryptografických protokolů založených na předpokladu může být stále bezpečné. Při navrhování kryptografických protokolů tedy člověk doufá, že bude schopen prokázat bezpečnost pomocí nejslabších možných předpokladů. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$

Předpoklady průměrného vs. nejhoršího případu

Předpoklad průměrného případu říká, že konkrétní problém je ve většině instancí z nějaké explicitní distribuce těžký, zatímco předpoklad nejhoršího případu pouze říká, že problém je v některých případech těžký . Pro daný problém znamená průměrná tvrdost nejhorší tvrdost, takže předpoklad tvrdosti průměrného případu je silnější než předpoklad nejhorší tvrdosti pro stejný problém. Kromě toho, dokonce i pro nesrovnatelné problémy, je předpoklad jako hypotéza exponenciálního času často považován za vhodnější než předpoklad průměrného případu, jako je zasadená kliková domněnka . Všimněte si však, že ve většině kryptografických aplikací je vědomí, že problém má nějakou těžkou instanci (tj. Problém je v nejhorším případě těžký), zbytečné, protože nám neposkytuje způsob generování tvrdých instancí. Naštěstí mnoho předpokladů průměrných případů používaných v kryptografii (včetně RSA , diskrétního protokolu a některých problémů s mřížkou ) může být založeno na předpokladech nejhoršího případu prostřednictvím redukce nejhoršího případu na průměrný případ.

Falšovatelnost

Požadovanou charakteristikou předpokladu výpočetní tvrdosti je falzifikovatelnost , tj. Že pokud by byl předpoklad nepravdivý, bylo by možné jej dokázat. Zejména Naor (2003) zavedl formální pojem kryptografické falšovatelnosti. Předpokládá se, že předpoklad výpočetní tvrdosti je zfalšovatelný, pokud jej lze formulovat jako výzvu: interaktivní protokol mezi protivníkem a efektivním ověřovatelem, kde efektivní protivník může přesvědčit ověřovatele, aby přijal, pouze pokud je předpoklad Nepravdivé.

Společné předpoklady kryptografické tvrdosti

Používá se mnoho předpokladů kryptografické tvrdosti. Toto je seznam některých nejběžnějších a některé kryptografické protokoly, které je používají.

Faktorizace celého čísla

Vzhledem ke složenému číslu , a zejména k číslu , které je součinem dvou velkých prvočísel , je problémem celočíselné faktorizace najít a (obecněji najít prvočísla taková, která ). Je velkým otevřeným problémem najít algoritmus pro celočíselnou faktorizaci, který běží v časovém polynomu ve velikosti reprezentace ( ). Zabezpečení mnoha kryptografických protokolů závisí na předpokladu, že celočíselná faktorizace je tvrdá (tj. Nelze ji vyřešit v polynomiálním čase). Mezi kryptosystémy, jejichž bezpečnost je ekvivalentní tomuto předpokladu, patří kryptosystém Rabin a kryptosystém Okamoto – Uchiyama . Mnoho dalších kryptosystémů se spoléhá na silnější předpoklady, jako je RSA , problémy s reziduitami a skrývání Phi . ${\ displaystyle n}$${\ Displaystyle n = p \ cdot q}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle p_ {1}, \ tečky, p_ {k}}$${\ Displaystyle n = \ prod _ {i} p_ {i}}$${\ displaystyle \ log (n)}$

Problém s RSA

Vzhledem k složenému číslu , exponentu a číslu je problém RSA najít . Problém je považován za obtížný, ale vzhledem k faktorizaci se stává snadným . V RSA šifrovací systém , je veřejný klíč , je šifrování zpráv a faktorizace je tajný klíč pro dešifrování. ${\ displaystyle n}$${\ displaystyle e}$${\ Displaystyle c: = m^{e} (\ mathrm {mod} \; n)}$${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle (n, e)}$${\ displaystyle c}$${\ displaystyle m}$${\ displaystyle n}$

Problémy s reziduitou

Vzhledem ke složenému číslu a celým číslům je problémem rezidua určit, zda existuje (případně najít) takové, že ${\ displaystyle n}$${\ displaystyle y, d}$${\ displaystyle x}$

${\ Displaystyle x^{d} \ equiv y {\ pmod {n}}.}$

Mezi důležité speciální případy patří problém kvadratické reziduity a problém reziduální kompozitní rezidua . Stejně jako v případě RSA je tento problém (a jeho speciální případy) považován za obtížný, ale vzhledem k faktorizaci se stává snadným . Některé kryptosystémy, které se spoléhají na tvrdost problémů se zbytkem, zahrnují: ${\ displaystyle n}$

• Kryptosystém Goldwasser – Micali (problém kvadratické redisduosity)
• Blum Blum Shub generátor (kvadratický problém redisduosity)
• Paillierův kryptosystém (problém s rozhodovací složenou reziduitou)
• Kryptosystém Benaloh (problém s vyšší reziduitou)
• Kryptosystém Naccache – Stern (problém s vyšší reziduitou)

Phi-skrývající se předpoklad

U složeného čísla není známo, jak efektivně vypočítat jeho Eulerovu funkci totientu . Phi-hiding předpoklad předpokládá, že je těžké vypočítat , a navíc i výpočet jakýchkoli hlavních faktorů je těžké. Tento předpoklad je použit v PIR protokolu Cachin – Micali – Stadler . ${\ displaystyle m}$ ${\ Displaystyle \ phi (m)}$${\ Displaystyle \ phi (m)}$${\ Displaystyle \ phi (m)}$

Problém s diskrétním protokolem (DLP)

Dané prvky a ze skupiny , problém diskrétního protokolu vyžaduje celé číslo takové, že . Problém diskrétního protokolu není znám jako srovnatelný s celočíselnou faktorizací, ale jejich výpočetní složitosti spolu úzce souvisejí . ${\ displaystyle a}$${\ displaystyle b}$ ${\ displaystyle G}$${\ displaystyle k}$${\ displaystyle a = b^{k}}$

Většina kryptografických protokolů souvisejících s problémem diskrétního protokolu ve skutečnosti spoléhá na silnější předpoklad Diffie -Hellmana : vzhledem k tomu, že prvky skupiny , kde je generátor a náhodná celá čísla, je těžké najít . Příklady protokolů, které používají tento předpoklad, zahrnují původní výměnu klíčů Diffie – Hellman a také šifrování ElGamal (které se spoléhá na ještě silnější variantu Decisional Diffie – Hellman (DDH) ). ${\ Displaystyle g, g^{a}, g^{b}}$${\ displaystyle g}$${\ displaystyle a, b}$${\ Displaystyle g^{a \ cdot b}}$

Víceřádkové mapy

Multilinear mapa je funkce (kde jsou skupiny ) tak, že pro všechny a , ${\ Displaystyle e: G_ {1}, \ dots, G_ {n} \ rightarrow G_ {T}}$${\ displaystyle G_ {1}, \ dots, G_ {n}, G_ {T}}$${\ Displaystyle g_ {1}, \ dots, g_ {n} \ in G_ {1}, \ dots G_ {n}}$${\ Displaystyle a_ {1}, \ tečky, a_ {n}}$

${\ Displaystyle e (g_ {1}^{a_ {1}}, \ dots, g_ {n}^{a_ {n}}) = e (g_ {1}, \ dots, g_ {n})^{ a_ {1} \ cdots a_ {n}}}$.

Pro kryptografické aplikace by člověk chtěl sestrojit skupiny a mapu tak, aby bylo možné efektivně vypočítat mapy a skupinové operace , ale problém s diskrétním protokolem je stále obtížný. Některé aplikace vyžadují silnější předpoklady, např. Víceřádkové analogy předpokladů Diffie-Hellmana. ${\ displaystyle G_ {1}, \ dots, G_ {n}, G_ {T}}$${\ displaystyle e}$${\ displaystyle G_ {1}, \ dots, G_ {n}, G_ {T}}$${\ displaystyle G_ {1}, \ tečky, G_ {n}}$

Pro zvláštní případ byly bilineární mapy s uvěřitelným zabezpečením vytvořeny pomocí Weilového párování a Tateho párování . V posledních letech bylo navrženo mnoho staveb, ale mnoho z nich bylo také rozbito a v současné době neexistuje shoda ohledně bezpečného kandidáta. ${\ displaystyle n = 2}$${\ displaystyle n> 2}$

Některé kryptosystémy, které se spoléhají na předpoklady víceřádkové tvrdosti, zahrnují:

• Schéma Boneh-Franklin (blinear Diffie-Hellman)
• Boneh – Lynn – Shacham (blinear Diffie-Hellman)
• Garg-Gentry-Halevi-Raykova-Sahai-Waters kandidát na zmatení nerozeznatelnosti a funkční šifrování (víceřádkové skládačky)

Mřížové problémy

Nejzákladnějším výpočetním problémem mřížek je Shortest Vector Problem (SVP) : vzhledem k mřížce najděte nejkratší nenulový vektor . Většina kryptosystémů vyžaduje silnější předpoklady pro varianty SVP, jako je problém s nejkratšími nezávislými vektory (SIVP) , GapSVP nebo Unique-SVP. ${\ displaystyle L}$${\ displaystyle v \ v L}$

Nejužitečnější předpoklad tvrdosti mřížky v kryptografii je pro problém Learning with errors (LWE): Dané vzorky , kde pro nějakou lineární funkci je snadné se naučit pomocí lineární algebry. V problému LWE má vstup do algoritmu chyby, tj. Pro každý pár s nějakou malou pravděpodobností. Předpokládá se, že chyby činí problém neřešitelným (u příslušných parametrů); zejména jsou známy varianty nejhorších až průměrných případů z variant SVP. ${\ displaystyle (x, y)}$${\ Displaystyle y = f (x)}$${\ Displaystyle f (\ cdot)}$${\ Displaystyle f (\ cdot)}$${\ Displaystyle y \ neq f (x)}$

U kvantových počítačů jsou problémy s faktoringem a diskrétním protokolem snadné, ale problémy s mřížkami jsou považovány za těžké. To činí některé kryptosystémy založené na mřížce kandidáty pro postkvantovou kryptografii .

Některé kryptosystémy, které se spoléhají na tvrdost problémů s mřížkou, zahrnují:

• NTRU ( NTRUEncrypt i NTRUSign )
• Většina kandidátů na plně homomorfní šifrování

Nekryptografické předpoklady tvrdosti

Stejně jako jejich kryptografické aplikace se v teorii výpočetní složitosti používají předpoklady tvrdosti k poskytnutí důkazů pro matematické výroky, které je obtížné bezpodmínečně prokázat. V těchto aplikacích člověk dokazuje, že předpoklad tvrdosti implikuje požadovanou teorii složitosti, místo aby dokázal, že tvrzení je samo o sobě pravdivé. Nejznámější předpoklad tohoto typu je předpoklad, že P? NP , ale jiní zahrnují exponenciální čas hypotézu , na zasadil kliku domněnku , a unikátní hry domněnku .

${\ displaystyle C}$-tvrdé problémy

Je známo, že mnoho nejhorších výpočetních problémů je pro některou třídu složitosti těžkých nebo dokonce úplných , zejména NP-hard (ale často také PSPACE-hard , PPAD-hard atd.). To znamená, že jsou přinejmenším stejně obtížní jako jakýkoli problém ve třídě . Pokud je problém tvrdý (s ohledem na redukci polynomiálního času), pak jej nelze vyřešit algoritmem polynomiálního času, pokud není předpoklad výpočetní tvrdosti falešný. ${\ displaystyle C}$${\ displaystyle C}$${\ displaystyle C}$${\ Displaystyle P \ neq C}$

Exponenciální časová hypotéza (ETH) a varianty

Exponenciální Time hypotéza (ETH) je posílení z předpokladu tvrdosti, která dohady, že nejenže Boolean satisfiability problém nemá polynomiální časový algoritmus, to dále vyžaduje exponenciální čas ( ). Ještě silnější předpoklad, známý jako hypotéza silné exponenciální doby (SETH), předpokládá, že -SAT vyžaduje čas, kde . ETH, SETH a související předpoklady výpočetní tvrdosti umožňují odvodit výsledky jemnozrnné složitosti, např. Výsledky, které rozlišují polynomiální čas a kvazi-polynomický čas , nebo dokonce versus . Takové předpoklady jsou také užitečné v parametrizované složitosti . ${\ Displaystyle P \ neq NP}$${\ Displaystyle 2^{\ Omega (n)}}$${\ displaystyle k}$${\ Displaystyle 2^{(1- \ varepsilon _ {k}) n}}$${\ Displaystyle \ lim _ {k \ rightarrow \ infty} \ varepsilon _ {k} = 0}$${\ displaystyle n^{1,99}}$${\ displaystyle n^{2}}$

Předpoklady průměrné tvrdosti

Předpokládá se, že některé výpočetní problémy jsou v průměru pro konkrétní distribuci instancí těžké. Například v problému s nasazenou klikou je vstupem náhodný graf, který je vzorkován, a to vzorkováním náhodného grafu Erdős – Rényi a poté „zasazením“ náhodného kliku, tj. Spojením rovnoměrně náhodných uzlů (kde ), a cílem je najít zasadil -clique (což je jedinečný whp). Dalším důležitým příkladem je Feigeova hypotéza, což je předpoklad výpočetní tvrdosti o náhodných instancích 3-SAT (vzorkováno tak, aby byl zachován specifický poměr klauzí k proměnným). Předpoklady výpočetní tvrdosti průměrných případů jsou užitečné pro prokázání průměrné tvrdosti v aplikacích, jako jsou statistiky, kde existuje přirozené rozdělení mezi vstupy. Navíc byl předpoklad tvrdosti zasazené kliky také použit k rozlišení mezi polynomiální a kvazi-polynomickou časovou složitostí nejhorších případů jiných problémů, podobně jako u hypotézy exponenciálního času . ${\ displaystyle k}$${\ displaystyle k}$${\ Displaystyle 2 \ log _ {2} n \ ll k \ ll {\ sqrt {n}}}$${\ displaystyle k}$

Unikátní hry

Problém Unique Label Cover je problémem uspokojení omezení, kde každé omezení zahrnuje dvě proměnné a pro každou hodnotu existuje jedinečná hodnota, která splňuje . Určení, zda lze splnit všechna omezení, je snadné, ale Unique Game Conjecture (UGC) předpokládá, že určení, zda lze splnit téměř všechna omezení ( -frakce, pro libovolnou konstantu ) nebo téměř žádná z nich ( -fraction) je NP-tvrdý. O problémech aproximace je často známo, že jsou NP-tvrdé za předpokladu UGC; takové problémy se označují jako UG-hard. Zejména za předpokladu UGC existuje semidefinitní programovací algoritmus, který dosahuje záruk optimální aproximace pro mnoho důležitých problémů. ${\ displaystyle C}$${\ displaystyle x, y}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle C}$${\ Displaystyle (1- \ varepsilon)}$${\ displaystyle \ varepsilon> 0}$${\ displaystyle \ varepsilon}$

Rozšíření malé sady

S problémem Unique Label Cover úzce souvisí problém s rozšířením malé sady (SSE) : Vzhledem k grafu najděte malou sadu vrcholů (velikosti ), jejichž rozšíření hran je minimální. Je známo, že pokud je SSE obtížné aproximovat, pak je tomu tak i u Unique Label Cover. Proto Small Set Expansion hypotéza , která předpokládá, že SSE je těžké přiblížit, je silnější (ale úzce souvisí) předpoklad, než je jedinečná hra domněnky. O některých problémech aproximace je známo, že jsou SSE-tvrdé (tj. Přinejmenším stejně těžké jako aproximace SSE). ${\ displaystyle G = (V, E)}$${\ displaystyle n/\ log (n)}$

3SUM Conjecture

Vzhledem k množině čísel se problém 3SUMY ptá, zda existuje triplet čísel, jejichž součet je nula. Existuje algoritmus kvadratického času pro 3SUM a bylo se spekulováno, že žádný algoritmus nemůže vyřešit 3SUM ve „skutečně subkvadratickém čase“: 3SUM Conjecture je předpokladem výpočetní tvrdosti, že pro 3SUM neexistují algoritmy bez času (pro konstantní ). Tato domněnka je užitečná pro prokázání téměř kvadratických dolních hranic pro několik problémů, většinou z výpočetní geometrie . ${\ displaystyle n}$${\ Displaystyle O (n^{2- \ varepsilon})}$${\ displaystyle \ varepsilon> 0}$

Viz také

• Úroveň zabezpečení

Reference