September 25, 2019 Practical Proof Systems: Implementations, Applications, and Next Steps
Speaker: Riad Wahby
Abstract: This talk sketches the built proof systems landscape, and discusses current and potential future applications of these systems in practice. The focus is both on the relative strengths and weaknesses of existing approaches and on the challenges common to all systems. We close with a brief "wish list" of open problems that have the potential to reshape this exciting research area.
October 02, 2019 Creating a Scalable Bank: A Case Study in using Cryptographic Proof Systems
Speaker: Alex Ozdemir
Abstract: Last week, in this seminar, Riad Wahby introduced a number of generic cryptographic proof systems and discussed their properties. This week we'll look at a particular application of these proof systems: the creation of a distributed bank which protects privacy and scales well. At a a high level, this talk will cover recent techniques for maintaining accumulated state. At a low level, it will give the audience a feel for the primitives provided by these systems, and what programming with them looks like.
October 09, 2019 CoSMIX: A Compiler-based System for Secure Memory Instrumentation and Execution in Enclaves
Speaker: Yan Michalevsky
Abstract: Hardware secure enclaves are increasingly used to run complex applications. Unfortunately, existing and emerging enclave architectures do not allow secure and efficient implementation of custom page fault handlers. This limitation impedes in-enclave use of secure memory-mapped files and prevents extensions of the application memory layer commonly used in untrusted systems, such as transparent memory compression or access to remote memory. CoSMIX is a Compiler-based system for Secure Memory Instrumentation and eXecution of applications in secure enclaves. A novel memory store abstraction allows implementation of application-level secure page fault handlers that are invoked by a lightweight enclave runtime. The CoSMIX compiler instruments the application memory accesses to use one or more memory stores, guided by a global instrumentation policy or code annotations without changing application code. The CoSMIX prototype runs on Intel SGX and is compatible with popular SGX execution environments, including SCONE and Graphene. Our evaluation of several production applications shows how CoSMIX improves their security and performance by recompiling them with appropriate memory stores. For example, unmodified Redis and Memcached key-value stores achieve about 2× speedup by using a self-paging memory store while working on datasets up to 6× larger than the enclave’s secure memory. Similarly, annotating a single line of code in a biometric verification server changes it to store its sensitive data in Oblivious RAM and makes it resilient against SGX side-channel attacks.
Paper: USENIX ATC '19
October 16, 2019 iOS13 security
Speaker: Himanshu Dwivedi (Data Theorem)
October 23, 2019 Transparent SNARKs from DARK Compilers
Speaker: Ben Fisch
Abstract: We construct a new polynomial commitment scheme for univariate and multivariate polynomials over finite fields, with public-coin evaluation proofs that have logarithmic communication and verification cost in the number of coefficients of the polynomial. The underlying technique is a Diophantine Argument of Knowledge (DARK), leveraging integer representations of polynomials and groups of unknown order. Security is shown from the strong RSA and the adaptive root assumption. Moreover, the scheme does not require a trusted setup if instantiated with class groups. We apply this new cryptographic compiler to a restricted class of algebraic linear IOPs in order to obtain doubly-efficient public-coin IPs with succinct communication and witness-extended emulation for any NP relation. Allowing for linear preprocessing, the online verifier's work is logarithmic in the circuit complexity of the relation. In particular, we obtain quasi-linear prover time when compiling the IOP employed in Sonic (MBKM, CCS 19). Applying the Fiat-Shamir transform in the random oracle model results in a SNARK system with quasi-linear preprocessing, quasi-linear (online) prover time, logarithmic proof size, and logarithmic (online) verification time for arbitrary circuits. The SNARK is also concretely efficient with 7.8KB proofs (70× reduction over state of the art) and 75ms verification time for circuits with 1 million gates. Most importantly, this SNARK is transparent: it does not require a trusted setup. We also obtain zk-SNARKs by applying a variant of our polynomial commitment scheme that is hiding and offers zero-knowledge evaluation proofs. This construction is the first transparent zk-SNARK that has both a practical prover time as well as asymptotically logarithmic proof size and verification time. We call this system *Supersonic*.
Joint work with: Benedikt Bünz and Alan Szepieniec
Paper: ePrint 2019/1229
October 30, 2019 Explaining and Attacking Deep Neural Networks
Speaker: Ankur Taly
Abstract: Abstract: Deep Neural Networks (DNN) have been causing a revolution in several fields, including, science and technology, finance, healthcare, cyber-security, etc. For instance, they can identify objects in images, perform language translation, enable web search, perform medical diagnosis — all with surprising accuracy. Unfortunately, much of this progress has come at the cost of the models becoming highly complex and hard to interpret. An overarching question that arises is why did the model make this prediction? This question is of importance to developers in debugging (mis-)predictions and identifying model blind spots, to evaluators in assessing the robustness and fairness of the model, and to end-users in deciding whether they can trust the model. In this talk, I will focus on the problem of understanding individual predictions by attributing them to input features — a problem that has received a lot of attention in the last couple of years. First, I will describe an attribution method, called Integrated Gradients (ICML 2017), that is applicable to a variety of DNN architectures, and is backed by an axiomatic justification. I will then present an application of Integrated Gradients in surfacing vulnerabilities in the DNN’s prediction logic, and crafting attacks (adversarial examples) that exploit those vulnerabilities. I will discuss several attacks against leading DNN models for various question answering tasks. Our strongest attack drops the accuracy of a visual question answering model from 61.1% to 19%, and that of a tabular question answering model from 33.5% to 3.3%. Time permitting, I will also discuss attacks on DNNs classifying drug molecules. This talk is based on joint work with several colleagues at Google Research.
November 06, 2019 PIR with sublinear online time
Speaker: Dima Kogan
Abstract: We present the first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements. To achieve these efficiency goals, our protocols work in an offline/online model. In an offline phase, which takes place before the client has decided which database bit it wants to read, the client fetches a short string from the servers. In a subsequent online phase, the client can privately retrieve its desired bit of the database by making a second query to the servers. By pushing the bulk of the server-side computation into the offline phase (which is independent of the client's query), our protocols allow the online phase to complete very quickly—in time sublinear in the size of the database. Finally, we prove that our protocols are optimal in terms of the trade-off they achieve between communication and running time.
Joint work with: Henry Corrigan-Gibbs
Paper: ePrint 2019/1075
November 13, 2019 Guard Placement Attacks on Path Selection Algorithms for Tor
Speaker: Gerry Wan
Abstract: The popularity of Tor has made it an attractive target for a variety of deanonymization and fingerprinting attacks. Location-based path selection algorithms have been proposed as a countermeasure to defend against such attacks. However, adversaries can exploit the location-awareness of these algorithms by strategically placing relays in locations that increase their chances of being selected as a client's guard. Being chosen as a guard facilitates website fingerprinting and traffic correlation attacks over extended time periods. In this work, we rigorously define and analyze the guard placement attack. We present novel guard placement attacks and show that three state-of-the-art path selection algorithms—Counter-RAPTOR, DeNASA, and LASTor—are vulnerable to these attacks, overcoming defenses considered by all three systems. For instance, in one attack, we show that an adversary contributing only 0.216% of Tor’s total bandwidth can attain an average selection probability of 18.22%, 84x higher than what it would be under Tor currently. Our findings indicate that existing location-based path selection algorithms allow guards to achieve disproportionately high selection probabilities relative to the cost required to run the guard. Finally, we propose and evaluate a generic defense mechanism that provably defends any path selection algorithm against guard placement attacks. We run our defense mechanism on each of the three path selection algorithms, and find that our mechanism significantly enhances the security of these algorithms against guard placement attacks with only minimal impact to the goals or performance of the original algorithms.
Paper: PETS 2019
November 20, 2019 Building Public Key Cryptography from Minicrypt Primitives with Structure
Speaker: Hart Montgomery
Abstract: Algebraic structure lies at the heart of cryptomania, and It has long been assumed by many in the cryptographic research community that there is some special relationship between mathematical structure and public key cryptography. For instance, Barak commented [Bar17] that “... it seems that you can’t throw a rock without hitting a one-way function” but public-key cryptography is somehow “special.” In the same work, Barak implicitly argues that there is some mathematical structure inherent in public-key cryptography: “One way to phrase the question we are asking is to understand what type of structure is needed for public-key cryptography.” The natural question is the following: can we formalize the relationship between mathematical structure and public key cryptography? It turns out we can! In this talk, I’ll explain how we can build many of the most common primitives in cryptomania from simple minicrypt primitives with structure. As an example, suppose we start with a standard weak PRF F. If we make F input-homomorphic—that is, F(k, x) + F(k, y) = F(k, x + y)—then it turns out we can use F to build many exciting cryptomania constructions, like identity-based encryption, lossy trapdoor functions, and more. We can generalize this approach further to both more simple primitives like one-way functions and unpredictable functions as well as to other structural relations, like ring homomorphisms and key homomorphisms. This generalization enables us to construct virtually all of the most common public key cryptosystems from structured minicrypt primitives, including everything from simple key exchange to indistinguishability obfuscation. Our results provide some interesting new ways to look at theoretical cryptographic research. Building new cryptosystems from structured primitives allows us to instantiate the cryptosystem from many different assumptions “for free” and showing that new assumptions imply certain structured primitives provides typically many cryptographic primitives from the assumption also “for free,” perhaps streamlining some areas of research. In addition, we can argue for the existence of a “cryptoplexity hierarchy” that classifies cryptosystems based on increasing mathematical structure that effectively models much of what we know about the black-box power of cryptosystems. This talk is based on three recent papers with a subset of Navid Alamati, Sikhar Patranabis, and Arnab Roy.
November 27, 2019 Thanksgiving
December 04, 2019 TBA
Speaker: Florian Tramèr