ICS 269, Spring 2004: Theory Seminar
30 April 2004:
Data Structure Forensics
Jonathan (Zheng) Sun
This is a presentation of the paper "Data Structure Forensics" by
Mikhail J. Atallah, Michael T. Goodrich, and Roberto Tamassia,
in submission.
The authors introduce data structure forensics -- techniques for
distributing data structures, so that alterations from an original
version can be detected and specifically identified. They provide a
new reduced randomness construction for nonadaptive combinatorial
group testing, such that for a reasonable
d=o(n1/3log2/3n),
only o(n) bits of storage is needed to detect up to d
alterations.
Then they show that the o(n) bits can be encoded into the
architecture for a class of data structures including binary search
trees, skip lists, arrays, linked lists and hash tables. This solution
uses no storage (except a master key) at the auditor, and adds (not
asymptotically but exactly) no storage to the data structure. The
adversary doesn't even know if the data structure is under auditing.