COMS E6261: Advanced
Cryptography
Spring 2016: Minimalist
Cryptography
Announcements
(4/15) project presentation
schedule has been posted.
Classrelated News
 Diffie + Hellman win Turing Award: link
 First zeroknowledge contingent payment on Bitcoin network: link
Instructor: Tal
Malkin, Office hours: Mondays 3:304:30pm in 514 CSB or by
appointment.
Teaching Assistant: Lucas Kowalczyk, Office hours:
Monday 4:305:30 in Data Science Institute (4th Floor Mudd) or by appointment.
Time & Place: Tue 10:1012:00, 253 Engineering Terrace
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 E6261 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
COMS4261
Introduction to Cryptography or
COMSW4236 Introduction to Computational Complexity or instructor
approval. The most important prerequisite is mathematical
maturity and comfort with rigorous definitions and proofs.
Course Description
The course will focus on selected cryptographic tools that
can be based on oneway functions or weaker assumptions (including
unconditional cryptography).
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
Below is a summary of what was covered in each class and related
readings. The readings may not match exactly what was covered in
class (e.g., the readings may provide expanded and more detailed
treatment than what was given in class, or class may cover things that
do not appear in the readings).
 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 nonnegligible probability (see
HW1).

Lecture 2 (1/26): OWF, HardCore 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 (worstcase OWF).
We claimed
that worstcase 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, oneway 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 hardcore predicates, and stated the
GoldreichLevin theorem, showing that if any OWF exists,
then a simple tweak yields a OWF with a hardcore bit.
Very briefly discussed the use of hardcore bits in the
creation of PRG from OWP.
We defined perfectly binding, computationally
hiding commitment schemes, focusing for
simplicity on the case of noninteractive, 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 hardcore predicates). Commitments are
defined and discussed in [Gol, 4.4.1]. For universal OWF,
I recommend the proof in [Ps] (Passshelat 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 graphnonisomorphism (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  graphisomorphism  has a
perfect ZK proof system. Revisited the GNI example, and
discussed the fact that the protocol that we saw before is a
honestverifier 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
blackbox zero knowledge simulation (all the examples we see here
are indeed blackbox 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 3colorability,
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
semihonest (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 idealreal 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 "standalone" model here, not UCsecurity).
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 koutofn secret sharing, and showed two schemes: noutofn
additive sharing, and Shamir's toutofn polynomialbased sharing. Both these scheme
are homomorphic under addition, but not under multiplication. We
mentioned the connection between Shamir's secret sharing and
ReedSolomon 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 BerlekampWalch (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 semihonest 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 semihonest)
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 informationtheoretic security, but not all functions: we proved
that Boolean AND cannot be.
We introduced the functionality of oneoutoftwo Oblivious Transfer
(OT), discussing its importance. Showed that given secure realization
of OT we can securely realize AND (thus, OT cannot be computed with
informationtheoretic 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 infotheoretic security if given
an idealized (oracle) version of OT (OThybrid 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 semihonest 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 noutofn 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 1outof4 OT
(which can be constructed from 1outof2 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 semihonest/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 semihonest
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 pointandpermute 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;
(semihonest) secure computation for AES circuit can be done in a few
milliseconds.
Briefly outlined the generalization of Yao to multiparty secure
computation with constant rounds (the BMR protocol).
Discussed GMW general compiler from any protocol secure in the
semihonest model, to a protocol secure in the malicious model. This
is based on commitments and zeroknowledge 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
malicioussecure 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
Homeworks will be posted here, and due at the beginning of class. No
late homework please.
The (few) problem sets are designed to make
sure you understand the material, and may be challenging. You should
not search for solutions on line (or anywhere else), but rather try to
solve the problems on your own. I am happy to discuss homework
problems with you and to give hints in office hours, and happy for
you to discuss the problems with other students in the class, but
these things should happen only after you spend a considerable
amount of effort on solving the problems on your own. If you do
discuss the problems, the actual solutions must still be written by
yourself independently, and all your discussion partners should be
listed. Even if I can't enforce these rules, I expect and trust that
you will abide by them.
Readings
There is no required textbook for the class. Below are some recommended
textbooks (all are available either online or through the library).
Pointers to required and recommended readings for specific lectures
will be posted above as the semester progresses.
Textbook most relevant to the class (in addition to research papers):
Other textbooks that can be used as reference (note there are some
differences in notation and approaches among these):
See some reading pointers for the lectures related to secure
computation.
For high level slides and videos of tutorial talks on various crytpgoraphic
areas, check the BarIlan
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
The class requirements are as follows:
 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
I expect that the primary goal of everyone in the class is to learn (I
can imagine no other reason that you would be in this class). Hopefully
this means that there will be no focus on grades (which I can tolerate
but do not like), and no issues of dishonesty (which I absolutely will
not tolerate).
As in every CS class, students are expected to adhere to
the academic
honesty policy of the CS department.