- talks - lists.cs.princeton.edu

Colloquium Speaker- Thurs. March 25- Vinod Vaikuntanathan
by Nicole E. Wagenblast 23 Mar '10

23 Mar '10

Side Channels and Clouds: New Challenges in Cryptography Vinod Vaikuntanathan, IBM T.J. Watson Thursday, March 25, 2010 4:30pm Small Auditorium, CS105 Emerging trends in computation such as cloud computing, virtualization, and trusted computing require that computation be carried out in remote and hostile environments, where attackers have unprecedented access to the devices, the data and the programs. This poses new problems and challenges for cryptography. In this talk, I will present two such challenges, and my recent work towards solving them. 1. Protecting against Side-channel Attacks: Computing devices leak information to the outside world not just through input-output interaction, but through physical characteristics of computation such as power consumption, timing, and electro-magnetic radiation. Such information leakage betrays information about the secrets stored within the devices, and has been successfully utilized to break many cryptographic algorithms in common use. These attacks are commonly called side-channel attacks. Side-channel attacks are particularly easy to carry out when the device is in the physical proximity of an attacker, as is often the case for modern devices such as smart-cards, TPM chips, mobile phones and laptops. In the first part of the talk, I will describe my recent work that lays the foundation of leakage-resilient cryptography - the design of cryptographic schemes that protect against large classes of side-channel attacks. 2. Computing on Encrypted Data: Security in the setting of cloud computing involves a delicate balance of privacy and functionality: while the client must encrypt its data to keep it private from the server, it should also allow for the server to compute on the encrypted data. Can we simultaneously achieve these opposing goals? In the second part of the talk, I will describe an elementary construction of a cryptographic mechanism that allows computation on encrypted data (also called a fully homomorphic encryption scheme). Both these works leverage new mathematical techniques based on geometric objects called lattices. Vinod Vaikuntanathan is a postdoctoral fellow in the cryptography group at IBM T.J. Watson. He received a Ph.D. from MIT in 2009 under the guidance of Shafi Goldwasser. He is a recipient of the MIT Akamai Graduate Fellowship, the IBM Josef Raviv Postdoctoral Fellowship, and more recently, the MIT George M. Sprowls award for the best Ph.D. thesis in Computer Science. The focus of his research is involves the dual goals of devising new mathematical tools for cryptography, as well as applying theoretical cryptography to counter practical attacks.

1 1

Colloquium Speaker, Wed March 24- David Levin
by Nicole E. Wagenblast 22 Mar '10

22 Mar '10

Systems without Cooperation David Levin, University of Maryland Wednesday, March 24 -4:30pm Small Auditorium, CS105 Successful networked systems must account for potentially competing interests: the Internet is no longer the cooperative, technological playground it once was. The protocols are the rules relegating the venue for this competition, but those rules often lack enforcement. I will present the application of economics and trusted hardware to keep participants in a networked system from deviating from the letter and spirit of a protocol. First, I will apply economic mechanism design to keep selfish users from gaining at the expense of others. I will show that the popular BitTorrent system uses, not tit-for-tat as widely believed, but an auction to decide which peers to serve. This model captures known, performance-improving strategies, and shapes or thinking toward new, effective incentive mechanisms. Second, I will apply trusted hardware to keep both selfish and malicious users from "equivocating," or sending semantically conflicting messages. I will present TrInc (Trusted Incrementer), a small piece of trusted hardware intended for use in large-scale distributed systems. With case studies and an implementation, I will demonstrate that TrInc is a practical primitive for protecting a wide range of systems. These two examples together demonstrate the importance of aligning the assumptions of economics and large-scale systems. Doing so allows us to develop new mechanisms that foster cooperation among the otherwise self-interested.

1 1

A Golovinskiy FPO
by Melissa Lawson 15 Mar '10

15 Mar '10

Alex Golovinskiy will present his FPO on Thursday March 18 at 9:30AM in Room 402. The members of his committee are: Tom Funkhouser, advisor; Szymon Rusinkiewicz and Adam Finkelstein, readers; David Dobkin and Rob Schapire, nonreaders. A copy of his thesis, "Analysis of Global Properties of Shapes", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Distinguished Colloquium Speaker Wed. March 10- Barbara Liskov
by Nicole E. Wagenblast 08 Mar '10

08 Mar '10

The Power of Abstraction Barbara Liskov Wednesday, March 10- 4:30pm Friend Convocation Room Abstraction is at the center of much work in Computer Science. It encompasses finding the right interface for a system as well as finding an effective design for a system implementation. Furthermore, abstraction is the basis for program construction, allowing programs to be built in a modular fashion. This talk will discuss how the abstraction mechanisms we use today came to be, how they are supported in programming languages, and some possible areas for future research.

1 1

Colloquium Speaker, Mon. March 8, 2010- Ranjit Jhala
by Nicole E. Wagenblast 04 Mar '10

04 Mar '10

Algorithmic Software Verification Ranjit Jhala, University of California, San Diego Monday, March 8, 2010- 4:30pm Small Auditorium, CS 105 Software is everywhere, and yet, extremely unreliable. One key to reliability is the design of cost-effective techniques whereby developers can formally specify essential properties of their code, and, machines can rigorously verify that the properties hold, or demonstrate corner cases where they fail. In this talk, we describe two such techniques. First, a scheme that uses logical predicates and theorem provers to automatically compute safety proofs. Second, an approach that uses random walks to find liveness bugs in distributed systems. We describe the key algorithms underlying these approaches and the resulting tools that have helped verify and find subtle defects in a variety of complex software.

1 1

Today's Colloquium moved to CS104
by Nicole E. Wagenblast 03 Mar '10

03 Mar '10

Today's Colloquium moved to the Large Auditorium CS104 Behind the Scenes at Pixar Rob Cook, Pixar Today- 4:30pm LARGE Auditorium CS 104 This talk takes you behind the scenes at Pixar Animation Studios for a look at how its 3D computer graphics films are made. The process starts with the development of the story and continues with modeling the geometry, animating the characters, simulating things like water and cloth and hair, defining the look of the surfaces, putting lights in the scene, and rendering the images. Making a computer animated film requires a close collaboration between artists and technical experts in many areas of expertise and is a great example of the value of bringing different disciplines together. Rob was the co-architect and primary author of RenderMan, software that creates photo-realistic computer images. Every film nominated for a Visual Effects Oscar in the last 15 years has used RenderMan. In 2001, along with two colleagues, Rob received an Oscar for his contributions, the first ever given for software. He has also received the Steven A. Coons Award for lifetime achievement in computer graphics and was inducted into the National Academy of Engineering. Rob has a Bachelor's degree in Physics from Duke University and a Master's in Computer Graphics from Cornell University. At Cornell, he worked on simulating realistic surfaces, taking computer-generated images beyond the distinctive plastic look they had at the time. In 1981, he joined Lucasfilm / Pixar, where he developed the first programmable shader, which is now an essential part of GPUs and game engines. He was the first to use Monte Carlo techniques in computer graphics, which was essential for the simulation of complex, realistic lights and camera effects. The latter proved particularly important in the special effects industry, because it allowed computer-generated imagery to match the motion blur and depth of field of the live-action footage with which it was combined. He is currently the Vice President of Advanced Technology at Pixar.

1 0

Distinguished Colloquium Speaker Wed. March 3- Rob Cook
by Nicole E. Wagenblast 01 Mar '10

01 Mar '10

Behind the Scenes at Pixar Rob Cook, Pixar 4:30pm Small Auditorium CS 105 This talk takes you behind the scenes at Pixar Animation Studios for a look at how its 3D computer graphics films are made. The process starts with the development of the story and continues with modeling the geometry, animating the characters, simulating things like water and cloth and hair, defining the look of the surfaces, putting lights in the scene, and rendering the images. Making a computer animated film requires a close collaboration between artists and technical experts in many areas of expertise and is a great example of the value of bringing different disciplines together. Rob was the co-architect and primary author of RenderMan, software that creates photo-realistic computer images. Every film nominated for a Visual Effects Oscar in the last 15 years has used RenderMan. In 2001, along with two colleagues, Rob received an Oscar for his contributions, the first ever given for software. He has also received the Steven A. Coons Award for lifetime achievement in computer graphics and was inducted into the National Academy of Engineering. Rob has a Bachelor's degree in Physics from Duke University and a Master's in Computer Graphics from Cornell University. At Cornell, he worked on simulating realistic surfaces, taking computer-generated images beyond the distinctive plastic look they had at the time. In 1981, he joined Lucasfilm / Pixar, where he developed the first programmable shader, which is now an essential part of GPUs and game engines. He was the first to use Monte Carlo techniques in computer graphics, which was essential for the simulation of complex, realistic lights and camera effects. The latter proved particularly important in the special effects industry, because it allowed computer-generated imagery to match the motion blur and depth of field of the live-action footage with which it was combined. He is currently the Vice President of Advanced Technology at Pixar.

1 1

Colloquium Speaker Monday, March 1- Eran Tromer
by Nicole E. Wagenblast 25 Feb '10

25 Feb '10

Side Channels and their Mitigation in Cloud Computing Security Eran Tromer, MIT 4:30pm Small Auditorium CS 105 Today's computers run numerous processes of different sensitivity and trustworthiness, and often the only boundary between a hostile network and sensitive data relies on flimsy confinement assumptions. The platform purports to protect processes from each other, but side channels arise from lower architectural layers, such as contention for shared hardware resources, and create inadvertent cross-talk. For example, we have shown how observing contention for the CPU cache allows an attacker to steal other users' encryption keys in a few milliseconds. Confinement violations are especially grievous in the context of cloud computing ("infrastructure as a service"), where users acquire computational capacity in the form of virtual machines running on a service provider's shared hardware pool. Cross-talk between mutually-untrusting virtual machines running on the same hardware creates the risk of information exfiltration across machines and between users, as we have demonstrated on Amazon EC2. These security vulnerabilities raise the challenge of achieving trustworthy computation on leaky platforms. We discuss potential solutions, including a new work on mitigating side channels using just-in-time dynamic transformation of x86 machine code. This talk includes joint works with Saman Amarasinghe, Dag Arne Osvik, Thomas Ristenpart, Ron Rivest, Stephan Savage, Hovav Shacham, Adi Shamir and Qin Zhao.

1 1

D Steurer preFPO
by Melissa Lawson 24 Feb '10

24 Feb '10

David Steurer will present his preFPO on Monday March 1 at 3PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Russell Impagliazzo (IAS), Boaz Barak, Moses Charikar, and Bernard Chazelle. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------------------------- On Strengths and Limits of Relaxations for Combinatorial Optimization Mathematical programming relaxations are powerful tools for solving or approximating combinatorial optimization problems. This thesis explores the strengths and limits of these tools for a selection of basic optimization problems. A central open question in this context is the Unique Games Conjecture (Khot 2002), which asserts that a certain optimization problem, called Unique Games, is hard to approximate in a certain regime. In recent years, a sequence of works established that this conjecture has profound implications: If the conjecture is true, then a certain semidefinite relaxations, called Basic-SDP, is optimal for a large range of optimization problems, in the sense that no efficient relaxation can achieve a better approximation for any of these problems. We make the following contributions towards a better understanding of the Unique Games Conjecture and semidefinite relaxations of combinatorial optimization problems: - We exhibit an optimal rounding scheme for constraint satisfaction problems (CSPs), a well-studied class of combinatorial optimization problem. The guarantee of the scheme matches the integrality gap of the Basic-SDP relaxation for every CSP. In contrast to many previous rounding algorithms, our scheme is generic and very simple. Moreover, it allows for a principled analysis. - Using our rounding scheme and a framework (Arora and Kale 2007) for solving semidefinite relaxations, we develop an approximation algorithm for CSPs whose approximation guarantee matches the integrality of the Basic-SDP relaxation and whose running time is quasi-linear. Assuming the Unique Games Conjecture, no polynomial time algorithm can have a better approximation guarantee. - We confirm the Unique Games Conjecture for a restricted model of computation given by a hierarchy of semidefinite relaxations. In particular, we show that for every CSP, the integrality gap of the Basic-SDP cannot be improved by adding a large class of valid inequalities. It was a long-standing open question whether such stronger relaxation could lead to better approximation algorithms for problems like Max-Cut or Multiway-Cut. Our result answers this question in the negative. - Finally, we establish a connection between the Unique Games Conjecture and the problem of approximating the expansion profile of graphs. In particular, we show that the Unique Games Conjecture is true if the expansion of small sets in graphs is hard to approximate in a certain regime. This result provides the first non-trivial sufficient condition for the truth of the conjecture. (Previously, only implications of the truth of the conjecture were known.) Based on joint works with Prasad Raghavendra.

1 0

Colloquium Speaker, Feb. 24, 2010- Edgar Berdahl
by Nicole E. Wagenblast 23 Feb '10

23 Feb '10

Physical Interfaces For Applications In Music Edgar Berdahl, Stanford University 4:30pm Small Auditorium CS 105 Since the 1960s at the latest, the computer has been capable of digitally synthesizing any perceivable sound. However, in a live context, human-computer interfaces limit the bandwidth and quality of the interaction between the performer and the sound synthesizer. This talk focuses on physical interfaces for music, which operate according to the laws of physics to seamlessly and intimately connect musicians with sound synthesizers. In particular, we study how to design interfaces that assist a performer in making musical gestures. For example, the haptic drum provides a performer's drumstick with an extra push every time that the performer strikes the drum. This device allows the performer to make gestures that would otherwise be very difficult or impossible, such as arbitrarily long one-handed drum rolls and arbitrarily complex rudiments. Next, we explain how to assist a performer in accurately selecting pitches from a continuous range on a Theremin-like haptic interface. We augment it with detents allowing the performer to feel the locations of equal-tempered pitches, yet the performer can still perform arbitrary pitch inflections such as glissandi, falls, and scoops. With the help of a subject test, we demonstrate that traditional detents as well as novel force-sensitive detents can provide accuracy improvements over simpler types of haptic feedback, such as spring feedback. In closing, we relate the work to research in robotics and mixed reality.

1 0