Quantum Information Processing with Weak Sources of Randomness

Abstract

Uniformna nahodnosť je cenný výpocetný zdroj s uplatnenim napriklad pri navrhu algoritmov, v kryptografii alebo pri studiu komunikacnej zložitosti. Nahodnostne algoritmy su casto rýchlejsie a jednoduchsie na navrh a analýzu ako ich deterministicke naprotivky. Užitocnosť uniformnej nahodnosti je zrejma aj zo skutocnosti, že pristup komunikujucich stran k uniformne distribuovaým bitom patri k jedným z najdoležitejsich predpokladov pri dokazoch bezpecnosti mnohých kryptografických protokolov. Nanesťastie, výzkumnikom a inžinierom sa zatiaľ nepodarilo postaviť zariadenie, ktore by produkovalo pravu uniformnu nahodnosť. Aj v pripade, že zariadenie je založene na teorii, ktora umožňuje produkciu pravej nahodnosti, napriklad zariadenie založene na merani kvantových stavov, technologicke nedokonalosti možu viesť k výrazným odchýlkam skutocnej implementacie od idealnej funkcnosti. Tato skutocnosť vyvolava doležitu otazku, ci je „slaba nahodnosť“, t. j. neuniformne nahodne procesy, použiteľna ako zdroj pre výpocetne a kryptograficke ulohy. Analýza kryptografických uloh za predpokladu slabej nahodnosti je obzlasť doležita. Dovodom je skutocnosť, že mnohe kryptograficke systemy priamo využivaju uniformne distribuovane nahodne bity – tajný kľuc – na utajenie urcitých informacii. Ak predpokladame, že utocnik je schopný ziskať nejake informacie o tajnom kľuci, je potrebne analyzovať daný kryptografický protokol s kľucom distribuovaným podľa pravdepodobnosti podminenej utocnikovou znalosťou. Tato distribucia kľuca sa z pohľadu utocnika može výrazne lisiť od uniformnej. Ako vidno, utocnikova znalosť može zmeniť uniformnu nahodnosť na slabu nahodnosť. Vo výsledku su slabe zdroje nahodnosti vhodným formalizmom pre modelovanie uniku informacii o tajnom kľuci. Ťažkosti ktore vznikaju pri použivani slabých zdrojov su dobre zname v oblasti klasickeho spracovania informacie. Existuju problemy, ktore sa daju riesiť aj pomocou relativne slabých zdrojov, ale aj problemy, ktore sa vyriesiť nedaju ak mame k dispozicii iba nahodnosť ktora je co i len mierne odlisna od uniformnej. V sucasnosti vsak neexistuje takato analýza pre kvantový naprotivok klasickeho spracovania informacie – kvantove spracovanie informacie (Quantum Information Processing - QIP). Tento fakt je v celku prekvapivý, pretože klasicka nahodnosť hra významnu rolu aj v ulohach kvantoveho spracovania informacie. Možným dovodom tohoto nedostatku výsledkov je pohľad, podľa ktoreho je v QIP klasicka nahodnosť voľný a vždypritomný výpocetný zdroj. V praxi sa vsak uniformna nahodnosť neda ziskať ani pomocou zariadeni založených na kvantových meraniach. Navyse, scenar v ktorom sa utocnik dozvie nejaku klasicku informaciu o tajnom kľuci zostava platný a zaujimavý aj v oblasti kvantoveho spracovania informacie. Hlavným zameranim navrhovanej dizertacnej prace je analýza roznych aplikacii kvantoveho spracovania informacie s predpokladom použitia slabej nahodnosti. Prvou ulohou prace je analyzovať sifrovanie klasickej informacie pomocou kľuca distribuovaneho podľa slabeho zdroja nahodnosti, za použitia kvantových sifrovacich sprav. Hlavným cieľom je dokazať, že použitie kvantových sprav ponuka vyssiu uroveň zabezpecenia v porovnani s klasickými spravami. Druhou ulohou je analýza vplyvu slabej nahodnosti na bezpecnosť protokolov kvantovej distribucie kľuca. Hlavným cieľom je najdenie horneho odhadu na množstvo informacie, ktore je utocnik schopný ziskať ak sa v protokoloch použiva slaba namiesto uniformnej nahodnosti. Poslednou ulohou je analýza privatnych kvantových kanalov (private quantum channels) a ich implement