Beräkningshårdhetsantagande

I beräkningskomplexitetsteori är ett antagande om beräkningshårdhet hypotesen att ett visst problem inte kan lösas effektivt (där effektivt typiskt betyder "i polynomtid "). Det är inte känt hur man kan bevisa (ovillkorlig) hårdhet för i princip alla användbara problem. Istället förlitar sig datavetare på reduktioner för att formellt relatera hårdheten hos ett nytt eller komplicerat problem till ett antagande om beräkningshårdhet om ett problem som är bättre förstådd.

Antaganden om beräkningshårdhet är av särskild betydelse vid kryptografi . Ett stort mål inom kryptografi är att skapa kryptografiska primitiver med bevisbar säkerhet . I vissa fall visar sig kryptografiska protokoll ha informationsteoretisk säkerhet ; engångsblocket är ett vanligt exempel . Informationsteoretisk säkerhet kan dock inte alltid uppnås; i sådana fall faller kryptografer tillbaka till beräkningssäkerhet. Grovt sett betyder detta att dessa system är säkra förutsatt att eventuella motståndare är beräkningsmässigt begränsade, vilket alla motståndare är i praktiken.

Antaganden om beräkningshårdhet är också användbara för att vägleda algoritmdesigners: en enkel algoritm kommer sannolikt inte att motbevisa ett väl studerat antagande om beräkningshårdhet såsom P ≠ NP .

Jämför hårdhetsantaganden

Datavetare har olika sätt att bedöma vilka hårdhetsantaganden som är mer tillförlitliga.

Antaganden om styrka av hårdhet

Vi säger att antagande $A$ är starkare än antagande $B$ när $A$ antyder $B$ (och motsatsen är falsk eller inte känd). Med andra ord, även om antagande $A$ var falskt, kan antagande $B$ fortfarande vara sant, och kryptografiska protokoll baserade på antagande $B$ kan fortfarande vara säkra att använda. Så när man utformar kryptografiska protokoll hoppas man kunna bevisa säkerhet med de svagaste möjliga antagandena.

Genomsnittligt fall kontra värsta tänkbara antaganden

Se även: Bästa, sämsta och genomsnittliga fallet

Ett genomsnittligt antagande säger att ett specifikt problem är svårt för de flesta instanser från någon explicit distribution, medan ett antagande i värsta fall bara säger att problemet är svårt i vissa instanser. För ett givet problem innebär medelhårdhet värsta fallet hårdhet, så ett antagande om medelhårdhet är starkare än ett antagande om värsta fallet för samma problem. Dessutom, även för ojämförliga problem, anses ett antagande som den exponentiella tidshypotesen ofta vara att föredra framför ett antagande om genomsnittsfall som den planterade klickantagandet . Observera dock att i de flesta kryptografiska applikationer är det värdelöst att veta att ett problem har en svår instans (dvs. ett problem är svårt i värsta fall) eftersom det inte ger oss ett sätt att generera svåra instanser. Lyckligtvis kan många genomsnittliga antaganden som används i kryptografi (inklusive RSA , diskret logg och vissa gitterproblem ) baseras på värsta tänkbara antaganden via reduktioner från värsta fall till genomsnitt.

Falsifierbarhet

En önskad egenskap hos ett antagande om beräkningshårdhet är falsifierbarhet , dvs att om antagandet var falskt skulle det vara möjligt att bevisa det. I synnerhet Naor (2003) ett formellt begrepp om kryptografisk förfalskning. Grovt sett sägs ett antagande om beräkningshårdhet vara falsifierbart om det kan formuleras i termer av en utmaning: ett interaktivt protokoll mellan en motståndare och en effektiv verifierare, där en effektiv motståndare kan övertyga verifieraren att acceptera om och endast om antagandet är falsk.

Vanliga antaganden om kryptografisk hårdhet

Det finns många antaganden om kryptografiska hårdhet som används. Detta är en lista över några av de vanligaste och några kryptografiska protokoll som använder dem.

Heltalsfaktorisering

Huvudartikel: Heltalsfaktorisering

Givet ett sammansatt tal $n$ , och i synnerhet ett som är produkten av två stora primtal $n=p\cdot q$ , är heltalsfaktoriseringsproblemet att hitta $p$ och $q$ (mer allmänt, hitta primtal $p_{1},\dots ,p_{k}$ så att $n =\prod _{i}p_{i}$ ). Det är ett stort öppet problem att hitta en algoritm för heltalsfaktorisering som körs i tidspolynom i representationsstorleken ( ${\displaystyle \log(n)} )$ . Säkerheten för många kryptografiska protokoll bygger på antagandet att heltalsfaktorisering är svår (dvs. inte kan lösas i polynomtid). Kryptosystem vars säkerhet är likvärdig med detta antagande inkluderar Rabins kryptosystem och Okamoto–Uchiyama kryptosystem . Många fler kryptosystem förlitar sig på starkare antaganden som RSA , Residuosity-problem och Phi-hiding .

RSA problem

Huvudartikel: RSA-problem

Givet ett sammansatt tal $n$ , exponent $e$ och nummer $c:=m^{e}(\mathrm {mod} \; n)$ , RSA-problemet är att hitta $m$ . Problemet antas vara svårt, men blir lätt med tanke på faktoriseringen av $n$ . I RSA-kryptosystemet är $(n,e)$ den publika nyckeln , c $\displaystyle c}$ är krypteringen av meddelandet $m$ och faktoriseringen av $n$ är den hemliga nyckel som används för dekryptering.

Restproblem

Huvudartikel: Problem med högre resthalt

Givet ett sammansatt tal $n$ och heltal $y,d$ , är residuositetsproblemet att avgöra om det finns (alternativt, hitta en) $x$ så att

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

Viktiga specialfall inkluderar Quadratic residuosity-problemet och Decisional composite residuosity-problemet . Precis som i fallet med RSA, antas detta problem (och dess specialfall) vara svårt, men blir lätt med tanke på faktoriseringen av $n$ . Vissa kryptosystem som förlitar sig på hårdheten hos restproblem inkluderar:

• Goldwasser-Micali-kryptosystem (kvadratiskt redisduositetsproblem)
• Blum Blum Shub-generator (kvadratiskt redisduositetsproblem)
• Paillier kryptosystem (beslutsproblem med sammansatt residuositet)
• Benalohs kryptosystem (problem med högre resthalt)
• Naccache–Stern kryptosystem (problem med högre resthalt)

Phi-gömma antagande

Huvudartikel: Phi-hiding antagande

För ett sammansatt tal $m$ är det inte känt hur man effektivt beräknar dess Eulers totientfunktion $\phi (m)$ . Phi-hiding-antagandet postulerar att det är svårt att beräkna ${\displaystyle \phi (m)} , och dessutom$ är det svårt att beräkna alla primtalsfaktorer för ${\displaystyle \phi (m)} .$ Detta antagande används i Cachin-Micali-Stadler PIR- protokoll.

Diskret loggproblem (DLP)

Huvudartikel: Diskret logaritm

Givet element $a$ och $b$ från en grupp $G$ , frågar det diskreta loggproblemet efter ett heltal $k$ så att $a= b^{k}$ . Problemet med diskret logg är inte känt för att vara jämförbart med heltalsfaktorisering, men deras beräkningskomplexitet är nära relaterade .

De flesta kryptografiska protokoll relaterade till det diskreta loggproblemet förlitar sig faktiskt på det starkare Diffie–Hellman-antagandet : givna gruppelement ${\displaystyle g,g^{a},g^{b}} ,$ där ${ \displaystyle g}$ är en generator och $a,b$ är slumpmässiga heltal, det är svårt att hitta $g^{a\cdot b}$ . Exempel på protokoll som använder detta antagande inkluderar det ursprungliga Diffie–Hellman-nyckelutbytet , såväl som ElGamal-krypteringen (som förlitar sig på den ännu starkare varianten Decision Diffie–Hellman (DDH) .

Multilinjära kartor

En multilinjär karta är en funktion $e:G_{1},\dots ,G_{n}\rightarrow G_{T}$ (där $G_{1},\dots ,G_{n},G_{T}$ är grupper ) så att för alla $g_ {1},\dots ,g_{n}\in G_{1},\dots G_{n}$ och $a_{1},\dots ,a_{n}$ ,

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

För kryptografiska applikationer skulle man vilja konstruera grupperna $G_{1},\dots ,G_{n},G_{T}$ och en karta $e$ så att kartan och gruppoperationerna på $G_{1},\dots ,G_{n},G_{T}$ kan beräknas effektivt, men det diskreta loggproblemet på $G_{1},\dots ,G_{n}$ är fortfarande svårt. Vissa tillämpningar kräver starkare antaganden, t.ex. multilinjära analoger av Diffie-Hellman-antaganden.

För specialfallet ${\displaystyle n=2} har$ bilinjära kartor med trovärdig säkerhet konstruerats med hjälp av Weil - parning och Tate-parning . För $n>2$ har många konstruktioner föreslagits de senaste åren, men många av dem har också brutits, och för närvarande finns det ingen konsensus om en säker kandidat.

Vissa kryptosystem som förlitar sig på multilinjära hårdhetsantaganden inkluderar:

• Boneh-Franklin-schema (blinjär Diffie-Hellman)
• Boneh–Lynn–Shacham (blinjär Diffie-Hellman)
• Garg-Gentry-Halevi-Raykova-Sahai-Waters kandidat för omöjlig att särskilja obfuskation och funktionell kryptering (multilinjära pussel)

Gallerproblem

Huvudartikel: Gitterproblem

Det mest grundläggande beräkningsproblemet på gitter är det kortaste vektorproblemet (SVP) : givet ett gitter $L$ , hitta den kortaste vektorn som inte är noll $v\in L$ . De flesta kryptosystem kräver starkare antaganden om varianter av SVP, som Shortest independent vectors problem (SIVP) , GapSVP eller Unique-SVP.

Det mest användbara antagandet om gitterhårdhet i kryptografi är för Learning with errors (LWE)-problemet: Givet exempel på $(x,y)$ , där $y=f (x)$ för någon linjär funktion $f(\cdot )$ är det lätt att lära sig $f(\cdot )$ med linjär algebra. I LWE-problemet har ingången till algoritmen fel, dvs för varje par $y\neq f(x)$ med någon liten sannolikhet. Felen tros göra problemet svårlöst (för lämpliga parametrar); i synnerhet finns det kända minskningar från värsta fall till genomsnittliga fall från varianter av SVP.

För kvantdatorer är Factoring och Discrete Log-problem lätta, men gallerproblem antas vara svåra. Detta gör vissa gitterbaserade kryptosystem till kandidater för post-kvantkryptografi .

Vissa kryptosystem som förlitar sig på hårdhetsproblem i gitter inkluderar:

• NTRU (både NTRUEncrypt och NTRUSign )
• De flesta kandidater för helt homomorf kryptering

Icke-kryptografiska hårdhetsantaganden

Förutom deras kryptografiska tillämpningar används hårdhetsantaganden i beräkningskomplexitetsteori för att ge bevis för matematiska påståenden som är svåra att bevisa ovillkorligt. I dessa applikationer bevisar man att hårdhetsantagandet innebär något önskat komplexitetsteoretiskt påstående, istället för att bevisa att påståendet i sig är sant. Det mest kända antagandet av denna typ är antagandet att P ≠ NP , men andra inkluderar den exponentiella tidshypotesen , den planterade klickförmodan och den unika spelförmodan .

C -hårda problem

Många värsta beräkningsproblem är kända för att vara svåra eller till och med kompletta för någon komplexitetsklass ${\displaystyle C},$ särskilt NP-hård (men ofta även PSPACE-hård , PPAD-hård , etc.). Det betyder att de är minst lika svåra som alla problem i klassen $C$ . Om ett problem är $C$ -hårt (med avseende på polynomiska tidsreduktioner), kan det inte lösas med en polynom-tidsalgoritm om inte antagandet om beräkningshårdhet $P\neq C$ är falskt .

Exponentiell tidshypotes (ETH) och varianter

Huvudartikel: Exponentiell tidshypotes

Den exponentiella tidshypotesen (ETH) är en förstärkning av $P\neq NP$ hårdhetsantagande, som antar att inte bara det booleska tillfredsställbarhetsproblemet inte har en polynomisk tidsalgoritm, det kräver dessutom exponentiell tid ( $2^{\Omega (n)}$ ). Ett ännu starkare antagande, känt som Strong Exponential Time Hypothesis (SETH) antar att $k$ -SAT kräver $2^{(1-\varepsilon _{k}) n}$ tid, där $\lim _{k\rightarrow \infty }\varepsilon _{k}=0$ . ETH, SETH och relaterade antaganden om beräkningshårdhet möjliggör härledning av finkorniga komplexitetsresultat, t.ex. resultat som särskiljer polynomtid och kvasipolynomtid , eller till och med $n^{1,99}$ kontra $n ^{2}$ . Sådana antaganden är också användbara i parametriserad komplexitet .

Antaganden om medelhårdhet i fallet

Huvudartikel: Average-case complexity

Vissa beräkningsproblem antas vara svåra i genomsnitt över en viss fördelning av instanser. Till exempel, i det planterade klickproblemet är inmatningen en slumpmässig graf samplad, genom att sampla en Erdős–Rényi slumpmässig graf och sedan "plantera" en slumpmässig $k$ -klick, dvs koppla $k$ enhetligt slumpmässiga noder (där ${\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}} ),$ och målet är att hitta det planterade ${\ displaystyle k}$ -klick (vilket är unikt whp). Ett annat viktigt exempel är Feiges hypotes, som är ett antagande om beräkningshårdhet om slumpmässiga instanser av 3-SAT (samplade för att upprätthålla ett specifikt förhållande mellan satser och variabler). Antaganden om genomsnittlig beräkningshårdhet är användbara för att bevisa genomsnittlig hårdhet i applikationer som statistik, där det finns en naturlig fördelning över indata. Dessutom har antagandet om planterade klickhårdhet också använts för att skilja mellan polynom och kvasipolynom värsta tänkbara tidskomplexitet för andra problem, på samma sätt som den exponentiella tidshypotesen .

Unika spel

Huvudartikel: Unique Games Conjecture

Problemet med Unique Label Cover är ett problem med begränsningstillfredsställelse, där varje begränsning $C$ involverar två variabler ${\displaystyle x,y} ,$ och för varje värde på $x$ finns ett unikt värde av $y$ som uppfyller $C$ . Det är lätt att avgöra om alla begränsningar kan uppfyllas, men Unique Game Conjecture (UGC) postulerar att bestämma om nästan alla begränsningar ( $(1-\varepsilon )$ -fraktion, för någon konstant $\varepsilon >0$ ) kan vara uppfyllda eller nästan ingen av dem ( $\varepsilon$ -fraktion) kan vara nöjd är NP-hård. Approximationsproblem är ofta kända för att vara NP-hårda om man antar UGC; sådana problem kallas UG-hårda. I synnerhet om man antar att UGC finns en semidefinite programmeringsalgoritm som uppnår optimala approximationsgarantier för många viktiga problem.

Liten Set Expansion

Nära relaterat till Unique Label Cover-problemet är Small Set Expansion (SSE) -problemet: Givet en graf $G=(V,E)$ , hitta en liten uppsättning hörn (av storleken $n/\log(n)$ ) vars kantexpansion är minimal. Det är känt att om SSE är svårt att uppskatta, så är Unique Label Cover det också. Därför är Small Set Expansion Hypothesis , som postulerar att SSE är svår att uppskatta, ett starkare (men närbesläktat) antagande än Unique Game Conjecture. Vissa approximationsproblem är kända för att vara SSE-hårda (dvs. minst lika svåra som approximerande SSE).

3SUM-förmodan

Huvudartikel: 3SUM

Givet en uppsättning av $n$ tal, frågar 3SUM-problemet om det finns en triplett av tal vars summa är noll. Det finns en kvadratisk-tidsalgoritm för 3SUM, och det har antagits att ingen algoritm kan lösa 3SUM i "verkligt subkvadratisk tid": 3SUM-förmodan är antagandet om beräkningshårdhet att det inte finns några ${ \displaystyle O(n^{2-\varepsilon })}$ -tidsalgoritmer för 3SUM (för valfri konstant ${\displaystyle \varepsilon >0} )$ . Denna gissning är användbar för att bevisa nästan kvadratiska nedre gränser för flera problem, mest från beräkningsgeometri .

Se även

• Säkerhetsnivå