  Storing data on an external server with information-theoretic security, while
using a key shorter than the data itself, is impossible. As an alternative, we
propose a scheme that achieves information-theoretically secure tamper
evidence: The server is able to obtain information about the stored data, but
not while staying undetected. Moreover, the client only needs to remember a key
whose length is much shorter than the data.
  We provide a security proof for our scheme, based on an entropic uncertainty
relation, similar to QKD proofs. Our scheme works if Alice is able to
(reversibly) randomise the message to almost-uniformity with only a short key.
By constructing an explicit attack we show that short-key unconditional tamper
evidence cannot be achieved without this randomisability.
