We consider an abstract storage device that can hold a single element x
from a fixed finite group G. Storage is private in the sense that an
adversary does not have read access at all. However, the device is only
weakly robust in that an adversary may manipulate the stored data x by
adding some value d of his choice. This abstracts a number of natural
adversarial scenarios as they are encountered in cryptography, e.g. in
the context of one-time-pad encryption or linear secret sharing.
We introduce the notion of an algebraic manipulation detection (AMD)
code, which offers a way to probabilistically encode a source s with
unique decodeability, such that if the encoding of s is stored then
manipulation will be detectable (except with a small error probability).
This is guaranteed even if the adversary has full a priori knowledge of
the source s, and no secret key is required: read access to the storage
device suffices for detection, and, in the absence of manipulation, for
decoding. This notion generalizes a number of approaches that have been
studied especially in the context of robust secret sharing.
Our technical contributions are as follows. We derive lower bounds on
the size of AMD codes, and we observe that known examples, as well as a
simple construction based on authentication codes, are in general not
optimal. We point out the connection to some new combinatorial objects,
related to difference sets, and we propose new constructions for AMD
codes: we give a generic construction based on error correcting codes
and highlight an concrete instantiation which (essentially) meets the
proven lower bound.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.