An Information-Theoretical Analysis of the Minimum Cost to Erase Information.

We normally hold a lot of confidential information in hard disk drives andsolid-state drives. When we want to erase such information to prevent theleakage, we have to overwrite the sequence of information with a sequence ofsymbols independent of the information. The overwriting is needed only atplaces where overwritten symbols are different from original symbols. Then, thecost of overwrites such as the number of overwritten symbols to eraseinformation is important. In this paper, we clarify the minimum cost such asthe minimum number of overwrites to erase information under weak and strongindependence criteria. The former (resp. the latter) criterion represents thatthe mutual information between the original sequence and the overwrittensequence normalized (resp. not normalized) by the length of the sequences isless than a given desired value.