Foundations of Cryptography (Spring 2008)

Error correcting codes are combinatorial objects that allow sending and recovering messages transmitted through noisy channels. Error correcting codes have many applications in both theory and practice in computer science. This class gives an

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:

In the end of the semester there will be a home assignment. Following the home assignment, I may decide to conduct an oral exam (to make sure that students indeed prepared the solutions).

In addition during the semester I will give 2-3 exercises. The exercises are not mandatory and their purpose is for students to check that they follow the material.

Course material:

The material in the course is mostly covered in the following book (that is available in several copies in the library)

FOUNDATION OF CRYPTOGRAPHY by ODED GOLDREICH.

Some of the material can be found in lecture notes of a course by Yehuda Lindell from Bar-Ilan University.

Every week I will upload a (very brief) summary of the subjects that were covered.

Lecture 1 : Introduction

• The purpose of this lecture is to give a flavor of the ideas and methodology that will be used in the course.
• Playing poker over the phone (coin tossing protocols).
• Impossibility of coin tossing protocols.
• Idea: Design protocols that are secure against adversaries that run in polynomial time. (This means that in the very least we need to assume that NP is not equal to P).
• Bit commitment: A description of a physical implementation with boxes, locks and keys.
  • The protocol has two phases:
    • In commit phase the sender puts a bit b inside a box locks the box and sends the box to the receiver.
    • In Reveal phase the sender sends the key to the receiver who can see whether the key unlocks the box and what bit is inside.
  • Security guarantees:
    • Hiding: The receiver cannot know what is inside the box if he doesn't have the key.
    • Binding: The sender cannot affect the bit in the box after it was sent. (He cannot send different keys that will lead to different bits).
• Challenge: Implement bit commitment in the digital world.
• More preliminary challenge: Have a meaningful and not-contradictory formal definition of digital implementation of a bit commitment that is secure against efficient adversaries.
• The definition introduces several ideas:
  • Injecting randomness: It is not good to have the digital implementation m of the box to be a fixed function of the bit b. Instead the sender randomly picks a string r of length n and computes a function commit(r,b) which gives him the "box" m and the "key" k. (This is needed as otherwise the receiver can open the box by computing commitments of both zero and one, and only one of them can be m by the binding property). (This also means that a brute force attack that tries all r breaks the commitment, but we cannot hope to avoid this).
  • The uncertainty of the receiver about the value in the box is defined over the probability space of choosing r: We require that every efficient machine R that gets m and tries to compute b can only succeed with probability at most 1/2+\epsilon (where the probability is over r).
  • The binding property makes sense even against unlimited adversaries: We require that there do not exist k1,k2 such that reveal(m,k1)=0 and reveal (m,k2)=1.
  • The reveal function gets a "box" m and a "key" k and answers one of three values:
    • "1" meaning that the bit in the box is 1.
    • "0" meaning that the bit in the box is 0.
    • "?" meaning that the key does not open the box.
  • This avoids the attack of running reveal(m,arbitrary key) and using the hiding property.
• In the end we developed a formal definition that seems meaningful and not contradictory.

Lecture 2 : One-way functions

• Formal definition of bit-commitment schemes.
• Observation: No such schemes exist if P=NP.
• Hope: construct such schemes based on the assumption P<>NP (major open problem).
• We do not know how to approach this problem because of two issues:
  • Average-case complexity: Maybe it is easy to solve NP problems "on average".
  • Generating witnesses: Even if it is hard to solve NP problems on average, can we generate hard inputs on which we have a witness.
• The notion of one-way functions: A function on f is one way if |f(x)|=|x| (that is f is length preserving) and:
  • Efficiency: There is a polynomial time algorithm which computes f.
  • Hardness: It is hard to invert f. For every poly-time prob. machine A and for every constant c we consider the experiment in which a randomx of length n is chosen and we check whether A(f(x)) is an input x' such that f(x')=f(x). It is requires that the probability of this event is smaller than n^{-c} for any sufficiently large n.
• Candidates: multiplication.
• The notion of weak one-way function.
• Theorem: Weak one-way functions imply strong one-way functions (we did not give a proof).

Lecture 3 : Hard core bits and the Goldreich-Levin theorem

• Even if f is one way it may be possible to compute the first bit of x when given f(x).
• Example: define g(x,r)=f(x),r.
  • Claim: if f is one way then g is one way.
  • Technique: proof by reduction: If g is not one-way then f is not one way.
  • Conclusion: It may be easy to predict many of the bits of the input.
• Definition of hard-core bit.
• Theorem [Goldreich-Levin]: If f is one-way then the function b(x,r)=<x,r>mod 2 is a hard-core bit for g.
• High level idea of the proof. 
  • We assume b is not good and get a machine A' that predicts b(x,r) when given f(x),r.
  • Things are simple if A' succeeds with prob 1. In that case A'(f(x),r) is always b(x,r). In particular setting e^i to be the vector with a single 1 at the i'th index we have that A'(f(x),e^i)=b(x,e^i)=x_i and we can indeed find x.
  • Things are still not too problematic if A' succeeds with prob 3/4+1/n^c. In that case we define G to be the set of x's for which A' succeeds with probability at least 3/4+1/2n^c (where the probability is over the choice of r and random coins). We first show that G is not tiny (that is that the probability that x lands in x is noticeable and at least 1/2n^c). For a fixed i we consider the algorithm that given f(x) chooses at random a string a and runs A'(f(x),r) and A'(f(x),r^i) where r^i is the string inb which the i'th bit is flipped. We showed that for an x in G, the probability that A'(f(x),r)=b(x,r) is at least 1/2+1/2n^c and we have the same probability for A'(f(x),r^i)=b(x,r^i). It is important to note that the two events are not independent. Still, by a union bound over the complements of the events we can deduce that both events happen simultaneously with prob 1/2+1/n^c and if we xor the outputs we get x_i. By repeating this procedure many times with independent random choices we can improve the probability to 1-1/2n. If we repeat this for all i we invert with probability at least 1/2n^c times 1-1/n which is noticeable.

Lecture 4 : Hard core bits and the Goldreich-Levin theorem (continued)

• We finished up the proof. The details can be found both at Oded Goldreich's book and at Yehuda Lindell's lecture notes.

Lecture 5 : Statistical Indistinguishability, Computational Indistinguishability and Pseudorandomness

• The notion of an ensemble.
• Definitions of statistical and computational indistinguishability.
• Pseudorandom ensembles and pseudorandom generators.
• Pseudorandom generators imply OWFs
• Prediction tests and the hybrid argument.

Lecture 6 : A construction of PRGs from any OWP.

• Details can be found in the references.

Lecture 7 : Interactive proof systems and ZK

• Definitions of a proof system and transcript (P,V)(x)
• Randomized proof systems
• Completenss and soundness
• Example: Graph Isomorphism
• The idea of ZK and the simulation paradigm

Lecture 8 : A ZK proof for every language in NP

• The simulation paradigm. Precise definition of ZK.
• Meaning of ZK.
• Thm: assuming Bit-commitment and language in NP has a zero knowledge protocol
• Proof using Graph Hamiltonicity.
• Is ZK sufficient for authentication? The need for POK.

Lecture 9 : More on ZK

• Auxiliary input ZK. What is it? Why is it necessary? Constructions from OWP that is secure against circuis/adversaries with advice.
• Sequential repetition and parallel repletion of ZK.
• The notion of POK.
• Application: authentication schemes.

Lecture 10 : Misc.

• Summary of course.
• Bit commitment from PRGs.
• The notion of secure function evaluation.
• The simulation paradigm: real vs. ideal. (we did not gave precise definitions as they are complicated).
• Malicious adversaries and honest but curious adversaries.
• Why ZK can be used to compile protocols secure against adversaries into protocols against malicious adversaries.(sketch)

Home assignment

The home assignment can be downloaded here. Any updates will appear below.

Updates: