PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Složitost pro kryptografii - NMMB405
Anglický název: Complexity for Cryptography
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní s.:4/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Garant: Mgr. Pavel Hubáček, Ph.D.
Třída: M Mgr. MMIB
M Mgr. MMIB > Povinné
Kategorizace předmětu: Matematika > Algebra
Neslučitelnost : NMIB002
Záměnnost : NMIB002
Anotace -
Poslední úprava: T_KA (14.05.2013)
Přednáška uvádí do pojmu výpočtové složitosti jednak v jeho nejzákladnějších aspektech (třídy P a NP), jednak v aspektech specifických pro potřeby kryptologie (pravděpodobnostní algoritmy, jednosměrné funkce, pseudonáhodné generátory, interaktivní důkazové systémy, důkazy s nulovou znalostí).
Podmínky zakončení předmětu
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (11.06.2019)

Zkouška má písemnou a ústní část.

Literatura -
Poslední úprava: T_KA (14.05.2013)

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

Požadavky ke zkoušce
Poslední úprava: doc. Mgr. Štěpán Holub, Ph.D. (12.10.2017)

Zkouška má písemnou a ústní část. Písemná část obsahuje nejzákladnější poznatky, jejichž dostatečná znalost je pro získání zkoušky nezbytná. Tyto poznatky jsou upřesněny v průběhu semestru a jsou zveřejněny na internetu. Ústní část je zaměřena na pokročilejší partie přednášky. Neúspěch u kterékoli z těchto částí znamená, že student(ka) musí opakovat obě části.

Sylabus -
Poslední úprava: T_KA (14.05.2013)
  • 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.

 
Univerzita Karlova | Informační systém UK