Šifrovací schéma GGH

Šifrovací schéma GGH ( Eng. Goldreich–Goldwasser–Halevi ) je asymetrický kryptografický systém založený na mřížkách . Existuje také schéma podpisu GGH .

Kryptosystém je založen na řešení problému nalezení nejkratšího vektoru a problému nalezení nejbližšího vektoru . Šifrovací schéma GGH, publikované v roce 1997 vědci Oded Goldreich , Shafi Goldwasser a Shai Halevi , používá jednosměrnou tajnou vstupní funkci , protože vzhledem k jakékoli mřížkové bázi je snadné generovat vektor blízko bodu mřížky. Například vzít bod mřížky a přidat malý chybový vektor. Pro návrat z chybového vektoru do počátečního bodu mřížky je potřeba speciální základ. V roce 1999 provedl Phong Q. Nguyen [1] upřesnění původního schématu šifrování GGH, které umožnilo vyřešit čtyři z pěti problémů GGH a získat o nich částečné informace. Zatímco GGH může být bezpečný s určitými volbami parametrů, jeho účinnost oproti tradičním kryptosystémům s veřejným klíčem zůstává diskutabilní [2] . Šifrování často vyžaduje velký rozměr mřížky, zatímco velikost klíče roste přibližně kvadraticky s ohledem na velikost mřížky [2] .

Jediné schéma mřížky, které zvládne vysoké dimenze, je NTRU [3] .

Algoritmus

GGH zahrnuje veřejný klíč a soukromý klíč [4] . Soukromý klíč je základem mřížky s unimodulární maticí . $B$ $L$ $U$

Veřejný klíč je dalším základem mřížky formuláře . $L$ $B'=UB$

Nechť prostor zprávy M sestává z vektorů patřících do intervalu . $(m_{1},...,m_{n})$ $-M<m_{i}<M$

Šifrování

Zadaná zpráva , chyba a veřejný klíč : $m=(m_{1},...,m_{n})$ $E$ $B'$

v=\sum m_{i}b_{i}'

V maticovém zápisu:

v=m\cdot B'

Je třeba mít na paměti, že se skládá z celočíselných hodnot, je to mřížkový bod, a proto je také mřížkovým bodem. Potom je šifrový text: $m$ $b'$ $proti$

c=v+e=m\cdot B'+e

Přepis

Pro dešifrování šifrovaného textu se vypočítá:

c\cdot B^{-1}=(m\cdot B^{\prime }+e)B^{-1}=m\cdot U\cdot B\cdot B^{-1}+e\cdot B ^{-1}=m\cdot U+e\cdot B^{-1}

K odstranění , pokud je dostatečně malý, se používá Babaiova metoda zaokrouhlení [5] . $e\cdot B^{-1}$

Poté získáte text:

m=m\cdot U\cdot U^{-1}

Bezpečnostní analýza

Tato část pojednává o několika způsobech útoku na kryptosystém [6] .

Útok zaokrouhlením

Útok zaokrouhlení je nejzřetelnějším útokem tohoto kryptografického systému, kromě útoku hrubou silou - hledání chybového vektoru . Jeho podstatou je použití veřejného klíče B k invertování funkce stejným způsobem jako při použití soukromého klíče R Totiž, když víte , můžete vypočítat . Můžete tedy najít vektor . Při rozměrech pod 80 LLL je algoritmus schopen správně určit základnu, avšak počínaje rozměry 100 a vyššími je tento útok horší než triviální výčet chybového vektoru. $e.$ $c=B\cdot v+e$ $B^{-1}\cdot c=v+B^{-1}\cdot e$ $d=B^{-1}\cdot e$

Bouřkový útok

Tento algoritmus je zjevným vylepšením zaokrouhlovacího útoku. Zde používáme nejlepší aproximační algoritmus pro nejkratší vektorový problém. Konkrétně se místo Babaiova zaokrouhlovacího algoritmu používá algoritmus nejbližší roviny. Funguje to takto. Daný bod a redukovaný základ c = { } pro LLL . Uvažují se všechny afinní prostory = { + } : }. Pro všechny existuje nadrovina nejblíže bodu . Dále je bod promítnut do (n - 1)-rozměrného prostoru, který je pokryt = { } . To dává nový bod a nový základ = { }. Algoritmus nyní pokračuje rekurzivně , aby našel bod v této (n-1)-rozměrné mřížce blízko . Nakonec algoritmus nastaví . Tato metoda funguje mnohem rychleji než ta předchozí. Jeho pracovní zátěž však také roste exponenciálně s dimenzí mřížky. Experimenty ukazují, že při použití LLL jako algoritmu pro redukci mřížky je vyžadována určitá doba hledání, počínaje velikostí 110-120. Počínaje velikostí 140-150 se útok stává neproveditelným. $c$ $B$ ${b_{1}},\tečky {b_{n}}$ ${H_{k))$ $k\cdot {b_{n))$ $\sum _{i=0}^{n-1}{a_{i}}\cdot {b_{i}}$ ${a_{i}}\in {\mathcal {R}}$ $k\in {\mathcal {Z))$ ${H_{k))$ $c$ $B$ ${b_{1}},\tečky {b_{n}}$ $ck\cdot {b_{n))$ $c'$ $B'$ ${b_{1}},\tečky {b_{n}}$ $p'$ $c'$ $p=p'+k\cdot {b_{n))$

Injekční útok

Dalším způsobem, který se často používá k aproximaci problému hledání nejbližšího vektoru , je vložení n bázových vektorů a bodu, pro který je nutné najít blízký bod mřížky v (n + 1)-rozměrné mřížce. $c$

$B'={\begin{pmatrix}\vdots &\vdots &\vdots &\cdots &\vdots \\c&b_{1}&b_{2}&\cdots &b_{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&0&0&\cdots &0\end{pmatrix}}$

Algoritmus redukce mřížky je pak použit k nalezení nejkratšího nenulového vektoru v , v naději, že prvních n prvků v tomto vektoru bude nejblíže bodům . Experimenty provedené na tomto útoku (pomocí LLL jako nástroje pro hledání nejkratších vektorů) ukazují, že funguje až do dimenzí kolem 110-120, což je lepší než útok zaokrouhlování, který je horší než triviální hledání po dimenzi 100. $L(B')$ $c$

Odhad efektivity útoků [7]

Odhadovaný útok zaokrouhlením

Nechte v každé dimenzi vytvořit pět uzavřených základen. Každá báze je zvolena jako = + rand , kde I je matice identity a rand je čtvercová matice , jejíž členy jsou vybrány jednotně z rozsahu . Pro každý základ se vypočítá hodnota = , kde je euklidovská norma největšího řádku a . Pro každou uzavřenou bázi je generováno pět otevřených základen $n$ ${R_{i))$ $4\left|{\sqrt {n}}\right|\cdot I$ $(\pm 4)$ $(\pm 4)$ ${-4,...,4}$ ${R_{i))$ ${\sigma _{i))$ ${\displaystyle ({\gamma _{i)){\sqrt {8\ln({2n}/{\varepsilon }))))^{-1))$ ${\gamma _{i))$ ${R_{i}}^{-1}$ $\varepsilon =10^{-5}$ ${R_{i))$ ${B_{ij))$

${pracovní zátěž_{ij))$ = , kde je vada dvojité ortogonality: kde označuje řádek matice . ${\displaystyle ({\pi }e)^{n/2))$ $\cdot {\sigma _{i}^{n))$ $\cdot {\frac {orth-defect^{*}({B_{ij)))}{det|{B_{ij}}|}}$ $orth-defect^{*}$ $orth-defect^{*}(B)=|det(B)|\cdot \prod _{i}\|{\hat {b_{i))}\|,$ ${\displaystyle {\klobouček {b_{i))))$ $B^{{-1}}$

Assault score

Pro vyhodnocení přepadového útoku byly použity stejné otevřené a uzavřené základny jako při útoku zaokrouhlením.

Hodnocení útoku vstřikováním

Protože nelze hovořit o „vytížení“ injekčního útoku, byla změřena maximální hodnota (vztažená k vektoru chyby), pro kterou tento útok funguje. Pro tyto experimenty byly použity stejné uzavřené základny a otevřené základny jako u předchozích dvou útoků. Poté byla každá otevřená báze použita k vyhodnocení funkce v několika bodech pomocí několika různých hodnot a zkontrolovalo se, zda injekční útok obnoví zašifrovanou zprávu. ${\sigma}$ ${R}$ ${B_{ij))$ $\sigma$

Příklad

Nechť mřížka se základnou a její převrácená je : $L\subset \mathbb {R} ^{2}$ $B$ $B^{{-1}}$

B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}

B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}

S unimodulární matricí:

U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix}}

U^{-1}={\begin{pmatrix}5&-3\\-3&2\\\end{pmatrix}}

Dostaneme:

B'=UB={\begin{pmatrix}14&9\\21&15\\\end{pmatrix}}

Nechte zprávu a vektor chyb Pak šifrový text: $m=(3,-7)$ $e=(1,-1).$

c=mB'+e=(-104,-79)

K dešifrování potřebujete:

cB^{-1}=\left({\frac {-104}{7)),{\frac {-79}{3}}\right)

Toto zaokrouhluje nahoru $(-15,-26).$

A zpráva se obnoví pomocí:

m=(-15,-26)U^{-1}=(3,-7).\,

Zdroje a další četba

Oded Goldreich, Shafi Goldwasser a Shai Halevi. Kryptosystémy s veřejným klíčem z problémů redukce mřížky. In CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112-131, London, UK, 1997. Springer-Verlag.
Phong Q. Nguyen. Kryptoanalýza kryptosystému Goldreich-Goldwasser-Halevi z Crypto '97. In CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288-304, London, UK, 1999. Springer-Verlag.

Poznámky

↑ Phong Q. Nguyen. Kryptoanalýza kryptosystému Goldreich-Goldwasser-Halevi z Crypto '97. . - S. 1-17 . Archivováno z originálu 16. července 2018.
↑ 1 2 Phong Q. Nguyen. Kryptoanalýza kryptosystému Goldreich-Goldwasser-Halevi z Crypto '97. S. - 1-2. . Archivováno z originálu 16. července 2018. (neurčitý)
↑ Phong Q. Nguyen. Kryptoanalýza kryptosystému Goldreich-Goldwasser-Halevi z Crypto '97. S. - 1 . Archivováno z originálu 16. července 2018. (neurčitý)
↑ Oded Goldreich, Shafi Goldwasser a Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Kryptosystémy s veřejným klíčem z problémů s redukcí mřížky]. - S. 112-114 . Archivováno 4. května 2019.
↑ Phong Q. Nguyen. Kryptoanalýza kryptosystému Goldreich-Goldwasser-Halevi z Crypto '97. . - S. 4 . Archivováno z originálu 16. července 2018.
↑ Oded Goldreich, Shafi Goldwasser a Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Kryptosystémy s veřejným klíčem z problémů s redukcí mřížky]. — S. 122-124 . Archivováno 4. května 2019.
↑ Oded Goldreich, Shafi Goldwasser a Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Kryptosystémy s veřejným klíčem z problémů s redukcí mřížky]. - S. 127-130 . Archivováno 4. května 2019.