May 6, 2016 (Friday) at Columbia
Located at 530 West 120th Street, New York, NY
Program
9:30 – 10:00.  Introduction/Coffee 
10:00 – 10:50. 
Moti Yung (Snapchat)
Crossing the Theory–Practice Chasm: on Deploying Secure Computations Commercially 
11:00 – 11:50.  Vassilis Zikas (RPI) Fair and Robust MultiParty Computation using a Global Transaction Ledger 
12:00 – 2:00.  Lunch (not provided) 
2:00 – 2:50.  Juan Garay (Yahoo! Research) Probabilistic Termination and Composability of Cryptographic Protocols 
3:00 – 3:50.  Valerio Pastro (Columbia) Essentially Optimal Robust Secret Sharing with Maximal Corruptions 
Venue
Columbia University, the Mudd Building, Computer Science Dept
Located at 530 West 120th Street, New York, NY
CS Conference Room and Lounge: Follow directions to department office, then go through double woodenglass doors and head down hallway to left. The entrance to the CS lounge and conference room is to the right of the door leading outside to the courtyard.
http://www.cs.columbia.edu/resources/directions
Organizers
Tal Rabin (IBM)
with the help and support of Tal Malkin (Columbia).
Support
Some travel support for NYC Crypto Day is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS1523467.
Abstracts

Crossing the Theory–Practice Chasm: on Deploying Secure Computations Commercially/ Moti Yung (Snapchat)Technological innovations in security and privacy are critical to advancing modern computing in our time. I will present an experimental effort involving deployment of commercial applications designed and built as a ‘secure multiparty computation protocol for specific tasks, to be used repetitively to achieve a number of concrete ubiquitous business goals. In these applications, the outputs are calculated in the presence of privacy constraints which prevent parties from sharing their individual inputs directly and openly. I will also discuss what I think are the reasons for the inherent difficulty of developing such routines in general (for achieving business goals). In particular, I will survey what I believe to be the reasons that about 38 years since secure computation protocols was invented as a basic theoretical notion, capturing specific and then general computational tasks, and in spite of its theoretical and even more recent commendable experimentation success, the notion has not yet been widely and seriously used in achieving routine relevant business goals (in contrast with symmetric key and public key cryptosystems and protocols, which were also proposed ~40 years ago and are used extensively, primarily to implement secure authenticated channels). I will cover some of the basic methodology taken to deploy the technology.
 Fair and Robust MultiParty Computation using a Global Transaction Ledger/ Vassilis Zikas (RPI)
Classical results on secure multiparty computation (MPC) imply that fully secure computation, including fairness (either all parties get output or none) and robustness (output delivery is guaranteed), is impossible unless a majority of the parties is honest. Recently, cryptocurrencies like Bitcoin where utilized to leverage the fairness loss in MPC against a dishonest majority. The idea is that when the protocol aborts in an unfair manner (i.e., after the adversary receives output) then honest parties get compensated (in coins) by the adversarially controlled parties.We describe the first robust MPC protocol with compensation, i.e., an MPC protocol where not only fairness is guaranteed (via compensation) but additionally the protocol is guaranteed to deliver output to the parties that get engaged. This means that the adversary, after an initial round of deposits, is not even able to mount a denialofservice attack without having to suffer a monetary penalty. Our robust MPC protocol requires only a constant number of (cointransfer and communication) rounds. To prove the security of our construction, we put forth a new formal model of secure MPC with compensation and show how the introduction of suitable ledger and synchronization functionalities makes it possible to describe such protocols using standard interactive Turing machines (ITM) circumventing the need for the use of extra features that are outside the standard model as in previous works. Our model is expressed in the universal composition setting with global setup and is equipped with a composition theorem that enables the design of protocols that compose safely with each other and within larger environments alongside other protocols with compensation; such a composition theorem for MPC protocols with compensation was not known before.This is joint work with Aggelos Kiayias and HongSheng Zhou.

Probabilistic Termination and Composability of Cryptographic Protocols/ Juan Garay (Yahoo! Research)
When analyzing the round complexity of multiparty cryptographic protocols, one often overlooks the fact that underlying resources, such as a broadcast channel, can be by themselves expensive to implement. For example, it is well known that it is impossible to implement a broadcast channel by a (deterministic) protocol in a sublinear (in the number of corrupted parties) number of rounds.The seminal works of Rabin and BenOr from the early 80’s demonstrated that limitations as the above can be overcome by using randomization and allowing parties to terminate at different rounds, igniting the study of protocols over pointtopoint channels with probabilistic termination and expected constant round complexity. However, absent a rigorous simulationbased definition, the suggested protocols are proven secure in a propertybased manner or via ad hoc simulationbased frameworks, therefore guaranteeing limited, if any, composability.In this work, we put forth the first simulationbased treatment of multiparty cryptographic protocols with probabilistic termination. We define secure multiparty computation (MPC) with probabilistic termination in the UC framework, and prove a universal composition theorem for probabilistictermination protocols. Our theorem allows to compile a protocol using deterministictermination hybrids into a protocol that uses expected constantround protocols for emulating these hybrids, preserving the expected round complexity of the calling protocol.This is joint work with Ran Cohen, Sandro Coretti and Vassilis Zikas.
 Essentially Optimal Robust Secret Sharing with Maximal Corruptions/ Valerio Pastro (Columbia). In a $t$outof$n$ robust secret sharing scheme, a secret message is shared among $n$ parties who can reconstruct the message by combining their shares. An adversary can adaptively corrupt up to $t$ of the parties, get their shares, and modify them arbitrarily. The scheme should satisfy privacy, meaning that the adversary cannot learn anything about the shared message, and robustness, meaning that the adversary cannot cause the reconstruction procedure to output an incorrect message. Such schemes are only possible in the case of an honest majority, and here we focus on unconditional security in the maximal corruption setting where $n = 2t+1$.In this scenario, to share an $m$bit message with a reconstruction failure probability of at most $2^{k}$, a known lowerbound showsthat the share size must be at least $m + k$ bits. On the other hand,all prior constructions have share size that scales linearly with thenumber of parties $n$, and the prior stateoftheart scheme due to Cevallos et al. (EUROCRYPT ’12) achieves $m + \widetilde O(k + n)$.
In this work, we construct the first robust secret sharing scheme in the maximal corruption setting with $n = 2t+1$, that avoids the linear dependence between share size and the number of parties $n$. In particular, we get a share size of only $m + \widetilde{O}(k)$ bits. Our scheme is computationally efficient and relies on approximation algorithms for the minimum graph bisection problem.
Joint work with Allison Bishop, Rajmohan Rajaraman, and Daniel Wichs