COMP647 Advanced Cryptography

Objectives: Cryptography has evolved significantly since the introduction of one-way functions for public-key cryptography and digital signatures in the 1970's. A number of new interests were born from relations between cryptography and complexity theory: interactive proofs, zero-knowledge protocols, multi-party computing, etc. This year, the orientation of the course will follow the guide-lines of the book I am preparing with Simon Pierre Desrosiers about two-party secure computations. We will use a simplified methodology to develop the tools sufficient to accomplish securily all two-party computations involvind some secret data. The main tools are Bit Commitment and Oblivious Transfer. Our purpose is to bring the student to understanding of the current issues in the fast evolving world of cryptography.

Winter 2016 Course outline:

Interactive Proof systems. (GMR89)
Arthur-Merlin games. (BM88)
AM=IP[k], k>=2. (GS)
IP = PSPACE. (Shamir)
Zero-Knowledge proofs. (GMR)
Bit commitment, computational implementations. (Commit, BCC)
Bit Commitment from PRBGs (and one-way functions). (HILL, Naor)
Zero-Knowledge arguments. (BCC)
Bit Commitment from One-way permutations. (NOVY)
Bit Commitment from regular One-way functions. (HKKM)
Bit Commitment from Cryptographic hash functions. (HM)
Zero-Knowledge arguments from One-way functions. (NOV06)
Zero-Knowledge and Soundness are symmetric for NP-languages. (OV06)
IP in Zero-Knowledge. (my way, IY88, BGGHKRW89)
MA in polytime-prover Zero-Knowledge. (my way, BCC88, BD89)
Multi-prover Interactive Proofs. (BGKW88,CSST11)
MIP = NEXP. (BFL91)
MIP in ZK. (BGKW88, CY16)
Secure Two-Party Computations.
Oblivious Transfer.
Committed Oblivious Transfer.
Oblivious Transfer from trapdoor one-way permutations.
Arbitray Two-Party Secure Computations from COT.
OT from various channels. Open problems.

Evaluation:
Evaluation is based on participation, 3 homeworks and one oral presentation. No exam is to be anticipated.