Monthly Archives: April 2016

May 6, 2016 (Friday) at Columbia

Located at 530 West 120th Street, New York, NY


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 Multi-Party 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


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 wooden-glass 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.


Tal Rabin (IBM)
with the help and support of Tal Malkin (Columbia).


Some travel support for NYC Crypto Day is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.


  • 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 multi-party 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 Multi-Party Computation using a Global Transaction Ledger/ Vassilis Zikas (RPI)
    Classical results on secure multi-party 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 denial-of-service attack without having to suffer a monetary penalty. Our robust MPC protocol requires only a constant number of (coin-transfer 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 Hong-Sheng Zhou.
  • Probabilistic Termination and Composability of Cryptographic Protocols/ Juan Garay (Yahoo! Research)
    When analyzing the round complexity of multi-party 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 sub-linear (in the number of corrupted parties) number of rounds.
    The seminal works of Rabin and Ben-Or 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 point-to-point channels with probabilistic termination and expected constant round complexity. However, absent a rigorous simulation-based definition, the suggested protocols are  proven secure in a property-based manner or via ad hoc simulation-based frameworks, therefore guaranteeing limited, if any, composability.
    In this work, we put forth the first simulation-based treatment of multi-party cryptographic protocols with probabilistic termination. We define secure multi-party computation (MPC) with probabilistic termination in the UC framework, and prove a universal composition theorem for probabilistic-termination protocols. Our theorem allows to compile a protocol using deterministic-termination hybrids into a protocol that uses expected constant-round 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$-out-of-$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 lower-bound 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 state-of-the-art 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

%d bloggers like this: