A kriptográfia , a bizonyítás a biztonság a bizonyítéka , hogy a kriptográfiai algoritmusok (más néven rendszer ) tiszteletben tartja a biztonsági definíciók, amelyek szükségesek őket. Ezek a biztonsági fogalmi meghatározások leírások séma osztályok nevű kriptográfiai primitívek . Néhány kriptológiai munka a primitívek meghatározásában áll e meghatározások egységesítése érdekében, például Bellare, Micciancio és Warinschi definíciói a 2003-as csoportos aláíráshoz , ezt a koncepciót Chaum és van Heyst határozta meg először 1991-ben.
A biztonság első bizonyítéka a biztonság az eldobható maszkok információelmélete értelmében . Ezt a fogalmat Claude Shannon vezette be az 1949-ben megjelent titoktartási rendszerek kommunikációelmélete című cikkében , és az eldobható maszk biztonságát ebben a cikkben mutatták be. Az eldobható maszk titkosítási séma , ezért a megkövetelt biztonság fogalma nem különböztethető meg az egyenruhától . Más szavakkal, a cél az, hogy egyetlen ellenfél sem tudja megmondani, hogy egy titkosított üzenet véletlenszerű bitekből áll-e, vagy rejt-e üzenetet. Informálisan ez megfelel az üzenetre adott igen vagy nem válaszadásnak , majd azt mondjuk, hogy egy kis információt levontunk az üzenetről. Ha ezt lehetetlen elérni, akkor lehetetlen következtetni az eredeti üzenetre.
Mivel az információelmélet értelmében nehéz elérni a biztonságot, a kriptográfiai bizonyítások gyakran számítási feltételezéseken alapulnak , ahol a biztonság fogalmát ezután ezeknek a feltételezéseknek a feltételezett bonyolultságára redukálják. Ezután egy közös hipotézisen alapuló diagramkészlet kriptanalízisét visszavezetjük a hipotézis nehézségének tanulmányozásához. Néha biztonságcsökkentésről beszélünk , utalva a komplexitáselmélet polinomiális csökkentésére .
A titkosítási területet, ahol a minták biztonságosnak bizonyulnak, bizonyítható biztonságnak nevezzük .
A biztonság megközelítései történelmileg különböznek a szimmetrikus és az aszimmetrikus kriptográfia között .
Annak ellenére, hogy vannak titkos kulcsú kriptográfiában bizonyított sémák, mint például a Blum Blum Shub ál-véletlenszerű generátora, amely biztonságos a másodfokú maradványok problémája alatt, a gyakorlati alkalmazásokban gyakran előnyben részesítették azokat a sémákat, amelyek ellenálltak a hatékonyságról ismert kriptanalízisnek . okokból. A NIST ennek alapján javasolta az SHA-1 és az SHA-2 alkalmazását. De 2012- ben Keccak lesz az új szabvány a kriptográfiai hash funkció szempontjából , biztonságosnak bizonyult a szivacsfunkciókkal kapcsolatos feltételezések alapján .
Az aszimmetrikus kriptográfiában viszont már régóta figyelembe vesszük a számítási hipotézisek alapján bizonyított sémákat. A nagyon gyors sémák iránti igényt a magánkulcsú titkosítás fedezi , és az aszimmetrikus kriptográfia használata gyakran hibrid kriptográfia révén történik . Például az ElGamal kriptorendszert a Diffie-Hellman (in) döntés problémájának feltételezése alapján bizonyítják , amely magában foglalja a diszkrét logaritmus nehéz problémáját , amely a moduláris aritmetika problémája . A bizonyíték a biztonsági az ElGamal titkosítórendszer készül csökkentése , más szóval annak bizonyítására, hogy a biztonság fogalmát ellenáll, azt bizonyítja, hogy ez a fogalom a diagramon legalább olyan nehéz, mint a biztonsági feltételezések akár egy polinom tényező. Ezért elhanyagolhatónak tekintett többletköltségekért találjuk magunkat megoldani egy állítólag nehéz problémát.
A biztonságcsökkentés egyik módja a nehézségi feltételezésektől a bizonyítandó biztonsági koncepciókig terjedő polinomcsökkentés. Ez a helyzet például az ElGamal vagy a Goldwasser-Micali kriptorendszer igazolásával .
A bizonyítékok finomságának fontosságaA bizonyítható biztonságban a támadó minőségét az előnyével mérjük , vagyis annak valószínűségével, hogy sikerül megtörnie egy biztonsági tulajdonságot (például hamisítást előállítani a digitális aláírásokhoz ). A biztonsági csökkentésben egy támadóval indulunk a biztonsági tulajdon ellen, így feltételezett előnyünk van , és egy biztonsági hipotézissel szemben támadóhoz érkezünk, polinomiailag gyengébb előnnyel. Ennek a polinomnak a tanulmányozása a fontos, mivel egy többfelhasználós rendszerben a csökkentés a felhasználók számától függhet, egy klasszikus általános módszer például annak kitalálása, hogy melyik felhasználót fogja megtámadni a felhasználó. ellenfelet, mielőtt egyfelhasználós rendszerbiztonságot alkalmazna a célfelhasználóra. Ez feltételezi az ε feltételezett előnyét az egyfelhasználós rendszer számára , ami azt jelenti, hogy az internetes hálózat számára 2016-ban 2⁴¹ nagyságrendű biztonsági veszteség következik be, ami azt jelenti, hogy egy több biztonsági - 80 bites felhasználó esetében egyetlen felhasználó 121 bites biztonságára van szüksége, amely ennek megfelelően megnöveli a kulcsok méretét (például az RSA Signature számára kiválasztott prímszámok , és ennek következtében az aláírás mérete).
A biztonságvesztés jobb becslésén végzett munka javítja a kriptográfiai rendszerek biztonságával kapcsolatos ismereteinket , és a legjobb esetben (állandó biztonsági veszteség) a kriptológusok szerint a bizonyítékok rendben vannak .
Játékonként néha bizonyítékot használnak, ha a biztonság definícióját az ellenfél által megnyerni kívánt kriptográfiai játék adja . Ez a helyzet például a rejtjelezési sémák szemantikai biztonságával . A cél lépésről lépésre haladni az eredeti játéktól, amelyet a támadónak meg kell nyernie, átalakítani lépésről lépésre játékgá, amelyet az ellenfél nem nyerhet meg, például azért, mert ez egy nehéz probléma megoldásának felel meg, vagy mert nincs több információk a kezdeti üzenetről. Az egyik szakaszból a másikba való átmenet csak elhanyagolható módon változtathatja meg az előnyt és az ellenfél nézőpontját az előző játékhoz képest. Olyan módon, hogy a különböző átalakítások alkalmazásával olyan játékhoz jutunk, amelyet az ellenfél nem képes megnyerni, elhanyagolható távolságban a biztonság fogalmától, amelyet demonstrálni akarunk.
Az ilyen bizonyítások előnye, hogy könnyen ellenőrizhetők, mivel az egyik lépéstől a másikig terjedő részeket egyértelművé teszik, és ezért az érvelés lépésről lépésre ellenőrizhető.
Így kriptográfiai játékokkal átfogalmazhatjuk az ElGamal kriptorendszer bizonyítékait .
A következőkben a " " kapcsolat azt jelenti, hogy két eloszlás statisztikailag vagy számítási szempontból szoros; az Adv i pedig az ellenfél előnyét jelöli . A szemantikai biztonság szempontjából a mennyiségről van szó .
Végül észrevesszük, hogy a 3. játékot egyetlen ellenfél sem nyerheti meg más valószínűséggel, mint 1/2. Ezenkívül az egyetlen átalakulás, amely ezt a valószínűséget megváltoztatja, a 2. játék, ahol a Diffie-Hellman számítási döntési argumentumot alkalmazzák. Ez azt jelenti, hogy az ellenfél előnyét e sémával szemben korlátozza az ellenfél előnye a DDH-val szemben; valóban
De mit nevezzünk nehéznek ? Erre a kérdésre a komplexitás elmélete ad választ, amelyből kölcsönözzük többek között a problémák közötti redukció fogalmát. Ez az elmélet arra törekszik, hogy a problémákat a megoldásukhoz szükséges számítási idő szerint osztályozza, és meghatározza a "nehézség" osztályait. Ebben az esetben a minket érdeklő osztály az úgynevezett nem-determinisztikus polinom (NP). Ezek azok a problémák, amelyekre egy adott megoldást "könnyű" ellenőrizni (a polinomi időben igaz ), de fennáll annak a veszélye, hogy nehéz (esetleg nem polinomiális időben) megtalálni .
Az NP osztály problémájához való tartozás nem jelenti azt , hogy polinom időben nem oldható meg. Valójában a P összes problémája NP-ben van, és az a tény, hogy tudjuk-e, éppen ellenkezőleg, vannak olyan NP-problémák, amelyek nem szerepelnek a P-ben, úgynevezett P = NP feladat , a matematika egyik legnagyobb nyitott kérdése.
Az elméleti rejtjelezés során a bonyolultság más osztályait vizsgálják annak meghatározása érdekében, hogy mi tekinthető nehéznek vagy sem, például az AC⁰ vagy az NC¹ annak megismerésére, hogy mi maradna a polinomiális hierarchia összeomlása esetén , akkor például tudjuk, hogy ha az függvények léteznek, akkor a P ≠ NP , amely érvénytelenítené a kriptográfia egy részét ezen munkahipotézis alapján egy összeomlás esetén.
A rejtjelezés által használt problémák mind az NP-ben vannak: "könnyű" kódolni egy üzenetet, vagy dekódolni egy üzenetet, ha megvan a kulcs. Másrészt a tudás jelenlegi állapotában a kódok feltörésére szolgáló összes létező módszer exponenciális a kulcs méretében. Egyrészt a kulccsal történő kódolás vagy dekódolás, másrészt a megszakítás közötti gyakorlati aránytalanság teszi a módszereket hasznossá.
Jelenleg nincs elméleti kifogás a ma használt polinomiális kódtörő algoritmusok létezése ellen, csupán az a gyakorlati megfigyelés, hogy ezek a problémák elég hosszú ideig ellenálltak a közösség tartós erőfeszítéseinek. Megjegyezzük azt is, hogy a kvantum számítógépek, ha sikerül elég "méretű" (qbits számú) felépíteni őket, lehetővé tennék az RSA-hoz hasonló rendszerek megszakítását Shor algoritmusán keresztül .
Végül fontos megjegyezni, hogy a biztonsági bizonyítékokat körültekintően kell venni. Phjt Nguyen és Jacques Stern például megtörte az Ajtai-nak és a Dwork-nek köszönhető rendszert, elméleti biztonsági bizonyítékokkal együtt, amelyek nehéz problémát feltételeznek .