Předmět Složitost pro kryptografii (NMMB405)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NMMB405 - Složitost pro kryptografii, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).

Materiál	Typ	Datum	Počet stažení

Sylabus

Motivační příklady kryptografických úkolů (kódování s tajným klíčem, digitální podpisy). Klasický přístup (t.informace) a moderní přístup (t.výpočetní složitosti). Bijekce mezi slovy nad konečnou abecedou a přirozenými čísly. Jazyky a rozhodovací problémy. Turingovy stroje (TM). Varianty TM (více pásek, atd.). Rekursivní funkce (RF) a částečně rek. fce (PRF). Rekursivní množiny (R) a rek. vyčíslitelné množiny (RE). coRE množiny. Vety: R je průnik RE a coRE. Množina je RE právě když je oborem hodnot PRF a též právě když je projekcí rekursivní relace. Souvislost RE mnozin a NTM (nedeterministické TM). Kódování TM slovy. Universální TM. Halting problém (HALT) a 10.Hilbertův problém. HALT není rekursivní. Časová složitost TM a NTM. Polynomiální čas (p-cas), třída P. Třída NP (ekvivalence definic přes NTM a jako p-omezené projekce p-relací). Prostorová složitost, třídy L, NL a PSPACE. Obecné vztahy mezi časovou a prostorovou složitostí. s-t souvislost v orientovaných grafech (algoritmus s log^2(n) prostorovou složitostí). Savitchova věta: NSPACE(f) je část SPACE(O(f^2)). Immerman - Szelepscenyi věta: NSPACE(f) = coNSPACE(f) (bez dk.). Hierarchie tříd složitosti: SPACE(f) je vlastní část SPACE(g) (je-li f = o(g)), TIME(f) je vlastní část TIME(g) (je-li f log(f) = o(g)) (bez dk.). Třídy E a EXP. NP je část EXP. Výroková logika, booleovské obvody. p-preveditelnost. NP-uplné jazyky. Cookova věta. SAT, CIRCSAT, 3SAT, 3COLOR. P/poly: neuniformní p-čas. Charakterizace využívající pomocná slova a booleovské obvody, a jejich ekvivalence. Pravděpodobnostní algoritmy. Příklady: PIT (polynomial identity testing) a náhodné procházky po grafech (s-t souvislost; toto bez dk.). Třídy BPP, RP, ZPP. BPP je část EXP. Amplifikace pravděpodobnosti u RP. Pozn. o hypotéze P = BPP (Impagliazzo-Wigdersonova věta - bez dk.). Konečmě pravděpodobnostní prostory, jevy, náhodné veličiny. Očekávaná (střední) hodnota E(X). Lineárnost E(X). Příklad: pocet hlav v n hodech minci. Podmíněná pravděpodobnost, nezávislé jevy a náhodné veličiny. Markovova (dk.) a Chernoffova (bez dk.) nerovnost. Amplifikace pravděpodobností u BPP. BPP je v P/poly. Distribuce a jejich konstruovatelnost. Zanedbatelne a vyznamne funkce. Výpočetně nerozlišitelné distribuce, základní vlastnosti. Poly-mnoho nezávislých kopií. Pseudonáhodné distribuce. Pseudonáhodné generátory (PRNG) a souvislost s P vs. NP problémem. Vlastnosti PRNG a důsledky jejich existence: polynomiálni prodloužení, derandomizace BPP do sub-exp.času a pseudonáhodné funkce (bez dk.). Jednosměrné funkce (OWF). Slabé OWF a ekvivalence s původní definicí (bez dk.). PRNG je OWF. Př.: rozklad na prvočísla, diskrétní logaritmus, RSA, Rabinova funkce. Věta: Existence OWF implikuje existenci PRNG (bez dk.). Důkaz slabší verse: Existence OWP (permutace) implikuje existenci PRNG. Těžký bit (tvrdé jádro) OWF. Goldreich-Levinův algoritmus a věta (s dk.). Charakterizace PRNG pomocí nepředpověditelnosti bitu (bez dk.). Definice funkci těžkých v průměru. Interaktivní důkazové systémy. Třída IP, a pozorování: NP a coRP jsou částí IP. Shamirova věta: IP=PSPACE (bez důkazu). Důkaz speciálního případu: coNP je část IP. PCP důkazový systém. PCP věta (bez důkazu). Alternativní formulace: amplifikace minimálního počtu nesplněných klausulí v 3CNF formulích. Důkaz ekvivalence obou formulací. Idea aplikace: ne-aproximovatelnost optimalizačních NP-uplnych úloh. Zero-knowledge (důkazové systémy s nulovou znalostí). Varianty: perfektní (PZK), statistická (SZK) a výpočetní (CZK). PZK protokoly pro grafový izomorfismus a neizomorfismus. CZK protokol pro všechny NP množiny (za předpokladu existence OWF): idea konstrukce CZK protokolu pro 3COLOR.

Literatura

Cormen, Leiserson, Rivest : Introduction to algorithms, Mc Graw Hill 1990; Garey, Johnson : Computers and intractability - a guide to the theory of NP-completeness, W.H.Freeman 1978; Aho, Hopcroft, Ullman: The design and analysis of computer algorithms, Addison-Wesley 1974, Oded Goldreich: Foundations of cryptography, Cambridge University Press 2001 Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994 literatura na webu: viz http://www.math.cas.cz/~krajicek/crypto.html

Garant

doc. Štěpán Holub, Ph.D.Michael Pinsker, dipl. ing.