Secure Computation

Overview

Secure multi-party computation allows a network of mutually distrustful players, each holding a secret input, to run an interactive protocol in order to evaluate a function on their joint inputs in a secure way, i.e. without revealing anything more than what the output of the function might reveal.

Secure computation is an abstraction of several important applications, including electronic voting, digital auctions, zero knowledge, and more. The course is thought as an introduction to secure computation, and will cover both its theoretical foundations and its applications to practical settings such as distributed ledgers and cryptographic currencies.

Syllabus

• Computing over encrypted data: Equivalence between semantic security and CPA security. Fully-homomorphic encryption (FHE) and somewhat-homomorphic encryption (SHE). The Learning with Errors (LWE) assumption. Constructing SHE from LWE. Bootstrapping theorems.
• Secure two-party computation (2PC): Two-party protocols and definitions for passive and active security. Sequential composition theorem. Zero knowledge for NP. Coin tossing by telephone. Oblivious transfer. Yao's garbled circuits protocol and its optimizations.
• Secure multi-party computation (MPC): Multi-party protocols and definitions for passive and active security. Secret sharing schemes. MPC with honest majority. The SPDZ protocol.
• Cryptocurrencies: The Bitcoin protocol. Distributed ledgers, smart contracts, and altcoins. Applications to secure computation.

Teaching Material

The slides for the course can be downloaded from here. The following books are also suggested as further references:

• [1] Yehuda Lindell (Editor). Tutorials on the Foundations of Cryptography (dedicated to Oded Goldreich). Springer, 2017.
• [2] Carmit Hazay and Yehuda Lindell. Efficient Secure Two-Party Protocols, Springer, 2010.
• [3] Ronald Cramer, Ivan Bjerre Damgård, Jesper Buus Nielsen. Secure Multiparty Computation and Secret Sharing. Cambridge University Press, 2015.

Logistics

Lectures time:

• Tuesday 10:30 - 13:00.
• Wednesday 16:30 - 19:00.

Location: Aula G50, 3rd Floor, Building G, Viale Regina Elena 295, 00161 Rome.

Twitter: @SapienzaCrypto

Grading

Oral exam (70%); Project/Paper presentation (30%).

Announcements

• 11/02/2019: The course will start on February 26, 2019.
• 26/02/2019: For logistics reasons, all the lectures on Tuesday are moved to Aula G50.