  The way data structures organize data is often a function of the sequence of
past operations. The organization of data is referred to as the data
structure's state, and the sequence of past operations constitutes the data
structure's history. A data structure state can therefore be used as an oracle
to derive information about its history. As a result, for history-sensitive
applications, such as privacy in e-voting, incremental signature schemes, and
regulatory compliant data retention; it is imperative to conceal historical
information contained within data structure states.
  Data structure history can be hidden by making data structures history
independent. In this paper, we explore how to achieve history independence.
  We observe that current history independence notions are significantly
limited in number and scope. There are two existing notions of history
independence -- weak history independence (WHI) and strong history independence
(SHI). WHI does not protect against insider adversaries and SHI mandates
canonical representations, resulting in inefficiency.
  We postulate the need for a broad, encompassing notion of history
independence, which can capture WHI, SHI, and a broad spectrum of new history
independence notions. To this end, we introduce $\Delta$history independence
($\Delta$HI), a generic game-based framework that is malleable enough to
accommodate existing and new history independence notions.
  As an essential step towards formalizing $\Delta$HI, we explore the concepts
of abstract data types, data structures, machine models, memory representations
and history independence. Finally, to bridge the gap between theory and
practice, we outline a general recipe for building end-to-end, history
independent systems and demonstrate the use of the recipe in designing two
history independent file systems.
