# Fall 2018 Crypto Day

Date: Thursday, December 13th
Location:  University of Maryland, A.V. Williams Building, 4172.
Parking: Here, for $3 / hour. Shuttle: from College Park Metro. Take a left out of the fare gates. Look for the 104 Shuttle bus, and exit at the first stop on campus. Time: 10:00-4:30 Lunch: Look here. (Vigilante Coffee is a good place for coffee.) Program (subject to change): • 9:30-10:00AM: Welcome breakfast • 10:00 – 10:45AM: Babis Papamanthou • 11AM-11:45PM: Gilad Asharov • 11:45PM-12:30PM: Prabhanjan Ananth • 12:30 – 2PM: Lunch (on your own) • 2pm-2:45PM: Phi Hung Le • 2:45-3:30PM: Marcella Hastings • 3:45-4:30PM: Erica Blum Speaker: Babis Papamanthou Title: Searchable Encryption with Optimal Locality: Achieving Sublogarithmic Read Efficiency. Abstract: We propose the first linear-space searchable encryption scheme with constant locality and sublogarithmic read efficiency, strictly improving the previously best known read efficiency bound (Asharov et al., STOC 2016) from to where for any fixed and where N is the number of keyword-document pairs. Our scheme employs four different allocation algorithms for storing the keyword lists, depending on the size of the list considered each time. For our construction we develop (i) new probability bounds for the offline two-choice allocation problem; (ii) and a new I/O-efficient oblivious RAM with bandwidth overhead and zero failure probability, both of which can be of independent interest. Speaker: Gilad Asharov Title: OptORAMa: Optimal Oblivious RAM Abstract: Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the programs’ secret inputs. To compile a general program to an oblivious counterpart, it is well-known that$\Omega(\log N)$amortized blowup is necessary, where$N$is the size of the logical memory. This was shown in Goldreich and Ostrovksy’s original ORAM work for statistical security and in a somewhat restricted model (the so called balls-and-bins model), and recently by Larsen and Nielsen (CRYPTO ’18) for computational security. A long standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this paper, we resolve this problem and present the first secure ORAM with$O(\log N)$amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et al. (FOCS ’18) who gave a construction with$O(\log N\cdot \log\log N)$amortized blowup, assuming one-way functions. One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction: Given an array of$n$elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our$O(n)$algorithm improves the previously best known deterministic or randomized algorithms whose running time is$O(n \cdot\log n)$or$O(n \cdot\log \log n)\$, respectively.

Joint work with: Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico and Elaine Shi

Speaker: Prabhanjan Ananth
Title
: Round Optimal Secure Multiparty Computation in the Honest Majority Setting
Abstract: I will present constructions of two-round secure multiparty computation protocols in the honest majority setting:
– Secure MPC for P/poly functionalities from one-way functions.
– Information-theoretically secure MPC for NC1 functionalities.
Both these protocols are secure against malicious (active) adversaries in the security with abort setting. I will also present two-round and three-round protocols with guaranteed output delivery and two-round protocols achieving computational complexity linear in the size of the functionality (ignoring additive and poly-log multiplicative factors).

Based on joint works with Arka Rai Choudhuri, Aarushi Goel and Abhishek Jain.

Speaker: Phi Hung Le
Title: Set Intersection Cardinality, and F(PSI) in the 3-party model.
Abstract: We consider set intersection on 2 sets, where the 2 input parties have access to a third, untrusted party.  We assume an honest majority among the 3 participants, but allow one malicious corruption.  We provide several new protocols for computing the cardinality of the intersection and union – a computation that  leaks less information than intersection / union We demonstrate 2 different approaches, with tradeoffs in communication and computation: one uses polynomial interpolation, and the other leverages techniques from generic 3-party computation.  We also demonstrate a new protocol for computing arbitrary functions of the set intersection.  Our results demonstrate substantial improvement over prior work in the 2-party setting.

Speaker: Marcella Hastings
Title: General Purpose Compilers for Secure Multi-party Computation
Abstract: Secure multi-party computation (MPC) allows a group of mutually distrustful parties to compute a joint function on their inputs without revealing any information beyond the result of the computation. This type of computation is extremely powerful and has wide-ranging applications in academia, industry, and government. Protocols for secure computation have existed for decades, but only recently have general-purpose compilers for executing MPC on arbitrary functions been developed. These projects rapidly improved the state of the art, and began to make MPC accessible to non-expert users by providing high-level abstractions to describe arbitrary functions and execute secure computation protocols.However, the field is changing so rapidly that it is difficult even for experts to keep track of the varied capabilities of modern frameworks.

In this talk, I will describe our recent survey of modern general-purpose frameworks for MPC.  I will discuss our evaluation criteria, describe the major limitations of the current set of state-of-the-art frameworks, and make recommendations for future directions in compiler development

Speaker: Erica Blum

Title: Provable Consistency Guarantees in Proof-of-Stake Blockchains
Abstract: Blockchain ledgers are decentralized data structures. A natural consequence of this decentralization is that a snapshot of different users’ local version of the blockchain may not always be exactly the same. In order for the ledger to be useful, hopefully such discrepancies are limited to a few recent blocks at the end of the chain. But how many? Previous state of the art for Proof-of-Stake blockchains proved that honest users need to remove Θ(k^2) blocks in order for the consistency error to be exponentially decreasing in k. Our recent work improves the length of this suffix to Θ(k) blocks, thus matching the linear consistency achieved by Proof-of-Work blockchains. (Based on work done jointly with Aggelos Kiayias, Cristopher Moore, Saad Quader, and Alexander Russell.)