CS 290G: Secure Computation (Spring 2014)

Instructor: Huijia (Rachel) Lin, rachel.lin(at)cs(dot)ucsb(dot)edu

Class time and location: TR 3-4:50pm, Phelps 2510

Office hours: Wed 1:30-2:30pm or by appointment, HFH 1153

Class webpage: http://www.cs.ucsb.edu/~rachel.lin/courses/14s290G/

Course Description

With the growing demand for security and privacy, the field of cryptography has expanded rapidly in the past three decades. Beyond the original goal of ensuring secure communication, innovative and powerful concepts and primitives have emerged that enable new secure paradigm of computing. In this course, we will survey some of the exciting new developments in private database, computation over encrypted data, secure computation without trusted third party, and verifiable outsourcing of computation.

The basic nature of cryptography is all-or-nothing, protecting the privacy of honest individuals against the evil. Core cryptographic primitives, such as, encryption, hash functions, signatures etc., are developed and continuously improved to ensure data confidentiality, integrity and authenticity. A fundamental question that follows is how to extract utility from the heavily securely guarded data? Can we still compute over them? Can we collaborate across boundaries of trust? Can we support dynamic data, maintain efficiency and flexibility? We will see examples of new cryptographic primitives---Oblivious RAM, Searchable Encryption, Fully Homomorphic Encryption, Secure Multi-Party Computation, and Universal Arguments---that achieve both security and utility in some scenarios, and brainstorm about other scenarios where security and utility remain in conflict.

Course Objectives: For students who are interested in cryptography research, the objective is preparing the background for delving into a topic. For students who are interested in security issues in other areas, the objective is familiarizing them with cryptographic tools and thinking, enabling application of cryptographic tools in other areas, and spurring interdisciplinary research.

Course Set-ups and Requirements: The course will be a combination of lectures and paper presentations by the students. At the beginning of the course, I will give lectures on bare basics of cryptography. Then the course will move on to more concrete topics. For each topic, I will again give lectures to introduce the primitives we study and some background. After that, students will present papers on this topic.

Students will also pursue a course research project. Some examples of the flavors of projects are: 1. Improve known construction of a primitive. 2 Propose a new primitive, formalize it and explore its construction. 3. Apply a primitive to solve a security problem in another area. Any combination of the flavors are also encouraged. The final outputs of the project include a presentation and a short report.

Final assessment will depend on a combination of presentation, in-class participation, and final project. The tentative weights of different components are 35%, 15%, 50%


The following is a WORKING DRAFT of the schedule of the class. There will be changes depending on the pace of the class.

WeekDateLecture contents Papers/Reading material Format
1 2014-04-01 Welcome and Basics I
  • Overview of modern cryptography
  • Secure communication and Secure computation
  • Introduction to topics to be discussed in the class
2014-04-03 Basics II
  • Block cipher
  • Pseudo-random functions
  • A first example of reduction: Pseudo-randomness ==> Security against key recovery
2 2014-04-08 Basics III
  • Model of Computation
  • Private-Key Encryption
  • Single-Message Security
  • Single-Message Secure Encryption from Block Cipher
2014-04-10 Basics IV
  • Notion of computational indistinguishability
  • Multi-Message Security (MMS)
  • IND-CPA security
  • IND-CPA is stronger than MMS
  • Construction of IND-CPA secure Encryption from PRF
3 2014-04-15 Basics V
  • Public-Key Encryption
  • IND-CPA security
  • Discrete-log, CDH and DDH
  • Diffie-Hellman Key Exchange
  • ElGamal PKE scheme
Further Reading: Lecture
2014-04-17 Private Databases I
  • Introduce Oblivious RAM
  • Application of to private database indexing
  • Definition
  • The Chung-Pass Construction of Oblivious RAM
Further Reading: Lecture
4 2014-04-22 Private Databases II
  • Introduce Searchable Symmetric Encryption
  • Student Presentation: Curtmola-Garay-Kamara-Ostrovsky Constructions of Searchable Encryption
Further Reading: Student Presentation by Victor
2014-04-24 Private Databases III
  • Student Presentation on Searchable Encryption
Student Presentation by Divya
5 2014-04-29 Computing Over Encrypted Data I
  • Introduction to Fully Homomorphic Encryption (FHE)
  • Lattice-based Cryptography
2014-05-01 Computing Over Encrypted Data II
  • Learning with Error
6 2014-05-06 Computing Over Encrypted Data III
  • Student Presentation: The Brakerski-Gentry-Vaikuntanathan FHE Construction
Student Presentation by Jason
2014-05-08 Computing Over Encrypted Data IV
  • Student Presentation: The Lopez-Tromer-Vaikuntanathan FHE Construction
Further Reading: Student Presentation by Akhila
7 2014-05-13 Secure Multi-Party Computation I
  • Introduction to Secure Multi-Party Computation (MPC) protocols---Two-party, Semi-Honest Security Case
  • Oblivious Transfer (OT)
  • Construction of Semi-Honest Secure Two-Party Computation (2PC) protocols using Yao's Garbled Circuits
2014-05-15 Secure Multi-Party Computation II
  • Introduction to Malicious Security
  • Example: Zero-Knowledge Protocols
Further Reading: Lecture
8 2014-05-20 Secure Multi-Party Computation III
  • Student Presentation: Goldreich-Micali-Wigderson Construction of MPC Protocols.
Student Presentation by Chirs and Omer
2014-05-22 Secure Multi-Party Computation IV
  • Student Presentation: shelat-Shen Construction of Efficient 2PC protocols.
Student Presentation by Morgan and Asad
9 2014-05-27 Verifiable Outsourcing of Computation I
  • Model of Outsourcing of Computation and the Correctness Concern
  • Introduction to Universal Argument
  • Collision Resistant Hash Functions and PCP proofs
2014-05-29 Verifiable Outsourcing of Computation II
  • Student Presentation: Barak-Goldreich Construction of Universal Argument
Student Presentation by Fish
10 2014-06-03 Verifiable Outsourcing of Computation III
  • Student Presentation: Bitansky-Canetti-Chiesa-Tromer Construction of Succinct Non-Interactive Arguments of Knowledge
Further Reading: Student Presentation
2014-06-05 Student Projects Presentation

Resources and References:

Additional reading material will be communicated during class.