# Friday, May 12 at Boston University

UPDATE: Videos from the Crypto Day are now posted here. Enjoy!

Join us for the second Charles River Crypto Day of 2017 on Friday, May 12 at Boston University.

**To help us plan for the event, please register here**.

**When:** Friday, May 12.

**Where:** Hariri Seminar Room, 111 Cummington Mall Room 180, Boston MA.

**Organizers:** Ran Canetti, Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.

**Thanks:** NSF MACS Project for their generous support.

### Program:

9:30 – 10:00. | Introduction/Coffee/Light Breakfast |

10:00 – 10:50. |
Raluca Ada Popa, UC Berkeley
An Oblivious and Encrypted Distributed Analytics Platform |

11:00 – 11:50. |
Justin Holmgren, MIT
Delegation with Nearly Minimal Time-Space Overhead |

12:00 – 1:30. | Lunch (provided) |

1:30 – 2:20. |
Fabrice Ben Hamouda, IBM Research
On the Robustness of Non-Interactive Multi-Party Computation |

2:30 – 3:20. |
Abhi Shelat, Northeastern
Full Accounting for Verifiable Outsourcing |

3:30 – 3:50. | Coffee Break |

3:50 – 4:40. |
Eran Tromer, Tel Aviv University and Columbia University
PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations |

4:40. | Ushering of Summer Reception |

### Abstracts:

**TITLE: **An Oblivious and Encrypted Distributed Analytics Platform

**SPEAKER:** Raluca Ada Popa, Berkeley

**ABSTRACT:**

Many systems run rich data analytics on sensitive data in the cloud, but are prone to data

breaches. A recent hardware enclave architecture promises data confidentiality and isolated

execution of arbitrary computations, yet still suffers from leakage due to memory and network accesses patterns. In this talk, I will describe Opaque, a distributed data analytics platform supporting a wide range of queries while protecting the data. Even a compromised operating system sees only encrypted data. Opaque also protects against leakage from memory and network accesses outside of the enclave (a property called obliviousness). To accomplish this goal, Opaque introduces new distributed oblivious relational operators, as well as new query planning techniques to optimize these new operators. Opaque is implemented on Spark SQL with few changes to the underlying system. Opaque provides data encryption, authentication, and computation verification with a performance ranging from 52% faster to 3.3x slower than vanilla Spark SQL; obliviousness comes with a 1.6–46x overhead. At the same time, Opaque provides an improvement of three orders of magnitude over state-of- the-art oblivious protocols.

Joint work with W. Zheng, A. Dave, J. G. Beekman, J. E. Gonzalez, and I. Stoica.

**TITLE: **Delegation with nearly minimal time-space overhead

**SPEAKER:** Justin Holmgren, MIT

**ABSTRACT:**

Consider a scenario in which a client wants to utilize a powerful, but untrusted, server to

perform computations which are beyond the client’s ability. Since the client does not trust the server, we would like the server to certify the correctness of the result. We would like the verification procedure to be extremely efficient, whereas the complexity of proving shouldn’t be much larger than that of computing.

Assuming LWE, we construct a one-round argument-system for proving the correctness of any

time T and space S computation, in which both the verifier and prover are extremely efficient. In particular, the prover runs in time T * poly(k) and space S + poly(k), where k is a security parameter.

Our result builds on a line of work initiated by Kalai et al. (STOC, 2014). The prover in all of these works runs in time T^c for a large constant c (where c is at least 3). As an additional contribution we significantly simplify a central construct that appears in all of these works.

Joint work with Ron Rothblum.

**TITLE: **On the Robustness of Non-Interactive Multi-Party Computation

**SPEAKER:** Fabrice Ben Hamouda, IBM

**ABSTRACT:**

Non-Interactive Multiparty Computation (Beimel et al., Crypto 2014) is a very powerful notion equivalent (under some corruption model) to garbled circuits, Private Simultaneous Messages protocols, and obfuscation. We present robust solutions to the problem of Non-Interactive Multiparty Computation in the computational and information-theoretic models. Our results include the first efficient and robust protocols to compute any function in NC1 for constant-size collusions, in the information-theoretic setting and in the computational setting, to compute any function in P for constant-size collusions, assuming the existence of one-way functions. Our constructions start from a Private Simultaneous Messages construction (Feige, Killian Naor, STOC 1994 and Ishai, Kushilevitz, ISTCS 1997) and transform it into a Non-Interactive Multiparty Computation for constant-size collusions.

We also present a new Non-Interactive Multiparty Computation protocol for symmetric functions with significantly better communication complexity compared to the only known one of Beimel et al.

This is joint work with Hugo Krawczyk and Tal Rabin.

**TITLE: ** Full accounting for verifiable outsourcing

**SPEAKER:** Abhi Shelat, Northeastern

**ABSTRACT:**

Systems for verifiable outsourcing incur costs for a prover, a verifier, and precomputation; outsourcing makes sense when these costs are cheaper than not outsourcing. Yet, prover costs are generally ignored. The only exception is Verifiable ASICs~(VA), wherein the prover is a custom chip; however, the only prior VA system ignores the cost of precomputation.

This paper describes a new VA system, called Giraffe; charges Giraffe for all three costs; and identifies regimes where outsourcing is worthwhile. Giraffe’s base is an interactive proof geared to data parallel computation. Giraffe makes this protocol asymptotically optimal for the prover, i.e., for a large enough batch size, the prover’s running time is linear in the total number of gates in the arithmetic circuit (whereas prior work incurs an extra log(width of circuit) factor).

Giraffe wins even when outsourcing several tens of sub-computations, scales to 500X larger computations than prior work, and can profitably outsource parts of programs that are not worthwhile to outsource in full.

Joint work with Riad Wahby, Ye Ji, Andrew J Blumberg, Justin Thaler, Michael Walfish and Thomas Wies.

**TITLE: ** PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations

**SPEAKER:** Eran Tromer, Tel Aviv University and Columbia University

**ABSTRACT:**

Authenticating images that claim to depict real events is desirable in many context. Some

cameras already attach digital signatures to photographs, but plain signatures become invalid when the image undergoes legitimate processing such as cropping, rotation, brightness-adjustment or compression. Prior attempts to address this need had inadequate functionality and/or security.

We present PhotoProof, a new approach to image authentication based on cryptographic proofs. It can be configured according to application requirements, to allow any permissible set of (efficiently computable) transformations. Starting with a signed image, the scheme attaches, to each legitimately derived image, a succinct proof of computational integrity attesting that the transformation was permissible. Anyone can verify these proofs, and generate updated proofs when applying further permissible transformations. Moreover, the proofs are zero-knowledge so that, for example, an authenticated cropped image reveals nothing about the cropped-out regions.

PhotoProof is based on Proof-Carrying Data (PCD), a cryptographic primitive for verified

execution of distributed computations, built on top of zero-knowledge SNARK proofs. We will

discuss the scheme, its implementation, and possible extensions to other forms of data provenance.

Joint with with Assa Naveh.