Day 1 — December 21st  
08:3008:45  Registration  Lobby of RM 1315 
08:4509:00  Opening speech  RM 1315 
Session: Distributed Systems Chair: Elaine 

09:0010:00  Lorenzo Alvisi, Cornell  
Title: The Pit and the Pendulum
Abstract: Since the elegant foundations of transaction processing were established in the mid 70’s with the notion of serializability and the codification of the ACID (Atomicity, Consistency, Isolation, Durability) paradigm, performance has not been considered one of ACID’s strong suits, especially for distributed data stores. Indeed, the NoSQL/BASE movement of the last decade was born out of frustration with the limited scalability of traditional ACID solutions, only to become itself a source of frustration once the challenges of programming applications in this new paradigm began to sink in. But how fundamental is this dichotomy between performance and ease of programming? In this talk, I will share what my students and I have recently learned while trying to overcome the traditional terms of this classic tradeoff. 

10:0010:15  Tea Break / Group Photo  Lobby of RM 1315 
10:1511:15  Rafael Pass, Cornell Tech  RM 1315 
Title: Rethinking LargeScale Consensus through Blockchains
Abstract: The literature on distributed computing (as well as the cryptographic literature) typically considers two types of players—honest ones and corrupted ones. Resilience properties are then analyzed assuming a lower bound on the fraction of honest players. Honest players, however, are not only assumed to follow the prescribed the protocol, but also assumed to be *online* throughout the whole execution of the protocol. The advent of “largescale” consensus protocols (such as e.g., the blockchain protocol) where we may have millions of players, makes this assumption unrealistic. In this work, we initiate a study of distributed protocols in a “sleepy” model of computation, where players can be either online (awake) or offline (asleep), and their online status may change at any point during the protocol. The main question we address is: Can we design consensus protocols that remain resilient under “sporadic participation”, where at any given point, only a subset of the players are actually online? As far as we know, all standard consensus protocols break down under such sporadic participation, even if we assume that 99% of the online players are honest. Our main result answers the above question in the affirmative, assuming only that a majority of the online players are honest. Perhaps surprisingly, our protocol significantly departs from the standard approaches to distributed consensus, and we instead rely on key ideas behind Nakamoto’s blockchain protocol (while dispensing with “proofsofwork”). Based on joint work with Iddo Bentov and Elaine Shi. 

11:1511:30  Mingle  
11:3012:30  Robbert van Renesse, Cornell  
Title: Federated Consensus
Abstract: The robustness of distributed systems is usually phrased in terms of the number of failures of certain types that they can withstand. However, these failure models are too crude to describe the different kinds of trust and expectations of participants in the modern world of complex, integrated systems extending across different owners, networks, and administrative domains. Modern systems often exist in an environment of heterogeneous trust, in which different participants may have different opinions about the trustworthiness of other nodes, and a single participant may consider other nodes to differ in their trustworthiness. We explore how to construct distributed protocols that meet the requirements of all participants, even in heterogeneous trust environments. 

12:3014:00  working lunch, mingle, lunch talks Chair: Antonio Marcedone 
RM 1222 
12:4013:00  Lunch talk 1: Ling Ren, MIT  
Title: Solidus: An Incentivecompatible Cryptocurrency Based on Permissionless Byzantine Consensus
Abstract: The decentralized cryptocurrency Bitcoin has experienced great success. 

13:0013:20  Lunch talk 2: Chang Liu, Berkeley  
Title: Exploring New Attack Space on Adversarial Deep Learning
Abstract: An intriguing property of deep neural networks is the existence of adversarial examples, which can transfer among different architectures. These transferable adversarial examples may severely hinder deep neural networkbased applications. Previous works mostly study the transferability using small scale datasets. In this work, we are the first to conduct an extensive study of the transferability of large models and a largescale dataset, and we are also the first to study the transferability of targeted adversarial examples with their target labels. We study both nontargeted and targeted adversarial examples, and show that while transferable nontargeted adversarial examples are easy to find, targeted adversarial examples generated using existing approaches almost never transfer with their target labels. Therefore, we propose novel ensemblebased approaches to generating transferable adversarial examples. Using such approaches, we observe a large proportion of targeted adversarial examples that are able to transfer with their target labels for the first time. We also present some geometric studies to help to understand the transferable adversarial examples. Finally, we show that the adversarial examples generated using ensemblebased approaches can successfully attack Clarifai.com, which is a blackbox image classification system. 

13:2014:00  Rump session I: 3 talks + 1 demo  
“Implementing and Scaling Provably Secure Proof of Stake” – Philip Daian “Breaking Web Applications built on top of Encrypted Data” – Paul Grubbs “Towards Formally Verified Cryptographic Protocols” – Joshua Gancher Demo — Wei Xu’s group 

14:0014:15  Break  
Session: Multiparty computation and interactive protocols Chair: Rafael Pass 
RM 1315  
14:1515:00  Andrew ChiChih Yao, Tsinghua University  
Title: Privacy Loss and Information Complexity
Abstract: How much private information is leaked in any given multiparty protocol? How many bits must be encrypted to protect the private information from leaking out? First raised in 2001, the concept of Information Complexity has been found extremely useful in addressing such issues. In this talk, we present some new results in information complexity and their applications to privacy loss. 

15:0015:30  Tea Break  
15:3016:00  Muthuramakrishnan Venkitasubramaniam, Rochester  
Title: Equivocating Yao: ConstantRounds Adaptively Secure Multiparty Computation in the Plain Model
Abstract: Yao’s circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable twomessage, twoparty secure computation, the scheme has been extended in many ways and has inumberable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds? We provide a positive answer to this question. We define a new type of encryption, called functionally equivocal encryption (FEE), and show that when Yao’s scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function. Combining our scheme with noncommitting encryption, we obtain the first twomessage, twoparty computation protocol, and the first constantrounds multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. We also provide extensions to the multiparty setting (with UCsecurity) and applications to leakage resilience. 

16:0016:30  Hubert Chan, HKU  
Title: Circuit OPRAM: A (Somewhat) Tight Oblivious Parallel RAM
Abstract: An Oblivious Parallel RAM (OPRAM) provides a general method to simulate any Parallel RAM (PRAM) program, such that the resulting memory access patterns leak nothing about secret inputs. OPRAM was originally proposed by Boyle et al. as the natural parallel counterpart of Oblivious RAM (ORAM). Although prior work (in particular, Circuit ORAM) has shown how to construct ORAM schemes that are asymptotically tight under certain parameter ranges, the performance of known OPRAM schemes still do not match their sequential counterparts, leaving open two main questions: (i) whether one can construct an OPRAM scheme whose performance is competitive relative to known sequential counterparts; and (ii) whether one can construct OPRAM schemes that are asymptotically optimal. In our new work, we construct Circuit OPRAM, a new OPRAM scheme that makes the following contributions: 1. We achieve asymptotical improvement in terms of both total work and parallel runtime in comparison with known OPRAM schemes. More specifically, we improve the total work by a logarithmic factor and parallel runtime by polylogarithmic factors. 2. We show that under sufficiently large block sizes, we can construct an OPRAM scheme that is asymptotically optimal both in total work and parallel runtime when the number of CPUs is not too small. 

16:3017:00  Antigoni Polychroniadou, Aarhus  
Title: Laconic Receiver Oblivious Transfer And Its Applications
Abstract: In this talk we will introduce a new technique for secure computation in the setting of large data sizes. Based on the Decisional DiffieHellman (DDH) Assumption we provide a new oblivious transfer (OT) protocol with a laconic receiver — specifically, the laconic OT allows the receiver to commit to an arbitrary many choice bits (with a short message) and the sender to send its OT response messages for any number of the receiver’s committed choice bit. Such an OT is apt for realizing securing computation over large data. In particular, we show applications of laconic OT to noninteractive secure computation and homomorphic encryption for RAM programs. 

18:00  Dinner in Hotel 
Day 2 — December 22nd  
Session: Hardware Chair: Robbert van Renesse 
RM 1315  
09:0010:00  Ed Suh, Cornell  
Title: Secure MultiCore Processors with Comprehensive and Verifiable Information Flow Control
Abstract: As computing devices are increasingly shared by multiple software entities, hardwarelevel protection for critical software is essential for a strong security guarantee. This talk will show how static information flow analysis and microarchitecture timingchannel protection can be used to build a multicore system with comprehensive and verifiable information flow assurance, and briefly discuss how such a system can be leveraged in the context of a selfdriving car to protect safetycritical functions. The first part of the talk will introduce a secure hardware design language, named SecVerilog, which enables designers to statically analyze information flow at the hardware level and thus to build systems where information channels are verifiably controlled. SecVerilog is Verilog, extended with security type annotations, and provides rigorous formal assurance that a hardware design enforces timingsensitive noninterference. Our experiences suggest that SecVerilog can be used to verify security properties of realistic hardware designs with low overhead. For example, we used SecVerilog to build a processor with a verifiable guarantee on timing channel protection as well as to detect implementation bugs in hardware security architecture similar to ARM TrustZone. 

10:0010:15  Tea Break  
Session: Cryptography, Theory Chair: Andrew ChiChih Yao 

10:1510:45  John Steinberger, Tsinghua  
Title: Provable Security of SubstitutionPermutation Networks
Abstract: A number of popular block ciphers (such as AES128, among others) are built on a soscalled “substitutionpermutation network” (SPN) paradigm. In this talk we discuss recent work investigating SPNs in an idealised paradigm, in which the Sboxes are modeled as random permutations. We show that a small number of rounds (1 or 3, depending on whether nonlinear key schedules are allowed) suffice to attain birthdaytype security on the Sbox input length. We will introduce a number of (rather cute!) nonlinear key schedules, that offer different structural tradeoffs for the network and that achieve provable security. 

10:4511:15  Yu Yu, Shanghai Jiao Tong University  
Title: Some Recent Progress on Cryptography from Learning Parity with Noise
Abstract: Learning Parity with Noise (LPN) is a notoriously hard problem in learning theory and coding theory. It represents the wellknown NPC problem “decoding random linear codes” and its averagecase hardness is also well studied. Recently, there has been renewed interest in building provably secure cryptosystems from LPN. This talk will introduce the LPN problem and some recent progress on LPNbased cryptographic schemes such as pseudorandom generators in AC0(mod 2), pseudorandom functions in almost constant depth, and publickey encryption schemes. The is a combination of two works (jointly with John Steinberger at EUROCRYPT 2016 and Jiang Zhang at CRYPTO 2016 respectively). 

11:1511:45  Xiongfeng Ma, Tsinghua  
Title: From quantumness to security in quantum cryptography
Abstract: Coherence and entanglement are two peculiar features of quantum theory. Coherence captures the phenomenon of coherent superposition of quantum states, while entanglement, “the spooky action at a distance”, plays a crucial role in the nonlocality of quantum mechanics. In this talk, I shall present two links: between coherence and randomness in quantum random number generation, and between entanglement and security in quantum key distribution. Random numbers play an indispensable role in modern society in various arenas of finance, cryptography, and computation. Considering individual and coherent measurement of the correlated party, we show that the coherence of formation and the relative entropy of coherence measure the quantum randomness for these two situations, respectively. Furthermore, we calculate the gap between the two quantum randomness, which turns out to related another quantum correlation — discord. In quantum information processing, entanglement becomes an important resource for various tasks, such as teleportation, quantum computation, and cryptography. Intuitively, entanglement means a strong nonlocal correlation between distant parties, which essentially offers a secure key generation tool. Various Bell’s inequality test experiments have proved that eavesdropping (as a local hidden variable) can be fundamentally ruled out. In this talk, I shall link the basic concept of entanglement with the security of key distribution. 

11:4512:15  KaiMin Chung, Academia Sinica  
Title: Computational Notions of Quantum MinEntropy
Abstract: Computational notions of entropy have many applications in cryptography and complexity theory. These notions measure how much (min)entropy a source $X$ has from the eyes of a computationally bounded party who may hold certain “leakage information” $B$ that is correlated with $X$. In this work, we initiate the study of computational entropy in the *quantum* setting, where $X$ and/or $B$ may become quantum states and the computationally bounded observer is modelled as a small quantum circuit. Specifically, we investigate to what extent the classical notions of computational entropy generalize to the quantum setting, and whether quantum analogues of classical theorems still hold. For example, we show: – There exist quantum states that are *pseudorandom* (i.e. they cannot be distinguished from the totally mixed state by polynomialsized quantum circuits) but have actual entropy 0 (i.e. are pure states). In contrast, a classical distribution needs superlogarithmic entropy to be pseudorandom. – We extend the classical Leakage Chain Rule for pseudoentropy to the case where the leakage information $B$ is quantum (while $X$ remains classical). Specifically, if $X$ has pseudoentropy at least $k$ against quantum distinguishers (i.e. it is indistinguishable from some distribution of minentropy at least $k$ by polynomialsized quantum distinguishers) and $B$ consists of at most a logarithmic number $\ell$ of qubits, then $X$ conditioned on $B$ has pseudoentropy at least $k\ell$ against quantum distinguishers. – We show that a general form of the classical Dense Model Theorem (interpreted as showing the equivalence between two definitions of pseudorelativeminentropy) does *not* extend to quantum states. Along the way, we develop quantum analogues of a number of classical techniques (e.g. the Leakage Simulation Lemma, proven using a Nonuniform MinMax Theorem or Boosting), and also identify classical techniques (namely, Gap Amplification) that do not hold in the quantum setting. Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, which raise a number of directions for future work. Joint work with YiHsiu Chen, ChingYi Lai, Salil Vadhan, and Xiaodi Wu 

12:1513:30  working lunch, lunch talks, mingle Session Chair: Phil Daian  RM 1222 
12:3013:00  Lunch talk: Qiang Tang, NJIT  
Title: Cliptography: PostSnowden Cryptography
Abstract: Despite the laudatory history of development of modern cryptography, an implicit assumption that the implementations are trusted has been made in (essentially) all security definitions. While the dangers of entertaining adversarial implementation of cryptographic primitives seem obvious, the ramifications of such attacks are surprisingly dire: it turns out that—in wide generality—adversarial implementations of cryptographic (randomized) algorithms may leak private information while producing output that is statistically indistinguishable from that of a faithful implementation. I will first briefly describe the intuition about the above subliminal channel attacks. Inspired by some folklore practical wisdom, I will also introduce some simple but rigorous immunizing strategies on subverted randomized algorithms. 

13:0013:30  FengHao Liu, Florida Atlantic University  
Title: Compact Identity Based Encryption from LWE
Abstract: We construct an identitybased encryption (IBE) scheme from the standard Learning with Errors (LWE) assumption that has \emph{compact} publickey and achieves adaptive security in the standard model. In particular, our scheme only needs 2 public matrices to support $O(\log^2 \secparam)$bit length identity, and $O(\secparam / \log^2 \secparam)$ public matrices to support $\secparam$bit length identity. This improves over previous IBE schemes from lattices substantially. Additionally, our techniques from IBE can be adapted to construct a compact digital signature scheme, which achieves existential unforgeability under the standard Short Integer Solution (SIS) assumption with small polynomial parameters. Joint work with Daniel Apon and Xiong Fan 

13:3014:00  Rump session II: 3 talks “Tolerating Password Typos: A securityusability tradeoff.” – Rahul Chatterjee ‘’Hash Garbled Circuits for Free’’ – Xiong Fan “Practical Secure Aggregation for PrivacyPreserving Machine Learning” – Antonio Marcedone “Immutability: This is the database property you are looking for” – Kai Mast 

14:0014:20  Ending notes  
14:20  Activities 