A key idea in modern cryptography is to try and design protocols that are secure against polynomial time adversaries (rather than all adversaries). This relaxed notion of security allows to implement many amazing tasks. (To give just one example we can consider two players playing poker over the phone without the help of a trusted party). In the course we will develop the basic machinery that allows such protocols with emphasis on precise definitions and rigorous proofs.
This course complements the course "introduction to cryptography" and students are allowed (and encouraged) to take both courses.
Requirements:
See Syllabus.
In the end of the semester there will be an exam.
During the course I will sometimes present questions in class that you can think of and try to solve.
You can also take a look at the following assignment that was used in a course four years ago and try to solve relevant questions.
Course material:
Books:
Lecture notes:
Resources to study for exam:
· A home
assignment given 4 years ago. I recommend that you try and solve the
exercises while going over the material.
· Here are some exams from 2 years
ago. Moed a, Moed b. Important
disclaimer: As I said in class, these do not necessarily represent the exam of
this year.
· Here are more exams from 2012: Moed a, Moed b.
Lectures:
1. Lecture 1: See Vadhan's lectures 1,3 (you may also want to go over lecture 2 which is a review of probability theory).
a. A story about three cryptographic tasks (symmetric encryption, public key encryption, coin tossing over the phone).
b. Symmetric encryption. How to define security? Shannon Secrecy and Perfect Indistinguishability.
c. Examples of some encryption schemes, and proof that OTP has Perfect Indistinguishability.
d. Shannon's theorem and the breakthrough idea of security against efficient adversaries.
2. Lecture 2: See Vadhan's lectures 3,5.
a. Proved: Perfect indistinguishability iff Shannon secrecy (see proof).
b. Proved Shannon's theorem.
c. Defined and discussed non-uniform algorithms and their relationship to software (TMs) and hardware (Boolean circuits).
d. Defined and discussed encryption with statistical and computational indistinguishability for both concrete and asymptotic setups.
3. Lecture 3: See Vadhan's lectures 6,7.
a. Defined semantic security and showed that computational indistinguishability implies semantic security.
b. Defined pseudorandom generators.
c. Existence of pseudorandom generators implies P<>NP.
d. Pseudorandom generators give encryption with short keys and computational indistinguishability.
e. Defined one way functions and stated theorem that one-way functions => pseudorandom generators => encryption.
4. Lecture 4: See Lindell's lecture 3.
a. Discussed candidate one-way functions, the notion of weak one-way function, and that weak OWF imply OWF (no proof).
b. Showed that length preserving OWF is implied by OWF. Emphasis on the method of proof (proof by reduction).
c. Defined hard-core bits.
d. Showed that if OWFs exist then there exist a OWF for which for all j, b(x)=x_j is not a hard-core bit. (Construction g(x,i)=(f(x),i,x_i)).
e. Showed that using a OWP with a hardcore bit, two players who don't trust eachother can toss a coin over the phone.
f. Stated the Goldreich-Levin Theorem and started with proof.
5. Lecture 5:
a. We showed that if f is a OWP then (X,f(X)) is indistinguishable from uniform. (In fact, even if f is a OWF then (X,f(X)) is indistinguishable from (X,U) but in this case f(X) can look very different from uniform as we observed).
b. This gives a PRG which stretches n bits to n+1 bits (and we discussed potential approaches to try and improve).
c. We proved that if G is a poly-time computable function stretching n bits to m bits, and if the output disytribution G(U_n)=Z_1,..,Z_m has the property that any poly-time prediction algorithm has negligible advantage then G is a pseudorandom generator.
d. We presented the Blum-Micali-Yao generator (based on the existence of OWP), and proved that it has the property above. More precisely, we proved that if there is a poly-time prediction algorithm then one can break the hard bit of the OWP.
6. Lecture 6+7: Pseudorandom functions (See Haitner's lecture 5).
a. Defined oracle Turing machines and pseudorandom functions.
b. Showed how to use pseudorandom functions to implement stateless encryption.
c. Constructed PRFs from PRGs (the GGM construction).
7. Lecture 8: Zero Knowledge
a. Interactive proofs and relation to NP (NP is what can be proven by deterministic provers).
b. An interactive proof for graph non-isomorphism (requires honest prover to be able to solve instances).
c. The notion of honest verifier zero knowledge.
d. The protocol for graph non-isopmorphism is honest verifier zero knowledge. However, a cheating verifier may be able to learn new information.
e. The notion of Zero knowledge.
f. A protocol for graph isomorphism.
8. Lecture 9+10: Zero Knowledge for NP
a. Commitment schemes. Definition and construction from OWP.
b. A protocol for 3-Coloring.
c. Cut and choose and a protocol for Hamiltonicity.
9. Lecture 11: Zero Knwoledge proofs of knowledge
a. Authentication.
b. The notion of POK.
c. A zero-knowledge proof of knowledge for NP.
d. Zero knowledge proof that you know x when the verifier holds f(x) (for a OWF f).
10. Lecture 12: Secure Multi-party Computation: See Lindell's lecture 13.
a. I gave an informal overview to the area. Main points are:
b. Definition using simulation and ideal setup with a trusted party.
c. A protocol for 2-party computation against semi-honest adversaries based on oblivious transfer.
d. Compilation of protocols against semi-honest parties into protocols against malicious parties.