Sémantická bezpečnost - Semantic security - Wikipedia

v kryptografie, a sémanticky bezpečné kryptosystém je takový, kde jsou pouze zanedbatelné informace o prostý text může být proveditelně extrahován z šifrový text. Konkrétně jakékoli pravděpodobnostní algoritmus polynomiálního času (PPTA), kterému je dán šifrový text určité zprávy ${ displaystyle m}$ (převzato z jakékoli distribuce zpráv) a délka zprávy nemůže s pravděpodobností určit žádné dílčí informace o zprávě nezanedbatelně vyšší než všechny ostatní PPTA, které mají přístup pouze k délce zprávy (a ne k šifrovacímu textu).^[1] Tento koncept je analogický výpočetní složitosti Shannon koncept dokonalé utajení. Dokonalé utajení znamená, že šifrový text neodhalí vůbec žádné informace o prostém textu, zatímco sémantická bezpečnost znamená, že jakékoli odhalené informace nelze provést.^{[2][3]:378–381}

Dějiny

Pojem sémantické bezpečnosti byl poprvé předložen Goldwasser a Micali v roce 1982.^[1] Definice, kterou původně navrhli, však nenabízela žádné přímé prostředky k prokázání bezpečnosti praktických kryptosystémů. Goldwasser / Micali následně prokázali, že sémantická bezpečnost je ekvivalentní jiné definici zabezpečení, která se nazývá nerozeznatelnost šifrovacího textu pod útokem vybraného holého textu.^[4] Tato druhá definice je častější než původní definice sémantické bezpečnosti, protože lépe usnadňuje prokazování bezpečnosti praktických kryptosystémů.

Kryptografie se symetrickým klíčem

V případě algoritmus symetrického klíče cryptosystems, protivník nesmí být schopen vypočítat ze svého šifrovacího textu žádné informace o prostém textu. To lze považovat za protivníka, vzhledem k tomu, že dva holé texty stejné délky a jejich dva příslušné šifry nemohou určit, který šifrový text patří ke kterému holému textu.

Kryptografie veřejného klíče

Tato sekce potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. (Září 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Pro asymetrický šifrovací algoritmus klíče aby byl kryptosystém sémanticky zabezpečený, musí být pro a výpočetně omezený protivník odvodit významné informace o zprávě (prostý text), pokud je dána pouze její šifrový text a odpovídající veřejný šifrovací klíč. Sémantická bezpečnost bere v úvahu pouze případ „pasivního“ útočníka, tj. Takového, který generuje a pozoruje šifry pomocí veřejného klíče a holých textů podle svého výběru. Na rozdíl od jiných definic zabezpečení sémantické zabezpečení nezohledňuje případ zvolený útok šifrovaného textu (CCA), kde je útočník schopen požadovat dešifrování vybraných šifrovacích textů, a mnoho sémanticky bezpečných šifrovacích schémat je prokazatelně nezabezpečeno proti vybranému útoku šifrovacím textem. V důsledku toho je sémantické zabezpečení nyní považováno za nedostatečnou podmínku pro zabezpečení obecného schématu šifrování.

Nerozlišitelnost pod Zvolený útok prostého textu (IND-CPA ) je běžně definován následujícím experimentem:^[5]

1. Náhodný pár ${ displaystyle (pk, sk)}$ je generován spuštěním ${ displaystyle Gen (1 ^ {n})}$.
2. Pravděpodobnostní polynomiální časově omezený protivník dostane veřejný klíč ${ displaystyle pk}$ , které může použít ke generování libovolného počtu šifrových textů (v polynomiálních mezích).
3. Protivník generuje dvě zprávy stejné délky ${ displaystyle m_ {0}}$ a ${ displaystyle m_ {1}}$a předává je do věštby výzev spolu s veřejným klíčem.
4. Výzva Oracle vybere jednu ze zpráv otočením spravedlivé mince (výběr náhodného bitu ${ displaystyle b in {0,1 }}$), zašifruje zprávu ${ displaystyle m_ {b}}$ pod veřejným klíčem a vrátí výsledný náročný ciphertext ${ displaystyle c}$ protivníkovi.

Podkladové kryptosystém je IND-CPA (a tedy sémanticky bezpečný pod zvoleným útokem holého textu), pokud protivník nemůže určit, která z těchto dvou zpráv byla vybrána věštcem, s pravděpodobností významně větší než ${ displaystyle 1/2}$ (úspěšnost náhodného hádání). Varianty této definice definují nerozeznatelnost pod zvolený útok šifrovaného textu a adaptivně zvolený útok šifrovaného textu (IND-CCA, IND-CCA2 ).

Protože protivník má ve výše uvedené hře veřejný šifrovací klíč, musí být podle definice sémanticky zabezpečené šifrovací schéma pravděpodobnostní, který vlastní komponentu náhodnost; pokud by tomu tak nebylo, mohl by protivník jednoduše vypočítat deterministické šifrování ${ displaystyle m_ {0}}$ a ${ displaystyle m_ {1}}$ a porovnat tyto šifrování s vráceným šifrovacím textem ${ displaystyle c}$ úspěšně uhodnout volbu věštce.

Mezi sémanticky bezpečné šifrovací algoritmy patří Goldwasser-Micali, El Gamal a Paillier. Tyto režimy jsou zvažovány prokazatelně bezpečný, protože jejich sémantická bezpečnost může být snížena na řešení nějakého těžkého matematického problému (např. Rozhodující Diffie-Hellman nebo Problém kvadratické reziduosity ). Jiné, sémanticky nezabezpečené algoritmy jako např RSA, lze sémanticky zabezpečit (za silnějších předpokladů) pomocí náhodných šifrovacích schémat, jako je Optimální asymetrické šifrování (OAEP).

Reference