DIMACS Mixer Series, September 17, 2009


Craig Gentry, IBM

Title: How to Do Anything You Want with Encrypted Data... without Decrypting It

What if you want to query a search engine, but don't want to tell the search engine what you are looking for? Is there a way that you can encrypt your query, such that the search engine can process your query without your decryption key, and send back an (encrypted) response that is well-formed and concise (up to some upper bound on length that you specify)? The answer is yes, if you use a "fully homomorphic" encryption scheme. As another application, you can store your encrypted data in the "cloud", and later ask the server to retrieve only those files that contain a particular (boolean) combination of keywords, without the server being able to "see" either these keywords or your files.

We will present a recent fully homomorphic encryption scheme. In particular, we will highlight the main ideas of the construction, discuss issues concerning the scheme's performance, and mention other applications.

Further background for the talk may be found in http://domino.research.ibm.com/comm/research_projects.nsf/pages/security.homoenc.html

Forbes.com article: A researcher's algorithm could teach computers a new privacy trick

Short bio sketch:

Craig Gentry is a research staff member in the Cryptography group at IBM T.J. Watson Research Center. His research tends towards the mathematical side of applied cryptography, both constructive (designing efficient and highly-functional cryptosystems) and destructive (cryptanalysis). From 2000 to 2005, he worked as a senior research engineer at DoCoMo USA Labs on the security and cryptography project. After many detours in life, he is about to obtain his Ph.D. in computer science from Stanford, with Dan Boneh as his advisor.

Karlo Hock, postdoc at Dept. of Ecology and Evolution, Rutgers

Title: Modeling dominance hierarchies in crayfish

Dominance hierarchies function as mechanisms to reduce the risks inherent in group living, either by consensual distribution of resources, or by diminishing the need for, and the dangers of, future conflicts. Even though social structure of a group stems from simple behavioral decisions in individual contests, it is difficult to predict how the characteristics of an emerging hierarchy will be affected by specific aspects of dyadic interactions. Using crayfish aggression as a premise, I developed a series of models aimed at unraveling the links between decision-making processes that govern agonistic encounters and the resulting social organization of a group.I will specifically focus on how changes in aggressive motivation influence formation and maintenance of dominance relations in a hierarchy, and the utility of such social conventions.

Siva Raj Rajagopalan, HP Labs

Title: Meeting New Challenges in Security

I will discuss two problems in security that have become important in recent times.

The first problem is in intrusion detection: the size of enterprise networks have become so large and the quality of current intrusion detection systems (IDS) alerts so low that we end up with huge numbers of intrusion alerts that easily overwhelm system administrators. At the same time attacks are sufficiently fast, subtle, and damaging that response must be rapid and prioritized. However, IDS alerts today largely do not distinguish between events that almost surely indicate an attack from those that merely indicate the possibility of one. In this talk, I will discuss existing approaches to quantify the certainty of attack detection and their shortcomings as well as some new results that offer hope for a realistic tool for sys administrators. Using a multi-level logic to characterize certainty of attack hypotheses, a model-based mapping of externally detectable events to internal states, and an automatic parser for Snort (a popular IDS system) we automatically combine alerts with labeled levels of certainty to help human administrators prioritize their efforts. This is joint work with Prof. Xinming Ou and Sakthi Sakthivelmurugan of Kansas State University.

The second problem I will discuss is of a very different kind and has been recognized only recently, namely, the inability of security vendors to effectively sell security products. Problems that lie in the intersection of economics and security have been addressed recently in the literature. One of these has been the possibility of market failure in security that causes a negative incentive for customers to purchase innovative and risky security products. Drawing from Michael Spence's Nobel-winning work on markets with incomplete information, I will present some thoughts on why this security failure might be happening, what solutions may be borrowed from economics, and some open problems specialized for the security product market.

This talk is intended to be an open and interactive to engender discussion and foster new collaborations. No prior knowledge of security or economics will be assumed.


S. Raj Rajagopalan is a Research Scientist at HP Labs located in Princeton, New Jersey where he is a member of the Secure Systems Lab. He is currently working in security testing, intrusion detection, and related areas. He has been with HP since 2004, before which he was at the Security and Cryptology Group in Applied Research at Telcordia (formerly Telcordia Technologies/Bellcore).

Guy Rothblum, postdoc at IAS

Title: Delegating Computation Reliably

In an emerging computing paradigm, computational capabilities, from processing power to storage capacities, are offered to users over communication networks as a service. This new paradigm holds enormous promise, especially for increasing the utility of computationally weak devices. A natural approach is for weak devices to delegate expensive tasks, such as storing a large file or running a complex computation, to more powerful entities (say servers) connected to the same network. While the delegation approach seems promising, it raises immediate concerns. In this talk we will focus on one such concern:

When and how can a weak device verify that a computational task was completed correctly?

This practically motivated question touches on foundational questions in cryptography and complexity theory. I will present recent progress and tools for delegating computational tasks reliably and mention applications of these new tools to cryptography and complexity theory.

Based on joint works with Shafi Goldwasser, Danny Gutfreund, Alex Healy, Yael Kalai and Tali Kaufman.

Harald Steck, Lucent

Title: Probabilistic Graphical Models for Understanding Complex Systems

Probabilistic graphical models have become popular for describing the interdependencies among components of complex systems. For instance, with the arrival of biological high-throughput experiments, one objective is to recover so-called gene-networks, which describe how the genes in a pathway regulate each other.

The challenge from a machine learning perspective is to recover the network structure from these data, which is not without pitfalls. In particular, I will talk about a somewhat counterintuitive effect in the most popular approach, namely the Bayesian approach to structure learning of graphical models: the Dirichlet prior over the model parameters can dominate over the information contained in the data, resulting in spurious dependencies or missing dependencies.

Danfeng Yao, Rutgers

Title: Host-Based And User-Centric Approaches For Detecting Drive-By-Download Attacks

In drive-by-download attacks, malware executable are downloaded and installed automatically by exploiting browser vulnerabilities. Botnets, e.g., Torpig, often use drive-by-download as the initial infection vector. In contrast, legitimate download activities are triggered by explicit user requests, e.g., a click on a "Save file as" button in a dialog window.

We describe a host-based detection approach against drive-by-downloads by exploring the behaviors and knowledge of human-users regarding file systems. Specifically, we examine the use of (trusted) user inputs to mark the trustworthiness of file system properties. This solution involves capturing keyboard/mouse inputs of user, and correlating these input events to file-downloading events. We describe our mechanism for monitoring file-creation events and our design and implementation of a security framework for controlling the access of processes to file systems.


Danfeng (Daphne) Yao is an assistant professor in the Department of Computer Science at Rutgers University, New Brunswick. She received her Computer Science Ph.D. degree from Brown University. Her research interests are in network and information security, in particular user-centric security and privacy, social- and human-behavior pattern recognition, insider threats, secure information sharing, data privacy, and applied cryptography. Danfeng has more than 25 publications on various topics of security and privacy. She won the Best Student Paper Award in ICICS 2006, and the Award for Technological Innovation from Brown in 2006, both for her privacy-preserving identity management work.

Danfeng has one provisional patent filed for her recent bot detection techniques. She is a member of DIMACS and DHS CCICADA Centers.