ICS Theory Group

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.