  We show that every almost universal hash function also has the storage
enforcement property. Almost universal hash functions have found numerous
applications and we show that this new storage enforcement property allows the
application of almost universal hash functions in a wide range of remote
verification tasks: (i) Proof of Secure Erasure (where we want to remotely
erase and securely update the code of a compromised machine with memory-bounded
adversary), (ii) Proof of Ownership (where a storage server wants to check if a
client has the data it claims to have before giving access to deduplicated
data) and (iii) Data possession (where the client wants to verify whether the
remote storage server is storing its data). Specifically, storage enforcement
guarantee in the classical data possession problem removes any practical
incentive for the storage server to cheat the client by saving on storage
space.
  The proof of our result relies on a natural combination of Kolmogorov
Complexity and List Decoding. To the best of our knowledge this is the first
work that combines these two techniques. We believe the newly introduced
storage enforcement property of almost universal hash functions will open
promising avenues of exciting research under memory-bounded (bounded storage)
adversary model.
