Jiří Pavlů a Tomáš Rosa

  Zpět...

Kvantové počítače přicházejí. Je čas panikařit?
Jiří Pavlů a Tomáš Rosa, Raiffeisenbank

Začalo to snahou o zrychlení a zpřesnění výpočetních simulací přírodních systémů popsaných zákony kvantové mechaniky. To byla původní myšlenka, která dodnes z významné části stojí za vývojem kvantových počítačů. Vzhledem k neustálému zrychlování klasických počítačů bylo však dlouhou dobu možné zrychlovat a zpřesňovat tyto simulace i bez použití kvantových jevů, čímž byla myšlenka kvantových počítačů poněkud upozaděna.

Zvrat nastal ve chvíli, kdy Peter Shor představil kvantový algoritmus, který zvládne rychle faktorizovat moduly RSA a počítat diskrétní logaritmy na běžných kryptografických grupách. To v podstatě znamená, že téměř veškerá současná kryptografie s veřejným klíčem je prolomitelná útokem kvantového počítače. Od té doby se o kvantové počítače začali zajímat kryptologové a technologické firmy z celého světa.

Síla kvantových počítačů spočívá mimo jiné v tom, že jejich výpočetní kapacita v jistém smyslu roste exponenciálně s počtem dostupných kvantových bitů, tzv. qubitů. Hovoříme o kvantovém paralelismu, kdy pro n qubitů lze provádět operace paralelně nad 2n bázových stavů. Zdůrazněme ale, že to dosud neznamená, že jsou kvantové počítače schopné eliminovat exponenciální růst počtu přípustných klíčů (vztaženo k délce klíče) a prolomit tak libovolnou šifru pouze prostým vyzkoušením všech možných klíčů paralelně a vybráním toho správného. I přes tento kvantový paralelismus totiž změříme na konci algoritmu jen jeden výsledek, který bude navíc vybrán náhodně.

Naštěstí, jsou v kvantových počítačích pravděpodobnosti naměření jednotlivých výsledků závislé na amplitudách, které jsou obecně komplexní čísla. Díky tomu mohou tyto amplitudy (a tedy i na nich závislé pravděpodobnosti) interferovat, a to buď konstruktivně, nebo destruktivně. Umění návrhu kvantových algoritmů pak spočívá v hledání způsobů, jak zajistit, aby se pravděpodobnosti naměření špatných (pro nás nezajímavých) výsledků vyrušily, a tím se zároveň zvýšila šance, že naměříme správný (pro nás zajímavý) výsledek. Vedle kvantového paralelismu je tak další zásadní vlastností kvantových počítačů jejich interferenční chování. V přednášce si ukážeme praktické ilustrační příklady.

Možná obrana proti kvantovým útokům se dá rozdělit na dvě hlavní ideje – kvantová distribuce klíče (QKD) a kryptografie odolná vůči kvantovým počítačům (tzv. post-kvantová kryptografie, PQC). Výhodou QKD je to, že využívá přímo samotnou kvantovou mechaniku, aby zajistila, že sdílený klíč nebyl odposlechnut. To je zajištěno tím, že pozorování neznámého kvantového bitu ovlivní jeho stav, a tedy každý pokus o odposlechnutí kvantových bitů sdíleného klíče je s určitou pravděpodobností detekován. Bohužel to také znamená, že QKD není odolná proti DoS útokům, jelikož libovolný pokus o odposlechnutí klíče znamená přerušení komunikace.

Oproti tomu PQC pouze vyžaduje, abychom zakládali bezpečnost našich kryptosystémů na obtížnosti řešení jiných matematických problémů než dnes. Konkrétněji bychom například již neměli předpokládat, že faktorizace je obtížná, ale používat takové problémy, které jsou neschůdné i pro kvantové počítače.

V přednášce se budeme zabývat mimo jiné následujícími otázkami: Kdy lze očekávat první kvantový útok? Jaká je hrozba retroaktivní kryptoanalýzy? Jak tyto útoky vlastně fungují? Můžeme se bránit? Jaká zavést protiopatření dnes, abychom zůstali v bezpečí i zítra? Nebo snad znamená příchod kvantových počítačů konec kryptografie tak, jak ji známe dnes?

Jiří Pavlů

Je absolventem magisterského studia v oboru Matematika pro informační technologie na Matematicko-fyzikální fakultě Univerzity Karlovy. Věnuje se teoretické kryptografii, zejména pak bezpečnosti a použitelnosti symetrických šifer, a teorii kódů. Je kryptologem kompetenčního centra skupiny Raiffeisen Bank International.

Tomáš Rosa

Je doktorem v oboru kryptologie s Cenou rektora ČVUT za rok 2004. Studoval na FEL ČVUT a MFF UK v Praze. Věnuje se matematicko-fyzikálním metodám počítačové bezpečnosti. Jeho práce pomohla také zlepšit několik celosvětových standardů, konkrétně protokol TLS, platební schéma EMV, bezdrátový standard Bluetooth a radionavigační systémy GNSS. Je hlavním kryptologem kompetenčního centra skupiny Raiffeisen Bank International.

  Zpět...