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 modelled as random functions from keys
to ciphertexts.