General Information

Instructors:

• Daniel Mitropolsky (512 CSB, office hours by appointment), Email: mitropolsky at cs
• Tal Malkin (514 CSB, office hours by appointment), Email: tal at cs

Teaching Assistant:

• Miranda Christ (516 CSB, office hours by appointment), Email: mchrist at cs

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, as a foundations track elective for undergraduates following the old curriculum, or an elective for undergrads following the new curriculum. 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. Auditing the class is certainly possible but requires instructor approval.

Prerequisites

Motivation and Course Description

In this course we will survey the new and burgeoning field of cryptography ∩ TFNP, exploring the connections between cryptography and the complexity of total search problem. We will also consider connections to meta-complexity. There will be an emphasis on open problems and research techniques.

This course is an advanced graduate level seminar, where most lectures will be given by students taking the class (with prior feedback and support from the instructors and fellow students). The specific papers covered will be selected by the instructors, biased by their interests, and (especially for the later lectures) also by the interests of the students taking the class.

Lectures and Readings

• Lecture 1 (1/18): Introduction and class overview. Tal gave a quick intro to crytography, including an overview of Impagliazzo worlds and definitions of OWF, OWP, CRHF, and IO. Dan gave a quick intro to total function complexity, including definitions of FP, FNP, TFNP, showed that TFNP does not have an NP-hard problem unless the polynomial hierarchy collapses, and started giving examples of problems in (and not in) TFNP. Talked about defining TFNP problems through combinatorial existence theorems: defined PIGEON and WEAK-PIGEON (based on pigeonhole principle) and the associated classes PPP and PWPP. Started talking about a graph theoretic theorem that can be used to define problems and associated classes in TFNP (PPA, PPAD, PLS, and even PPP) -- as we will see next time.
  • Reading: Here are the lecture notes from class. For some general background on crytpography, you can see the general resources recommended here (in particular, shelat-Pass and Goldreich).
  • Quiz 1 solutions (corrected a previous error!) (also available on gradescope).
• Lecture 2 (1/25):
  • Part 1: Dan continued from last time. Showed a proof that PWPP-p(n) (finding collisions for circuits that shrink a longer poly(n) input string to a shorter n bit string) is equivalent to PWPP (finding a collision for circuits with input length = output length+1) - this generalizes a statement we saw last time. Continued discussing how to make a TFNP problem out of the graph-theoretic existence theorem (an undirected acyclic graph with a vertex of degree 1, has another vertex of degree 1). We discussed several attempts and variations/special cases, giving rise to different TFNP subclasses. Specifically, PPA via "END-OF-UNDIRECTED-LINE", a variation that is equivalent to PIGEON (thus gives PPP), PPAD via END-OF-LINE problem, PLS via ITER problem. We said that PPAD is a subset of PPA intersect PPP. We defined two more problems that turn out to be complete to PPA (in addition to the END-OF-UNDIRECTED-LINE): ODD-DEGREE and LONELY (aka PAIRING).
    • Reading: Here are the lecture notes from class.
  • Part 2: Yuriko Nishijima, with support from Akash Kumar, presented on where factoring fits within TFNP. She prepared a presentation on the main points from the following two papers:
    • On the TFNP complexity of factoring, Buresh-Oppenheim
    • Integer factoring and modular square roots, Jerabek
    However, given time constraints, she only ended up covering the first paper showing that factoring specific types of integers is in PPA, and (for more general integers) in PPP with randomized reductions. She also gave a more general overview of what is known. We will discuss some of the more general results from the second paper next time.
    • Reading: Here are Yuriko's notes.
  • Quiz 2 solutions
• Lecture 3 (2/1):
  • Part 1: Akash Kumar, with support from Yuriko Nishijima, presented the result from Jerabek's paper, showing that (general) factoring can be randomly reduced to PWPP (the paper also shows this for PPA).
    • Reading: Here are Akash's notes
    • Jerabek's paper (same as second one above)
  • Part 2: Tal gave a high level overview of what is known about TFNP and crypto, including some things we will see later in the class, to help contextuealize the class topic. She also discussed some open problem and areas for project ideas.
    • Reading: Here are the lecture notes from class.
  • Quiz 3 solutions
• Lecture 4 (2/8):
  • Part 1: Shouqiao Wang, with support from Hugo Bucquet, presented a result placing discrete log in TFNP. In particular, DLOG_p for a prime p is in (but not likely to be complete for) PWPP, while for general groups (with a group operation given by a boolean circuit), two different ways to formulate the problem so that it is total, result in two different complexities: one (INDEX) that is complete for PPP, and one (DLOG) that is complete for PWPP. Some open problems were also mentioned.
    • The paper presented: On Search Complexity of Discrete Logarithm, Hubacek and Vaclavek
    • Here are Shouqiao's slides
    This ends our first topic, placing some cryptographic group-theoretic problems in TFNP.
  • Part 2: Akshat Yaparla, with support from Mark Chen, covered the following paper:
    • The journey from NP to TFNP hardness, Hubacek, Yogev, and Naor
    • Here are Akshat's slides
    • And here's a background document prepared by Akshat and Mark, containing material that was not covered in the lecture itself.
    This starts our next topic, TFNP hardness from NP hardness.
  • Quiz 4 solutions
• Lecture 5 (2/15):
  • Yizhi Huang, with support from Jiaqian Li, covered the following paper:
    • Is it Easier to Prove Theorems that are Guaranteed to be True?, Rafael Pass and Muthuramakrishnan Venkitasubramaniam which addresses TFNP hardness in Pessiland.
    • Here are Yizhi's slides
  • Quiz 5 solutions
• Lecture 6 (2/22):
  • Kashvi Gupta, with support from Tianqi Yang, covered the following paper:
    • One-Way Functions vs. TFNP: Simpler and Improved, Folwarczny, Goos, Hubacek, Maystre, Yuan
    • Here are Kasvhi's slides.
  • Quiz 6 solutions
• Lecture 7 (2/29):
  • Part 1: We started our next unit -- hardness of PPAD (and related classes) from cryptography. Dan gave several definitions and preliminaries. He defined PPAD and PPADS (via END-OF-LINE problem, where in PPADS a sink must be given, while in PPAD either a sink or another source), as well as PLS (via the SINK-OF-DAG problem, which is equivalent to ITER that we saw in Lecture 1). He then defined SVL -- Sink-Of-Verified-Line -- a promise problem (not total) which is reducible to PPAD ∩ PLS (so, if there's a way to generate yes-instances of SVL that are hard to solve, then both PPAD and PLS are also hard on average). Dan showed this reduction -- how to transform a yes-instance of SVL to an instance of PPAD (or of PLS) in a way that a solution to the PPAD (PLS) instance will give a solution to the SVL instance. Intuitively, the main problem is that in SVL the given instance includes only a way to go forward one step, and a way to verify a given node (n-bit-string) is T steps away, but it's not clear how to go backwards (nor how to compute a node that is T steps away efficiently). In contrast, for END-OF-LINE instance we need both a successor and predecessor circuits. The main technique in the reduction used a pebbling game, where each step is reversible, and where we can show that with t pebbles we can reach a point in location 2^t-1. This allows to transform the SVL instance to an END-OF-LINE instance, where the each node in the new graph consists of all the t=log T pebble locations (together with the corresponding n-bit strings that can be used to verify this location). The fact that each step in the pebbling game is reversible allows to create both a successor and a predecessor circuit (as well as to create a "cost" circuit, which is which stage we are in in the pebbling game, if we want a reduction to PLS).

    We noted that this reduction produces an instance with a unique solution (namely, SVL reduces to UEOPL), which is much more structured (harder/lower/contained in) PPAD ∩ PLS.

    • Here are Dan's notes.

    In the next few lectures we will see how various crytpographic assumptions imply that we can generate hard promise-true intances of SVL (which in turn imply hardness-on-average of UEOPL and thus also of PPAD and PLS).

  • Part 2: Miranda discussed the project -- note that the proposal is due next Tuesday! (see more details on the project page). We have an evolving document with project ideas -- Miranda went over several of these in class. Even if you don't pick any of these suggestions (which is absolutely fine!) this may help give you some ideas about types of questions and possible scope.
  • There's no quiz this week, but be sure to submit the project proposal on gradescope by Tue March 5th, and review Dan's lecture and especially the definition of SVL prior to next week.
• Lecture 8 (3/7):
  • Part 1: Mark Chen (with support from Yizhi Huang) covered the BPR paper (see below), showing how to use super-polynomial hardness of indistinguishability obfuscation and OWF to get hardness of SVL.
  • Part 2: Ashvin Jagadeesan (with support from Akshat Yaparla) covered part of the GPS paper (see below), which builds on the BPR paper and improves on it, showing how we can use (standard) polynomial hardness of iO and OWF to get SVL hardness.
  • The papers covered:
    • On the Cryptographic Hardness of Finding a Nash Equilibrium, Bitansky, Paneth, Rosen
    • Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium, Garg, Pandey, Srinivasan
  • The presentation slides about the above two papers, respectively:
    • Mark's slides
    • Ashvin's slides (this is an html format -- here is the original jupyter notes source which looks prettier).
  • We will end class early, so those who are interested can attend Columbia 3MT Competition and see Dan describe his thesis in 3 minutes (and compete with other PhD students from across the university, doing the same!).
• Lecture 9 (3/21):
  • Jiaqian Li, with support from Kashvi Gupta, covered the following paper:
    • Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir, Choudhuri, Hubacek, Kamath, Pietrzak, Rosen, and Rothblum
    • Here are Jiaqian's slides
  • Quiz 9 solutions
• Lecture 10 (3/28):
  • Tianqi Yang (with support from Yizhi Huang) first gave a high level overview of the known results on instantiating the approach described last time to get rSVL hardness using incrementally verfiable unambiguous SNARGs for a hard language. He then discussed the technique at the heart of this line of work (although many additional details on top of this technique were omitted): instantiating the Fiat-Shamir paradigm via collision intractable hash functions. He also showed the circular-FHE based instantiation.
    • Here are Tianqi's notes.
  • Quiz 10 solutions
• Lecture 11 plan:
  • Part 1: Shouqiao Wang (with support from Yuriko Nishijima) covered Unconditional hardness of PLS in the ROM: the second half of the Bitansky-Gerichter paper on complexity of local search. This paper uses a technique from blockchain -- incremental proofs of work -- to prove hardness of PLS in the random oracle model! It's also one of the only papers showing hardness of something easier than than rSVL, which is something we're always interested in doing, as it gives the hope of starting with easier crypto assumptions! The paper is related to the teqhnique we saw last week (Lecture 9) and the associated quiz, making an observation about how a relaxation of it - incrementally verifiable computation without uniqueness - is sufficient for PLS hardness. We want to present only the second half of the paper, not the instantiations in the plain model from computational assumptions, but yes the unconditional instantiation in the ROM -- this is the part taken from blockchain techniques.
  • Shouqiao's slides
  • Part 2: Hugo Bucquet (with support from Kashvi Gupta) covered Bitansky-Paneth-Wichs Perfect structure on the edge of chaos-- a beautiful title, and this paper is a great example of how progress in one area can significantly help in another. Using techniques from the BPR'15, they solved a big problem purely in cryptography: they showed that iO and OWF implies trapdoor permutations (and thus OWP).
  • Hugo's slides
  • Quiz 11 solutions
• Lecture 12 plan:
  • (presenter: Yizhi, supporter: Ashvin) Rosen-Segev-Shahaf's Can PPAD Hardness be Based on Standard Cryptographic Assumptions? This is an important paper giving us partial answers on the big questions we've been thinking about in this class: (1) can we base rSVL hardness on OWF? and (2) what about basing OWF on rSVL hardness? (this is one of the only papers that talks about the crypto from TFNP hardness direction! and even about crypto from TFNP+weaker crypto direction! all these are problems discussed in class and in the open problems document we shared. The paper shows that for (1), if the answer were yes, we would have exponentially many solutions (in contrast to techniques we have seen so far / know how to show hardness, which gives a unique solution). For (2) it shows the answer is no (black-box separation). And a couple other results. This is a long paper, but we will only focus on part of it (will figure out which part).
  • (presenter: Mark, supporter: Tianqi) Going back to the bigger picture and some things that were mentioned in passing in class, including clarifying the historical context and importance of some of the relevant classes that the literature focuses on, in particular PPAD and CLS. We had focused on the technical definitions of these classes via graph problems such as SVL, END-OF-LINE, etc, but what is the significance of these classes? This will not be very technical or a specific paper, but rather a historical and contexual perspective, with some motivation (it will also be a shorter segment).
  • No quiz this week; more time to work on projects.
• Lecture 13 plan (tentative!):
  • Komargodski-Naor-Yogev's White-box vs Black-box Complexity of Search Problems: Ramsey and Graph Property Testing. This paper considers a very beautiful total search problem that doesn't fit neatly into the classes we studied so far: the Ramsey problems, which is to find a clique or independent set of a certain size in a graph; it turns out hardness of this problem follows from CRHFs!
  • Range avoidance (which is higher in the total hierarchy than TFNP), and connections to cryptography Ilango,Li,Williams iO, Range Avoidance, and Bounded Arithmetic. Introduced by Dan and co-authors in a recent paper, turns out there are interesting total search problems that cannot be NP verified, but live in the total polynomial hierarchy. A particularly important one is range avoidance, based off the empty pigeonhole principle (a mapping with more outputs than inputs has an empty pigeonhole). This paper is one of the first to show hardness of this problem from cryptographic assumptions!

Other upcoming topics are listed below (this section continues to be updated, and note that we won't necessarily cover papers in this order in class). We will also post materials (slides or notes as necessary) associated with each lecture after it takes place.

Topic 1: Number Theory and TFNP (completed by Lecture 4)

The hardness of factoring of finding discrete logarithms in cyclic groups are used to construct public-key cryptographic primitives. What do we know about the complexity of these problems in TFNP?

Papers:

• On the TFNP complexity of factoring, Buresh-Oppenheim
• Integer factoring and modular square roots, Jerabek
• On Search Complexity of Discrete Logarithm, Hubacek and Vaclavek

Topic 2: Going from NP Hardness-on-average to TNFP hardness

Assuming that NP is hard-on-average, what can we say about the hardness of TFNP? What if we assume one-way functions do not exist, that is, is TFNP hard in Pessiland?

Papers:

• The journey from NP to TFNP hardness, Hubacek, Yogev, and Naor
• Is it Easier to Prove Theorems that are Guaranteed to be True?, Rafael Pass and Muthuramakrishnan Venkitasubramaniam

Topic 3: PPAD hardness from Indistinguishability Obfuscation

One of the most important and earliest results in TFNP Cryptography was the construction of hard a PPAD distribution from iO.

Papers:

• On the Cryptographic Hardness of Finding a Nash Equilibrium, Bitansky, Paneth, Rosen
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium, Garg, Pandey, Srinivasan

Topic 4: Beating iO: PPAD / PLS / CLS hardness from other assumptions

Papers:

• Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir, Choudhuri, Hubacek, Kamath, Pietrzak, Rosen, and Rothblum
• SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE, Jawale, Kalai, Khuruna, and Zhang
• PPAD is as Hard as LWE and Iterated Squaring, Bitansky, Choudhuri, Holmgrem, Kamath, Lombardi, Paneth, Rothblum
• On the Cryptographic Hardness of Local Search, Bitansky, Gerichter

Topic 5: From OWFs to TNFP hardness

iO, and even the other assumptions that have been used to construct hard TNFP instances, are quite strong. Can we hope to show TFNP hardness from the most basic cryptographic primitive: one-way functions? Some negative results (black box separations of a certain kind) are known:

Papers:

• One-Way Functions vs. TFNP: Simpler and Improved, Folwarczny, Goos, Hubacek, Maystre, Yuan
• Can PPAD Hardness be based on standard cryptographic assumptions?, Rosen, Segev Shahaf

Other papers to cover later (schedule TBD):

• White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing, Komargodski, Naor, and Yogev
• PPP-Completeness with Connections to Cryptography, Sotiraki, Zampetakis, Zirdelis
• Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic, Rahul Ilango, Jiatu Li, Ryan Williams
• Perfect Structure on the Edge of Chaos, Nir Bitansky, Omer Paneth, and Daniel Wichs

Other topics will be chosen based on instructor and student interests. Potential topics include: cryptography and meta complexity, limits on basing cryptography on NP hardness, cryptography from learning theory, and more.

Class Requirements

• Lecture Presentation and Support (40%): Each weekly meeting will be divided into two lectures of about 50 minutes each, and most lectures will be delivered by students. There will be 1 or 2 students in charge of the lecture (presenting the assigned papers to the class), and 1 or 2 students supporting the presenter(s). Every student is expected to take the role of a presenter twice and the role of a supporter twice throughout the semester. See additional details on lecture presentations below.
• Quizzes (10%): Every week, there will be a short, auto-graded quiz on gradescope. This is meant to be a simple, easy quiz, to check that students have been paying attention and understood the main take-home messages of the lectures. The quiz should be taken individually by every student, without collaboration.
• Attendance, Participation, Homework (10%): Students are expected to be present in lectures (physically, but not only), and are encouraged to particpate. There may also be a small number (between 0 and 2, likely closer to 0) of homeworks.
• Project (40%): 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 in a group. If you would like to collaborate with others outside the class, e.g., other professors or fellow students, you may do so, provided that all your collaborators know and approve, and that you're not getting double credit for the same project (and of course, we will hold you accountable for your project). More information about the requirements, deadlines, and suggested topics for the projects is available on the projects page.

Lecture Presentation Details

• Presenter(s): have to read the paper carefully, think about the right way to teach it to the audience, how to structure their presentation, what to include and not include in the given time (some papers may be quite long), what the main message is, and determine the mechanism they prefer (slides or blackboard). They should also answer student questions during the lecture.
• Supporters(s): have to read the paper carefully, and meet with presenters prior to their lecture to go over the presentation and give feedback (generally, the presenters should share their preliminary slides or lecture notes with the supporters for feedback at least a day before the class they are teaching). Supporters should be generally available over email to answer presenters' questions prior to the lecutre, and prepared to help answer stduents' questions during the lecture if needed.
• Meeting with instructors: the team will receive an email with instructions and recommendations from an instructor a week before their presentation. The team will then need to meet with the other instructor prior to their presentation for feedback.
• Materials: the team should also provide materials for rest of the class, in the form of notes or slides summarizing the lecture (again with feedback from the teaching staff).
• Overlap: in general, we will try to have the two papers in a given week be thematically related. As such, they may overlap substantially in definitions and even lemmas, propositions, etc. The second team on any given week has an additional challenge (and benefit): they should read the introduction of the first paper to see if there is such overlap, and then coordinate with the other team so that if they will be presenting those definitions or results already, the second team knows that they can be much more brief in their presentation of them (in general, the second team should at least briefly show those definitions and result statements again, but can save time doing so).

Academic Honesty

As in every CS class, students are expected to adhere to the academic honesty policy of the CS department. This policy has been passed by the faculty of the Department and approved by the school deans.