Month: October 2015

Columbia theoretical computer scientists are presenting four papers at the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS) held October 18-20 in Berkeley, CA. One of these papers, An average-case depth hierarchy theorem for Boolean circuits, which solved a problem open for almost 30 years, earned the best paper award. A high-level description of this paper is given below, with abstracts from each of the other papers.

An average-case depth hierarchy theorem for Boolean circuits

Benjamin Rossman, National Institute of Informatics in Japan (to start a professorship at the University of Toronto in 2016)
Rocco Servedio, Columbia University
Li-Yang Tan, Columbia University, CS PhD’14, now research assistant professor at TTI-Chicago

Are deep Boolean circuits more computationally powerful than shallow ones? If so, by how much? The answers to these questions help computer scientists understand what problems can be solved efficiently by parallel computers.

In a celebrated result from 1986, Johan Håstad proved that shallow circuits can be exponentially less efficient than deeper ones in the worst case. In the language of parallel computation, this means that there are problems that can be solved efficiently in 101 parallel time steps, but to solve them in the worst case (i.e., on every possible input) in only 100 parallel time steps would require exponentially many processors.

For almost 30 years, it has been an open question as to whether what is true in the worst-case—that deep circuits can efficiently compute functions that shallow ones cannot—is also true for the average case.

In An average-case depth hierarchy theorem for Boolean circuits, Benjamin Rossman, Rocco Servedio, and Li-Yang Tan gave an affirmative answer to this question, by proving that for every d, even in the average case, there are functions that are efficiently computable by depth-(d+1) circuits but not by circuits of depth d. Rocco Servedio described the result as follows: “The paper shows that there’s a problem that can be solved very efficiently in 101 parallel time steps, i.e., it doesn’t require many processors if you get to use that much time. But if you only get 100 rather than 101 parallel time steps, without a really huge number of processors there’s no way to do much better than random guessing—for a yes/no question, you won’t be able to get the right answer even 51% of the time.”

A key technique for the new result is an extension of the “random restriction” method, a classic tool in circuit complexity. This method works by randomly fixing some input variables to constants; the extended method, which the paper calls “random projections,” works by additionally identifying certain variables in a carefully designed way (i.e., “projecting” a set of distinct input variables to a common new variable). These variable identifications enable a level of “control” over the random process that makes it possible to prove the lower bound.

The depth hierarchy theorem which is the paper’s main result answers several long-standing open questions in structural complexity theory and Boolean function analysis. An average-case depth hierarchy theorem for Boolean circuits received the Best Paper Award at FOCS 2015.

Xi Chen, Columbia University
Ilias Diakonikolas, School of Informatics, University of Edinburgh
Anthi Orfanou, Columbia University
Dimitris Paparas, Columbia University
Xiaorui Sun, Columbia University
Mihalis Yannakakis, Columbia University

The authors of On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms show that even a relatively simple lottery pricing scenario presents a computational problem that one cannot hope to solve efficiently in polynomial time.

In economics, lottery pricing is a strategy for maximizing a seller’s expected revenue. Unlike item pricing, the seller does not fix the price of each item but offers the buyer lotteries at different prices (according to a probability distribution). For example, the seller may offer the buyer, at a certain price, 50% chance of getting item 1 and 50% chance of getting item 2. Lotteries create for the seller a bigger space to price things, and lottery pricing has been shown in some cases to achieve strictly higher revenues for the seller than the seller can get from item pricing.

The computational problem for the seller is to figure out an optimal menu (or set) of lotteries that maximizes the seller’s revenue, and the authors consider the case when there is a single unit-demand buyer. This setup is similar to the optimal item pricing problem that the authors examined last year in another paper.

Moving from item pricing to lottery pricing, however, completely changes the computational problem. While item pricing is in some ways a discrete problem, lottery pricing is essentially continuous given its linear program characterization that involves exponentially many variables and constraints. Though it had been previously conjectured that the optimal lottery pricing problem is hard, it required a delicate construction and a 30-page proof from the authors to finally obtain the hardness evidence.

That evidence is summarized in On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms, where the authors show that even for a simple lottery scenario—one seller and one unit-demand buyer—it’s not possible to solve the pricing problem efficiently in polynomial time without adding in conditions or special cases. Via a folklore connection, the result also provides the same hardness evidence for the problem of optimal mechanism design under the same simple setup.

Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption
Craig Gentry, IBM T.J. Watson Research Center,
Allison Lewko Bishop, Columbia University,
Amit Sahai, University of California at Los Angeles
Brent Waters, University of Texas at Austin

Abstract:

We revisit the question of constructing secure general-purpose indistinguishability obfuscation, with a security reduction based on explicit computational assumptions over multilinear maps. Previous to our work, such reductions were only known to exist based on meta-assumptions and/or ad-hoc assumptions: In the original constructive work of Garg et al. (FOCS 2013), the underlying explicit computational assumption encapsulated an exponential family of assumptions for each pair of circuits to be obfuscated. In the more recent work of Pass et al. (Crypto 2014), the underlying assumption is a meta-assumption that also encapsulates an exponential family of assumptions, and this meta-assumption is invoked in a manner that captures the specific pair of circuits to be obfuscated. The assumptions underlying both these works substantially capture (either explicitly or implicitly) the actual structure of the obfuscation mechanism itself.

In our work, we provide the first construction of general-purpose indistinguishability obfuscation proven secure via a reduction to a natural computational assumption over multilinear maps, namely, the Multilinear Subgroup Elimination Assumption. This assumption does not depend on the circuits to be obfuscated (except for its size), and does not correspond to the underlying structure of our obfuscator. The technical heart of our paper is our reduction, which gives a new way to argue about the security of indistinguishability obfuscation.

Cynthia Dwork, Microsoft Research
Adam D. Smith, Pennsylvania State University
Thomas Steinke, Harvard University
Jonathan Ullman , Columbia University CS PhD’14, now assistant professor at Northeastern University

Abstract.

In 2008, Homer et al. (PLoS Genetics) demonstrated the privacy risks inherent in the release of a large number of summary statistics (specifically, 1-way marginals of SNP allele frequencies) about participants in a genome-wide association study. Specifically, they showed how given a large number of summary statistics from a case group (a dataset of individuals that have been diagnosed with a particular disease), the data of a single target individual, and statistics from a sizable reference dataset independently drawn from the same population, they could determine with confidence whether or not the target is in the case group. That is, the trace amount of data (DNA) that the target individual contributes to the summary statistics enables his or her presence in the case group to be traced by an adversary. The Homer et al. work had a major impact, changing the way that the US NIH and Wellcome Trust allow access to information from studies they fund.

In a side-channel attack, an attacker is able to glean crucial information by analyzing physical emissions (power, radiation, heat, vibrations) produced during an otherwise secure computation. Side-channel attacks are not new; Cold-War examples abound, from aiming a laser beam at a window to pick up vibrations from conversations inside, or installing microphones in typewriters to identify letters being typed. On computers, side-channel-attacks often work by inferring information from how much time or battery power is required to process an input or execute an operation. Given precise side-channel measurements, an attacker can work backward to reconstruct the input.

Side channel attacks can be particularly insidious because they circumvent security mechanisms. Traditionally they are directed against targeted individuals and assume proximity and special software installed on the victim’s computer. However, those assumptions may have to be rethought after four computer scientists from Columbia University (Yossef Oren, Vasileios P. Kemerlis, Simha Sethumadhavan, and Angelos D. Keromytis) demonstrated for the first time that it is possible to launch a side channel attack from within a web browser. The method is detailed in their paper The Spy in the Sandbox — Practical Cache Attacks in JavaScript and Their Implications, which was presented this week (October 12) at the ACM Conference on Computer and Communications Security.

The attack, dubbed spy-in-the-sandbox by the researchers, does not steal passwords or extract encryption keys. Instead, it shows that the privacy of computer users can be compromised from code running inside the highly restricted (sandboxed) environment of a web browser. The researchers were able to tell for instance whether a user was sitting at the computer and hitting keys or moving the mouse; more worrisome from a privacy perspective, the researchers could determine with 80% accuracy whether the victim was visiting certain websites.

More may be possible. As Yossef Oren, a postdoctoral researcher who worked on the project (now an Assistant Professor at the Department of Information Systems Engineering in Ben-Gurion University) puts it, “Attacks always become worse.”

In one sense at least, spy-in-the-sandbox attacks are more dangerous than other side-channel attacks because they can scale up to attack 1,000, 10,000, or even a million users at once. Nor are only a few users vulnerable; the attack works against users running an HTML5-capable browser on a PC with an Intel CPU based on the Sandy Bridge, Ivy Bridge, Haswell, or Broadwell micro-architectures, which account for approximately 80% of PCs sold after 2011.

Neither proximity or special software is required; the one assumption is that the victim can be lured to a website controlled by the attacker and leaves open the browser window.

What’s running in that open browser window is JavaScript code capable of viewing and recording the flow of data in and out of the computer’s cache, specifically the L3, or last-level, cache. (A cache is extra-fast memory close to the CPU to hold data currently in use; caching data saves the time it would take to fetch data from regular memory.)

That an attacker can launch a side-channel attack from a web browser is somewhat surprising. Websites running on a computer operate within a tightly contained environment (the sandbox) that restricts what the website’s JavaScript can do.

However, the sandbox does not prevent JavaScript running in an open browser window from observing activity in the L3 cache, where websites interact with other processes running on the computer, even those processes protected by higher-level security mechanisms like virtual memory, privilege rings, hypervisors, and sandboxing.

The attack is possible because memory location information leaks out by timing cache events. If a needed element is not in the cache (a cache miss event), for instance, it takes longer to retrieve the data element. This allows the researchers to know what data is currently being used by the computer. To add a new data element to the cache, the CPU will need to evict data elements to make room. The data element is evicted not only from the L3 cache but from lower-level caches as well. To check whether data residing at a certain physical address are present in the L3 cache as well, the CPU calculates which part of the cache (cache set) is responsible for the address, then only checks the certain lines within the cache that correspond to this set, allowing the researchers to associate cache lines with physical memory.

In timing events, researchers were able to infer which instruction sets are active and which are not, and what areas in memory are active when data is being fetched. “It’s remarkable that such a wealth of information about the system is available to an unprivileged webpage,” says Oren.

“While previous studies have been able to see some of the same behavior, they relied on specially written software that had to be installed on the victim’s machine. What’s remarkable here is that we see some of the same information using only a browser,” says Vasileios Kemerlis, a PhD student who worked on the project (now an Assistant Professor in the Computer Science Department at Brown University).

By selecting a group of cache sets and repeatedly measuring their access latencies over time, the researchers were able to construct a very detailed picture, or memorygram, of the real-time activity of the cache.

Such a detailed picture is possible only because many web browsers recently upgraded the precision of their timers, making it possible to time events with microsecond precision. If memorygrams were fuzzier and less detailed, it would not be possible to capture such small events as a cache miss. (Different browsers implement this new feature with different precisions.) High-resolution timers have recently been added to browsers as a way to give developers, especially game developers, sufficient fine-grained detail to know what processes might be slowing performance. Of course, the more information developers have, the more information an attacker can access also.

Different processes have different memorygrams, and the same is true for different websites; their memorygrams will differ depending on the data the site is using, how the site is structured, how many images it contains and the size of those images. These various parts of the website end up in different locations in memory, and need to be called and cached, giving each website its own distinctive signature.

The researchers visited 10 sites and recorded multiple memorygrams in each case to build a classifier that could, with 80% accuracy, determine if a website open on a victim’s machine matched one of the 10 pre-selected sites. (The same website viewed on different browsers will exhibit slight differences; it’s this noise that prevents 100% accuracy when matching memorygrams.)

As pernicious as is the side-channel attack, especially considering how practical, scalable, and low-cost it is, avoiding it is surprisingly easy: run only a single web browser window at a time. An across-the-board fix to prevent the attacks is easy also; have browsers return to using less precise timers (or alert users of the high-precision timers that there exist possible security vulnerabilities).

And in this story of data privacy at least there is a happy ending. In March 2015, the researchers shared their research with all major browser vendors; by September 2015, Apple, Google, and Mozilla had released updated versions of their browsers to close the identified security hole.

The researchers are not yet done examining the potential of web-based side-channel attacks. They will continue looking at the problem (on old versions of browsers) to test the attack at larger scale. They are also considering a more interesting question; can memorygrams be used for good purposes?

A pre-set memorygrams might be placed in memory to be viewed by a trusted party to convey information. One memorygram might represent a 1 bit, another a 0 bit. The process of communicating in this fashion would be slow, but it would be extremely difficult for an attacker to even figure out that explicit communication is occurring between two parties. Memorygrams might thus serve as a primitive in securely conveying information, and what was once a threat to security may serve to enhance it.

Yossi Oren, currently Senior Lecturer (Assistant Professor) at Ben Gurion University’s Cyber Security Research Center, had previously worked as a postdoc at Columbia University within the Network Security Lab of Angelos D. Keromytis and as a Senior Innovation Research Engineer at Samsung Research Israel. Oren holds a PhD in Electrical Engineering from Tel-Aviv University and an M.Sc. in Computer Science from the Weizmann Institute of Science. His main research interests are hardware and architectural security (low-resource cryptographic constructions, power analysis and other hardware attacks and countermeasures) and Network Security (cyber-physical system security, consumer and voter privacy, web application security).Vasileios (Vasilis) Kemerlis is an Assistant Professor of Computer Science at Brown University. His research interests are in the areas of systems and network security, with a focus on automated software hardening and information-flow tracking. Currently, he works on operating systems security, and specifically on kernel exploitation and defense. Kemerlis graduated in the summer of 2015 from Columbia University with a PhD in Computer Science, working under the supervision of Angelos Keromytis. In addition, he holds a M.Phil (2013) and MS (2010) in Computer Science from Columbia University, and a BS (2006) in Computer Science from Athens University of Economics and Business.

Simha Sethumadhavan is an Associate Professor of Computer Science at Columbia Engineering. He is the founding director of the Computer Architecture and Security Technologies Lab (CASTL) at Columbia University. Sethumadhavan’s research interests are in hardware security, hardware support for security and privacy and energy-efficient computing. He has been recognized with an NSF CAREER award (2011), a top paper award (2004) and a teaching award (2006). He obtained his PhD from University of Texas, Austin in 2007.

Angelos D. Keromytis is an associate professor in the Computer Science department at Columbia University, where he directs the Network Security Lab. His general research interests are in systems and network security, and applied cryptography. In the past, he was an active participant in the IETF (Internet Engineering Task Force), and in particular the IPsec and IPSP Working Groups. He was the primary author of the IPsec stack and the OpenBSD Cryptographic Framework (OCF), which was later ported to FreeBSD and NetBSD. He has co-founded two technology startups, published over 250 refereed technical papers, and is a co-inventor in 33 issued US patents.