Time-space tradeoffs in cryptography

Speaker 

Itai Dinur November 8, 2024. 

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.