2009-2010 Distinguished Lecture Series

Hosted by the David R. Cheriton School of Computer Science

Andy Yao, June 2009
Paul Van Oorschot, June 2009
Shafi Goldwasser, September 2009
Adi Shamir, October 2009
Fran Allen, December 2009

Previous year: 2008-2009 Lecture Series

Date: Thursday, June 11, 2009, 4:30 p.m., DC1302
Speaker: Andrew Chi-Chih Yao , Professor, Institute for Theoretical Computer Science, Tsinghua University
Title: Communication Complexity and Its Applications
Abstract: For any function f(x, y), its communication complexity is the minimum number of bits needed to be exchanged between two parties holding integers x and y respectively. Invented thirty years ago, communication complexity has been a central research area in theoretical computer science with rich applications to algorithmic problems in data structure, circuit complexity, and cryptography. In this talk, we give an overview of communication complexity, high-lighting notable recent results and the diverse mathematical techniques needed to obtain these results.
Biography: Prof. Yao is currently a Professor of Computer Science at Tsinghua University, Beijing. Between 1975 and 2004, he held faculty positions at MIT, Stanford, UC Berkeley and Princeton University. He is recipient of the prestigious A.M. Turing Award in 2000 for his fundamental contributions to the theory of computation, including communication complexity, pseudorandom number generation, and quantum communication. Other honors include the Polya Prize, the Knuth Prize, and several honorary degrees. He is a member of the US National Academy of Sciences, the American Academy of Arts and Sciences, and the Chinese Academy of Sciences.
Date: Thursday, June 25, 2009, 4:30 p.m., DC1302
Speaker: Paul Van Oorschot, Professor of Computer Science, Carleton University
Title: Learning about Human-Computer Authentication through Graphical Passwords
Abstract: Passwords are inseparable from computers, To most users, passwords are a nuisance --- they get in the way of our primary tasks. On the other hand, attackers view passwords more favorably --- because they are amenable to so many easy forms of attack, providing access to user accounts. The challenge is therefore to design password systems which are simultaneously usable, and secure. Recent years have seen numerous proposals of new password schemes involving images --- so-called graphical passwords --- in an attempt to address long-standing problems with traditional alphanumeric text passwords. We provide a selective review of research in this area over the past five years, including security and usability analysis of existing proposals, design and analysis of new proposals, and the value of user studies. Our goal is to design better password systems in general, including text password systems, through principles learned from experience with graphical password systems; and more broadly, to extract principles of general use in the emerging field of security and usability, as it becomes an important sub-discipline of computer security.
Biography: Paul Van Oorschot is a Professor of Computer Science at Carleton University, where he is Canada Research Chair in Network and Software Security, and founding director of Carletons Computer Security Lab. He previously held positions in network security R&D and senior management at Bell-Northern Research (Ottawa), Entrust Technologies (Ottawa), and Cloakware Corp. (Ottawa). He completed his PhD in Computer Science at the University of Waterloo in 1988. He is co- author of the standard reference Handbook of Applied Cryptography, and regularly serves on program committees of major international computer security conferences, including ACM CCS, NDSS, USENIX Security, and IEEE Security and Privacy. He is on the editorial board of ACM TISSEC, and was Program Chair of USENIX Security 2008, and of the Internet Societys NDSS 2002 and 2001. He is Scientific Director of NSERC ISSNet, a pan-Canadian research network exploring Internetworked Systems Security. His current research focus includes computer security and usability, software security, authentication and identity management, and Internet security.
Date: Monday, September 14, 2009, 4:30 p.m., DC1302
Speaker: Shafi Goldwasser, MIT, USA, and Weizmann Institute of Science, Israel
Title: Cryptography without (Hardly) Any Secrets
Abstract: The absolute privacy of the secret-keys associated with cryptographic algorithms has been the corner-stone of modern cryptography. Still, in practice, keys do get compromised at times for a variety of reasons. A particularly disturbing loss of secrecy is as a result of side channel attacks. These attacks exploit the fact that every cryptographic algorithm is ultimately implemented on a physical device and such implementations enable 'observations' which can be made and measured on secret data and secret keys. Indeed, side channel observations can lead to information leakage about secret keys. Traditionally, such attacks have been followed by ad-hoc 'fixes' which make particular implementation invulnerable to particular attacks, only to potentially be broken anew by new examples of side-channel attacks.
In recent years, several general theories of physical security against a large class of families of side channel attacks have been proposed. Examples of such families include (1) the 'computation but only computation' (of Micali and Reyzin) attacks where one assumes that computation proceeds in steps and the only portions of secret memory which may leak during a computational step are those which effect its outcome, and (2) the 'Memory-attacks' proposed (of Akavia, Goldwasser, and Vaikuntanathan) that assumes that any function of the entire secret memory may leak as long as its output is of bounded length.
Provably secure cryptographic constructions, under standard cryptographic intractability, have been proposed in the above attack model. These include constructions of encryption scheme, digital signatures schemes, pseudo random number generators, and even general computations under the additional assumption of the existence of simple secure one-time memory.
The talk will survey highlights of these exciting developments.

Biography: Shafi Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel. She is a member of the Theory of Computation group at MIT Computer Science and Artificial Intelligence Laboratory.
Goldwasser's research areas include complexity theory, cryptography and computational number theory. She is the co-inventor of zero-knowledge proofs, which probabilistically and interactively demonstrate the validity of an assertion without conveying any additional knowledge, and are a key tool in the design of cryptographic protocols. Her work in complexity theory includes the classification of approximation problems, showing that some problems in NP remain hard even when only an approximate solution is needed.
Goldwasser has twice won the Gödel Prize in theoretical computer science: first in 1993 (for "The knowledge complexity of interactive proof systems"), and again in 2001 (for "Interactive Proofs and the Hardness of Approximating Cliques"). She won the RSA Award in Mathematics (1998) for outstanding mathematical contributions to cryptography. In 2001 she was elected to the American Academy of Arts and Sciences, in 2004 she was elected to the National Academy of Science, and in 2005 to the National Academy of Engineering. She was selected as an IACR Fellow in 2007.
Date: Thursday, October 22, 2009, 4:00 p.m., DC1351
Speaker: Adi Shamir, Weizmann Institute of Science, Israel
Title: How Cryptosystems Are Really Broken
Abstract: Most of the cryptosystems we currently use are highly secure, and cannot be broken by mathematical cryptanalysis. However, over the last ten years researchers have developed many types of physical attacks on their implementation which can easily bypass their mathematical security.
In this talk I will survey some of these techniques, and show how difficult it is to build a truly secure communication system.
Biography: Adi Shamir holds a PhD degree in Computer Science from the Weizmann Institute. After a year postdoc at the University of Warwick, he did research at MIT before returning to be a member of the faculty of Mathematics and Computer Science at the Weizmann Institute. Starting in 2006, he is also an invited professor at École Normale Supérieure in Paris.
In addition to RSA, Shamir's other numerous inventions and contributions to cryptography include the Shamir secret sharing scheme, the breaking of the Merkle-Hellman knapsack cryptosystem, visual cryptography, and the TWIRL and TWINKLE factoring devices. Together with Eli Biham, he discovered differential cryptanalysis, a general method for attacking block ciphers. (It later emerged that differential cryptanalysis was already known --- and kept a secret --- by both IBM and the NSA.)
Shamir has also made contributions to computer science outside of cryptography, such as showing the equivalence of the complexity classes PSPACE and IP.
Shamir has received a number of awards, including the following: the 2002 ACM Turing Award, together with Rivest and Adleman, in recognition of his contributions to cryptography; the Paris Kanellakis Theory and Practice Award; the UAP Scientific Prize; The Vatican's PIUS XI Gold Medal; the IEEE Koji Kobayashi Computers and Communications Award; the Israel Prize, in 2008, for computer sciences.
Date: Thursday, December 3, 2009, 2:00 p.m., DC 1302
Speaker: Fran Allen
Title: High Performance Computers and Compilers: A Personal Perspective
The talk will describe a related sequence of projects including some early, very bold projects that profoundly influenced high performance computing even as some of them failed. The talk includes a personal perspective of what worked and what didn't, the historical threads of some ideas and the lessons learned. The talk concludes by identifying some current compiler challenges and the need for a new focus on new compilers.
Bio: Fran Allen's specialty is compilers and program optimization for high performance computers. Soon after joining IBM Research as a programmer in 1957 with a University of Michigan masters degree in mathematics, Fran found the technical goal that would drive her career: Enable both programmer productivity and program performance in the development of computer applications. One result of this goal was that Fran was the recipient of ACM's 2006 Turing Award "For pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel execution."
Fran is a member of the American Philosophical Society and the National Academy of Engineers, and a Fellow of the American Academy of Arts and Sciences, ACM, IEEE, and the Computer History Museum. Fran has several honorary doctorate degrees and has served on numerous national technology boards including CISE at the National Science Foundation and CSTB for the National Research Council. Fran is an active mentor, an advocate for technical women in computing, an environmentalist and an explorer.

David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293
Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics

Last modified: Friday, 06-Nov-2009 16:26:22 EST

Menu:Show Hide