Program

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.

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 “large-scale” 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 “proofs-of-work”).

Based on joint work with Iddo Bentov and Elaine Shi.

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.

Abstract: The decentralized cryptocurrency Bitcoin has experienced great success.
It has also encountered many challenges, including the low throughput and long confirmation time of transactions, and the lack of incentives to follow the protocol at multiple steps.
To address these challenges, we propose Solidus, a decentralized cryptocurrency based on a Byzantine consensus protocol adapted to the permissionless setting.
We design each component of Solidus to be incentive compatible.
With these techniques, our protocol has the potential to improve throughput and confirmation time,  and provides safety and liveness assuming a supermajority of participants are rational (the rest are Byzantine) and no large coalition exists.

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 network-based 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 large-scale dataset, and we are also the first to study the transferability of targeted adversarial examples with their target labels. We study both non-targeted and targeted adversarial examples, and show that while transferable non-targeted adversarial examples are easy to find, targeted adversarial examples generated using existing approaches almost never transfer with their target labels. Therefore, we propose novel ensemble-based 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 ensemble-based approaches can successfully attack Clarifai.com, which is a black-box image classification system.

Abstract:  How much private information is leaked in any given multi-party 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.

Abstract:  Yao’s circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party 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 non-committing encryption, we obtain the first two-message, two-party computation protocol, and the first constant-rounds multiparty computation protocol, in the plain model, that are secure against semi-honest adversaries who can adaptively corrupt all parties. We also provide extensions to the multiparty setting (with UC-security) and applications to leakage resilience.

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 poly-logarithmic 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.
This is joint work with Elaine Shi.

Abstract: In this talk we will introduce a new technique for secure computation in the setting of large data sizes. Based on the Decisional Diffie-Hellman (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 non-interactive secure computation and homomorphic encryption for RAM programs.

Abstract: As computing devices are increasingly shared by multiple software entities, hardware-level protection for critical software is essential for a strong security guarantee. This talk will show how static information flow analysis and micro-architecture timing-channel protection can be used to build a multi-core system with comprehensive and verifiable information flow assurance, and briefly discuss how such a system can be leveraged in the context of a self-driving car to protect safety-critical 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 timing-sensitive 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.

Abstract: A number of popular block ciphers (such as AES-128, among others) are built on a so-scalled “substitution-permutation network” (SPN)  paradigm. In this talk we discuss recent work investigating SPNs in an idealised paradigm, in which the S-boxes 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 birthday-type security on the S-box 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.

Abstract: Learning Parity with Noise (LPN) is a notoriously hard problem in learning theory and coding theory. It represents the well-known NPC problem “decoding random linear codes” and its average-case hardness is also well studied. Recently, there has been renewed interest in building provably secure crypto-systems from LPN. This talk will introduce the LPN problem and some recent progress on LPN-based cryptographic schemes such as pseudorandom generators in AC0(mod 2), pseudorandom functions in almost constant depth, and public-key encryption schemes. The is a combination of two works (jointly with John Steinberger at EUROCRYPT 2016 and Jiang Zhang at CRYPTO 2016 respectively).

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.

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 polynomial-sized quantum circuits) but have actual entropy 0 (i.e. are pure states).  In contrast, a classical distribution needs super-logarithmic 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 min-entropy at least $k$ by polynomial-sized 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 pseudo-relative-min-entropy) 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 Non-uniform Min-Max 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 Yi-Hsiu Chen, Ching-Yi Lai, Salil Vadhan, and Xiaodi Wu

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.

Abstract: We construct an  identity-based encryption (IBE) scheme from the standard Learning with Errors (LWE) assumption that has \emph{compact} public-key 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