InvitedTalks
Invited Talks
| Speaker: | Craig Gentry (IBM Research) |  |
|---|---|---|
| Title: | Encrypted Messages from the Heights of Cryptomania | |
| Abstract: | How flexible can encryption be? On the one hand, fully homomorphic
encryption handles computation very flexibly, but not access control;
there is only one keyholder, and only it can decrypt. On the other hand,
building on Garg et al.'s multilinear maps, we now have attribute-based
encryption schemes for circuits, which handle access control very
flexibly, but not computation; the decrypter recovers the encrypter's
message, unmodified. In between, we have concepts like obfuscation and
functional encryption that attempt, in some sense, to handle computation
and access control simultaneously. Here lies the the edge of
Cryptomania, as we bump against impossibility results for obfuscation and
incompressibility. However, the precise contours of the boundary between
possible and impossible remain unknown. In this talk, I will focus mostly on recent positive results, showing how a somewhat homomorphic variant of the NTRU encryption scheme leads quite naturally to Garg et al.'s approximate multilinear maps, and describing how to use multilinear maps to construct something beyond even attribute-based encryption for circuits: namely, a "witness encryption" scheme where a user's decryption key need not be an actual "key" at all, but rather can be a witness for some arbitrary NP relation specified by the encrypter (the encrypter itself may not know a witness). Regarding obfuscation, functional encryption, and the boundary between possible and impossible, I only promise to leave you with intriguing questions. | |
| Biography: | Craig Gentry is a research scientist in the cryptography group at the IBM Thomas J. Watson Research Center. He received his PhD in computer science from Stanford in 2009 and won the ACM Doctoral Dissertation Award and the ACM Grace Murray Hopper Award for his work on developing the first fully homomorphic encryption scheme. His research tends toward the mathematical side of applied cryptography, both constructive (designing efficient and highly functional cryptosystems) and destructive (cryptanalysis). In a past life, he was an intellectual property attorney. | |
| Speaker: | Tal Malkin (Columbia University) |  |
|---|---|---|
| Title: | Secure Computation for Big Data | |
| Abstract: | Secure computation has been a powerful and important research area in
cryptography since the first breakthrough results in the 1980s. For many
years this area was purely theoretical, as the feasibility results have
not been considered even close to practical. Recently, it appears to have
turned a corner, with several research efforts showing that secure
computation for large classes of functions, and even generic secure
computation, has the potential to become truly practical. This shift is
brought on by algorithmic advancements and new cryptographic tools,
alongside advancements in CPU speed, parallelism, and storage
capabilities; it is further motivated by the explosion of new potential
application domains for secure computation. A compelling motivation for making secure computation practical is provided by the burgeoning field of Big Data, representing the deluge of data being generated, collected, and stored all around us. Protocols for secure computation on big data can provide critical value for many business, medical, legal, and personal applications. However, conventional approaches to secure computation are inherently insufficient in this setting, where even linear computation can be too prohibitive. In this talk I will discuss challenges and solutions related to secure computation for big data, following two thrusts: (1) Overcoming inherent theoretical bounds of (in)efficiency; and (2) Satisfying immediate practical needs in a theoretically sound way. Both goals require the development of new models of secure computation, allowing for theoretically and practically meaningful relaxations of the standard model. In particular, I will discuss a few works I have participated in over the last decade, which address the challenge of achieving efficient secure computation for massive data. I will also share some experiences from the last few years working on secure search over massive data sets. This research has externally imposed practical constraints, such as strict performance requirements. I will focus on my perspective as a theoretical cryptographer and discuss some open cryptographic challenges in this emerging domain. | |
| Biography: | Tal Malkin is an associate professor of Computer Science at Columbia University, where she directs the Cryptography Lab. She received her Ph.D. in Computer Science from the Massachusetts Institute of Technology in 2000, and joined Columbia after three years as a research scientist in the Secure Systems Research Department at AT&T Labs - Research. Her research interests are in cryptography, security, complexity theory, and related areas. Her research has been funded by NSF, NSA, NYSIA, DHS, IARPA, and gifts from Google, IBM, Mitsubishi, and NEC. | |
| Speaker: | Benny Applebaum (Tel-Aviv University) |  |
|---|---|---|
| Title: | Cryptographic Hardness of Random Local Functions -- Survey | |
| Abstract: | Constant parallel-time cryptography allows performing complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use *random local functions* in which each output bit is computed by applying some fixed d-local predicate P to a randomly chosen d-size subset of the input bits. In this talk, we will investigate the cryptographic hardness of random local functions. In particular, we will survey known attacks and hardness results, discuss different flavors of hardness (one-wayness, pseudorandomness, collision resistance, public-key encryption), and mention applications to other problems in cryptography and computational complexity. We also present some open questions with the hope to develop a systematic study of the cryptographic hardness of local functions, which will eventually lead to a comprehensive theory of ``locally-computable'' cryptography. | |
| Biography: | Benny Applebaum is an Assistant Professor of Electrical Engineering at Tel-Aviv University. He received his B.Sc. from the Hebrew University of Jerusalem in 2002, and his Ph.D from the Computer Science Department of the Technion in 2007. Before joining Tel-Aviv he was a postdoc at Princeton University and Weizmann Institute of Science. He is interested in the theory of computer science, mainly in computational complexity and cryptography. | |