Gil Segev (MSR- SVC) @ TAU: From Cryptography to Algorithms and Back Again

Primary tabs

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.

Date and Time: 
Wednesday, December 7, 2011 - 10:15 to 11:30
Speaker: 
Gil Segev (MSR- SVC)
Location: 
Shenkar (Physics) 104