Instructor: Rafael Pass
Time: Th 10:10-12.55
Place: Big Red, Cornell Tech
Course Web page: http://www.cs.cornell.edu/courses/cs5831/2014sp/
Office Hours: By appointment
In today's society, we face adversarial entities that attempt to, through malicious attacks, get access to sensitive information. At the same time, we continuously face corporations who are willing to tease us with free services while collecting bits and pieces of perhaps innocuous information, who then can combine this information through sophisticated
algorithms in order to maintain alarmingly accurate profiles of individuals.
In this course we will survey modern techniques for preventing against these types of attacks. Topics include basic key-exchange protocols, Internet Security protocols (such as TLS), methods for secure multi-party computation, methods for securely outsourcing data, methods for deriving keys from passwords, random number generation and methods for data
sanitization (i.e., how to ensure that publicly released data does not violate individuals' privacy).
The course will have a strong theory-to-practice component, through a course-long project (with the aim of building systems based on the course
material), and through guest lectures from industry.
Equivalent of CS2800 (Discrete Mathematics) and comfort with reasoning about algorithms, such as proving their correctness and analyzing their running times, or permission of instructor. The main skill that will be assumed is the ability to understand and write formal mathematical definitions and proofs. It is also important that you are familiar with basic probability (although we will recall some basic concepts); please refresh yourself by reading Chapter 5 in the following lecture notes: [Pass-Tseng]
We also assume basic familiarity with Cryptography; you may refresh yourself using the following lecture notes: [Pass-Shelat]
There will be between 1-2 homeworks (corresponding to 30% of the grade), and one course-long project (corresponding to 70% of the grade).
The following notation might be useful.
You are free to collaborate with other students on the homework (in fact, I highly encourage you to work in pairs), but you must turn in your own individually written solution and you must specify the names of your collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used. Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to a member of the course staff.
· Chapters 1 and 3 in [Pass-Shelat]
· Bellare et al: Message-Locked Encryption and Secure Deduplication
· Narayanan and Shmatikov: Robust De-anonymization of Large Sparse Datasets
· Islam et al: Access Pattern disclosure on Searchable Encryption
· Shi et al: ORAM with log^3 worst-case cost
· Stefanov et al: Path ORAM
· Chung and Pass: A Simple ORAM
10:00 – 10:30.
10:30 – 11:20.
Dana Dachman-Soled (UMD)
Securing Circuits and Protocols Against 1/poly(k) Tampering Rate
11:30 – 12:20.
Thomas Ristenpart (University of Wisconsin – Madison)
New Encryption Primitives for Uncertain Times
12:30 – 2:30.
Lunch (not provided)
2:30 – 3:20.
Hemanta Maji (UCLA)
A Full Characterization of Completeness for Two-party Randomized Function Evaluation
3:30 – 4:20.
Omer Paneth (BU)
On the Existence of Extractable One-Way Functions
An introduction to the design and analysis of authenticated key exchange protocols
Authenticated key-exchange (AKE) protocols are cryptographic mechanisms by which
two parties that communicate over an adversarially-controlled network can
generate a shared secret key and be assured that no one other than the intended
partner to the communication learns that key. AKE protocols are an essential
component of secure communications as they enable the use of efficient
symmetric-key techniques (encryption and authentication) to protect bulk
communication over insecure channels (e.g., the Internet). In particular, AKE
protocols are the most important class of cryptographic protocols in use today
with TLS, IPsec and SSH being examples of prime applications whose security
fully depends on the underlying AKE protocol.
While the functionality and security requirements of AKE protocols is intuitive
and simple, the design of such protocols has proven highly non-trivial with
numerous examples of broken protocols. The very formalization of security for
these protocols has been challenging and is still an active area of research.
In this short course we will cover basic principles of design and analysis of
AKE protocols with examples from real-world applications, including IPsec's Key
Exchange (IKE) and (time permitting TLS handshake, and of more advanced protocols.
The intention is to use AKE protocols as a window into the challenging world of
crypto-protocol design and analysis. While the subject is highly technical, we
will try to emphasize more the principles than the mathematical details.
1. Definition of Entropy and Randomness Extractors
2. Construction of seeded Randomness Extractors
3. Impossibility of Cryptography with Biased randomness.