Announcements

(4/15) project presentation schedule has been posted.

Class-related News

• Diffie + Hellman win Turing Award: link
• First zero-knowledge contingent payment on Bitcoin network: link

General Information

Administrative Notes: This course can be used as a theory elective for the PhD program in computer science, as a track elective for MS students in the "Foundations of Computer Science" track or the "Computer Security" track, or as a track elective for undergraduates in the "Foundations" track. COMS E-6261 Advanced Cryptography focuses around a different topic, possibly with a different format, every time it is taught. The class can be repeated for credit.

Prerequisites

Course Description

This theme could easily span several semesters, so we will not try to give an exhaustive treatment. Instead, we will study in depth a few results in different areas, and give an overview and pointers to other directions and applications. The specific topic selection will be biased by the interests of the instructor and the students taking the class, and will range from classic results from the 80s to cutting edge research papers. In all cases, we will take a rigorous theoretical approach (including precise definitions, theorem statements, and proofs). Example topics may include: zero knowledge proofs, secret sharing, secure multiparty computation, randomized encoding, circuit complexity of cryptographic primitives, barriers to basing cryptography on P not equal NP, and many other options.

Lecture Summaries

• Lecture 1 (1/19): Intro and OWF. Introduction to the class, crypto landscape, motivation and overview. Definitions of P, NP, BPP, P/Poly. Definition of a one way function (OWF). Discussed (informally) the OWF guarantee and why it's not sufficient for encryption. Mentioned that if OWF exist, then there are OWF that reveal half of their input bits. Mentioned that if OWF exist, then there is a OWF where every bit of input can be efficiently predicted with non-negligible probability (see HW1).
• Lecture 2 (1/26): OWF, Hard-Core Predicates, Commitments. We considered variations on the OWF definition, where the advantage of any efficient adversary is required to be zero (not achievable), negligible (this is the default -- strong -- OWF), noticably less than 1 (weak OWF), or less than 1 (worst-case OWF).
  We claimed that worst-case OWF exists if and only if NP is not a subset of BPP (we did not show the proof). These worst case OWF are not directly useful for cryptographic constructions, as those typically require average case hardness; whether or not worst case OWF can be used for obtaining average case hardness (i.e., can we base OWF on NP hardness) is a long standing and very important open problem.
  We also claimed that the existence of OWF is equivalent to the existence of weak OWF, and briefly outlined the proof (amplification construction). Discussed multiplication over the integers as an example for a weak OWF under the factoring assumption.
  Defined collections (or families) of OWF, and claimed that their existence is equivalent to the existence of OWF (outlined the construction). Also mentioned that the existence of length preserving OWF is equivalent to the existence of OWF However, one-way permutations (OWP) or injective OWF are not known to be equivalent to OWF (in fact, there's evidence that they may not be). Also, the transformation from a collection of OWF to a single OWF does not necessarily preserve injectiveness.
  We defined a universal OWF, claiming that if any OWF exist, this specific function is a OWF. The proof (which we did not show -- see HW1) is based on the fact that if any OWF exists, there is a OWF that runs in quadratic time.
  We defined hard-core predicates, and stated the Goldreich-Levin theorem, showing that if any OWF exists, then a simple tweak yields a OWF with a hard-core bit. Very briefly discussed the use of hard-core bits in the creation of PRG from OWP.
  We defined perfectly binding, computationally hiding commitment schemes, focusing for simplicity on the case of non-interactive, single bit commitment (committing to a string can be done by committing to each bit separately). We then proved that such a commitment scheme can be constructed from any injective OWF (and mentioned that an interactive version can be achieved from any OWF). We finished by informally discussing how commitment can be used for coin flipping over the phone, showing Blum's protocol, and mentioned the fairness issue with this protocol.
  Reading: most definitions and theorems in the first two lectures followed the presentation of [Gold] (Goldreich's textbook) in the relevant parts of the first two chapters (mostly chapter 2, for OWF and hard-core predicates). Commitments are defined and discussed in [Gol, 4.4.1]. For universal OWF, I recommend the proof in [Ps] (Pass-shelat textbook), chapter 2.13.
• Lecture 3 (2/2): IP and PZK. We discussed the general notion of proofs, and defined an interactive proof system for a language L (default definition with completeness 2/3 and soundness 1/3), and the corresponding class IP. Stated that this, as well as any parameters such that the gap between completeness and soundness is noticable, is equivalent to negligible error interacitve proof. We did not prove this formally, but discussed that sequential repetition (with independent randomness) brings the completeness and soundness errors down (this is not hard to prove). We also discussed the (standard) augmentation of the definition with auxiliary inputs.
  Showed examples: BPP and NP are both subsets of IP (ignoring the prover, or having the prover just send a single string, respectively). But IP contains languages that are not believed to be in NP, such as GNI --graph-non-isomorphism (we showed the proof system, as well as a motivating example proving to a color blind person that two cards are of different colors). In fact, IP=PSPACE (we just stated this), which is believed to be significantly bigger than NP. However, we will focus on proofs for NP languages, where the prover can be efficient (given a witness as an auxiliary input). We will use interaction (and allow a small error) in order to obtain ZK proofs, as we shall see.
  Some discussion and motivation for zero knowledge and its definition through simulation (for every verifier V*, there is a simulator that can simulate the view / output of V*, without the help of P). We defined perfect ZK property for a proof system and the corresponding class PZK. Showed that GI -- graph-isomorphism -- has a perfect ZK proof system. Revisited the GNI example, and discussed the fact that the protocol that we saw before is a honest-verifier ZK proof system, but not ZK for a cheating verifier.
  Ended class with a riddle: showed a proof system for L={0,1}* (this language has a trivial zero knowledge proof system, but we showed a convoluted proof system - see email), and asked whether or not this is a ZK proof system.
  Readings: [Gold] chapter 4 is very detailed (much more so than we were/will be in class), and I recommend it. Some of the other textbooks should also have a shortened exposition of ZK.
• Lecture 4 (2/11): ZK Examples, ZK for all NP. Definitions of PZK, SZK, CZK and some discussion on their believed relationships. Comments: by default, "ZK" refers to computational zero knowledge; Definitions are with auxiliary inputs; mentioned black-box zero knowledge simulation (all the examples we see here are indeed black-box ZK). Example: perfect ZK proof system with completeness 1 and soundness 1/2 for the language of DH tuples. Short discussion on reducing soundness error while maintaining ZK via sequential composition. Discussed the solution to last week's riddle, and concluded that it is essential to include the internal coins as part of the verifiers view. If OWF exist, then every language in NP has a ZK proof system: showed why proving this for one NP complete language is sufficient; showed a ZK proof system for graph 3-colorability, using perfectly binding commitment (can be achieved from OWF), with completeness 1 and soundness 1- 1/|E| (where |E| is the number of edges).
  Reading: As with last lecture, this material is also in Goldreich's chapter 4.
• Lecture 5 (2/16): Wrapping Up ZK. See the slides presented. There were some remraks and explanations on the board, but overall this was a high level and informal lecture summing up ZK and hinting at some other very important results and directions we won't have the time to go into.
• Lecture 6 (2/23): Guest Lecture by Siyao Guo: Cryptographic Negation Complexity. Boolean circuits (size, depth, AND/OR/NOT gates). Monotone circuits (circuits without NOT gates). Monotone functions (functions computed by monotone circuits; value doesn't decrease when flipping 0 to 1 in input coordinates; alternating number is at most 1). Examples: AND, OR, many graph properties (containing a clique) are monotone. Parity function is not monotone.
  Negation complexity of cryptography: See the slides.
  Monotone OWF exists: Middle slice of OWF + Hardness Amplification from weak to strong. No monotone OWP: Output is a permutation of input coordinates (tool: Talagrand's inequality). No logn - Omega(1) PRF: fix arbitrary chain and checking the alternating number (tool: Markov's theorem). Two more tools: decomposition (xor of 2^t monotone functions) and t level selection tree.
  Reading: Based on this paper from TCC 2015.
• Lecture 7 (3/1): Secure Computation: introduction. Motivated secure computation and various requirements from the definition, via simple examples for computing the sum/average (in a cycle with first party adding randomness, or via additive sharing of inputs of every party). Introduced the real/ideal paradigm for defining secure computation, and its advantages over defining specific properties directly (privacy, correctness, independence of inputs, fairness, etc). For the semi-honest (passive) case, correctness and privacy are sufficient, and the definition is equivalent to showing a simulator that, for any given inputs and outputs of corrupted parties, can simulate their view, so that the joint distribution of the simulator's output and the honest parties' output are close to the joint distribution of the adversary's output and the honest parties' output in the real execution. For the malicious case, "inputs" of the malicious parties in the real execution may not be well defined; Still, the ideal-real model definition captures security in the malicious model as well: for every adversary A in real world, there exists an adversary (simulator) S in the ideal world, such that the joint output of A and honest parties is close to joint output of S and honest parties. This can be defined in various models (bounded or not, perfect/statistical/indistinguishable closeness, etc).
  Reading: see here (reading for all our secure computation lectures).
• Lecture 8 (3/8): Secure Computation: Overview of models and results, Secret Sharing, BGW/CCD protocol. Reviewed definition of security using real/ideal paradigm. Discussed the many different settings for secure computation, including types of functionality, types of network, types of adversary, quality of security guarantee. Discussed security with abort (relaxation of ideal world, necessary if want general secure computation against malicious/active adversary without honest majority). Mentioned that the security notion provides closure under sequential modular composition (via hybrid model). But no concurrent composition (ie., we have only discussed the "stand-alone" model here, not UC-security). Stated two main results showing feasibility of secure computation of any function (with polynomial overhead in efficiency):
  • information theoretic security, when t < n/2 (honest majority), even against unbounded, adaptive, malicious adversary. For the malicious case, unless we have t < n/3, we assume the existence of a broadcast channel, and we get statistical rather than perfect simulation.
  • computational (or information theoretic with access to OT oracle or to correlated randomness), for any t , assuming OT (or eTDP). For the malicious case with no honest majority, this is security with abort (ie we lose fairness).
  Defined k-out-of-n secret sharing, and showed two schemes: n-out-of-n additive sharing, and Shamir's t-out-of-n polynomial-based sharing. Both these scheme are homomorphic under addition, but not under multiplication. We mentioned the connection between Shamir's secret sharing and Reed-Solomon error correcting codes. In particular, given n shares, if at most t < n/3 are corrupted (even if we don't know which) we can still correct and reconstruct the secret (and the whole polynomial), using Berlekamp-Walch (we didn't show how).
  We outlined the use of secret sharing for secure computation of any function, represented as a circuit. In particular, outlined the BGW/CCD construction using Shamir secret sharing.
  Reading: see here (reading for all our secure computation lectures).
• Lecture 9 (3/22): MPC in the semi-honest model: BGW/CCD, GMW, OT. Reviewed Shamir secret sharing and the BGW/CCD approach for secure computation with information theoretic security, assuming private channels and honest majority (t< n/2) for passive (ie semi-honest) adversaries. We completed the description from last time by showing how shares of inputs to multiplication gate can be used (with interaction among every two parties) to compute shares of the output to a multiplication gate. All the above relies on the fact that the coefficients of a polynomial can be computed as a linear combination of the values of the polynomial in (degree+1) points.
  Next, we considered the case of no honest majority, e.g. for two parties (one of which is controlled by the passive adversary). We showed that some (so called "trivial") functions can be computed with information-theoretic security, but not all functions: we proved that Boolean AND cannot be.
  We introduced the functionality of one-out-of-two Oblivious Transfer (OT), discussing its importance. Showed that given secure realization of OT we can securely realize AND (thus, OT cannot be computed with information-theoretic security). In fact, OT is complete: given OT we can securely implement any function, even without honest majority (as we will see below), and can even achieve info-theoretic security if given an idealized (oracle) version of OT (OT-hybrid model).
  We showed how OT can be realized with information theoretic security if we had trusted correlated randomness (this can also be interpreted as "precomputing OT": a random OT in a preprocessing stage, can be used to get OT in an online stage (when inputs arrive) very efficiently. We then showed how to realize OT from eTDP: enhanced trapdoor permutations (including informal discussion of what "enhanced" means). Showed an example from the RSA assumption. All the above is for semi-honest OT. The situation for malicious OT is more complex (only briefly discussed).
  Finally, we showed the GMW protocol for secure computation of any function with computational security, assuming OT, for any t < n, for passive adversaries. The blue print is the same as we saw above (and in fact GMW was historically earlier): use secret sharing to share inputs, then for each gate, given input shares, compute output shares. Here, however, we use n-out-of-n additive secret sharing for a boolean circuit. Negation and addition (xor) can be computed locally. To compute AND (or multiplication mod 2), need to use 1-out-of-4 OT (which can be constructed from 1-out-of-2 OT).
  Both the BGW/CCD protocol and the GMW protocols presented above have a number of rounds that depends on the function being computed (proportional to the multiplicative depth of the arithmetic/boolean circuit). We will discuss constant round protocols next time. For all the protocols presented so far, we did not give a rigorous proof of security (via simulation). You are encouraged to read the full proof (which is not too hard for the semi-honest/passive case: need to show a simulator that uses input+output to simulate the entire view of the adversary).
  Reading: see here (reading for all our secure computation lectures).
• Lecture 10 (3/29): Yao's garbled circuits (constant round secure computation), security against malicious adversaries. We saw Yao's garbled circuit construction, used (together with OT) to get a constant round secure two party computation (in the semi-honest model). In particular, the garbled circuit itself can be sent in a single round, and OT can be performed in a constant round protocol. We discussed some implementations of the encryption for each garbled gate, and point-and-permute optimization. While we did not prove security, we discussed it intuitively, and also discussed what a malicious player (in particular, a malicious sender) could do to compromise security.
  Secure computation in general, and garbled circuits in particular, is an active area of research, motivated both theoretically and practically. Current implementations can securely compute a circuit with a couple million gates in a second or two; (semi-honest) secure computation for AES circuit can be done in a few milliseconds.
  Briefly outlined the generalization of Yao to multi-party secure computation with constant rounds (the BMR protocol).
  Discussed GMW general compiler from any protocol secure in the semi-honest model, to a protocol secure in the malicious model. This is based on commitments and zero-knowledge proofs of knowledge for NP, which can be based on the existence of a OWF. The overhead is polynomial, but large. We mentioned (without details) other approaches to achieving secure computation in the malicious model more efficiently (special purpose zero knowledge proofs, specific malicious-secure OT, cut and choose method for garbled circuits, and there are more).
• Rest: unfortunately I did not summarize the rest of the class, but we have spent a few lectures on Randomized Encodings of various types, and a last lecture on "maximalist cryptography", surveying other recent areas of cryptography that were not covered in this class.

Homework

• Homework 1 (due Tue 2/9)
• Homework 2 (due Tue 2/23)
• Homework 3 (partially due Tue 4/5, fully due Tue 4/12)

Readings

Textbook most relevant to the class (in addition to research papers):

• Oded Goldreich. The Foundations of Cryptography.

• Rafael Pass and abhi shelat. A Course in Cryptography (free for download)
• Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography
• Nigel Smart. Cryptography, An Introduction (free for download).
• Dan Boneh and Victor Shoup. A Graduate Course in Applied Cryptography (free for download).
• Victor Shoup. A Computational Introduction to Number Theory and Algebra (free for download).
• Salil Vadhan. Pseudorandomness (free for download).
• Ronald Cramer, Ivan Damgård, Jesper Buus Nielsen. Secure Multiparty Computation and Secret Sharing. (Available to purchase, but not yet in the library - let me know if you want to borrow my copy).

For high level slides and videos of tutorial talks on various crytpgoraphic areas, check the Bar-Ilan Winter Schools (every year starting 2011), and the 2015 Simons semester on Crypto (in particular the lectures in the Crypto Boot Camp). More detailed links to the above are given in section 2.7 and 2.8 of the projects page.

Grading and Requirements

• Class Participation: Students are expected to come to lecture and are encouraged to participate.
• Homework: There will be a small number of problem sets, as well as some required reading that will be assigned throughout the semester. Your solutions should be clear, rigorous, and readable.
• Presentation: Every student is required to give a class presentation (roughly 20 minutes). The presentation will be either of the final project, or of research papers relating to the class topic.
• Project: Every student should complete a research project on any cryptographic topic of their choice (subject to instructor approval). Students may work on their research project individually or with one partner. A group of three is also allowed, but requires prior approval from the instructor. If you would like to collaborate or consult with others outside the class, e.g., other professors or fellow students who are not in the class, you may also do so with prior approval from me (and of course, I will hold you accountable for your project).
  The first stage of the project will consist of literature study of the selected area. Based on that, you will then select a research problem or direction which you hope to make new progress in by the end of the semester. I will be available to help you with both these stages, and expect to be updated about your progress throughout the semester. Specifically, here are milestones/deadlines you must follow:
  • by 2/28: Identify a topic that you will study, and some specific papers that you will read.
  • by 4/2 (extended from 3/26): Identify more specifically the open problem you will address, suggest specific directions you will explore, update the list of papers you have/will read, report on what you learned so far.
  • by 5/2: Submit your final report.
  For the first two milestones, it is sufficient to submit something very short (ok to do so via email) outlining the required information. I would recommend to complete these two stages earlier than the deadlines above, so you have more time for completing the project. Feel free to check in with me more frequently about your progress (I will be happy to meet with you to hear about your progress and help by guiding the project as much as I can). Your final project report should consist of a clear summary and exposition of what you have learned, motivation and exposition of the specific research problem you investigated, and a description of the progress you have made. You are not required to solve the research problem and obtain a new publishable result (though that would be nice, and has happened before, research can't be planned and scheduled in this way). However, you are required to attack the research problem, and your project report should describe either your new result, or your attempt, where and why you got stuck, and what you learned from those obstacles, including a suggestion for the next research steps.

  Here you can find evolving suggestions for specific project topics, although I am open to any cryptographic topic you are interested in. Whether or not you choose something suggested in the document above, you are encouraged to come talk to me about your selection.

  Here is the schedule for project presentations Tuesday, May 3rd.

Academic Honesty

As in every CS class, students are expected to adhere to the academic honesty policy of the CS department.