„Základní výzkum mívá před soukromou sférou často velký náskok a může otevírat zajímavé aplikace,“ říká teoretický informatik Pavel Hubáček a čerstvý laureát výroční Ceny Nadačního fondu Bernarda Bolzana.
Na Matfyzu vystudoval matematiku pro informační bezpečnost, na dánské Aarhus University informatiku. Badatelské zkušenosti sbíral na prestižních vědeckých institucích, jako je třeba izraelský Weizmannův institut věd. Před pěti lety se Pavel Hubáček vrátil zpátky na Matfyz, kde se věnuje studiu problémů z oblasti kryptografie a výpočetní složitosti. Jeho snem je proměnit Česko v kryptografickou velmoc.
Pohybujete se v rámci výzkumu výhradně na teoretické úrovni, anebo vás inspiruje také praxe?
Jelikož je můj výzkum na pomezí výpočetní složitosti a kryptografie, často se dostávám k otázkám motivovaným praktickými aplikacemi kryptografie. Teoretická informatika obecně často řeší otázky vyvstávající v praxi.
Jak jste se dostal k tématu svého výzkumu?
Na Matfyz jsem po střední škole přicházel studovat s úmyslem, že bych se rád věnoval kryptografii. Když jsem se pak na přednášce profesora Krajíčka poprvé dozvěděl o výpočetní složitosti a jejích aplikacích v kryptografii, byl jsem naprosto uchvácen. V průběhu doktorátu a postdoktorátu jsem potom postupně dospěl k tématům, kterým se věnuji dnes.
Čím vás jako studenta zaujaly šifry a kryptografie?
Zajímavým aspektem kryptografie, který mě původně zaujal, je fakt, že kryptograf by vlastně měl myslet jako potenciální útočník snažící se o prolomení bezpečnosti daného kryptosystému nebo protokolu. Musím také říct, že mě velice překvapilo, nakolik je dnes mezinárodní komunita v teoretické kryptografii extrémně vstřícným prostředím, které je otevřené novým myšlenkám a lidem. Zpětně si uvědomuji, že jsem měl ve volbě oboru v tomto ohledu velké štěstí.
Spojení „výpočetní složitost“ evokuje, že nejspíš půjde o dost komplikované téma. Jak byste ho přiblížil?
Máte pravdu, že to zní trochu neuchopitelně, ale rozhodně se nejedná o nějaké mysteriózní „zhmotňování tmy“. Výpočetní složitost se snaží zodpovědět docela základní otázky o limitech efektivních algoritmů, kde efektivitu můžeme měřit například počtem výpočetních kroků algoritmu nebo velikostí použitého diskového prostoru. Možná překvapivě jednou z hlavních otázek stále zůstává, zda vůbec existují výpočetní problémy, jež efektivně řešit nelze. V praxi se samozřejmě často setkáváme s výpočetními problémy, pro které efektivní algoritmy zatím neznáme. Dokázat však, že pro daný problém žádný efektivní algoritmus neexistuje, je řádově těžší problém.
Kryptografie má dlouhou historii. Jak se liší současná moderní kryptografie od té klasické?
Od antiky až do první poloviny 20. století fungoval návrh šifer a kryptografických schémat naprosto heuristicky. Šifra byla považovaná za bezpečnou do momentu, než ji někdo prolomil. Moderní kryptografie ale využívá diametrálně odlišný přístup, kdy se bezpečnost kryptografických schémat staví na předpokladu výpočetní obtížnosti nějakého známého problému. Specificky důkazy bezpečnosti kryptografických schémat zaručují, že pokud by se podařilo dané schéma efektivně prolomit, znamenalo by to nutně existenci efektivního algoritmu pro uvažovaný výpočetní problém. To nás dostává do takzvaně win-win situace, kdy buď máme bezpečné kryptografické schéma, nebo alespoň nový algoritmus pro problém, který jsme efektivně neuměli řešit. Metody výpočetní složitosti nám umožňují formalizovat tento typ argumentu. Kryptografie díky nim zažila na konci 20. století obrovský rozkvět, jenž byl zásadní pro bezpečnost internetu a dalších technologií, které dnes denně využíváme.
Cenu Nadačního fondu Bernarda Bolzana jste získal za soubor tří prací. Které si osobně ceníte nejvíc a proč?
Každá z těchto prací je pro mě důležitá trochu jinak. V té první se nám podařilo značně rozšířit aplikovatelnost již známých výsledků. Zpětně se ukazuje, že hlavním přínosem našeho článku byla definice nové třídy výpočetních problémů, která je velice robustní a kterou už ve svých článcích použili kolegové z několika výzkumných skupin po světě. Druhá z prací studuje limity těchto technik a vznikla ve spolupráci se studenty na Informatickém ústavu UK. Bylo pro nás docela frustrující, že výsledek, který jsme sice očekávali, se nám dlouho nedařilo dokázat. Díky značnému úsilí mé doktorandky Veroniky Králové se nám však podařilo přijít se zajímavým novým přístupem a formálním důkazem. Poslední práce pak ukazuje opravdu překvapivou spojitost mezi problémy v algoritmické teorii her a dokazatelnou bezpečností základních kryptografických protokolů. Je proto pro mě těžké vybrat jedinou z těchto prací, mám radost opravdu ze všech.
Co bylo cílem vaší práce?
Studuji výpočetní složitost problémů, pro které je existence řešení zaručena. Zdálo by se, že takové problémy lze vždy řešit efektivně, ale obecně to pravda není. V optimalizaci, kombinatorice, topologii a ekonomii vyvstávají takové výpočetní problémy velice často, a tak je důležité jejich výpočetní složitosti porozumět. Na začátku tohoto století se podařilo nalézt společnou strukturu pro mnoho těchto problémů a alespoň je klasifikovat do specializovaných tříd výpočetní složitosti. Tyto výsledky nám ale zatím neumožnily vysvětlit, proč pro ně zatím efektivní algoritmy neznáme. V mých pracích se snažíme ukázat, že tyto problémy jsou alespoň tak těžké jako problémy prolomení standardních kryptosystémů používaných v praxi. Pokud by se nám toto podařilo ukázat, tak by bylo zřejmé, že algoritmický průlom nelze v blízké době očekávat, protože řešení těchto problémů by nutně naráželo na stejná úskalí jako kryptoanalýza moderních šifer.
Co vás přimělo dát přednost vědecké dráze před soukromou IT sférou?
Vědecká práce má pro mě největší výhodu v relativní volnosti problémů, na kterých může člověk pracovat. Motivuje mě také to, že se můžu setkávat s nejnovějšími myšlenkami v mém oboru. V průběhu doktorátu jsem byl součástí skupiny, která se věnuje kryptografickým protokolům pro takzvané secure multi-party computation. Jedná se o kryptografické techniky, které umožňují odstranit v různých aplikacích nutnost zapojení důvěryhodné třetí strany. Teprve dnes, s odstupem zhruba deseti let, se objevují první opravdu úspěšné firmy, které tyto technologie používají ve svých produktech. Základní výzkum tak má často před IT sférou značný náskok a může otevírat zajímavé aplikace.
Studoval jste v Dánsku a také jste absolvoval několik stáží na univerzitách a výzkumných institucích v Rakousku, Izraeli a USA. Jak po této zkušenosti vnímáte českou vědu?
Jednoznačně vidím náš obrovský lidský potenciál. V České republice máme vynikající studijní obory, zapálené pedagogy, a hlavně studentky a studenty, kteří chtějí řešit problémy na hranici našeho poznání. To je optimální podhoubí pro skvělou vědu a věřím, že jsme na dobré cestě tento potenciál plně využít. Na naší fakultě je jasně viditelné úsilí o vybudování prostředí pro výzkum po vzoru úspěšných univerzit v zahraničí a například status doktorandů se nedávno rozhodně posunul správným směrem obdobným v západní Evropě. Jako hlavní výzvu vidím větší zapojení dobrých zahraničních studentů a vědců, kteří by krátkodobě, ale i dlouhodobě přicházeli obohatit naše výzkumné prostředí. Česká republika možná stále pořád působí pro cizince trochu exoticky a netransparentně, ale věřím, že je jen otázkou času, kdy se to díky našim výsledkům změní. Pokud budeme chápáni jako prestižní centrum excelentního výzkumu v zahraničí, bude se nám ve vědě dařit o to lépe.
Momentálně se znovu chystáte za hranice. Prozradíte, kam jedete?
V letním semestru budu na návštěvě na Bocconiho univerzitě v Miláně, kde spolupracuji na řešení projektu profesora Alona Rosena podpořeného prestižním ERC Advanced Grantem. Zabýváme se momentálně výpočetními problémy ve statistice v kontextu mého předchozího výzkumu. Rádi bychom také nalezli nové typy výpočetních problémů, které by bylo možné použít ke konstrukcím bezpečných kryptografických schémat.
Co je vaším cílem z dlouhodobějšího hlediska?
V kratším horizontu bych samozřejmě rád vyřešil některou z hlavních nezodpovězených otázek v mé specializaci. Takovou je například problém výpočetní složitost rozkladu přirozených čísel na součin prvočísel. Každé složené číslo lze rozložit na součin prvočísel, ale najít tento rozklad efektivně neumíme. Moderní kryptografie tohoto využívá a často konstruuje praktická schémata, jejichž prolomení je alespoň tak obtížné jako faktorizovat velká přirozená čísla na součin prvočísel. V kontextu výpočetní složitosti se nedávno podařilo ukázat, že mnoho význačných problémů ve výpočetní topologii je alespoň tak obtížných jako problém faktorizace. Já bych rád tyto výsledky rozšířil na další typy výpočetních problémů například z teorie her nebo kombinatoriky. Na této otázce mě fascinuje možná spojitost faktorizace jako základního problému v teorii čísel s jinými problémy ve zdánlivě nesouvisejících doménách.
V dlouhodobém horizontu bych rád přispěl k podpoře nové generace našich kryptografů, kteří třeba na čas odejdou získávat zkušenosti do zahraničí, ale budou se do České republiky vracet jako do jednoho z mnoha evropských center výzkumu v kryptografii. Dnešní věda převážně nestojí na jednotlivcích, ale těží z práce a podpory v rámci větších výzkumných skupin. Česká republika má mnoho významných skupin v různých oblastech teoretické informatiky. V Praze máme například skvělou školu kombinatoriky s dlouhou historií. V teoretické kryptografii zatím ale ve světě moc známí nejsme. Inspiruje mě v tomto příklad Ivana Damgårda z dánského Aarhusu. Když v roce 1988 končil doktorát, působil jako dánský kryptograf relativně osamoceně, a dnes je Dánsko jeho velkou zásluhou kryptografickou supervelmocí. Rád bych trochu pomohl k tomu, aby to šlo jednou říct i o České republice.
Nadační fond Bernarda Bolzana funguje od roku 1999 při Matematicko-fyzikální fakultě UK. K jeho úkolům patří mimo jiné nevýdělečná podpora vědecké a pedagogické činnosti na Univerzitě Karlově v oborech fyziky, matematiky a informatiky, rozšiřování úrovně experimentálních možností a teoretických postupů nebo zprostředkování širšího mezinárodního uplatnění vědeckých výsledků dosažených v daných oborech na UK.
Mohlo by vás také zajímat:
