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).
Poslední úprava: T_KA (14.05.2013)
Podmínky zakončení předmětu -
Zkouška má písemnou a ústní část.
Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (11.06.2019)
Students have to pass final test and oral exam.
Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (28.10.2019)
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
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
Poslední úprava: T_KA (14.05.2013)
Požadavky ke zkoušce -
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: Holub Štěpán, doc. Mgr., Ph.D. et Ph.D. (12.10.2017)
Students have to pass final test and oral exam. The requirements for the exam correspond to what has been done during lectures.
Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (28.10.2019)
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.
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.
