Technion
 
         Computer Science Colloquium
 
Time+Place : Tuesday 06/12/2011 14:30 room 337-8 Taub  Bld.
 
Speaker    : Gil Segev
 
Affiliation: Microsoft Research Silicon Valley
 
Host       : Eyal Kushilevitz
 
Title      : From Cryptography to Algorithms and Back Again
 
Abstract   :
 
For more than 30 years cryptography has been enjoying rich and fertile
interactions with a wide variety of other research areas. These include
number theory, complexity theory, learning theory, and more, each of which
has had a major effect on the development of modern cryptography. This talk
will review my recent work on a somewhat less obvious and insufficiently
explored interaction between cryptography and fundamental problems in the
design and analysis of algorithms.
 
In the first part of the talk, I will demonstrate that cryptographic
techniques can be utilized for solving classical algorithmic problems that
were extensively studied over the years without any apparent connection to
cryptography. In particular, I will describe a general approach underlying
the construction of the first dictionary that is essentially optimal both in
the running time of its operations and in its memory utilization. This
settles an open problem dating back more than 45 years to Knuth's historical
memorandum presenting the first analysis of a dictionary, now considered to
be the birth of the analysis of algorithms.
 
In the second part of the talk, I will demonstrate that algorithmic
techniques can be utilized for solving various cryptographic problems. In
particular, I will describe a part of my research establishing the
foundations of leakage-resilient cryptography. This recently emerging line
of research is motivated by the fact that most of the work in the analysis
of cryptographic schemes has traditionally focused on abstract adversarial
models that do not capture "side-channel attacks". Such attacks exploit
various forms of unintended leakage of sensitive information, which is
inherent to almost all physical implementations. I will describe rigorous
approaches for modeling and combating wide classes of side-channel attacks,
where both cryptographic and algorithmic techniques play an instrumental
role.
 
Shot Bio:
 
Gil Segev is currently a postdoctoral researcher at Microsoft Research
Silicon Valley. He joined Microsoft in 2010 after receiving a Ph.D. in
computer science from the Weizmann Institute of Science, where he was
advised by Prof. Moni Naor. His research focuses on cryptography and its
interplay with various other areas in the foundations of computer science.
Gil is the recipient of various awards for his achievements in research.
Most notably, these include the Gad Resheff Memorial Prize for outstanding
Ph.D. research awarded by the Weizmann Institute of Science, and the Adams
Fellowship awarded by the Israel Academy of Sciences and Humanities.
 
Refreshments served from 14:15 on,
 	Lecture starts at 14:30
 
----------------------------------------------------------
Visit our home page-   <http://www.cs.technion.ac.il/~colloq>
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Hadas Heier   <heier@cs.technion.ac.il>