SubjectsSubjects(version: 806)
Course, academic year 2017/2018
   Login via CAS
Complexity for Cryptography - NMMB405
Czech title: Složitost pro kryptografii
Guaranteed by: Department of Algebra (32-KA)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:4/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: English, Czech
Teaching methods: full-time
Guarantor: doc. Štěpán Holub, Ph.D.
Class: M Mgr. MMIB
M Mgr. MMIB > Povinné
Classification: Mathematics > Algebra
Incompatibility : NMIB002
Interchangeability : NMIB002
Annotation -
Last update: 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).
Literature -
Last update: 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

Syllabus -
Last update: 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.
  • Propositional logic, boolean circuits.
  • p-reducibility. NP-complete languages. Cook's thm. SAT, CIRCSAT, 3SAT, 3COLOR.
  • 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.

Charles University | Information system of Charles University |