CS Colloquium: “Time-space Tradeoffs In Cryptography” (Itai Dinur, Ben-Gurion University)

Abstract

A time-space tradeoff for a problem is a curve that quantifies the difficulty of solving it in terms of both the time complexity and the space complexity. Such tradeoffs play a significant role in algorithmic research, as they provide a more realistic estimate of how difficult it is to solve a problem than merely considering time complexity.

In this talk I will discuss time-space tradeoff algorithms and lower bounds for important problems in the domain of cryptography, under various computational models. These problems include distinguishing a uniformly chosen permutation from a uniformly chosen function and finding multiple collisions in a uniformly chosen function. I will also discuss barriers that prevent us from proving that certain time-space algorithms are optimal.

Speaker’s Biography

Itai Dinur is an Associate Professor at Ben-Gurion University and a visiting researcher at Georgetown University. His research interests are in cryptography and more broadly in theoretical computer science. He has worked on both developing cryptanalytic algorithms and proving resistance against them. He obtained his PhD from the Weizmann Institute.