This is for all of the many security nuts that follow this blog.
Have you ever heard of a History Independent Data Structure? If yes, good for you. Otherwise, I hadn't either until yesterday. So what is one?
The Problem
For some popular and useful data structures, it is possible to figure out the order in which data was inserted into the structure, or even derive information that should have been erased. The example in the document cited below, is a pdf in which key areas were blacked out, however the data being covered up still existed underneath the censored areas.
So what is a History Independent Data Structure?
A history independent data structure is one that disallows operation that leave it in a state that can reveal its past state. If a pdf was such a data structure, it would mean that putting a black bar over text would erase the text underneath and make it impossible to find hidden information.
Types of history independent structure
There are two categories, strong and weak. In short, the strong one means that if you observe the data structure multiple times, you shouldn't be able to figure out which versions of the data structure came first.
Conclusions
So it turns out that "History Independant Data Structure" is a conceited academic way of describing an obvious concept. They are just data structures that don't indicate the order in which data was added to the datastructure.
If you need some, probably settle for sets ordered by something other than time.
Citation:
www.eecs.northwestern.edu/~hartline/papers/hist-indep-ISAAC-02.pdf