On the minimum worst-case cost and the minimum average cost to erase information

摘要

We normally hold a lot of confidential information in hard disk drives and solid-state drives. When we want to erase such information to prevent the leakage, we have to overwrite the sequence of information with a sequence of symbols that is independent of the information. The overwriting is needed only at places where overwritten symbols are different from original symbols. Then, the cost of overwrites such as the number of overwritten symbols to erase information is important. In this paper, we deal with the worst-case cost which is the cost to erase the most laborious sequence and the average cost which is the expectation of the cost with respect to sequences. We clarify the minimum worst-case cost such that the mutual information between the original sequence and the overwritten sequence normalized by the blocklength of the sequences goes to zero as the blocklength tends to infinity. We also clarify the minimum average cost for stationary memoryless sources in the finite blocklength regime.