Description: CornellNYCTech-logo.jpg

Security Protocols and Privacy

Computer Science 5831
Cornell University
Spring 2014

Instructor: Rafael Pass

Time: Th 10:10-12.55
Place: Big Red, Cornell Tech
Course Web page:

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.


Homework Policy

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.

Schedule (subject to change)


·      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.