Sylabus a literatura k prednasce

"Slozitost pro kryptografii", Jan Krajicek


Otazky ke zkousce.

Sylabus:

  • Priklady kryptografickych ukolu (kodovani s tajnym klicem, digitalni podpisy). Klasicky pristup (t.informace) a moderni pristup (t.vypocetni slozitosti).

  • Bijekce mezi slovy nad konecnou abecedou a prirozenymi cisly. Jazyky a rozhodovaci problemy. Turingovy stroje (TM). Varianty TM (vice pasek, atd.).

  • Rekursivni funkce (RF) a castecne rek. fce (PRF). Rekursivni mnoziny (R=Delta_1) a rek. vycislitelne mnoziny (RE = Sigma_1). coRE (= Pi_1) mnoziny.

  • Vety: R je prunik RE a coRE. Mnozina je RE prave kdyz je oborem hodnot PRF a tez prave kdyz je projekci rekursivni relace. Souvislost RE mnozin a NTM (nedeterministicke TM).

  • Kodovani TM slovy. Universalni TM. Halting problem (HALT) a 10.Hilbertuv problem. HALT neni rekursivni.

  • Casova slozitost TM a NTM. Polynomialni cas (p-cas), trida P. Trida NP (ekvivalence definic pres NTM a jako p-omezene projekce p-relaci).

  • Prostorova slozitost, tridy L, NL a PSPACE. Obecne vztahy mezi casovou a prostorovou slozitosti: TIME(f) je cast NTIME(f) je cast SPACE(f) je cast TIME(2^{O(f)}).

  • s-t souvislost v orientovanych grafech (algoritmus s log^2(n) prostorovou slozitosti). Savitchova veta: NSPACE(f) je cast SPACE(O(f^2)). Immerman - Szelepscenyi veta: NSPACE(f) = coNSPACE(f) (bez dk.).

  • Hierrarchie trid slozitosti: SPACE(f) je vlastni cast SPACE(g) (je-li f = o(g)),
    TIME(f) je vlastni cast TIME(g) (je-li f log(f) = o(g)) (bez dk.). Tridy E a EXP. NP je cast EXP.

  • Vyrokova logika, booleovske obvody.

  • p-preveditelnost. NP-uplne jazyky. Cookova veta. SAT, CIRCSAT, 3SAT, 3-obarvitelnost.

  • P/poly: neuniformni p-cas. Charakterizace vyuzivajici pomocna slova (advice) a booleovske obvody, a jejich ekvivalence.

  • Pravdepodobnostni algoritmy. Priklady: PIT (polynomial identity testing) a nahodne prochazky po grafech (s-t souvislost; toto bez dk.).

  • Tridy BPP, RP, ZPP. BPP je cast EXP. Amplifikace pravdepodobnosti u RP.
    Pozn. o hypoteze P = BPP (Impagliazzo-Wigdersonova veta - bez dk.).

  • Konecne pravdepodobnostni prostory, jevy, nahodne veliciny. Ocekavana (stredni) hodnota E(X). Linearnost E(X). Pr.: pocet hlav v n hodech minci.

  • Podminena pravdepodobnost, nezavisle jevy a nahodne veliciny. Markovova nerovnost (dk.) a Chernoffova (bez dk.).

  • Amplifikace pravdepodobnosti u BPP. BPP je v P/poly.

  • Distribuce a jejich konstruovatelnost. Zanedbatelne a vyznamne funkce. Vypocetne nerozlisitelne distribuce, zakladni vlastnosti. Poly-mnoho nezavislych kopii.

  • Pseudonahodne distribuce. Pseudonahodne generatory (PRNG) a souvislost s P vs. NP problemem.

  • Vlastnosti PRNG a dusledky jejich existence: polynomialni prodlouzeni, derandomizace BPP do sub-exp.casu a pseudonahodne funkce (bez dk.).

  • Jednosmerne funkce (OWF). Slabe OWF a ekvivalence s puvodni definici (bez dk.). PRNG je OWF. Pr.: rozklad na prvocisla, diskretni logaritmus, RSA, Rabinova funkce.

  • Veta: Existence OWF implikuje existenci PRNG (bez dk.). Dukaz slabsi verse: Existence OWP (permutace) implikuje existenci PRNG. Tezky bit (tvrde jadro) OWF.

  • Goldreich-Levinuv algoritmus a veta (s dk.).

  • Charakterizace PRNG pomoci nepredpoveditelnosti bitu (bez dk.). Definice funkci tezkych v prumeru.

  • Interaktivni dukazove systemy. Trida IP, a pozorovani: NP a coRP jsou casti IP. Shamirova veta: IP=PSPACE (bez dukazu). Dukaz specialniho pripadu: coNP je cast IP.

  • PCP dukazovy system. PCP veta (bez dukazu). Alternativni formulace: amplifikace minimalniho poctu nesplnenych klausuli v 3CNF formulich. Dukaz ekvivalence obou formulaci. Idea aplikace: ne-aproximovatelnost optimalizacnich NP-uplnych uloh.

  • Zero-knowledge (dukazove systemy s nulovou znalosti). Varianty: perfektni (PZK), statisticka (SZK) a vypocetni CZK). PZK protokoly pro grafovy izomorfismus a neizomorfismus. CZK protokol pro vsechny NP mnoziny (za predpokladu existence OWF): idea konstrukce CZK protokolu pro 3COLOR.

    Temata, ktera jsou probirana, je-li dost casu (ale nejsou zkousena):

  • Spodni odhady na velikost booleovskych obvodu: monotoni obvody pro kliku (jen formulace), obvody konstantni hloubky pro paritu (dukaz aproximacni metodou Razborov-Smolensky).

  • Komunikacni slozitost a Karchmer-Wigdersonova veta (dukaz). Priklad: parita.

  • "Natural proofs" Razborova a Rudiche a veta o jejich neexistenci (s dk.).

  • Efektivni interpolace pro rezoluci. Tezko oddelitelne disjunktni NP pary a tezky bit.

  • Extraktory a expandery.

    Literatura na webu:

  • skripta Stepana Holuba (obsahuji jen cast probirane latky)

  • Boaz Barak's courses (complexity theory and cryptography)

  • a draft of Sanjeev Arora a Boaz Barak's book "Complexity Theory: A Modern Approach".

  • Rudich-Blum course (graduate course in computational complexity)

  • Jonathan Katz's course (complexity theory)

  • a draft of Oded Goldreich's book "Foundations of Cryptography".

  • a draft of Oded Goldreich's book "Computational Complexity: A Conceptual perspective".

  • Bellare-Rogaway course ("Introduction to Modern Cryptogtaphy")

  • Bellare-Goldwasser course (lecture notes on cryptography)