Title:Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs
Speaker: Adi Shamir Weizmann Institute of Science
Time: 2006-12-14 14:00-2006-12-14 15:00


In this talk we formalize a very general model of time/memory tradeoffs for the cryptanalysis of arbitrary encryption schemes, which is based on the new notion of "stateful random graphs". We prove that in this model it is possible to rigorously bound the probability of success and the best possible time and space complexities required to break strong cryptosystems which are modeled as random functions from keys to ciphertexts.

Short Bio: