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í).
Poslední úprava: T_KA (14.05.2013)
The course gives an introduction into computational complexity, both basic topics (classes P and NP) and topics of special interest for cryptography
(probabilistic algorithms, one way functions, pseudorandom number generators, interactive proofs, zero-knowledge proofs).
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.
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (28.10.2019)
Students have to pass final test and oral exam.
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
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
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.
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (28.10.2019)
Students have to pass final test and oral exam. The requirements for the exam correspond to what has been done during lectures.
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.
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.
Poslední úprava: T_KA (14.05.2013)
Motivating examples of cryptographic tasks (private key cryptography,digital signatures). Classical approach (th. of information) and modern approach (computational complexity th.).
Bijection between words over a finite alphabet and natural numbers. Languages and decision problems. Turing machines (TM). Variants of TM (more tapes, etc.).
Recursive function (RF) a partial recursive functions (PRF). Recursive sets (R) and recursively enumerable sets (RE). coRE sets.
Thms: R is the intersection of RE and coRE. A set is RE iff it is the range of a PRF iff it is a projection of a recursive relation. A link between RE sets and NTMs (non-deterministic TM).
Coding of TMs by words. Universal TM. Halting problem (HALT) and 10th Hilbert's problem. HALT is not recursive.
Time complexity of TM and NTM. Polynomial time (p-time), class P. Class NP (the equivalence of definitions via NTM and as p-bounded projections of p-relations).
Space complexity, classes L, NL and PSPACE. General relations between time and space complexity.
s-t connectivity in directed graphs (the idea of an algorithm using quadratic-log space). Savitch thm: NSPACE(f) is included in SPACE(O(f^2)). Immerman - Szelepscenyi thm: NSPACE(f) = coNSPACE(f) (without prf.).
The hierarchy of complexity classes: SPACE(f) is a proper subclass of SPACE(g), if f = o(g), TIME(f) is a proper subclass of TIME(g), if log(f) = o(g) (without prf.). Classes E and EXP. NP is included in EXP.
P/poly: non-uniform p-time. Characterisations using advice words and via circuits, and their equivalence.
Probabilistic algorithms. Examples: PIT (polynomial identity testing) and random walks on graphs (s-t connectivity; without prf.).
Classes BPP, RP, ZPP. BPP is included in EXP. Amplification of probability in RP.
Remark on the hypothesis that P = BPP (Impagliazzo-Wigderson thm - without prf.).
Finite probabilistic spaces, events, random variables. Expected value E(X). Linearity of E(X). Example: The number of heads in n coin tosses.
Conditional probability, independent events and random variables. Markov's inequality (with prf.) and Chernoff's inequality (without prf.).
Probability amplification in BPP. BPP is included in P/poly.
Distributions and their computability. Negligible functions. Computationally indistinguishable distributions, basic properties. Poly-many independent copies.
Pseudo-random distributions. Pseudo-random generators (PRNG) and link to the P vs. NP problem.
Properties of PRNGs and consequences of their existence: Polynomial extendability, derandomization of BPP in sub-exponential time and pseudo-random functions (without prf.).
One-way functions (OWF). Weak OWF and the equivalence with the definition of OWF (without prf.). A PRNG is a OWF. Examples: Prime factorization, discrete logarithm, RSA, Rabin's function.
Thm.: The existence of a OWF implies the existence of a PRNG (without prf.). A proof of weaker statement: The existence of a OWP (permutation) implies the existence of a PRNG. Hard bit of OWF.
Goldreich-Levin's algorithm and theorem (with prf.).
The characterization of PRNGs using bit unpredictability (without prf.). The definition of functions hard on average.
Interactive proof systems. Class IP and observations: NP and coRP are included in IP. Shamir thm.: IP=PSPACE (without prf.). A proof of a special case: coNP is included in IP.
PCP proof system. PCP thm. (without prf.). Alternative formulation: Amplification of the minimal number of unsatisfied clauses in 3CNF formulas. A proof of the equivalence of the two formulations. An idea of an application: Non-approximability of optimization problems.
Zero-knowledge proof systems. Variants: Perfect (PZK), statistical (SZK) and computational (CZK). PZK protocols for graph isomorphism and non-izomorphism. CZK protocol for all NP sets (assuming the existence of OWF): The idea of the construction of a CZK protocol for 3COLOR.