Description

The ubiquity of big data along with modern distributed and cloud computing infrastructures makes it possible to leverage data assets from a variety of sources in order to compute large-scale analytics that serve decision-makers and the public good. A major hurdle to unleashing this potential is the need to trust the entity that gathers the data. Secure Multi-Party Computation (MPC) relies on cryptographic constructs to overcome this hurdle by allowing computation to be performed in a way that reveals only the output result, and reveals nothing about the input or intermediate values used in the computation other than what can be derived from the output. Secure MPC has been an active area of research for over 30 years, with many theoretical results and software artifacts. While fast enough to use today on small-scale data, MPC faces three key challenges that inhibit adoption at scale: the high learning curve of developing private analytics, the challenge of connecting private analytics to existing data stacks, and the inability to balance the privacy and performance provided by the analytic.

This team-taught course aims to prepare/recruit students interested in pursuing research that tackle these challenges by focusing on the deployment of state-of-the-art MPC technologies toward applications with important economic and social justice benefits, such as pay equity, economic stability of the banking system, market diversity to detect monopolies, and distributed network anomaly detection. The course leverages active research and real systems developed at BU by the team of instructors and their students.

We will first review in a lecture/reading group format the mathematical and algorithmic foundations of different MPC frameworks and systems. Next, we will also review some real-world instances of MPC deployment and the associated challenges. Finally, we will break up into project-oriented teams who will set up and deploy MPC systems by applying them to real-world or real-world-inspired data analysis problems. In particular, students will be expected to develop expertise in the use of one or more of the existing MPC libraries/APIs/systems that have been developed over the last few years, leading each student or small groups of students to a course project that will either use these existing MPC capabilities to tackle a large-scale big-data analytics problem, or else integrate these capabilities into the backend of popular big-data analytics platforms. Projects ideas from students that complement and/or augment those proposed by the instructors are welcome!

General Information

Lecture time and location
Mondays 3-5pm in MCS 180
Participation and grading
Students will be evaluated in this class on the following metrics.
- Attendance at lectures
- Participation in the discussion about assigned material to read/watch outside of class. Each student shall lead the in-class discussion at least once.
- The majority of the grade shall come from the student's final project. Project deliverables shall include a report, presentation to the class, and source code.
Collaboration policy
You are welcome and encouraged to discuss your work on Piazza with your classmates, read publications or other resources on the web, and share code with others. But, always remember the following three rules:

1. Your submitted report must be your own writing.
2. Your work must cite all of the sources you consult, including personal conversations with people outside of your project! Be verbose: if you are uncertain whether an interaction is citation-worthy, please include it.
3. You will be graded on your novel contributions. So, while it's encouraged to build upon the work of others, make sure that your contribution is a substantial one!

Violations of this policy will result in a grade reduction. They may also be treated as plagiarism and referred to BU’s Academic Conduct Committee.
Prerequisites
Required: Basics of number theory, abstract algebra, and probability theory for CS applications (covered in CS-235 and CS-237). Also, experience with building non-trivial multi-module applications in a modern programming language (such as Python, C, Java, and so on).

Not required, but good to have: Familiarity with or interest in distributed/cloud systems (covered in CS-350 or CS-451) and basics of cryptography and net security (covered in CS-538 or CS-558).

Undergraduate students must obtain permission of the instructors.

Announcements

Homework Assignment: Get AWS (or MOC) up and ready for MPC action
10/13/16 4:01 PM

As I mentioned at the end of the lecture part of our meeting on Tuesday, we would like you to get your feet wet setting up a a cloud environment. Here is what we need you to do: 

  1. Set yourself up on AWS by following the step-by-step process is available from the UPenn course that I mentioned. If you prefer to get set up on the MOC, please go ahead!  You may find some of the slides about AWS in the intro to cloud lecture helpful. 
  2. Choose and install an MPC framework from the ones we discussed/mentioned in the course -- check the resources page for a bunch of pointers.  Your set up should allow for an AWS (or MOC) VM to act as a single party in an MPC protocol.

  3. Test that your set up is able to run a simple (or complex!) MPC protocol of your choosing (could be as simple as averaging a set of secret values).

Let us know if you encounter any problems (and make sure not to leave your AWS instances humming when not in use, your $100 of credit will evaporate in no time :)

Course schedule
9/11/16 11:53 PM

DatePre-lecture reading assignmentPre-lecture viewing assignmentLecture topic
9/12(none)(none)Intro to MPC: motivating applications, rough definitions & constructions
9/19

1. Shen et al: MPC future vision

2. Lapets et al: Usable MPC application

3. Cramer-Damgard-Nielsen chapters 1 and 3

Discussed in class: Reflections on trusting trust

Ishai: intro to MPC parts 1 and 2 (can stop the 2nd video at the 45:15 mark)

MPC theory: basic techniques, definitions, security threats
9/26

Prep for 9/26 lecture:

Post 9/19 lecture:

Optional reading: Secure coin tossing, ObliVM

1. Pinkas: Yao's garbled circuits

2. Rosulek: Garbled circuit optimizations
Use of MPC frameworks
10/3

Prep for 10/3 lecture:

Viff, SPDZ, and Sharemind MPC frameworks

Damgard: SPDZ protocol parts 1 and 2

Big-data computing stacks
10/11

Review of 10/3 lecture:

MapReduce, Dryad, Naiad, and COST (optional: Musketeer)

(None. Focus on the reading.)Distributed computing: Hadoop & Spark 
10/17

(no reading, do the homework assignment in note @30 instead)

5-part introduction to big data, Hadoop, and Spark

10/24

1. Cramer-Damgard-Nielsen chapters 5 and 7 (but not 6!)

2. Cut-and-choose for garbled RAM (focus on the concepts of cut-and-choose and garbled RAM independently in sections 1-2)

Lindell: Two-party secure computation for malicious adversaries

(Relevant papers, if you're curious: 1, 2, 3, 4, 5, and more)

Active security in the info-theoretic and computational settings
10/31

1. Chung, Pass: A Simple ORAM

2. Dani et al: Communication locality

1. From passive to active security at low cost

2. Garg: Advances in Secure RAM Computation (read the ORAM paper first!)

(optional: Pinkas on ORAM)

Hiding access patterns & sub-linear MPC
11/7

1. Secure MPC for privacy-preserving data mining (review sec 3.1-3.2, then read sec 3.3 and 4)

2. Private set intersection: Are GCs better than custom protocols? (think of this as a rebuttal to sec 3.3 of the first paper)

3. ABY: A framework for efficient mixed-protocol secure 2PC (code)

Pinkas: Set Intersection

MPC optimizations
11/14

(none)

(none)

Initial presentations on projects
11/21

Canetti et al: Simpler variant of UC security for MPC (read while watching the video)

(optional) Cramer-Damgard-Nielsen chapter 4

Simpler variant of UC security for MPCComposition
11/28

(none)

(none)Guest lecture by abhi shelat
12/5

Crypto for big data security

(none)Special-purpose MPC for database search
Future...(TBD, mostly reserved for project discussions)

Staff Office Hours
NameOffice Hours
Andrei Lapets
When?
Where?
Azer Bestavros
When?
Where?
Ran Canetti
When?
Where?
Nikolaj Volgushev
When?
Where?
Mayank Varia
When?
Where?
Emily Shen
When?
Where?